D. Equalization【Educational Codeforces Round 176 (Rated for Div. 2)】

D. Equalization

思路：

好逆天的题
由题意可以发现将x、y右移直到完全相等时符合条件。
令$dp[i][j]$为$x$右移$i$位、$y$右移$j$位所需的最小代价，可以预处理一个二维的01背包dp。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int, int>
#define FU(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, a, b) for (int i = (a); i >= (b); --i)
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;int dp[65][65];
void init() {memset(dp, 0x3f, sizeof(dp));dp[0][0] = 0;for (int k = 1; k <= 60; k++) {for (int i = 60; i >= 0; i--) {for (int j = 60; j >= 0; j--) {if (i >= k)dp[i][j] = min(dp[i][j], dp[i - k][j] + (1ll << k));if (j >= k)dp[i][j] = min(dp[i][j], dp[i][j - k] + (1ll << k));}}}
}void solve() {int x, y;cin >> x >> y;int ans = 1e9;for (int i = 0; i <= 60; i++) {for (int j = 0; j <= 60; j++) {if (x >> i == y >> j) {ans = min(ans, dp[i][j]);}}}cout << ans << endl;
}signed main() {int T = 1;cin >> T;init();while (T--) {solve();}return 0;
}