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;
}