HDU 4260 The End of The World：漢諾塔剩餘步數遞歸計算

題目大意

• 標準漢諾塔：3 柱，n ≤ 63 個盤，從 A 移到 B，最優解步數 2^n - 1。
• 給定中間狀態（字符串表示每盤所在柱），求完成遷移所需剩餘步數。

遞歸性質

設 `calc(k, goal)` 為將前 `k` 小盤全部移至 `goal` 柱所需步數。
觀察第 `k` 個盤（最大的未就位盤）：

• 若其已在 `goal`：`calc(k, goal) = calc(k-1, goal)`。
• 若不在 `goal`：設 `other` 為第三根柱。
   1. 將前 `k-1` 盤移至 `other`：`calc(k-1, other)` 步。
   2. 移動第 `k` 盤至 `goal`：1 步。
   3. 將 `k-1` 盤從 `other` 移至 `goal`：標準漢諾塔需 `2^{k-1} - 1` 步。
   總計：`calc(k-1, other) + 2^{k-1}`。

完整代碼

#include 
using namespace std;
using ll = long long;
string s; // s[0] 最小盤，s[n-1] 最大盤
int n;

ll calc(int k, char goal) { // k: 1-indexed 前 k 個盤
    for (int i = k; i >= 1; --i) {
        if (s[i-1] != goal) {
            char other = 'A' ^ 'B' ^ 'C' ^ s[i-1] ^ goal; // 三柱異或得第三根
            return calc(i-1, other) + (1LL << (i-1));
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> s) {
        if (s == "X") break;
        n = s.size();
        cout << calc(n, 'B') << "\n";
    }
    return 0;
}

複雜度

• 遞歸深度 ≤ 63，每層常數操作，時間 O(n)。
• 位運算 `1LL << (i-1)` 計算 2 的冪，`n=63` 時 `2^62` 符合 64 位有符號整數。