题解：P17867 [FJCPC 2026] 哦 搞错了

· · 题解

思路

不难证明 A_i \oplus X < A_i 等价于 X 的二进制最高有效位与 A_i 对应的位是 1。于是 W 就只跟 A_i 与 X 的这一位有关。

由于要构造一个大小最大可以为 10 ^ 5 的数组，且 0 < A_i < 2 ^ {60}，我们考虑用 base = 2 ^ {50} 作为基底进行构造，即 X 的二进制最高有效位为第 51 位，这样我们可以使得比 base 大的数，第 51 位为 1，比 base 小的数，第 51 位为 0。

注： base 的选取依赖于比它大的与比它小的定义域内的数分别能否容纳 10 ^ 5 个数。

题目允许有一位误差，先尝试无误差。

当 S_i = 1 时，说明 A_i 基准位为 1，我们可以令 A_i = base + i + 1。

当 S_i = 0 时，说明 A_i 基准位为 0，我们可以令 A_i = i + 1。（i + 1 是为了防止 0）

注意，为了使得 X 的二进制最高有效位为第 51 位，我们需要基准位为 1 的数恰好为奇数，这等价于 W 中 1 的个数为奇数。如果实际 W 中 1 的个数为偶数，因为允许有一位误差，我们直接将 S 的最后一位取反得到目标串 tgt，再进行构造即可。

:::success[Code]

#include <iostream>
#include <string>
using namespace std;
long long A[100005];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string S;
    cin >> S;
    int N = S.length();
    long long Base = 1LL << 50;
    int cnt = 0;
    for (char c : S) if (c == '1') cnt++;
    string tgt = S;
    if ((cnt & 1) == 0) tgt[N-1] = '0' + '1' - tgt[N - 1];
    for (int i = 0; i < N; i++) {
        long long val = i + 1;
        if (tgt[i] == '1') A[i] = Base + val;
        else A[i] = val;
    }
    for (int i = 0; i < N; i++) {
        printf("%lld ", A[i]);
    }
    return 0;
}

:::