?我们分析一下3个操作:
1.三个操作都会使得a, b变大
2.进行完第2个操作后,a >= b
3.最优解一定最多只能操作一次第2个操作
接着我们分情况讨论,
1.没有使用第2个操作:操作次数为b - a
2.使用了第2个操作,假设使用这次操作时,a 和 b的值增大为a1, b1, 那么操作次数为a1 - a + b1 - b + 1 + (a1 | b1) - b1 = a1 + (a1 | b1) + 1 - a - b.由于1 - a - b是常数,所以我们要使得a1 + (a1 | b1)最小.两个变量,我们可以枚举一个变量a1,枚举过程中要满足以下条件:a1 < b, a1 < b1, b >= b1.
于是,我们可以这样得到b1的值,枚举a1和b的每一位(从高到低):
b = 1, a1 = 1 / 0, b1 = 1
b = 0, a1 = 0, b1 = 0
b = 0, a1 = 1, b1 = 1, break
代码实现如下:
#include <bits/stdc++.h>
//#define LOCAL
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define PLL pair<int, int>
#define int long long
#define debug(a) cout << #a << "=" << a << endl;
#define all(x) (x).begin(), (x).end()
using namespace std;
void solve() {
int a, b;
cin >> a >> b;
int ans = b - a;//没有使用一次第3个操作
for (int a1 = a; a1 < b; ++a1) {
int b1 = 0;
for (int i = 30; i >= 0; --i)
if (b >> i & 1)
b1 |= (1 << i);
else if (a1 >> i & 1) {
b1 |= (1 << i);
break;
}
ans = min(ans, a1 + (a1 | b1) + (1 - a - b));
}
cout << ans << "\n";
}
signed main() {
#ifdef LOCAL
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#endif
IOS;
int T;
cin >> T;
while (T--)
solve();
}
