C. XOR-distance 题解

题意回顾

给定三个整数 $a, b, r$，要求在 $0 \le x \le r$ 的范围内选取 $x$，使得 $|(a \oplus x) - (b \oplus x)|$ 达到最小，并输出该最小值。

问题转化

令 $f(x) = |(a \oplus x) - (b \oplus x)|$。由于异或运算是按位独立的，我们可以逐位分析 $x$ 的取值对结果的影响。

不妨设 $a \le b$（若 $a > b$ 则交换两者，不影响答案）。对于某一位 $i$：

• 若 $a$ 和 $b$ 在第 $i$ 位上相同（同为 $0$ 或同为 $1$），则无论 $x$ 该位取何值，异或后 $a \oplus x$ 和 $b \oplus x$ 的该位依然相同，差值在该位上不受影响。
• 若 $a$ 和 $b$ 在第 $i$ 位上不同，则必定一个是 $0$ 一个是 $1$。由于 $a \le b$，在最高的不同位上，一定是 $a$ 的该位为 $0$，$b$ 的该位为 $1$。在该位异或 $x$ 的对应位会同时翻转两个数的该位：原本为 $0$ 的变成 $1$，为 $1$ 的变成 $0$。因此，若 $x$ 的该位为 $1$，则 $a$ 和 $b$ 在该位上的大小关系会反转（$a$ 的位变成 $1$，$b$ 变成 $0$），这会使 $b-a$ 减少 $2^i$；若 $x$ 的该位为 $0$，则保持原状，差值不变。

我们的目标是最小化 $b - a$（因为 $a \le b$ 且异或后两者大小关系可能变化，但绝对值保证了非负）。因此，我们希望在某些不同位上通过令 $x_i = 1$ 来缩小差距，同时要满足 $x \le r$ 的限制。

贪心策略

从最高位向最低位考虑（例如从第 $59$ 位到第 $0$ 位）：

1. 第一个不同的位
   这是 $a$ 与 $b$ 的最高不同位。在这一位上，$a$ 为 $0$，$b$ 为 $1$。如果我们令 $x$ 的这一位为 $1$，会使得原本较大的 $b$ 变小、较小的 $a$ 变大，可能导致 $a > b$，从而差值变为 $a - b$，但这并不一定比保持原样更优。事实上，保持第一个不同位的原状可以保留 $b > a$ 的“优势”，使得后续有更多的机会通过翻转其他位来减小差距。因此，对于最高不同位，我们选择不翻转（$x$ 该位取 $0$）。

2. 后续的不同位
   对于之后遇到的每一位 $i$，如果 $a$ 和 $b$ 在该位不同，则由于高位已经确定大小关系，此时 $a$ 的该位仍为 $0$，$b$ 为 $1$。如果我们令 $x$ 的这一位为 $1$，则 $a$ 增加 $2^i$，$b$ 减少 $2^i$，总差值减少 $2^{i+1}$。
   显然，只要加上这一位的 $2^i$ 后 $x$ 仍然不超过 $r$，我们就应该执行这一翻转，因为它严格减小最终差值且不会破坏高位已经建立的大小关系（因为高位不同位的取值已经固定，低位翻转不会改变 $a \le b$ 的大局）。如果翻转会导致 $x > r$，则不能进行，只能取 $0$。

这种贪心选择能够保证在限制 $r$ 下差值尽可能小。正确性基于：每一位的贡献是独立的，且高位翻转的影响远大于所有低位翻转的总和（因为 $2^i > \sum_{j=0}^{i-1} 2^j$）。因此，在第一个不同位之后，只要有机会减小差值且不超限，就立即执行是最优的。

算法步骤

1. 读入 $a, b, r$。
2. 若 $a > b$，交换 $a, b$，使 $a \le b$。
3. 初始化 $x = 0$，标志变量 first_bit = true 表示尚未遇到第一个不同位。
4. 从高位到低位遍历（例如 $i = 59$ 到 $0$）：
   • 获取 $a$ 和 $b$ 在第 $i$ 位的值。
   • 若两值不同：
     • 若是第一个不同位，则将 first_bit 置为 false，不做其他操作。
     • 若不是第一个不同位，且 $a$ 的该位为 $0$（即 $b$ 的该位为 $1$），并且 $x + 2^i \le r$，则：
       • $x \gets x + 2^i$
       • 同时将 $a$ 和 $b$ 的该位翻转（a ^= (1<<i), b ^= (1<<i)），以模拟 $x$ 的影响，便于后续计算差值。
5. 输出 $b - a$。

时间复杂度：每个测试用例 $O(\log \max(a,b,r)) \approx O(60)$，总复杂度 $O(t \cdot 60)$，轻松通过。

参考代码

#include <bits/stdc++.h>

using namespace std;

const int maxb = 60;

bool get_bit(int64_t a, int i) {
    return a & (1ll << i);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int64_t a, b, r;
        cin >> a >> b >> r;
        int64_t x = 0;
        bool first_bit = true;
        if (a > b)
            swap(a, b);
        for (int i = maxb - 1; i >= 0; --i) {
            bool bit_a = get_bit(a, i);
            bool bit_b = get_bit(b, i);
            if (bit_a != bit_b) {
                if (first_bit) {
                    first_bit = false;
                } else {
                    if (!bit_a && x + (1ll << i) <= r) {
                        x += (1ll << i);
                        a ^= (1ll << i);
                        b ^= (1ll << i);
                    }
                }
            }
        }
        cout << b - a << "\n";
    }
    return 0;
}

细节说明

• 由于 $a, b, r \le 10^{18} < 2^{60}$，故最高位只需考虑到第 $59$ 位即可。
• 代码中 x 的累加用于判断是否超过 $r$，但并不需要真正输出 $x$，因此可以省略对 $a, b$ 的实际异或操作，直接维护当前差值并计算潜在收益，但直接修改 $a, b$ 亦无妨，逻辑更直观。
• 若 $a, b$ 在初始时高位就有多个不同位，第一个不同位不处理，后续按贪心尽可能翻转，最终差值即为答案。