题解归档 - cf2232D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2232D
• 本地来源：problems/cf2232D/idea.md
• 题目链接：https://codeforces.com/contest/2232/problem/D
• 原始标题：2232D Magical Tiered Cake

思路

2232D Magical Tiered Cake

题意

$n$ 层蛋糕（$1$ 最小在顶，$n$ 最大在底）初始在厨房（位置 1），仓库为 2，派对为 3。第 $i$ 层可移动当且仅当同一位置上恰有 $a_i$ 层比它小的蛋糕在它上方。每次可将一个可移动层移到另一位置，须放在严格更大的层之上（或空位）。在 $\le 2^n$ 步内将全部层搬到位置 3，或判无解。

无解条件

层 $i$ 上方最多有 $i-1$ 个更小的层，故若 $a_i \ge i$ 则不可能，输出 NO。

构造（Tower of Hanoi 推广）

若对所有 $i$ 有 $a_i < i$，则必有解。递归 move_range(k, src, dst, aux) 表示把层 $1..k$ 从 src 搬到 dst：

• $a_k = 0$（只能先移走上方）：经典 Hanoi
  move_range(k-1, src, aux, dst) → 移 $k$ → move_range(k-1, aux, dst, src)
• $a_k \ge 1$：令 $t = k-1-a_k$，先把最小 $t$ 层暂存到 aux，使 $k$ 上方恰剩 $a_k$ 层，移 $k$ 到 dst，再把 $t$ 层放回 src，最后 move_range(k-1, src, dst, aux)。

步数 $\le 2^n$：介于「全 $a_i=i-1$」的 $n$ 步与「全 $a_i=0$」的 $2^n-1$ 步之间。

样例

验证

Python 模拟器对 200 组随机 $n\le12$、合法 $a_i$ 全部通过，步数 $\le 2^n$。

代码

来源：problems/cf2232D/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=25;
int n;
int a[maxn];
vector<array<int,3>> moves;
void addMove(int id,int from,int to){
    moves.push_back({id,from,to});
}
void moveRange(int k,int src,int dst,int aux){
    if(k==0) return;
    if(a[k]==0){
        moveRange(k-1,src,aux,dst);
        addMove(k,src,dst);
        moveRange(k-1,aux,dst,src);
    }else{
        int keep=k-1-a[k];
        moveRange(keep,src,aux,dst);
        addMove(k,src,dst);
        moveRange(keep,aux,src,dst);
        moveRange(k-1,src,dst,aux);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        bool bad=false;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(a[i]>=i) bad=true;
        }
        if(bad){
            cout<<"NO\n";
            continue;
        }
        moves.clear();
        moveRange(n,1,3,2);
        cout<<"YES\n";
        cout<<moves.size()<<"\n";
        for(auto e:moves) cout<<e[0]<<" "<<e[1]<<" "<<e[2]<<"\n";
    }
    return 0;
}