自动搬运

查看原文

来自洛谷，原作者为

	saixingzhe 『自己选择的路，跪着也要走完』

搬运于2025-08-24 23:05:16，当前版本为作者最后更新于2024-10-19 22:25:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

验题人题解。

分析

答案不超过 $2$ 是显然的，因为一定可以通过修改两人的第一张牌满足题目要求。

判断答案为 $0$ 根据题意模拟即可。

规定 $1\leq x$。

考虑如和判断答案是否可以为 $1$，发现当她出完此轮牌时各颜色数量为 $x-1,x,x+1$ 时可以通过调整一次得到，将前面一张 $x+1$ 颜色的牌变为 $x-1$ 的颜色的牌即可。

然后我们考虑你不能在她前面达成获胜条件。

• 你先出现 $x,x,x$，她后出现 $x-1,x,x+1$，只需要将你出现 $x,x,x$ 情况前某一张 $x+1$ 颜色的牌变为 $x-1$ 的颜色的牌即可。

• 你先出现 $x-1,x,x+1$，她后出现 $x-1,x,x+1$，（注意你和她 $x-1,x,x+1$ 的颜色一一对应）只需要将你出现 $x-1,x,x+1$ 情况后，她出现 $x-1,x,x+1$ 前某一张 $x+1$ 颜色的牌变为 $x-1$ 的颜色的牌即可。

• 你先出现 $x-1,x,x+1$，再出现 $x,x,x$，她后出现 $x-1,x,x+1$，（注意你和她 $x-1,x,x+1$ 的颜色一一对应）只需要将你出现 $x-1,x,x+1$ 情况后，出现 $x,x,x$ 前某一张 $x+1$ 颜色的牌变为 $x-1$ 的颜色的牌即可。

• 你先出现 $x,x,x$，再出现 $x-1,x,x+1$，她后出现 $x-1,x,x+1$，（注意你和她 $x-1,x,x+1$ 的颜色一一对应）显然，此时无论如何不能通过只修改一张牌使得她先于你达成胜利条件。

对于最后一种情况进行大力分讨，记录你最先出现 $x,x,x$ 的位置，最后出现 $x-1,x,x+1$ 的位置，判断即可。

对于记录 $x-1,x,x+1$ 最后出现的位置有种不动脑的方法就是枚举 $x-1,x+1$ 的颜色，直接开 $6$ 个变量，简单判断即可。

代码

#include<bits/stdc++.h>
using namespace std;
int T,n,a[3];
string s,t;
int main(){
	cin>>T;
	while(T--){
		a[0]=a[1]=a[2]=0;
		bool fl=1;
		int t01=0,t02=0,t10=0,t12=0,t20=0,t21=0,p=INT_MAX;
		cin>>n>>s>>t;
		for(int i=0;i<n;i++){
			if(s[i]=='P')	a[0]++;
			if(s[i]=='V')	a[1]++;
			if(s[i]=='W')	a[2]++;
			if(a[0]==a[1]&&a[0]==a[2]){
				fl=0;
				break;
			}	
			if(t[i]=='P')	a[0]++;
			if(t[i]=='V')	a[1]++;
			if(t[i]=='W')	a[2]++;
			if(a[0]==a[1]&&a[0]==a[2]){
				p=i;
				break;
			}	
		}
		if(fl){
			a[0]=a[1]=a[2]=0;
			for(int i=0;i<n;i++){
				if(s[i]=='P')	a[0]++;
				if(s[i]=='V')	a[1]++;
				if(s[i]=='W')	a[2]++;
				if(a[0]-a[1]==2&&a[0]-a[2]==1&&p>t01){
					fl=0;
					break;
				}
				if(a[0]-a[2]==2&&a[0]-a[1]==1&&p>t02){
					fl=0;
					break;
				}
				if(a[1]-a[0]==2&&a[1]-a[2]==1&&p>t10){
					fl=0;
					break;
				}
				if(a[1]-a[2]==2&&a[1]-a[0]==1&&p>t12){
					fl=0;
					break;
				}
				if(a[2]-a[0]==2&&a[2]-a[1]==1&&p>t20){
					fl=0;
					break;
				}
				if(a[2]-a[1]==2&&a[2]-a[0]==1&&p>t21){
					fl=0;
					break;
				}
				if(t[i]=='P')	a[0]++;
				if(t[i]=='V')	a[1]++;
				if(t[i]=='W')	a[2]++;
				if(a[0]-a[1]==2&&a[0]-a[2]==1)	t01=i;
				if(a[0]-a[2]==2&&a[0]-a[1]==1)	t02=i;
				if(a[1]-a[0]==2&&a[1]-a[2]==1)	t10=i;
				if(a[1]-a[2]==2&&a[1]-a[0]==1)	t12=i;
				if(a[2]-a[0]==2&&a[2]-a[1]==1)	t20=i;
				if(a[2]-a[1]==2&&a[2]-a[0]==1)	t21=i;
			}
			if(fl)	printf("2\n");
			else	printf("1\n"); 
		}
		else	printf("0\n");
	}
	return 0;
}