C. 按位平衡 详细题解

题目回顾

给定三个非负整数 $b,c,d$，求一个非负整数 $a \in [0,2^{61}]$，满足：

若无解输出 $-1$，有多个解输出任意一个。

一、核心观察：按位独立

这是解题的关键突破口： 等式 $(a \mid b) - (a \mathbin{\&} c) = d$ 每一位独立计算，不会产生进位/借位。

为什么无进位/借位？

1. 对于任意一位，$(a \mid b)$ 的取值只能是 $0$ 或 $1$，$(a \mathbin{\&} c)$ 的取值也只能是 $0$ 或 $1$；
2. 两者的差值只有三种可能：$0,1,-1$；
3. 差值为 $-1$ 是不可能的：
   • 要求 $a \mid b = 0$ 且 $a \mathbin{\&} c = 1$；
   • $a \mid b = 0 \implies a=0$；
   • $a \mathbin{\&} c = 1 \implies a=1$；
   • 矛盾，因此每一位的差值只能是 $0$ 或 $1$，绝对不会产生借位。

因此，我们可以逐位（0~61位）独立判断，直接确定 $a$ 的每一位是 $0$ 还是 $1$。

二、逐位推导规则

定义：

• $a_i$：数字 $a$ 的第 $i$ 位（$0/1$）
• $b_i$：数字 $b$ 的第 $i$ 位（$0/1$）
• $c_i$：数字 $c$ 的第 $i$ 位（$0/1$）
• $d_i$：数字 $d$ 的第 $i$ 位（$0/1$）

等式按位等价于：

1. 无解的两种情况（必须直接返回 -1）

这两种组合绝对不可能满足等式：

1. $b_i=1,\ c_i=0,\ d_i=0$
2. $b_i=0,\ c_i=1,\ d_i=1$

2. 有解时 $a_i$ 的取值规则

1. 若 $b_i=1$ 且 $c_i=1$： $a_i = 1 - d_i$
2. 其他情况： $a_i = d_i$

三、标程代码解析

#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
void solve() {
    ll a = 0, b, c, d, pos = 1, bit_b, bit_c, bit_d, mask = 1;
    cin >> b >> c >> d;
    // 遍历 0~61 位（满足 a ≤ 2^61）
    for (ll i = 0; i < 62; i++) {
        // 取出当前位的 b_i, c_i, d_i
        bit_b = (b & mask) ? 1 : 0;
        bit_c = (c & mask) ? 1 : 0;
        bit_d = (d & mask) ? 1 : 0;
        
        // 两种无解情况，直接标记并退出
        if ((bit_b && !bit_c && !bit_d) || (!bit_b && bit_c && bit_d)) {
            pos = 0;
            break;
        }
        
        // 计算 a 的当前位
        if (bit_b && bit_c) {
            // b_i=1 且 c_i=1 → a_i = 1 - d_i
            a += (1ll - bit_d) * mask;
        } else {
            // 其他情况 → a_i = d_i
            a += bit_d * mask;
        }
        
        mask <<= 1; // 掩码左移，检查下一位
    }
    // 输出答案
    cout << (pos ? a : -1) << "\n";
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t;
    cin >> t;
    while (t--) solve();
}

关键代码说明

1. 逐位遍历：循环 $0\sim61$ 位，覆盖 $a \le 2^{61}$ 的要求；
2. 掩码提取位：用 mask 逐位取出 $b,c,d$ 的对应位；
3. 无解判断：直接检测两种矛盾情况，标记 pos=0；
4. 构造答案 $a$：严格按照推导规则逐位赋值；
5. 高效输入：主函数加了 ios::sync_with_stdio(false); 加速，适配 $t \le 10^5$ 的大数据量。

四、样例验证

样例 1

输入：$b=2,\ c=2,\ d=2$ 逐位验证后得到 $a=0$，满足：

样例 2

输入：$b=4,\ c=2,\ d=6$ 某一位触发无解条件，输出 $-1$。

样例 3

输入：$b=10,\ c=2,\ d=14$ 逐位构造得到 $a=12$，满足：

五、算法复杂度

• 时间复杂度：$O(t \cdot 62)$，$t$ 为测试用例数，完全通过时间限制；
• 空间复杂度：$O(1)$，仅使用常数变量。

总结

1. 核心思想：等式按位独立，无进位/借位；
2. 无解判断：仅两种情况 $(1,0,0)$ 和 $(0,1,1)$；
3. 构造规则：
   • $b_i=1,c_i=1 \implies a_i=1-d_i$
   • 其余情况 $\implies a_i=d_i$；
4. 实现：逐位遍历 $0\sim61$ 位，直接构造答案。