Searching for Soulmates

题意

给定若干组 (a,b)。只能对 a 做这些操作：

$a = a * 2$
如果 a 是偶数， $a = a / 2$
$a = a + 1$

问最少多少次操作能把 a 变成 b。

思路

先看一个小数据暴力。它直接把数字看成状态，用 BFS 枚举三种操作。

cpp

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 19:28
 * update_at: 2026-07-11 19:30
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int T;

int bfs(int a, int b) {
    int limit = max(a, b) * 4 + 20;
    vector<int> dist(limit + 1, -1);
    queue<int> q;

    dist[a] = 0;
    q.push(a);

    while (!q.empty()) {
        int x = q.front();
        q.pop();

        if (x == b) return dist[x];

        int nxt[3];
        int cnt = 0;
        if (x + 1 <= limit) nxt[cnt++] = x + 1;
        if (x * 2 <= limit) nxt[cnt++] = x * 2;
        if (x % 2 == 0) nxt[cnt++] = x / 2;

        for (int i = 0; i < cnt; i++) {
            int y = nxt[i];
            if (y >= 1 && y <= limit && dist[y] == -1) {
                dist[y] = dist[x] + 1;
                q.push(y);
            }
        }
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        int a, b;
        cin >> a >> b;
        cout << bfs(a, b) << '\n';
    }

    return 0;
}

满分做法利用一个关键性质：最优方案中，不会出现“先乘 2，后面又除 2”的结构。因为形如：

text

1x -> 2x -> 2x+k -> x+k/2

总可以改成更短的：

text

1x -> x+k/2

所以操作可以分成三段：

先对 a 做若干次“除以 2”相关操作，把它缩小；
中间做若干次 +1；
最后做若干次 $*2$ 和少量 +1，恢复到 b。

关键是枚举第 3 段有多少次 $*2$ 。设这个次数为 removed，那么第 3 段开始前要达到：

text

1prefix = b >> removed

也就是 b 去掉最后 removed 个二进制位后的前缀。

固定 prefix 后，把 a 缩小到不超过 prefix 的过程是贪心确定的：

如果当前数是偶数，直接 $/2$ ；
如果当前数是奇数，必须先 +1，再 $/2$ 。

这样每次都会少一位二进制长度，并且不会吃亏。

当 a 被压到 $cur <= prefix$ 后，中间需要 prefix-cur 次 +1。

最后恢复 b 的低 removed 位：

每一位都需要一次 $*2$ ，所以贡献 removed；
低位中每个 1 还需要一次 +1，所以贡献 popcount(b 的低 removed 位)。

枚举所有可能的 removed，取最小值即可。

代码

cpp

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 19:28
 * update_at: 2026-07-11 19:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int T;

ll solve_pair(ll a, ll b) {
    ll ans = (1LL << 62);

    for (int removed = 0; (b >> removed) > 0; removed++) {
        ll prefix = b >> removed;
        ll cur = a;
        ll steps = 0;

        // 固定除法次数后，S1 阶段是唯一的：奇数先 +1，再 /2。
        while (cur > prefix) {
            if (cur % 2 == 1) {
                cur++;
                steps++;
            }
            cur /= 2;
            steps++;
        }

        // 中间只需要补若干次 +1，让 cur 变成 prefix。
        steps += prefix - cur;

        // S3 阶段：removed 次 *2，加上恢复 b 的低 removed 位中所有 1 的代价。
        steps += removed;
        if (removed > 0) {
            ll mask = (1LL << removed) - 1;
            steps += __builtin_popcountll((unsigned long long)(b & mask));
        }

        ans = min(ans, steps);
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        ll a, b;
        cin >> a >> b;
        cout << solve_pair(a, b) << '\n';
    }

    return 0;
}

复杂度

removed 最多枚举到 $b$ 的二进制位数，内部每次也至多除掉 $a$ 的若干位。

单组时间复杂度为 $O(\log^2 \max(a,b))$ ，空间复杂度为 $O(1)$ 。

总结

本题的关键是从二进制角度看操作。

固定最后的乘二次数后，前面的缩小过程和后面的恢复低位代价都可以直接算出来，于是枚举这个分界点即可。

Searching for Soulmates

目录

题意

思路

代码

复杂度

总结