题解：CF2153B Bitwise Reversion

Part 1 题意

现在，也就是说给了我们三个数

x

，

y

，

z

，其中

a \mathbin{\&} b = x

b \mathbin{\&} c = y

a \mathbin{\&} c = z

我们需要判断是否存在

x

，

y

，

z

使得它们满足上面的条件。

Part 2 思路

我们考虑一下按位与运算的性质，当且仅当

1 \mathbin{\&} 1 = 1

。
我们按照二进制位来考虑，设

p

为

x

从右往左数二进制第

i

位的值。同理，我们也设

q

和

r

分别为

y

和

z

从右往左数二进制第

i

位的值。
我们来分情况讨论一下：

$p = 0$ ， $q = 0$ ， $r = 0$ 。很明显，我们会发现这样一定是存在合法方案的。因为只要 $a$ ， $b$ ， $c$ 这位上都是 $0$ 即可。
$p = 0$ ， $q = 0$ ， $r = 1$ 。我们发现 $r = 1$ ，也就是说 $x$ 和 $z$ 这位上都是 $1$ 。只要 $y$ 这一位上是 $0$ 即可。
$p = 1$ ， $q = 0$ ， $r = 1$ 。我们发现，这种其实是不合法的方案。为什么呢？因为 $p = 1$ 和 $r = 1$ ，说明这一位上 $a$ ， $b$ ， $c$ 上都是 $1$ 。那么，在这种情况下， $q$ 的值也一定是 $1$ ，但是这里给出的是 $0$ ，所以不合法。

通过上面举出的三个例子，我们可以发现规律：
只要

p

、

q

、

r

这三个数里面有两个是

1

，那么这一定是不合法方案，因为这就代表了三个数这一位上都是

1

，不可能有一个出现

0

。只要所有的

i

都是合法的，那么存在一种合法方案。

Part 3 代码

CPP

#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)

。

题解：CF2153B Bitwise Reversion

文章操作

Part 1 题意

Part 2 思路

Part 3 代码

相关推荐

评论

题解：CF2153B Bitwise Reversion