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

ICPC_AK_ME · 2026-08-09 16:11:30 · 题解

原理

首先，由 f 的定义可知：假如我们选择一个未在 a 中出现的 x = x_0，则f(a, x_0) = 0。

因为 a 不包含 x_0，所以 a \oplus x_0 = (a_1 \oplus x_0, a_2 \oplus x_0 ..., a_n \oplus x_0) 的每个元素也都 > 0。 显然，a \oplus x_0 中最小的未出现的非负整数（记作 \mathrm{mex}(a \oplus x_0)）就是 0。

考虑我们需要最小化的式子 x + f(a, x)。 到目前为止，我们已经有办法让 f(a, x) 直接取 0 了。 一个朴素的想法是，如果我们可以让 x 在这个基础上也尽可能小，最终的结果就可能是最小的。 注意到，取 x_0 = \mathrm{mex}(a) 即可达成目的。

现在的问题是，是否存在一个更小的 x = x_1，使得 x_1 + f(a, x_1) < x_0 + f(a, x_0)？ 显然，x_1 + f(a, x_1) \ge x_1 \oplus f(a, x_1)。 由于 f(a, x_1) 是一个未在 a \oplus x_1 中出现的值，易得 x_1 \oplus f(a, x_1) 同样未出现在 a 中。 鉴于 x_0 已是 a 中未出现的最小的非负整数，显然 x_1 \oplus f(a, x_1) \ge x_0 = x_0 + f(a, x_0)。

由上，我们可以保证 x + f(a, x) \ge x_0 + f(a, x_0) = \mathrm{mex}(a)。

实现

先 O(n \log{n}) 排个序，然后 O(n) 找 \mathrm{mex}。 递归栈总比大桶要省空间吧，所以就多费了点时间排序，接着从头开始排一个数出没出现。

代码如下：

int solve(vector<int> a)
{
    sort(a.begin(), a.end());
    int mex = 0;

    for (int i = 0; i < a.size(); i += 1)
    {
        if (mex == a[i]) mex += 1;
        else if (mex < a[i]) return mex;
    }

    return mex;
}