CF1867C Salyg1n and the MEX Game

· · 题解

思路

看着无从下手，实际上又是一道诈骗题。

假设原数列不存在 0，那么我们可以直接加入 0，然后游戏结束，假设答案是 k。那么，如果我们选择加入 k，来试图让答案变大，那么 Bob 就会移除一个数，最优的话是 1，这样的话，你无论加入 1 还是 0，答案都不会超过 1，于是一手好牌就被你打没了，就算 Bob 不移除 1，移除 x，你的最终答案也不会超过 x 了。

（因为 Bob 只能移除比你加入的数还要小的数，所以如果你操作不好，Bob 甚至还没法让你）

那么，我们直接猜测最优的操作是每次加入目前集合中不存在的最小的数。

蒟蒻大概证明一下：

假设目前最小的不存在的数是 x，那么 [0,x) 都应该是存在的，那么加入以后 [0,x] 都是存在的，答案为 x+1，此时 Bob 会移除中间的某个数，那么我们再加回来，直到 Bob 移除了 0，然后你添加了 0，游戏结束。

但是如果你不加入 x，那么，Bob 再随便移除一个数 y，这时，如果你使用之前的策略，答案也只是 x，不使用的话，Bob 再移除一个小于 y 的数，答案将会再次变小，你就会无力回天了。

所以想要答案尽可能的大，我们就只能每次选择最小的不存在的数。

蒟蒻在开始想的是拿个 set 存，但是，显然 set 的常数是接受不了的，可以想象，如果数据是 [0,n-1]，那么 Bob 就可以和你扯大约 n 次皮，加上 set \log n 的复杂度，轻松让你 TLE。

当然，也可能是我操作 set 有问题，因为我是把前 10^5 都统计进了一个 set，然后再转一遍到另一个 set，并且赛后才发现给的是有序的，连最开始的 set 也不需要。（果然 OI 学多了，会掉视力）

然后蒟蒻转念一想，如果最开始加入 x，那么 Bob 无论取走那个数，下一次最小的都一定是 Bob 取走的那个数。

原来这么简单，赛时交了一发 TLE 一定是我脑抽了。

AC code

#include<bits/stdc++.h>
using namespace std;
int T,n,a,p;
set<int>s;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        cin>>n,s.clear();
        for(int i=1;i<=n;++i) cin>>a,s.insert(a);
        for(int i=0;i<=100000;++i) if(!s.count(i)){p=i;break;}//这里只是为了方便找到第一次的答案，所以用了set
     //其实不需要的，因为给的本身就是有序的，但是赛时没看到，现在又懒得改了。。。
        while(1)
        {
            cout<<p<<endl;//上文是指这里用了set
            cin>>a;
            if(a==-1||a==-2) break;
            p=a;
        }
    }
    return 0;
}