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

· · 题解

先提问：周处除三害，三害是哪三害？

赛时卡了，吃了好多发。。。这个 \max_{i=1}^{N} A 怎么可以这么大。

考虑这个构造 W_i = 1，无脑一点当 A_i 在二进制中最高位等于 X 在二进制的最高位，那么一定有 A_i \oplus X < A_i，如果 A_i 在二进制中的最高位小于 X 在二进制的最高位，那么一定有 A_i \oplus X > A_i。

证明应该不难：设当前 A_i 最高位是 2^{x}，当 k < 2^{x} 时，因为 (2^{x} \oplus 2^{x}) = 0 就有 (2^{x} \oplus 2^{x}) + k < 2^{x}，又因为当 1 \le k \le 2^{x+1} -1 的时候 2^{x+1} + k > 2^{x} 所以一定有 2^{x+1} + (k \oplus 2^{x}) > 2^{x}。

所以我们就有一个构造方案：我们首先让 X 的最高位 g 的出现次数为奇数，那么只要我的 A_i 的最高位是 g 根据刚才的结论：W_i = 1，那么我们就会构造 W_i = 1，那么怎么构造 W_i = 0 呢，不难发现当 A_i 的最高位小于 g 时，就一定有 W_i = 0。

现在问题就只剩下一个了：怎么保证 g 出现奇数次呢？我们发现如果保证 W_i 全部构造正确如果 \sum W_i 是奇数那么自然成立，反之我们令 W_1 = W_1 \oplus 1 我们也可以让 g 的出现次数为奇数次。

:::success[code]

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

void write(int x) {
    static int sta[40];
    int top = 0;
    do {
        sta[top++] = x % 10;
        x /= 10;
    } while (x);
    while (top) putchar('0' + sta[--top]);
    putchar(' ');
}

string s;
int cnt_0,cnt_1;
__int128_t ans[100005],cnt,tot;
signed main(){
    cin>>s;
    for(int i=0;i<s.size();i++)cnt_1^=(s[i]=='1');

    ans[0]=1;
    for(int i=1;i<=59;i++)ans[0]*=2;
    for(int i=1;i<=100000;i++)ans[i]=ans[0]+(++cnt);

    if(cnt_1){
        for(int i=0;i<s.size();i++){
            if(s[i]=='1'){
                write(ans[++tot]);
            }
            else{
                write(++tot);
            }
        }
    }
    else{
        bool flag=true;
        for(int i=0;i<s.size();i++){
            if(s[i]=='1'){
                if(flag){
                    write(++tot);
                    flag=!flag;
                }
                else write(ans[++tot]);
            }
            else{
                if(flag){
                    write(ans[++tot]);
                    flag=!flag;
                }
                else{
                    write((++tot));
                }
            }
        }
    }
    return 0;
}
/*
如果是 0 那么 A_i = (59位01串保证不重集)
否则是 1 那么 A_i = 1(59位01串保证不重集)

1 的个数是奇数就万事大吉，否则把一个数翻转 
*/

:::