1 条题解
-
0
思路与算法
先把两组三坐标排序,设相邻间隔为u、v。不等距时,把较短间隔一侧的外棋子向内跳,得到唯一跨度缩小的父状态;连续同类父跳可按(v-1)/u或(u-1)/v批量计算,直到u=v的等差根。根不同则不可达。根相同则按父跳次数对齐深度,二分共同向上多少步后两状态相同,最短距离为深度差加两倍共同上移步数。
正确性说明
每个非等差三点状态的合法跳法中恰有一个缩小跨度,其他是其子状态方向,因此每个等差根的连通分量形成一棵隐式树。辗转相减父跳严格减少正间隔并保持三点不同,批量取商与逐步跳完全相同。树上两点最短路必经最低共同祖先;对齐深度后“上移后相同”单调成立,所以二分得到最少共同步数,距离公式正确。
复杂度
单次批量上移按欧几里得缩减间隔,需要O(log D)批,D为初始跨度。根、深度计算O(log D),二分O(log D)轮各执行上移,所以总O(log²D),额外空间O(1)。排序3个数和初始化O(1),坐标、跳数及乘积使用long long。
易错点
棋子无区别,先排序;不能把一次越过两颗棋子算合法跳。批量次数用(大间隔-1)/小间隔,避免跳成两个棋子重叠。独立小状态BFS对拍,跨度10^9且短间隔1的长链用逐跳规律的闭式距离验证。
参考代码(C++11)
#include <bits/stdc++.h> using namespace std; using T = array<long long, 3>; pair<T, long long> up(T a, long long steps) { long long used = 0; while (steps) { long long x = a[1] - a[0], y = a[2] - a[1]; if (x == y) break; if (x < y) { long long t = min(steps, (y - 1) / x); a[0] += t * x; a[1] += t * x; steps -= t; used += t; } else { long long t = min(steps, (x - 1) / y); a[1] -= t * y; a[2] -= t * y; steps -= t; used += t; } } return {a, used}; } int main() { T a, b; for (auto &x : a) cin >> x; for (auto &x : b) cin >> x; sort(a.begin(), a.end()); sort(b.begin(), b.end()); auto ra = up(a, 1LL << 60), rb = up(b, 1LL << 60); if (ra.first != rb.first) { cout << "NO\n"; return 0; } long long da = ra.second, db = rb.second, diff = llabs(da - db); if (da > db) a = up(a, diff).first; else b = up(b, diff).first; long long low = 0, high = min(da, db); while (low < high) { long long mid = (low + high) / 2; if (up(a, mid).first == up(b, mid).first) high = mid; else low = mid + 1; } cout << "YES\n" << diff + 2 * low << '\n'; }
- 1