题解：P11207 「Cfz Round 9」Rose

saixingzhe · 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;
}