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

CDSuperDuo · 2026-08-09 23:50:12 · 题解

题目大意

给定序列 a，求 \min\limits_{x=0}^{\infty}(x+\operatorname{mex}(a_i\oplus x))。

解题思路

答案其实就是原序列的 \operatorname{mex}。

也就是说：

:::info[证明] 令 m=\operatorname{mex}(a_i)。

下界：

对于任意 x，令 k=\operatorname{mex}(a_i\oplus x)。 若 x+k<m，则原序列中 0 到 m-1 不可能全部出现，矛盾。所以 x+\operatorname{mex}(a_i\oplus x)\ge m。

上界：

取 x=0，得到 0+\operatorname{mex}(a_i)=m。

综上所述，最小值为 m。

::: 那接下来就简单了，我们可以标记 0 \sim n 中出现的数，从 0 开始找第一个没出现的数，这个数就是答案。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,f[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            int x;cin>>x;
            if(x<=n) f[x]=1;
        }
        int k=0;
        while(f[k++]){
        }
        cout<<k-1<<"\n";
        memset(f,0,sizeof(f));
    }
    return 0;
}

多测不清空，考完两行泪。

十年 OI 一场空，不加快读见祖宗。

感谢阅读。