HDU 3830 Checkers：狀態空間二叉樹 + LCA 求最小跳躍步數

問題建模

三枚棋子位置 x

關鍵洞察：狀態形成二叉樹

• 根節點：三枚棋子等距分布（y-x = z-y）
• 父節點：短邊向長邊方向跳一步後的狀態
• 子節點：中間棋子向左右跳的兩種狀態

兩狀態可達 ⇔ 同一根節點。最小步數 = u 到根距離 + v 到根距離 - 2 × LCA(u,v) 到根距離。

核心操作

// 向根移動 floor 步
void GoUp(int floor) {
    while (floor) {
        int a1 = x[1] - x[0], a2 = x[2] - x[1];
        if (a1 > a2) { // 右邊短，左邊棋子右跳
            int d = (a1 - 1) / a2; if (d > floor) d = floor;
            floor -= d; x[2] -= d * a2; x[1] -= d * a2;
        } else { // 左邊短，右邊棋子左跳
            int d = (a2 - 1) / a1; if (d > floor) d = floor;
            floor -= d; x[0] += d * a1; x[1] += d * a1;
        }
        sort(x, x+3);
    }
}

// 計算到根距離
int Root() {
    int floor = 0;
    int a1 = x[1] - x[0], a2 = x[2] - x[1];
    while (a1 != a2) {
        if (a1 > a2) {
            int d = (a1 - 1) / a2; floor += d;
            x[2] -= d * a2; x[1] -= d * a2;
        } else {
            int d = (a2 - 1) / a1; floor += d;
            x[0] += d * a1; x[1] += d * a1;
        }
        sort(x, x+3);
        a1 = x[1] - x[0]; a2 = x[2] - x[1];
    }
    return floor;
}

LCA 查找：二分法

完整代碼結構

狀態結構體封裝 x[3]、排序、Root、GoUp、比較運算符
主循環讀入 u,v，計算各自根及深度
根不同輸出 NO，根同輸出 YES 及最小步數