1 条题解

  • 0
    @ 2026-10-26 13:21:31

    思路与算法

    先把两组三坐标排序,设相邻间隔为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

    信息

    ID
    1763
    时间
    1000ms
    内存
    512MiB
    难度
    普及+
    标签
    递交数
    1
    已通过
    1
    上传者