题解：P17204 「DLESS-6」XOR and MEX

· · 题解

先说结论：求 \operatorname{mex}(a_1,a_2,\dots,a_n) 即可。

怎么证？一发过了，得证。

证明：首先，设原序列的 \operatorname{mex} 为 m。当 x=0 时，答案就是 m，所以答案不超过 m。那么我们只需要再证明答案大于等于 m 即可。我们任取一 x\in[0,+\infty)，设 y=f(a,x)，根据 \operatorname{mex} 的定义，有 y 是 \{a_1\oplus x,a_2\oplus x,\dots a_n\oplus x\} 中未出现过的最小自然数，所以 y\oplus x 没有出现在序列 a 中，所以 x\oplus y\ge m。因为异或运算就是不进位加法，所以 x\oplus y\le x+y=x+f(a,x)，所以 x+f(a,x)\ge m，得证。

那怎么找到 \operatorname{mex}(a_1,a_2,\dots,a_n) 呢？我们有一种思路：既然 a_i 的值域是 [0,2^{30})，那就开一个大小为值域的 bool 数组，每次将下标为 a_i 的数设为 1，答案就是第一个值为 0 的下标。容易发现，此时空间炸了，用 bitset 即可。

如果我们懒，还能这样做：由于 n\le10^6，所以答案不超过 10^6，所以 bitset 只用开到 10^6 即可。bitset 有一个冷门函数 _Find_first()，可以返回第一个值为 1 的下标。我们要找第一个值为 0 的下标，只用将其取反后再调用 _Find_first() 即可。实现非常简单，时间复杂度为 O(Tn)，瓶颈是输入，空间复杂度为 O(\frac{n}{w})。当然，我的代码使用了 fread 快读，所以空间消耗会更大，但可过。 :::success[代码]

#include<bits/stdc++.h>
using namespace std;
uint8_t buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin)),*p1++)
inline unsigned int read(){
    unsigned int x=0;
    char ch=gc();
    while(!isdigit(ch))ch=gc();
    while(isdigit(ch))x=x*10+(ch&15),ch=gc();
    return x;
}
bitset<1000000>b;
bitset<1000000>c;
int main(){
    int t=read();
    while(t--){
        b.reset();
        int n=read();
        for(int i=1;i<=n;i++){
            int a=read();
            if(a<1000000)b[a]=1;
        }
        c=~b;
        cout<<c._Find_first()<<"\n";
    }
    return 0;
}

:::