题目描述

难度分:$1400$

输入$T(\leq 10^5)$表示$T$组数据。

每组数据输入三个整数$b$、$c$、$d$，范围$[0,10^{18}]$。

输出任意一个在$[0,2^{61}]$中的整数$a$，满足$(a \lor b)−(a \land 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$对齐了）：

1. 如果$d$是$1$，只有$b$和$c$在这一位都是$0$的时候，$a$在这一位需要是$1$，这样可以让$a \lor b$在这一位是$1$，$a \land c$在这一位是$0$，两者一减就能为$d$贡献$2^i$。
2. 如果$d$是$0$，那么$b$和$c$在这一位分别是$0$和$1$或者都是$1$的时候，$a$在这一位才要求是$1$。这样能保证$a \lor b$和$a \land c$在这一位是相等的，不会对$d$产生额外贡献。

构造出$a$之后检查一下$(a \lor b)-(a \land c)=d$是否成立，成立就输出$a$，否则输出$-1$。

复杂度分析

时间复杂度

遍历$62$个二进制为就能构造出答案，因此时间复杂度为$O(log_2N)$，其中$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;
}