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

· · 题解

思路

不难注意到对于两个数 A_i 和 A_i\oplus X，它们大小关系只由 X 的最高位决定。

设 k=\operatorname{msb}(X)，即 X 的最高二进制位。则：若 A_i 的第 k 位为 1，所以 A_i\oplus X>A_i，即 W_i=0。反之则 W_i=1。

考虑极限情况，所以令 k=59。那么只要所有 A_i 的第 59 位异或和为 1，那么 X 的最高位就是第 59 位。

如果要使所有 A_i 的第 59 位异或和为 1，即 A_i 的第 59 位 1 的个数和是奇数，即 W_i=0 的个数应该是奇数。

如果 S 中 1 的个数已经是奇数，那么令 W=S 即可。反之，翻转第一位也行。

有了 W 考虑怎么构造，这不简单。若 W_i=0 则从 2^{59} 加起，否则从 1 加起即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int rd(){
    int x=0;bool f=0;char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-')f=1;
        ch=getchar();
    }do{x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}while(ch>='0'&&ch<='9');
    return f?-x:x;
}
int n,s=1,x=1,y;
char c[100001],b[100001];
signed main(){
    scanf("%s",c+1),n=strlen(c+1);
    for(int i=1;i<=n;i++)b[i]=c[i],s^=(c[i]=='1');
    if(s)b[1]='1'-b[1]+'0';
    for(int i=1;i<=n;i++){
        if(b[i]-'0')printf("%lld ",(1ll<<59)+y++);
        else printf("%lld ",x++);
    }
    return 0;
}