跳跳棋

形式化题目

在数轴上，三颗棋子分别位于整数位置 $a < b < c$ 。每次操作选择外侧的一颗棋子，使其跳过相邻的中轴棋子，落在对称位置（跳后两段间隙中的一段翻转到另一侧，两段间隙长度不变的性质被打破，但两棋子间距等于被跳过的间隙长度）。

给定初始位置 $(a, b, c)$ 与目标位置 $(x, y, z)$ （棋子无区别），求是否能通过若干次跳动使棋子位置变为目标位置；若能，求最少跳动次数。

正解

思路

1. 跳动的逆操作构成树结构

一次跳动的逆操作是唯一的：若外侧棋子跳过中轴棋子，则逆操作就是把它跳回来。将每个状态看作节点，逆操作看作父边，则所有状态构成一棵二叉树：

当两段间隙相等（ $b - a = c - b$ ）时，该状态是叶子（根），无法再向"根"方向收缩；
否则，间隙较大的一侧的外侧棋子可以跳过中轴棋子，向内收缩一步。

两个状态互相可达 $\iff$ 它们在这棵树上的根相同。以间隙 $(d_1, d_2)$ 标注状态，树的形状如下（每个父节点恰好长出两个孩子）：

graph TD
    R["(d, d) 根"] --> L["(d, 2d)"]
    R --> RR["(2d, d)"]
    L --> L1["..."]
    RR --> R1["..."]
    S["S: (1,2,3) 间隙 (1,1) · depth 0"]:::sol
    G["G: (0,3,5) 间隙 (3,2) → (1,2) → (1,1) · depth 2"]:::sol
    R -.-> S
    R -.-> G
    classDef sol fill:#e8f5e9

样例的收缩过程（ $G$ 沿父边两步走到根，与 $S$ 同根，故 $\mathrm{LCA}$ 即根，答案 $0 + 2 - 0 = 2$ ）：

步骤	状态（升序）	间隙 $(d_1, d_2)$	动作
0	$(0, 3, 5)$	$(3, 2)$	左间隙大：右外侧棋子 $5$ 跳过中轴 $3$
1	$(0, 1, 3)$	$(1, 2)$	右间隙大：左外侧棋子 $0$ 跳过中轴 $1$
2	$(1, 2, 3)$	$(1, 1)$	间隙相等，抵达根

2. 收缩到根与深度计算

climb(state, limit) 沿父边向根收缩，同时记录步数（深度）。关键优化：当一侧间隙远大于另一侧时（如 $(1, 10^9)$ ），逐单步收缩效率极低。观察到同方向连续收缩可批量执行：若左间隙 $d_1$ 小于右间隙 $d_2$ ，则连续 $\lfloor (d_2-1)/d_1 \rfloor$ 步都在"右间隙减左间隙"，一步整除算清批长，将复杂度从 $O(\text{步数})$ 降至 $O(\log(\text{间隙比}))$ 。

3. LCA 求最少跳动次数

两状态 $S$ 、 $G$ 在同一棵树上的距离：

\text{dist}(S, G) = \text{depth}(S) + \text{depth}(G) - 2 \cdot \text{depth}(\mathrm{LCA}(S, G))

求 LCA 的方法：

先将较深的一方收缩到与另一方同一深度；
在同深度下二分搜索最小的 $k$ ，使得双方各收缩 $k$ 步后相遇（ $k$ 对"是否相遇"单调）；
最近公共祖先深度 $= \text{depth} - k$ ，代入公式得最少跳动次数。

代码

Python 版：

python

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78#!/usr/bin/env python3
# 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-09-30 18:05
# update_at: 2026-09-30 18:05

import sys

INF_STEPS = 10**18  # "不限步"的上界：收缩到根的真实步数远小于它


def climb(state: tuple[int, int, int], limit: int) -> tuple[tuple[int, int, int], int]:
    """从 state 沿唯一父边向根收缩，最多走 limit 步；返回 (落点, 实际步数)。

    收缩一步 = 外侧棋子跳过相邻中轴棋子，等价于把较大间隙减去较小间隙；
    同方向的连续收缩整批执行（一次整除算清批长），否则 (1, 1e9) 这种间隙
    要单步走 1e9 次。两间隙相等即到达根，收缩方向不再存在。
    """
    a, b, c = state
    d1, d2 = b - a, c - b  # 左右两段间隙
    done = 0
    while d1 != d2 and done < limit:
        if d1 < d2:  # 右间隙大：批量"右间隙 -= 左间隙"，直到右间隙不超左间隙
            t = min((d2 - 1) // d1, limit - done)
            a += t * d1  # 每步最左与中轴两子同步右移一个左间隙，间隙差逐批递减
            b += t * d1
            d2 -= t * d1
        else:  # 左间隙大：批量"左间隙 -= 右间隙"，中轴与最右两子同步左移
            t = min((d1 - 1) // d2, limit - done)
            b -= t * d2
            c -= t * d2
            d1 -= t * d2
        done += t
    return (a, b, c), done


def distance(start: tuple[int, int, int], goal: tuple[int, int, int]) -> int | None:
    """跳动树上两状态的距离（最少跳动次数）；根不同说明无解，返回 None。"""
    root_s, depth_s = climb(start, INF_STEPS)
    root_g, depth_g = climb(goal, INF_STEPS)
    if root_s != root_g:
        return None

    # 深的一方先缩到同一深度；再同步收缩，"缩 k 步后相遇"对 k 单调，二分求最小 k
    if depth_s > depth_g:
        start, _ = climb(start, depth_s - depth_g)
    elif depth_g > depth_s:
        goal, _ = climb(goal, depth_g - depth_s)
    lo, hi = 0, min(depth_s, depth_g)  # k 的上界 = 同深后的深度（最迟在根相遇）
    while lo < hi:
        mid = (lo + hi) // 2
        if climb(start, mid)[0] == climb(goal, mid)[0]:
            hi = mid
        else:
            lo = mid + 1

    lca_depth = min(depth_s, depth_g) - lo  # 最近公共祖先距根的深度
    return depth_s + depth_g - 2 * lca_depth


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    a, b, c = next(data), next(data), next(data)
    d, e, f = next(data), next(data), next(data)
    start = tuple(sorted((a, b, c)))
    goal = tuple(sorted((d, e, f)))

    steps = distance(start, goal)
    if steps is None:
        print("NO")
    else:
        print("YES")
        print(steps)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142/**
 * 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-09-30 18:02
 * update_at: 2026-10-05 08:18
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// 一个状态就是三颗棋子升序排列后的位置
struct State {
    ll a;
    ll b;
    ll c;
};

// 收缩步数上界：任何状态的深度都远小于它，用来表示“一直收缩到根”
const ll INF_STEPS = 1000000000000000000LL;

// 比较两个状态是否完全相同（即是否为树上的同一个节点）
bool same_state(State x, State y) {
    return x.a == y.a && x.b == y.b && x.c == y.c;
}

// 从状态 s 沿唯一的父边向根收缩，最多走 limit 步。
// 返回收缩后的状态，实际步数写入 out_steps。
State climb(State s, ll limit, ll &out_steps) {
    ll d1 = s.b - s.a; // 左间隙
    ll d2 = s.c - s.b; // 右间隙
    ll done = 0;
    // 两间隙相等时已经是根，无法继续向根收缩
    while (d1 != d2 && done < limit) {
        if (d1 < d2) {
            // 右间隙大：最右棋子连续跳过中轴，等价于右间隙反复减去左间隙。
            // 一次整除算出这批能走多少步，避免 (1, 1e9) 这类数据单步退化。
            ll t = (d2 - 1) / d1;
            if (t > limit - done) {
                t = limit - done;
            }
            s.a += t * d1;
            s.b += t * d1;
            d2 -= t * d1;
            done += t;
        } else {
            // 左间隙大：最左棋子连续跳过中轴，等价于左间隙反复减去右间隙
            ll t = (d1 - 1) / d2;
            if (t > limit - done) {
                t = limit - done;
            }
            s.b -= t * d2;
            s.c -= t * d2;
            d1 -= t * d2;
            done += t;
        }
    }
    out_steps = done;
    return s;
}

// 求跳动树上两状态的距离（最少跳动次数）。
// reachable 用来区分“根不同，无解”这种情况。
ll tree_distance(State start, State goal, bool &reachable) {
    ll depth_start = 0;
    ll depth_goal = 0;
    State root_start = climb(start, INF_STEPS, depth_start);
    State root_goal = climb(goal, INF_STEPS, depth_goal);
    if (!same_state(root_start, root_goal)) {
        reachable = false;
        return 0;
    }
    reachable = true;

    // 先把较深的一方收缩到和另一方同深度
    if (depth_start > depth_goal) {
        ll ignored = 0;
        start = climb(start, depth_start - depth_goal, ignored);
    } else if (depth_goal > depth_start) {
        ll ignored = 0;
        goal = climb(goal, depth_goal - depth_start, ignored);
    }

    // 同深度下“两边各收缩 k 步后相遇”对 k 单调，二分最小 k 即到达 LCA
    ll common_depth = min(depth_start, depth_goal);
    ll lo = 0;
    ll hi = common_depth;
    while (lo < hi) {
        ll mid = (lo + hi) / 2;
        ll ignored_start = 0;
        ll ignored_goal = 0;
        State up_start = climb(start, mid, ignored_start);
        State up_goal = climb(goal, mid, ignored_goal);
        if (same_state(up_start, up_goal)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }

    ll lca_depth = common_depth - lo; // 最近公共祖先到根的深度
    return depth_start + depth_goal - 2 * lca_depth;
}

void read_data(State &start, State &goal) {
    ll p[3];
    for (int i = 0; i < 3; i++) {
        cin >> p[i];
    }
    sort(p, p + 3);
    start.a = p[0];
    start.b = p[1];
    start.c = p[2];

    for (int i = 0; i < 3; i++) {
        cin >> p[i];
    }
    sort(p, p + 3);
    goal.a = p[0];
    goal.b = p[1];
    goal.c = p[2];
}

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

    State start;
    State goal;
    read_data(start, goal);

    bool reachable = false;
    ll steps = tree_distance(start, goal, reachable);
    if (!reachable) {
        cout << "NO" << "\n";
    } else {
        cout << "YES" << "\n";
        cout << steps << "\n";
    }

    return 0;
}

复杂度

时间复杂度：每次 climb 的批量收缩在 $O(\log(\text{间隙比}))$ 时间内完成；求 LCA 需二分 $O(\log(\text{depth}))$ 次 climb，故总时间复杂度为 $O(\log(\text{间隙比}) \cdot \log(\text{depth}))$ ，对于 $10^9$ 范围的坐标非常高效。
空间复杂度： $O(1)$ ，仅使用常数个变量。

总结

本题的关键洞见：跳动的逆操作唯一，所有状态构成二叉树，两状态可达 $\iff$ 根相同。
最少跳动次数转化为树上 LCA 距离问题，用"同深度二分相遇点"求最近公共祖先。
批量倍增加速收缩是避免 $O(\text{步数})$ 退化的关键，使算法能处理间隙比达 $10^9$ 的极端数据。

目录

形式化题目

正解

思路

1. 跳动的逆操作构成树结构

2. 收缩到根与深度计算

3. LCA 求最少跳动次数

代码

复杂度

总结