题解：CF2020C Bitwise Balancing

· · 题解

题目传送门

洛谷 CF

题目大意

给你三个非负整数 b，c，和 d。

请找出一个非负整数 a \in [0, 2^{61}]，使得 (a\operatorname{OR}b)-(a\operatorname{AND}c)=d。

如果存在 a，请输出其值。如果没有解，则输出 -1。如果有多个解，则打印任意一个。

解法

一道二进制题。

可以对每一位进行考虑。把 b，c，d 三个数每一位取出来，这样 a 的每一位只有两种可能：0 或 1，再判断两种情况是否可以，即把原先对数的判断转换为对每一个 bit 的判断。

具体细节请参见代码。

代码

CF 提交记录\ （代码块展示 solve 函数部分，ll 为 long long。）

void solve(){
    ll b,c,d;
    cin>>b>>c>>d;
    ll a=0;
    bool fail=0;//记录是否未找到
    for(int bit=0;bit<60;bit++){//循环每一位
        int bb=(b>>bit)&1;//取出b从右往左第bit+1位
        int cc=(c>>bit)&1;//同上
        int dd=(d>>bit)&1;//同上
        vector<int> v;
        if((0|bb)-(0&cc)==dd)v.push_back(0);
        if((1|bb)-(1&cc)==dd)v.push_back(1);
        if(v.empty()){
            fail=1;
            break;
        }//判断是否成立
        a|=ll(v[0])<<bit;//记得类型转换，否则可能会溢出
    }
    cout<<(fail?-1:a)<<endl;//输出答案
}