自动搬运

查看原文

来自洛谷，原作者为

	Unnamed114514 祈祷着今后的你的人生，永远都有幸福的「魔法」相伴。

搬运于2025-08-24 23:00:48，当前版本为作者最后更新于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;
}