Magical Tiered Cake

Mier_Samuelle · 2026-07-24 19:30:21 · 题解

变种汉诺塔问题。先回顾一下经典的汉诺塔问题，要将盘子 x 从 A 移到 C，要先递归地将盘子 1 \sim x-1 从 A 移到 B。

考虑套用这个策略，本题中，要将盘子 x 从 A 移到 C，需要满足 x 上方恰好有 a_x 个盘子，就要先将盘子 1 \sim x-a_x-1 移到 B，并将盘子 x-a_x \sim x-1 叠在 x 上面。

据此，定义递归函数 f(x,\text{to}) 表示将盘子 1 \sim x 移到 \text{to} 数组中指定的位置上，并用 p_x 记录 x 此时的位置。

• 若 p_x=\text{to}_x，则无需额外操作，执行 f(x-1,\text{to}) 即可。
• 否则，按照上述策略构建盘子 1 \sim x-1 的目标位置数组 \text{pos}，执行 f(x-1,\text{pos})，将 x 移到 \text{to}_x，再执行 f(x-1,\text{to}_x)。

接下来证明操作次数小于 2^n。记 f_n 为将 n 个盘子从 A 移到 C 的操作次数，则有 f_n=2 \cdot f_{n-1}+1，且 f_0=0，则 f_n=2^n-1<2^n。注意无解的情形需特判。

:::success[Code]{open}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
int a[MAXN], p[MAXN], t[MAXN], n;
struct Opt{
    int id, from, to;
};
vector <Opt> op;
void output(int id, int from, int to){
    cout << id << " " << from << " " << to << "\n";
    return;
}
void move(int x, int to[]){
    if (x == 0){
        return;
    }
    if (p[x] == to[x]){
        move(x - 1, to);
        return;
    }
    int tmp[25] = {};
    for (int i = 1; i <= x - a[x] - 1; i++){
        tmp[i] = 6 - to[x] - p[x];
    }
    for (int i = x - a[x]; i <= x - 1; i++){
        tmp[i] = p[x];
    }
    move(x - 1, tmp);
    op.push_back({x, p[x], to[x]});
    p[x] = to[x];
    move(x - 1, to);
    return;
}
void solve(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        p[i] = 1;
        t[i] = 3;
    }
    for (int i = 1; i <= n; i++){
        if (a[i] >= i){
            cout << "NO\n";
            return;
        }
    }
    op.clear();
    move(n, t);
    cout << "YES\n";
    cout << op.size() << "\n";
    for (auto x : op){
        output(x.id, x.from, x.to);
    }
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--){
        solve();
    }
    return 0;
}

:::