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

Hughpig · 2026-08-09 11:58:22 · 题解

先想想看怎么让 f(a,x) 往小了取。把 a 中所有元素都异或 x 之后得到序列 a_1\oplus x,a_2\oplus x,\cdots,a_n\oplus x。这个序列的 \text{mex} 最小取值 0 取到时，即对任意 1\le i\le n，a_i\oplus x\not =0。

两边同时异或 x 得到 a_i\oplus x\oplus x=a_i\not =x。

也就是取一个序列 a 中不存在的 x 就可以让 f(a,x)=0。

然后题目里要求的是 \min(f(a,x)+x)。f(a,x)+x 对于 f(a,x)=0 的情况取值就是 x；如果 f(a,x)\not =0，设其值为 y，取值是 x+y。

那么有任意 1\le i\le n，a_i\oplus x\not =y。两边同时异或 x 有 a_i\not =x\oplus y。

也就是说，原序列里不存在 x\oplus y。把这个带进去就可以得到 f(a,x\oplus y)=0。新取值是 x\oplus y。

因为异或操作可以看作不进位的加法，有 x\oplus y\le x+y。所以让 f(a,x) 取 0 一定更优，这时候答案就是 x。

所以现在问题就变成了找到最小的 x 满足原序列中不存在，也就是原序列的 \text{mex}，必然 \le n。

我们记录一下值域在 0\sim n-1 中哪些数字出现了，然后扫一遍第一个没出现的数字就是答案。时间复杂度 O(n)。

::::info[代码]

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int tc;cin>>tc;while(tc--){
        int n,ans;cin>>n;ans=n;
        vector<int> a(n,0),vis(n,0);
        for(int i=0;i<n;++i){
            cin>>a[i];
            if(a[i]<n)vis[a[i]]=1;
        }
        for(int i=0;i<n;++i){
            if(vis[i]==0){
                ans=i;break;
            }
        }
        cout<<ans<<'\n';
    }
}

::::