题解 CF925C 【Big Secret】

红色OI再临 · 2019-09-01 20:18:25 · 题解

首先考虑使得 s ⊕ k > s 的 k 会有什么性质?

所有满足 s⊕k > s 的 k 必然满足, 在二进制表示下 k 不为 0 的最高位在 s 上为 0.

然后就可以用前缀和去一个个判断

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define re register int
#define maxn 10005
#define ll long long
using namespace std;
ll sum,a[maxn];
int len,flag,n,t[maxn];
queue<int>q[62];
int main(){
    scanf("%d",&n);
    for(re i=1;i<=n;i++){
        scanf("%d",&a[i]);
        for(re j=60;j>=0;j--){
            if((a[i]>>j)&1){q[j].push(i);break;}
        }   //存下最高位是这个数的编号
    for(re j=1;j<=n;j++){
        flag=0;
        for(re i=0;i<=60;i++){
            if(!((sum>>i)&1)&&!q[i].empty()){
                //所有满足 s^ k > s 的 k 必然满足, 在二进制表示下 k 不为 0 的最高位在 s 上为 0.
                //如果当前前缀和上的k的最高位为0，更新答案
                t[++len]=q[i].front;
                q[i].pop();
                flag=1;
                sum^=a[t[len]];break;
            }

        }
    if(!flag){printf("No");return 0;}
    }
    if(len!=n){printf("No");return 0;}
    printf("Yes\n");
    for(re i=1;i<=len;i++)printf("%lld ",a[t[i]]);
}

    return 0;
}