题目描述
难度分:1400
输入T(≤105)表示T组数据。
每组数据输入三个整数b、c、d,范围[0,1018]。
输出任意一个在[0,261]中的整数a,满足(a∨b)−(a∧c)=d。
若不存在这样的a,输出−1。
输入样例
3
2 2 2
4 2 6
10 2 14
输出样例
0
-1
12
算法
拆位+构造
这样的位运算题看着就先往拆位上想一下,遍历所有的二进制位构造出a。d也是一个二进制数,因此我们从低到高遍历d的二进制位。可以这样来构造,对于某个位i(位运算不存在进位,但是-
属于四则运算,是有进位的,所以尽量避免考虑进位,否则就不能拆位了。假设[0,i−1]位已经和d对齐了):
- 如果d是1,只有b和c在这一位都是0的时候,a在这一位需要是1,这样可以让a∨b在这一位是1,a∧c在这一位是0,两者一减就能为d贡献2i。
- 如果d是0,那么b和c在这一位分别是0和1或者都是1的时候,a在这一位才要求是1。这样能保证a∨b和a∧c在这一位是相等的,不会对d产生额外贡献。
构造出a之后检查一下(a∨b)−(a∧c)=d是否成立,成立就输出a,否则输出−1。
复杂度分析
时间复杂度
遍历62个二进制为就能构造出答案,因此时间复杂度为O(log2N),其中N是最大值域。
空间复杂度
仅使用了有限几个变量,额外空间复杂度为O(1)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int t;
LL b, c, d;
int main() {
scanf("%d", &t);
while(t--) {
scanf("%lld%lld%lld", &b, &c, &d);
LL a = 0;
for(int i = 0; i <= 61; i++) {
int bit = d>>i&1;
int b1 = b>>i&1, b2 = c>>i&1;
if(bit) {
if(b1 == 0 && b2 == 0) {
a |= 1LL<<i;
}
}else {
if(b1 == 0 && b2 == 1) {
a |= 1LL<<i;
}
if(b1 == 1 && b2 == 1) {
a |= 1LL<<i;
}
}
}
printf("%lld\n", (a|b) - (a&c) == d? a: -1);
}
return 0;
}