题解：P10608 双人游戏

Kcjhdsq · 2024-06-20 18:39:51 · 题解

题解：P10608 双人游戏

题意

给予你一个长度为 n 的字符串 c，c 上有三种颜色的棋子，其中有 m 个空字符。

接下来有 m 个操作，每个操作意味小 M 或小 R 将某一个空棋子改成黑或白棋子。

小 R 希望游戏结束后棋子组成的极长同色连续段数尽可能多，而小 M 则希望其尽可能少。

每个人都会按照自己的意愿做最有做法。

求最终的极长同色连续段数。

思路

我们可以先将 c 的空格子改成改变它的人。

• 若 c_{i} 是 W 或 B，则不用管它。

• 易得，若 c_{i} 是 R，则肯定是将它改成与 c_{i-1} 相反。

• 易得，若 c_{i} 是 M，则肯定是将它改成与 c_{i-1} 相同。

但这么写会遗漏前面一大堆空格子的情况，这样的话，只要从尾到头的重复上述步骤即可。

如果全是空格子，上述步骤是不起作用的，易得当且仅当这种情况下 c_{1} 的数值是不影响最后结果的，所以可以取任意值。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,s[200005],x;
string c;
char  A;
int main(){
    cin>>n>>m>>c;
    c=' '+c;
    for(int i=1;i<=m;i++){
        cin>>A>>x;
        if(m==n&&i==1)A='W';
        c[x]=A;
    }   
//  cout<<c<<"\n";
    for(int i=1;i<=n;i++){

        if(c[i]=='R'){
            if(c[i-1]=='B')c[i]='W';
            else if(c[i-1]=='W')c[i]='B';
        }else if(c[i]=='M'){
            if(c[i-1]=='B')c[i]='B';
            else if(c[i-1]=='W')c[i]='W';
        }
        //cout<<c<<"\n";
    }
    for(int i=n;i>=1;i--){

        if(c[i]=='R'){
            if(c[i+1]=='B')c[i]='W';
            else if(c[i+1]=='W')c[i]='B';
        }else if(c[i]=='M'){
            if(c[i+1]=='B')c[i]='B';
            else if(c[i+1]=='W')c[i]='W';
        }
        //cout<<c<<"\n";
    }
//  cout<<c<<"\n";
    int ans=1;
    for(int i=2;i<=n;i++)if(c[i]!=c[i-1])ans++;
    cout<<ans;
    return 0;
}