题解：CF2029B Replacement

_Tatsu_ · 2024-11-23 12:52:01 · 题解

问题分析

给定一个二进制字符串 s，在每一步中，我们需要找到一个相邻字符不同的位置 j，然后将其替换为另一个字符串 r 中的字符，并继续进行直到字符串只剩下一个字符。我们需要判断是否可以完成所有的操作。

目标: 判断能否按照规则成功完成所有的操作。如果无法进行操作，即 s_k=s_{k+1} 对于所有的 k，则游戏失败。

解题思路

对于每一步，我们需要尽可能选择一个相邻的不同字符对，并且确保替换后的结果能继续进行下去。

对于每一对相邻的不同字符，查看是否可以将其替换为 r_i。

Code

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while (t--)
    {
        int n;
        cin>>n;
        string s,r;
        cin>>s;
        cin>>r;
        bool f=1;//表示是否可以完成操作
        // 进行 n-1 次操作
        for (int i=0;i<n-1;i++)
        {
            bool ff=0;//是否找到可替换的字符对
            for (int j=0;j<s.size()-1;j++)
            {
                if (s[j]!=s[j+1])
                {
                    //找到相邻不同的字符
                    s[j]=r[i];//将s[j]换为 r[i]
                    s.erase(j+1,1); //删除s[j+1]长度减1
                    ff=1;
                    break;//一旦找到替换对，退出当前循环
                }
            }
            if (!ff)
            {
                f=0;
                break;
            }
        }
        if (f)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}