自动搬运

查看原文

来自洛谷，原作者为

	tongyanmin **

搬运于2025-08-24 22:34:30，当前版本为作者最后更新于2021-11-13 07:27:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

由题意，我们必须恰好改变每队恰好 $n$ 个人的出拳方案。即会出现在已经构造出全胜方案之后还有剩余的操作次数的情况。所以我们必须考虑如何构造，维持最终得分为 $2n$。

下面讲讲我的做法。

我们不妨定义修改 A 组的操作为操作 $x$，修改 B 组的操作为操作 $y$。

1. 依次使用操作 $x,y$，构造出 A 组全胜的状态。
2. 在经过上一步之后，可能存在操作次数还未用完的情况。对此我们不妨找出之前未被修改的对局（即 A 组本来就胜利的情况），同时对 $a_i,b_i$ 进行修改，使得两种操作的使用次数同时增加。
3. 经过以上两轮之后，可以发现要么已经构造完毕，要么还剩下一次 $y$ 操作（第 $1$ 步中可能会出现 $cnt_x=cnt_y+1$ 的情况）。对于这种情况，不妨找出第一次被修改的对局，对其使用一次 $y$ 操作即可。

Code

#include<bits/stdc++.h>
using namespace std;
int t,n,a[200005],b[200005],c[200005],d[200005];//把修改后的数存在数组c,d中
bool check(int x,int y){
	if(x==1&&y==2)return 1;
	if(x==2&&y==3)return 1;
	if(x==3&&y==1)return 1;
	return 0;
}//判断胜负
bool vis[200005];
int main(){
	cin>>t;
	while(t--){
		cin>>n;	
		int cnt=0,cntx=0,cnty=0;
		for(int i=1;i<=n*2;i++){
			cin>>a[i];
			c[i]=a[i];
			vis[i]=0;
		}
		for(int i=1;i<=n*2;i++){
			cin>>b[i];
			d[i]=b[i];
		}
		for(int i=1;i<=2*n;i++){
			if(check(a[i],b[i]))continue;
			cnt++;
			if(cnt%2==1){
				cntx++;
				c[i]=d[i]-1;
				if(c[i]==0)c[i]=3;
			}//改a
			else{
				cnty++;
				d[i]=c[i]+1;
				if(d[i]==4)d[i]=1;
			}//改b
			vis[i]=1;			
		}//改为a必胜的局面
		for(int i=1;i<=2*n;i++){
			if(vis[i])continue;
			if(cntx<n&&cnty<n){
				c[i]+=1;
				if(c[i]==4)c[i]=1;
				d[i]+=1;
				if(d[i]==4)d[i]=1;
				cntx++,cnty++;
			}
			if(cntx==cnty&&cntx==n)break;
		}//消耗多余的操作次数
		if(cnty<n){
			for(int i=1;i<=n*2;i++){
				if(vis[i]){
					for(int j=1;j<=3;j++){
						for(int k=1;k<=3;k++)
							if(j!=a[i]&&k!=b[i]&&check(j,k))c[i]=j,d[i]=k;
					}//此处直接暴力修改即可，记得判重
					break;
				}	
			}
		}
		cout<<n*2<<endl;
		for(int i=1;i<=n*2;i++)cout<<c[i]<<" ";
		cout<<endl;	
		for(int i=1;i<=n*2;i++)cout<<d[i]<<" ";
		cout<<endl;		
	}
	return 0;
}