题解：CF2153B Bitwise Reversion

Bob1108 · 2025-10-13 20:13:35 · 题解

Part 1 题意

现在，也就是说给了我们三个数 x，y，z，其中

我们需要判断是否存在 x，y，z 使得它们满足上面的条件。

Part 2 思路

我们考虑一下按位与运算的性质，当且仅当 1 \mathbin{\&} 1 = 1。\ 我们按照二进制位来考虑，设 p 为 x 从右往左数二进制第 i 位的值。同理，我们也设 q 和 r 分别为 y 和 z 从右往左数二进制第 i 位的值。 \ 我们来分情况讨论一下：

通过上面举出的三个例子，我们可以发现规律：\ 只要 p、q、r 这三个数里面有两个是 1，那么这一定是不合法方案，因为这就代表了三个数这一位上都是 1，不可能有一个出现 0。只要所有的 i 都是合法的，那么存在一种合法方案。

Part 3 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll x, y, z;

void work() {
    cin >> x >> y >> z;
    for (ll i = 0; i <= 31; i ++) {
        ll a = ((x >> i) & 1), b = ((y >> i) & 1), c = ((z >> i) & 1);
//      cout << "i = " << i << " a = " << a << " b = " << b << " c = " << c << " \n";
        if (a == 0 && b == 1 && c == 1) {
            cout << "NO\n";
            return ;
        } 
        if (a == 1 && b == 1 && c == 0) {
            cout << "NO\n";
            return ;
        }
        if (a == 1 && b == 0 && c == 1) {
            cout << "NO\n";
            return ;
        }
    }
    cout << "YES\n";
}

int main() {

    int _; cin >> _;
    while (_ --) work();

    return 0;
} 

这里解释一下代码，代码中的 a、b、c 分别对应着上面的 p、q、r。

总复杂度应该是 O(T \log V)，T 表示测试组数，V 表示 \max(a, b, c)。