传送门：洛谷 CF2072C Creating Keys for StORages Has Become My Main Skill | Codeforces C. Creating Keys for StORages Has Become My Main Skill

更佳的阅读体验：CF2072C 题解

简要题意：构造一个长度为 $n$ 的序列 $a$，使得 $\operatorname{or} \limits_{i = 1}^{n} a_i = x$ 且 $\text{mex}(\{a_1, a_2, a_3, \cdots a_n\})$ 最大，其中 $a \text{ or } b$ 表示 $a$ 与 $b$ 的按位或。

如果不考虑其他条件，要使 $\text{mex}$ 最大，有一个最直接的想法是，从 $0$ 到 $n - 1$ 按顺序填一遍。但此时发现，可能出现 $\operatorname{or} \limits_{i = 1}^{n} a_i \neq x$ 的情况。

可以证明，对于 $0 \sim n - 1$ 的每一个数，贪心地将满足 $x \text{ or } i = x$ 的所有数 $i$ 填入序列中，这样填出来的序列一定是 $\text{mex}$ 最大的。

根据按位或的性质，此时一定有 $x \text{ or }(\operatorname{or} \limits_{i = 1}^{n} a_i) = x$，要想让 $\operatorname{or} \limits_{i = 1}^{n} a_i = x$ 成立，我们只需要在后面继续填至少一个 $x$。

但如果此时序列已经填够了 $n$ 个数，却不满足 $\operatorname{or} \limits_{i = 1}^{n} a_i = x$ 呢？只需要将最后一个数删掉，再填上一个 $x$ 即可。

#include <iostream>
using namespace std;

int t, n, x, sum;
basic_string<int> ans;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        sum = 0;
        ans.clear();
        cin >> n >> x;
        for (int i = 0; i < n; ++i) if ((sum | i | x) == x) ans += i, sum |= i;
        if (ans.size() == n && sum != x) ans.pop_back();
        while (ans.size() < n) ans += x;
        for (int i = 0; i < n; ++i) cout << ans[i] << " \n"[i == n - 1];
    } return 0;
}