题目大意 / 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; }
Comments NOTHING