题解：CF2153B Bitwise Reversion

空气粽子·Air · 2025-11-04 20:28:36 · 题解

温馨提示：本题无法评测。
对于&运算，其实就是二进制下的两个数的一中位运算。每一位全 1 为 1，否则为 0。
本人第一直觉，先把 x,y,z 每个&运算的结果写出来，显然：

问题就变为：如何从上面几个表达式中求出原题有解或无解。其实也就是变为一道构造题。
那么，设 x 的第 i 位为 x_i，其余同理。那么，根据&运算法则：
若 x_i=1 则 a_i=1,b_i=1
若 y_i=1 则 b_i=1,c_i=1
若 z_i=1 则 a_i=1,c_i=1
根据结果可得，若 x_i=1,y_i=1 则 a_i=1,b_i=1,c_i=1,z_i=1，其余同理。
则推出结论：若 x_i,y_i,z_i 其中至少两个为 1，则 x_i,y_i,z_i,a_i,b_i,c_i 全为 1。
那么，很显然，若 x=0,y=0,z=0 原题有解。
则在原题有解情况下，x\&y=x\&z=y\&z。
证明：
因为 x_i=1,y_i=1 或 x_i=1,z_i=1 或 y_i=1,z_i=1 则 x_i,y_i,z_i,a_i,b_i,c_i 全为 1。
所以若 x_i\&y_i,x_i\&z_i,y_i\&z_i 其中至少一个不为 0，则上述三个表达式全都不为 0。
所以若 x\&y=y\&z=x\&z，原题有解。
证毕。

code

#include<bits/stdc++.h>
using namespace std;
int main(  )
{
    int t;
    cin>>t;
    while(t--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        if((x&y)==(y&z)&&(x&z)==(y&z)) cout<<"yEs\n";
        else cout<<"No\n";
    }
    return 0;
}

感谢观看。