题解：CF522C Chicken or Fish?

· · 题解

6 题 Duel 技巧教学之：

先做 24 可以逼对面 56 取胜，对面被 5 爆了可以偷 5，没有被爆公平竞争 6，赢完了。

你怎么知道我就是这么趋势的。/ll

一直很想问这真的是题吗 /yun

其实先不用管反馈，注意到每个人的意愿是不确定的，所以可以让意愿和分配到了些啥假装没有关系，要是满意的话就假装很喜欢分配到的东西就好了。

讨厌的话就假装用光的那个是我喜欢的就好了。假装假装嘟嘟嘟。

于是反馈的唯一意义就只是告诉我们某一个时间点前有一个堆被用光了。这个时间点是容易得到的。

我们称这个时间点为「一次清算」，然后将轮到我点餐的时间点称作「最终清算」。

对于有指向性的选择，直接模拟减掉即可。否则把机会存起来让我们统一安排，这一部分的机会我们称作「自由机会」。

到了「一次清算」时，我们把所有能够在「自由机会」集火后被打掉的目标全部标记为可解，这显然是对的。

由于这里必须选择一个品类击杀才能继续推进后面的内容，为了给「最终清算」留足足够的「自由机会」，我们选择最容易击溃的目标击杀，然后进入下一阶段。

上面有锅。并不是所有这样的目标都是可解的。

后面的订单突然要求了你标记为可解准备在这里击杀的品类，那不就甲烷了？？

对每个品类统计最晚订单出现时间，然后特判即可。

到了「最终清算」时，你不需要考虑已经标记可解的东西，剩余的「自由机会」也留存到了极致，直接判断是否能集火击杀即可。

时间复杂度线性，做完了。

#include<bits/stdc++.h>
using namespace std;
int a[100005];
bool ans[100005];
int x[100005];
int op[100005];
int mx[100005];
void solve(){
    int n,m;
    cin>>m>>n;m--;
    for(int i=1;i<=n;i++)
    cin>>a[i],ans[i]=0,mx[i]=0;
    int sum=0;
    bool flag=0;
    for(int i=1;i<=m;i++)
    cin>>x[i]>>op[i],mx[x[i]]=i;
    for(int i=1;i<=m;i++){
        if(op[i]&&!flag){
            flag=1;
            int mn=1e9;
            for(int j=1;j<=n;j++){
                if(a[j]<=sum&&mx[j]<i)
                mn=min(mn,a[j]),ans[j]=1;
            }
            sum-=mn;
        }
        if(x[i]==0)sum++;
        else a[x[i]]--;
    }
    for(int i=1;i<=n;i++)
    if(a[i]<=sum)ans[i]=1;
    for(int i=1;i<=n;i++)
    if(ans[i])cout<<"Y";
    else cout<<"N";
    cout<<'\n';
}
int main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
//「缇亚忒学姊说过命中注定的两人无论何时都会在一起。」

//「那个学姊有点被映像晶石的恋爱故事影响太深了……」

题解首杀。