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

· · 题解

观察样例，注意到答案是序列的 \text{mex}，交一发发现过了。

证明的话，考虑到我们扔一个 \text{mex} 进去异或那么新数列的 \text{mex} 就是 0 了，所以这个可以取到。

然后就是证明这个为啥最小，考虑丢进去异或一个其他数 x，得到的 \text{mex} 记为 y，那么代价就是 x+y。

但是我们根据上面的过程同样可以得到序列的 \text{mex} 是 x\oplus y。

异或又被称为不进位加法，谁更优秀一目了然。于是证完啦。

用 bitset 维护一下序列 \text{mex}，复杂度线性。

#include<bits/stdc++.h>
using namespace std;
bitset<1000005>b;
void solve(){
    int n;
    cin>>n;
    b.set();
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x>n)continue;
        b[x]=0;
    }
    cout<<b._Find_first()<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
// 琴瑟愿与 共沐春秋
// 滢溪潺潺 炊烟悠悠
// 敢请东风 玉成双偶
// 遥递佳信 知否知否
// 为理云鬓 为簪银钩
// 明月可鉴 情深亦寿
// 此生相依 人间白首
// 千金不易 清茶淡粥