题解：AT_abc347_d [ABC347D] Popcount and XOR

wangbinfeng · 2024-03-31 11:57:26 · 题解

题意：已知 X 和 Y 在二进制下的 1 的个数分别为 a,b，求满足 X\oplus Y=C 的任意 X,Y。

可以发现，对于 X 和 Y 的二进制每一位，若均为 0 或 1 则 C 的该位一定为 0，若一个为 0，另一个为 1 则 C 该位一定是 1。

可以想到，用 \operatorname{popcount}(c) 个 1 分摊（不一定平均）给 A 和 B，再把多余的 1 给 A 和 B 两两抵消掉即可。

下面作为易错点讲一下如何判断无解：

可以发现，其他条件全部有解。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int popcnt(long long x){
    int ret=0;
    for(;x;x&=x-1)ret++;
    return ret;
}
long long a,b,c;
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>a>>b>>c;
    if(a+b<popcnt(c)||(a+b-popcnt(c))%2){printf("-1");return 0;}
    if((a+b-popcnt(c))/2>(60-popcnt(c))){printf("-1");return 0;}
    if((a-b>popcnt(c)||b-a>popcnt(c))){printf("-1");return 0;}
    bitset<60>d(c);//转成二进制 
    bitset<60>e,f;
    e.reset(),f.reset();
    for(int i=0;i<60;i++)cerr<<d[i];
    cerr<<endl;
    for(int i=0;i<60;i++){//抵消掉多余的 1
        if(a+b==popcnt(c))break;
        if(d[i]==false)e[i]=f[i]=true,a--,b--;
    }
    for(int i=0;i<60;i++){//将剩下的 1 分摊给 X,Y
        if(d[i]&&a-->0)
            e[i]=true;
        else{if(d[i]&&b-->0)
            f[i]=true;}
    }
    for(int i=0;i<60;i++)cerr<<e[i];
    cerr<<endl;
    for(int i=0;i<60;i++)cerr<<f[i];
    cerr<<endl;             //所有 cerr 仅在本地测试使用。正式提交应当删除（这里保留仅仅为了帮助读者测试）
    cout<<e.to_ullong()<<' '<<f.to_ullong();//用 bitset 自带的二进制转十进制函数输出结果
}