原题链接

题目大意：给定两种字符串替换规则：”ab”可以替换成”ba”，”bc”可以替换成”cb”,每组数据给出两个字符串s和t，问是否能对s进行有限次（可以为零）替换得到t，可以输出YES，否则输出NO，字符串保证只含a b c三种字母

例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
input

5
3
cab
cab
1
a
b
6
abbabc
bbaacb
10
bcaabababc
cbbababaac
2
ba
ab

output

YES
NO
YES
YES
NO

不难发现b可以依靠其前面紧挨的a向前移动，依靠后面紧挨的c向后移动，可以统计其他每两个字母间的b的数量，若除去b后s和t相同（不同直接NO）再从头到尾遍历对比s和t区段的b的数量之差，若当前遍历到的s中b数量较多则b必须能够后移，若较少则b必须能够前移，由此可以抓住问题本质找到通用解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
#define fastIO	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
const int N=2e5+10;
int q,n;

int main(){
    fastIO
    cin>>q;
    while(q--){
        string s="",t="";
        cin>>n;
        cin>>s>>t;
        vector<int> ns(1,0);
        vector<int> nt(1,0);
        string cs="",ct="";
        for(int i=0;i<n;i++){
            if(s[i]!='b'){
                cs+=s[i];
                ns.push_back(0);
            }
            else ns.back()+=1;
            if(t[i]!='b'){
                ct+=t[i];
                nt.push_back(0);
            }
            else nt.back()+=1;
        }
        int sum=0;
        bool ok=true;
        if(cs==ct){
            for(int i=0;i<ns.size()-1;i++){
                sum+=ns[i]-nt[i];
                if(sum>0&&cs[i]=='a'){  //b无法后移
                    ok=false;
                    break;
                }
                if(sum<0&&cs[i]=='c'){  //b无法前移
                    ok=false;
                    break;
                }
            }
        }
        cout<<(ok&&cs==ct ? "YES":"NO")<<'\n';
    }
    return 0;
}