[CodeForces]1697.C. awoo’s Favorite Problem(字符串 + 思维 + 构造)

发布于 2022-06-16  606 次阅读


题目链接:Problem - C - Codeforces

题目大意 / Problem

有T个测试用例,在每个用例中:

给定一个长度N。

给定两个长度为N的字符串S和T,可以对S进行两种操作:

操作一:将“ab”修改为“ba”

操作二:将“bc”修改为“cb”

问能否通过若干次操作使得S变为T。

思路 / Thought

观察这两个操作的特点,都与b有关,而且ac的相对位置关系是不会改变的

换言之,如果给字符串中的每个a和c编号的话,每一个a和c的相对位置是固定的。

假如有一个字符串S为 “acbbaca”那么这里a和c的相对位置关系就应该是a->c->a->c->a不可能变为其他的,比如a->a->c->c->a这是不可能的。

因为a和c都可以通过b作为桥梁来移动,但是当a和c相遇时是不可以动的。

也就是说,S若要变成T,首先需要保证去除掉b后的两个字符串相等。

然后还要保证一点就是a只能向右移动,c只能向左移动,所以我们可以给S和T中出现的每个a和c都记录一下下标然后再进行比较即可。

如果出现了T中对应的a的位置小于S中对应a的位置说明a要向左移动,答案为否;

同样地如果在T中对应c的位置大于S中对应c的位置说明c要向右移动,答案为否。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9;
char s[maxn], t[maxn];

void solve()
{
	int N;cin >> N >> s + 1 >> t + 1;
	bool tag = 1;//表示答案 
	vector<int> sa, ta, sc, tc;
	string s2, t2;//表示删除 'b' 之后的字符串 
	for(int i = 1;i <= N; ++ i)
	{
		if(s[i] == 'b')continue;
		if(s[i] == 'a')sa.push_back(i), s2 += 'a';
		else if(s[i] == 'c')sc.push_back(i), s2 += 'c';
	}
	//处理t串 
	for(int i = 1;i <= N; ++ i)
	{
		if(t[i] == 'b')continue;
		if(t[i] == 'a')
		{
			ta.push_back(i), t2 += 'a';
			//在读取ta的同时检验i的合法性,注意要先确保下标的合法性 
			if(sa.size() >= ta.size() && sa[ta.size() - 1] > i)tag = 0;
		}
		else if(t[i] == 'c')
		{
			tc.push_back(i), t2 += 'c';
			if(sc.size() >= tc.size() && sc[tc.size() - 1] < i)tag = 0;
		}
	}
	if(s2 != t2 || ta.size() != sa.size() || tc.size() != sc.size())tag = 0;
	printf("%s\n", tag ? "YES" : "NO");
} 

signed main()
{
	//加快cin读取速度 
	ios::sync_with_stdio(0);
	int _;cin >> _;
	while(_ --)solve();
	return 0;
}