题解：P17204 XOR and MEX
Ma_Zeshu
·
·
题解
题目传送门
我们不难注意到，若 f(a,x)=y，那么 x\oplus y 没有在 a 中出现，所以对于任意 i\in[1,n]，a_i\oplus x\oplus y\ne0。
不妨设 x'=x\oplus y，则 f(a,x')=0。
此时 $x'$ 可以取任意不在 $a$ 中的元素，其中取 $a$ 的 $\operatorname{mex}$ 最优，此时答案为 $a$ 的 $\operatorname{mex}$。
:::success[[AC](https://www.luogu.com.cn/record/291592172) Code]
赛时脑抽写了个 $O(n \log n)$ 的算法（排序+去重求 $\operatorname{mex}$），事实上本题存在 $O(n)$ 做法。
```cpp
#include<bits/stdc++.h>
using namespace std;
struct IO{
#define mxsz (1 << 21)
char buf[mxsz],*p1,*p2;
IO():p1(buf),p2(buf){}
inline char gc(){
if(p1==p2)p2=(p1=buf)+fread(buf,1,mxsz,stdin);
return p1==p2?' ':*p1++;
}
inline int read(){
int r=0;char c=gc();bool rev=0;
while(c<'0'||c>'9')rev|=(c=='-'),c=gc();
while(c>='0'&&c<='9')r=r*10+(c^48),c=gc();
return rev?~r+1:r;
}
}io;
const int N=1e6+5;
int n,a[N];
void solve(){
n=io.read();
for(int i=1;i<=n;i++)
a[i]=io.read();
sort(a+1,a+n+1),n=unique(a+1,a+n+1)-a-1;
for(int i=0;i<=n;i++)
if(i==n||a[i+1]!=i)
return cout<<i<<"\n",void();
}
int main(){
int T;
T=io.read();
while(T--)solve();
return 0;
}
```
:::