题解：CF2072C - Creating Keys for StORages Has Become My Main Skill

题目分析

题目要求构造长度为 $n$ 的数组，使所有元素的按位或等于 $x$，并且数组元素集合的 MEX 最大。

要让 MEX 至少为 $m$，数组中必须出现 $0,1,\ldots,m-1$。同时，由于最终按位或必须等于 $x$，数组里的任何数都不能在 $x$ 为 $0$ 的二进制位上出现 $1$，否则整体 OR 会超过 $x$。也就是说，被放入数组的每个数都必须是 $x$ 的子掩码。

难点在于：我们既想尽量放入从 $0$ 开始的连续整数，又必须留下足够的位置把 OR 补成 $x$。

从暴力到正解

小数据时可以枚举 MEX 的值 $m$，检查 $0,1,\ldots,m-1$ 是否都能放入数组，并判断这些数的 OR 是否已经等于 $x$。如果还没有等于 $x$，就需要额外占用一个位置放入 $x$ 或其他补位数。

直接枚举 $m$ 的思路是正确的，但实现上可以更自然地从小到大尝试放入 $0,1,2,\ldots$：

• 当前数 $i$ 如果不是 $x$ 的子掩码，就不能放，否则整体 OR 会产生多余的 $1$；
• 如果还能放，就把 $i$ 放进答案并更新当前 OR；
• 为了保证最终 OR 等于 $x$，除非当前前缀的 OR 已经能够覆盖 $x$，否则最后至少要留一个位置放 $x$。

因此，我们先最多放前 $n-1$ 个连续整数，把最后一个位置预留给 $x$。如果放满前 $n-1$ 个以后，再放 $n-1$ 本身也能让整体 OR 正好等于 $x$，那么最后一个位置也可以放成 $n-1$，MEX 可以继续增加到 $n$。

正解思路

初始化答案数组全为 $x$。这样无论后面能放入多少个前缀数，只要剩余位置还保留着 $x$，整体 OR 就一定至少能补成 $x$；又因为所有已放入的前缀数都是 $x$ 的子掩码，整体 OR 不会超过 $x$。

具体做法：

1. 令 cur_or=0。
2. 从 $i=0$ 到 $n-2$ 依次尝试：
   • 如果 cur_or | i 仍然是 $x$ 的子掩码，就把 ans[i] 改为 $i$，并更新 cur_or；
   • 否则停止尝试。
3. 如果前面的尝试没有中途停止，并且 cur_or | (n-1) == x，说明最后一个位置也可以放 $n-1$，把 ans[n-1] 改为 $n-1$。
4. 输出数组。

为什么第 3 步要求等于 $x$？因为此时没有额外位置再放 $x$ 了。如果把最后一个位置也改成 $n-1$，所有元素的 OR 必须已经正好等于 $x$。

正确性说明

首先，算法放入的每个连续整数 $i$ 都满足 cur_or | i 是 $x$ 的子掩码，所以这些数不会引入 $x$ 中不存在的二进制位。未被修改的位置保持为 $x$，因此最终 OR 一定不会小于 $x$，也不会超过 $x$，所以等于 $x$。当最后一个位置也被改成 $n-1$ 时，算法额外检查了整体 OR 正好等于 $x$，仍然合法。

其次，如果某个整数 $i$ 不是 $x$ 的子掩码，那么任何 MEX 大于 $i$ 的合法数组都必须包含 $i$，但包含它会让整体 OR 出现多余的 $1$，这是不可能的。因此在第一个无法放入的整数处停止不会损失更优答案。

最后，如果前 $n$ 个数都能作为子掩码放入，那么 MEX 想达到 $n$ 必须放入 $0,1,\ldots,n-1$。这时没有额外位置补 OR，所以只有这些数的 OR 正好等于 $x$ 时，MEX 才能达到 $n$；否则最多只能达到 $n-1$，并用一个位置保留 $x$。算法正是按这个条件处理最后一个位置，所以得到的 MEX 最大。

复杂度分析

每个测试用例只需扫描至多 $n$ 个位置。

时间复杂度为 $O(n)$，所有测试用例总复杂度为 $O(\sum n)$。

空间复杂度为 $O(n)$，用于保存答案数组。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, x;
        cin >> n >> x;

        // 先把所有位置填成 x，保证有位置负责补齐最终 OR。
        vector<int> ans(n, x);
        int cur_or = 0;
        bool can_continue = true;

        // 前 n-1 个位置尽量放 0,1,2,...，从而提高 MEX。
        for (int i = 0; i < n - 1; ++i) {
            int next_or = cur_or | i;

            // next_or 的所有 1 位都必须包含在 x 中。
            if ((next_or & x) == next_or) {
                ans[i] = i;
                cur_or = next_or;
            } else {
                can_continue = false;
                break;
            }
        }

        // 如果最后一个位置也放成 n-1 后，整体 OR 正好为 x，
        // 就可以把 MEX 提高到 n。
        if (can_continue && ((cur_or | (n - 1)) == x)) {
            ans[n - 1] = n - 1;
        }

        for (int i = 0; i < n; ++i) {
            if (i) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }

    return 0;
}