题解：P10739 [SEERC 2020] Disk Sort

Unnamed114514 · 2025-02-24 20:05:09 · 题解

首先，在构造过程中，我们应始终保持一根空柱子，这样我们构造的方式始终相同。

注意到在这种情况下，至少有一种未解决的颜色有一个盘在最顶上，因为解决的颜色只会占一个最顶上的盘，最顶上的盘一共有 n 个，所以一定会有剩的。

我们找到这种颜色，并求出它的三个位置，剩下的问题下放到手玩即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,c[3][N],tot[N],top[N];
bool vis[N];
vector<pair<int,int> > ans;
void upd(int a,int b){
    ans.emplace_back(make_pair(a,b));
    c[--top[b]][b]=c[top[a]++][a];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=0;i<3;++i) for(int j=1;j<=n;++j) cin>>c[i][j];
    top[n+1]=3;
    for(int T=1;T<n;++T){
        int emp=0;
        for(int i=1;i<=n+1;++i) if(top[i]==3){
            emp=i;
            break;
        }
        for(int i=1;i<=n+1;++i) if(i!=emp&&!vis[c[0][i]]){
            vis[c[0][i]]=1;
            int tot=0;
            pair<int,int> p[3];
            for(int j=0;j<3;++j) for(int k=1;k<=n+1;++k) if(k!=emp&&c[j][k]==c[0][i]) p[tot++]=make_pair(j,k);
            if(!p[2].first) upd(p[0].second,emp),upd(p[1].second,emp),upd(p[2].second,emp),upd(p[2].second,p[0].second),upd(p[2].second,p[1].second);
            else if(!p[1].first){
                if(p[0].second==p[2].second){
                    upd(p[0].second,emp),upd(p[1].second,emp);
                    if(p[2].first==1) upd(p[0].second,emp),upd(p[0].second,p[1].second);
                    else upd(p[0].second,p[1].second),upd(p[0].second,emp);
                } else if(p[1].second==p[2].second){
                    upd(p[0].second,emp),upd(p[1].second,emp);
                    if(p[2].first==1) upd(p[1].second,emp),upd(p[1].second,p[0].second);
                    else upd(p[1].second,p[0].second),upd(p[1].second,emp);
                } else{
                    upd(p[0].second,emp),upd(p[1].second,emp),upd(p[2].second,p[0].second);
                    if(p[2].first==1) upd(p[2].second,emp),upd(p[2].second,p[1].second);
                    else upd(p[2].second,p[1].second),upd(p[2].second,emp);
                }
            } else{
                if(p[0].second==p[1].second){
                    if(p[2].second!=p[0].second){
                        if(p[1].first==1){
                            upd(p[0].second,emp),upd(p[0].second,emp),upd(p[2].second,p[0].second);
                            if(p[2].first==1) upd(p[2].second,emp),upd(p[2].second,p[0].second);
                            else upd(p[2].second,p[0].second),upd(p[2].second,emp);
                        } else upd(p[2].second,emp),upd(p[2].second,emp),upd(p[0].second,p[2].second),upd(p[0].second,emp),upd(p[0].second,p[2].second);
                    }
                } else if(p[0].second==p[2].second){
                    if(p[2].first==1) upd(p[0].second,emp),upd(p[0].second,emp),upd(p[1].second,p[0].second),upd(p[1].second,emp),upd(p[1].second,p[0].second);
                    else{
                        if(p[1].first==1) upd(p[0].second,emp),upd(p[1].second,p[0].second),upd(p[1].second,emp),upd(p[0].second,p[1].second),upd(p[0].second,p[1].second),upd(p[0].second,emp);
                        else upd(p[1].second,emp),upd(p[1].second,emp),upd(p[0].second,p[1].second),upd(p[0].second,emp),upd(p[0].second,p[1].second);
                    }
                } else if(p[1].second==p[2].second) upd(p[1].second,emp),upd(p[0].second,p[1].second),upd(emp,p[0].second);
                else{
                    if(p[1].first==1){
                        upd(p[0].second,emp),upd(p[1].second,p[0].second),upd(p[1].second,emp),upd(p[2].second,p[1].second);
                        if(p[2].first==1) upd(p[2].second,emp),upd(p[2].second,p[1].second);
                        else upd(p[2].second,p[1].second),upd(p[2].second,emp);
                    } else upd(p[2].second,emp),upd(p[2].second,emp),upd(p[0].second,p[2].second),upd(p[1].second,p[0].second),upd(p[1].second,emp),upd(p[1].second,p[2].second);
                }
            }
            for(int i=1;i<=n+1;++i) if(top[i]!=0&&top[i]!=3) exit(0);
            break;
        }
    }
    int emp=0;
    for(int i=1;i<=n+1;++i) if(top[i]==3){
        emp=i;
        break;
    }
    if(emp!=n+1) upd(n+1,emp),upd(n+1,emp),upd(n+1,emp);
    cout<<ans.size()<<endl;
    for(auto p:ans) cout<<p.first<<' '<<p.second<<endl;
    return 0;
}