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

hhy11_ · 2026-08-08 20:35:05 · 题解

题目简述

这题其实挺有意思的。说难也不难，说简单也不简单。

首先我们先读一下题意：对于序列 \{a_1,a_2,a_3,\dots,a_n\}，求

读完题我们发现求这个值还是比较难的。所以我们先考虑去手玩一下样例。

找规律

对于题目给出的样例：

于是我们可以发现，似乎每个样例的答案都是 \operatorname{mex}(a_1,a_2,\ldots,a_n)，考虑去证明这个结论。证明如下。

证明

我们观察到的性质是：对于一个序列 a，有

我们令 m=\operatorname{mex}(a_1,a_2,\ldots,a_n)、b=\left \{ a_1\oplus x,a_2\oplus x,\ldots,a_n\oplus x \right \} 。

那么就是对于任意 x 都有 \operatorname{mex}(b)+x\ge m。

当 m=0 时，如果 x=0，那么 \operatorname{mex}(b)+x=\operatorname{mex}(a)+0=m+0=0，所以答案就是 0+m=m。

当 m>0 时，分三种情况讨论。

情况一：x=m

当 x=m 时，因为只有 m\oplus m 才等于 0，而由于 a 中不存在 m，所以 b 中也没有 0。那么当 x=m 时答案就是 0+m=m。

情况二：x>m

当 x>m 时，显然 \operatorname{mex}(b)\ge0，所以 \operatorname{mex}(b)+x\ge0+x，所以 \operatorname{mex}(b)+x>m，一定比 m 大，不可能成为最小值。

情况三：x<m（核心）

当 x<m 时，要证 \operatorname{mex}(b)+x\ge m。

用反证法。假设存在一个 x<m 使得 \operatorname{mex}(b)+x < m，那么 \operatorname{mex}(b) < m - x。

由于 \operatorname{mex}(a)=m，所以 a 中一定存在 0, 1, 2, \dots, m-1。

设 \operatorname{mex}(b)=y，z=x\oplus y。由假设条件 \operatorname{mex}(b)+x<m 可得 x+y<m。又由于 x\oplus y \le x + y，所以 x \oplus y < m，即 z<m，那么 z 一定在 a 中。

若 z=a_p，那么 b_p=z \oplus x=x \oplus y \oplus x = y，所以 b 中存在 y。

但是 y=\operatorname{mex}(b)，所以 b 中又不存在 y，矛盾。

所以不存在这样的 x，也不会有 \operatorname{mex}(b)+x < m。

结论

综上所述，对于任意 x 都有 \operatorname{mex}(b)+x\ge m，且当 x=m 时取到等号（m=0 时取 x=0）。因此最小值为 m，即答案就是 \operatorname{mex}(a)。

代码实现

证完上面的的结论，就来到了喜闻乐见的代码环节。作为一个橙题，代码是不难的。只要对每个测试数据都求一遍 \operatorname{mex}(a) 即可。实现方面我用了一个桶来统计 10^6 以内的值的出现次数，因为 n \le 10^6，所以 \operatorname{mex}(a) 也一定小于 10^6。只要从 0 开始遍历到一个出现次数为 0 的再输出就行了。

代码如下，也是非常简洁：

#include<bits/stdc++.h>
#define N 1000007
using namespace std;
int T, n;
int a[N];
int cnt[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> T;
    while(T--){
        memset(cnt, 0, sizeof cnt);
        cin >> n;
        for(int i = 1;i <= n;i++){
            cin >> a[i];
            if(a[i] < N){
                cnt[a[i]]++;
            }
        }
        for(int i = 0;i < N;i++){
            if(cnt[i] == 0){
                cout << i << '\n';
                break;
            }
        }
    }

    return 0;
} 

注意输入输出的效率，不然可能超时。