原题链接

一句话总结：两个只能动一个

经过艰苦卓绝的努力，我们发现在 $a \geq b$ 时，答案为 $a - b$。原因很简单：这时除了将 $b$ 加一，我们的任何操作都会让 $a$ 变大，而无益于让二者相等。

这就让我们可以用 $b$ 控制 $a$ 的大小，让数据范围中的值域限制有了意义。

注意到执行一次操作 3 就会让 $a$ 变得不小于 $b$。这样就会落入 $a \geq b$ 的情况中，最优策略是固定的了。

所以我们最多执行一次操作 3。

那么，我们需要决策的，就仅仅是在这次操作之前，操作 1 和操作 2 的执行情况。

一种方法是枚举让 $a$ 加了多少，让 $b$ 加了多少。但平方复杂度肯定会超时。

回收伏笔：两个只能动一个。也就是说，操作 1 和操作 2 中至少有一种没有被执行。

证明：假设操作 1 执行了 $i$ 次，操作二执行了 $j$ 次。

那么我们的总代价就是 $i + j + ((a + i) \text{ or } (b + j)) - (b + j)$。

整理，得到 $i + ((a + i) \text{ or } (b + j)) - b$，注意到 $-b$ 是常数，所以我们的目标就是最小化 $i + ((a + i) \text{ or } (b + j))$。

这个式子里 $j$ 只出现了一次。那么我们考虑，固定 $i$，哪个 $j$ 是最优的？

肯定是使 $((a + i) \text{ or } (b + j))$ 最小的 $j$ 最优。这是废话。

设 $b' = b + j, a' = a + i$。

但注意此时有 $b + j > a + i$。所以 $b'$ 二进制下的位数不少于 $a'$。或上 $a'$ 不会影响高位，但会影响低位（即 $a'$ 的最高位以下的部分）。

我们要让 $b'$ 加上一个值，之后低位上的或的结果就会变小。注意到我们不能影响高位，否则一定不优。那么只需要考虑优化低位，低位里我们跟 $a'$ 对齐（保持一样）即可。

可能 $a'$ 甚至不如 $b'$ 的低位大，但这不影响，我们反过来让 $a'$ 和 $b'$ 的低位变成一样即可，这个过程一定是不劣的，因为对于 $b'$ 低位中的 $1$，加上这一位的代价和好处是抵消的，而可能还有一些低位的 $0$，就提供更多的好处。

这时我们让 $a'$ 和 $b'$ 同时变小 1，发现答案变优了（$a'$ 或 $b'$ 变小之后低位部分整体就变小了）。于是我们不停做这个操作，直到做不动为止。什么时候会做不动呢？就是 $i$ 或 $j$ 为 $0$ 的时候。

于是我们就证明了这个关键结论。剩下的就是写两遍循环，分别枚举 $i$ 和 $j$。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <bits/stdc++.h>

using namespace std;
int T;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    for (int _ = 0; _ < T; ++_) {
        int a, b;
        cin >> a >> b;

        if (a >= b) {
            cout << a - b << "\n";
        } else {
            const int bound = b - a;
            int ans = bound;
            for (int i = a; i <= b; ++i) {
                ans = min(ans, i - a + 1 + (i | b) - b);
            }

            for (int i = b; i - b <= bound; ++i) {
                ans = min(ans, 1 + (i | a) - b);
            }
            cout << ans << "\n";
        }
    }
    return 0;
}