P8093 题解

YCSluogu · 2022-02-08 11:55:10 · 题解

这里提供一个新奇的思路。

大家考虑一个弱化情况：如果只允许除以 2 和加一并且 a > b。会怎么做？

这就非常容易考虑。让 a 不断加 1 与除以 2 直到 b > a，这样 a 便可以一路加到 b 去。

大家推样例是否发现这样一个情况：a 会一开始不断除以 2 和加 1，一旦开始乘 2 后就不会再除以 2。 原因其实很好理解，若除以 2 后乘 2 对答案不会更优。

啧……是不是就和我们弱化情况开始有点类似了呢？也就是说，我们需要找一个数 t，作为我们的中转值。 负责让我们完成弱化情况。那么这个中转值，要满足什么条件？

后面只允许乘 2 和加 1。所以，t 的二进制一定是 b 二进制表示下的一个前缀。

所以，我们只需要枚举 b 二进制前缀表示的数字，即 t。然后按照弱化情况求出 a 变为 t 所花的次数。 这都求出来了，还想不到后面怎么写？不断将 a 乘 2 和加 1，使其与 b 的前缀保证相同即可。

code

#include <bits/stdc++.h>

using namespace std;

long long n;

long long len(long long num) {
  for (long long i = 63; i >= 0; i--) {
    if ((num >> i) & 1) {
      return i + 1;
    }
  }
  return 0;
}

long long get(long long num, long long i, long long len) {
  return num >> (len - i);
}

void solve() {
  long long a, b, c, cnt = 0, ans = INT_MAX;
  cin >> a >> b;
  if (a == b) {
    cout << 0 << endl;
    return;
  }
  c = len(b);
  long long save = a;
  for (long long i = 1; i <= c; i++, ans = min(ans, cnt), a = save) {
    cnt = 0;
    long long nowb = get(b, i, c);
    while (a != nowb) {
      if (a > nowb) {
        if (a & 1) a++;
        else a /= 2;
        cnt++;
      } else {
        cnt += nowb - a;
        a = nowb;
      }
    }
    for (long long j = i + 1; j <= c; j++) {
      nowb = get(b, j, c);
      a <<= 1;
      cnt++;
      if (nowb != a) a++, cnt++;
    }
  }
  cout << ans << endl;
}

int main() {
  cin >> n;
  while (n--) {
    solve();
  }
  return 0;
}