Big Secret

eat_axuan · 2024-01-11 20:25:28 · 题解

Big Secret 题解

solution

问题一，考虑已知 b 序列，如何还原出 a 序列。

显然，由于 b_i = a_{i - 1} \oplus a_i，我们可知 b_i \oplus a_{i - 1}= a_i。

于是我们可以通过记录 a_{i - 1}，以简便地求出 a_{i}。

问题二，如何求最小的 b 序列。

记我们重新排序后的 b 数组（即答案数组）为 ans_{i}。

题目限制了 a_{i} 序列严格递增，于是我们可以先取出 b_{min} 当做 ans_{1} 即 a_{1} ，考虑如何操作才能选出 ans_{2} 。

记我们正处理的数为 x ，最新算出的 a 数组的值为 y，bitcnt(x) 表示 x 的二进制位数。然后进行分类讨论：

1°当 bitcnt(x)=bitcnt(y) 时，因为最高位经过异或后变为零，所以 x \oplus y < y，显然不可行。

2°当 bitcnt(x)<bitcnt(y) 时，当且仅当 y 的第 bitcnt(x) 位为 0 时，x \oplus y > y。

3°当 bitcnt(x)>bitcnt(y) 时，x \oplus y > y，显然可行。

于是我们开优先队列 q[n]，其中 q[i] 表示二进制位数为 i 的所有 b 的集合，按照上述操作，从低位数到高位数枚举计算即可。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,b[100005];
int ans[100005],cnt=0;
int minn=0x3f3f3f3f3f3f3f3f,pla;
priority_queue<int,vector<int>,greater<int> >q[100005];
int bitc(int x){
    int a=0;
    while(x>0){
        a++;
        x>>=1;
    }
    return a-1;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)scanf("%lld",&b[i]);
    for(int i=1;i<=n;++i)
        if(b[i]<minn){
            minn=b[i];
            pla=i;
        }
    for(int i=1;i<=n;++i){
        if(i==pla)continue;
        q[bitc(b[i])].push(b[i]);
    }
    ans[++cnt]=b[pla];
    int nowc=bitc(b[pla]),now=b[pla];
    while(cnt<n){
        int cntt=0;
        while((q[cntt].empty()||now>>cntt&1)&&cntt<=nowc-1)++cntt;
        if(cntt==nowc){
            cntt=nowc+1;
            while(cntt<64&&q[cntt].empty())++cntt;
            if(cntt==64){
                printf("No\n");
                return 0;
            } 
                now^=q[cntt].top();
                nowc=bitc(q[cntt].top());
                ans[++cnt]=q[cntt].top();
                q[cntt].pop();
        }
        else{
            now^=q[cntt].top();
            ans[++cnt]=q[cntt].top();
            q[cntt].pop();
        }
    }
    printf("Yes\n");
    for(int i=1;i<=cnt;++i)printf("%lld ",ans[i]);
    return 0;
}