题解：CF2029B Replacement

问题分析

给定一个二进制字符串

s

，在每一步中，我们需要找到一个相邻字符不同的位置

j

，然后将其替换为另一个字符串

r

中的字符，并继续进行直到字符串只剩下一个字符。我们需要判断是否可以完成所有的操作。

目标: 判断能否按照规则成功完成所有的操作。如果无法进行操作，即

s_k=s_{k+1}

对于所有的

k

，则游戏失败。

解题思路

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

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

r_i

。

Code

CPP

#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;
}

题解：CF2029B Replacement

文章操作

问题分析

解题思路

Code

相关推荐

评论

题解：CF2029B Replacement