题目大意 / 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;
}
文章评论