链接

https://codeforces.com/contest/2232/problem/D

简要题意

汉诺塔加强版，保留小盘必须在大盘之上的限制，同时移动的规则变更为，盘i能被移动，当且仅当上面正好有$a[i]$个盘（盘i不需要在顶部），问能否让盘在$2^n$步内从A柱移动到C柱，如果可以，构造方案。

大概思路

可以参考普通汉诺塔的做法。

首先有一些必要的限制，$a[i]<i$ 必须成立，否则一定无解。
接下来，我们可以使用归纳法，证明满足任意$a[i]<i$ 时，一定是有解的。

当只有一个盘的时候，可以直接把它从A柱移动到C柱，一个盘的时候有解。

假设现在有$k$个盘，而且他有解。那么对于$k+1$个盘的情况，我们可以先把k-$a[k+1]$个盘移动到B柱，然后把第$k+1$个盘移动到C柱，再把B柱上的盘移回A柱，然后把这k个盘移动到C柱，就移动完成了。

所以可以知道，满足以上条件，一定有解，且构造方式类似于普通汉诺塔。

接下来证明一定可以在$2^n$内解决，同样使用归纳法。
1个盘的时候，操作次数$1<2^1$。
假设n个盘的时候操作次数小于$2^n$，考察$n+1$个盘的操作次数。当$a[n+1]=0$时，退化为普通汉诺塔问题，操作次数为$2^{n+1}-1$；当$a[n+1]!=0$时，操作次数$<=1+2^n-1+2*(2^{n-a[n+1]}-1)<=2^{n+1}-1$

丑陋的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        if(a[i]>=i){
            cout<<"NO\n";
            return;
        }
    }
    cout<<"YES\n";
    vector<array<int,3>> result;
    auto dfs=[&](auto &&self,int n,int from,int mid,int to)->void{
        if(n==0) return;
        if(n==1){
            result.push_back({n,from,to});
            return;
        }
        if(a[n]==0){
            self(self,n-1-a[n],from,to,mid);
            result.push_back({n,from,to});
            self(self,n-1,mid,from,to);
        }else{
            self(self,n-1-a[n],from,to,mid);
            result.push_back({n,from,to});
            self(self,n-1-a[n],mid,to,from);
            self(self,n-1,from,mid,to);
        }
    };
    dfs(dfs,n,1,2,3);
    cout<<result.size()<<"\n";
    for(auto &[a,b,c]:result) cout<<a<<" "<<b<<" "<<c<<"\n";
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int t=1;
    cin>>t;
    while(t--) solve();
}