https://codeforc.es/contest/1697/problem/C
因为规则中，两种字符串变换都与‘b’有关，所以我们根据b的位置来进行考虑；
先去掉所有的'b'，如果两字符串不相等就“NO”；
否则通过‘b'在a,b串中的位置，如果posa>posb,那么他们之间如果出现'a'就说明不可能
如果posb<posa，那么他们之间如果出现'c'说明不可能
1 # include<iostream>
2 # include<bits/stdc++.h>
3 using namespace std;
4 const int N = 3e5 + 10;
5 #define int long long
6 # define endl "\n"
7 int suma[N], sumc[N];
8 char a[N], b[N];
9 char newa[N], newb[N];
10 int posa[N], posb[N];
11 void solve() {
12 int n;
13 cin >> n;
14 cin >> a + 1 >> b + 1;
15 int cnt1 = 0, cnt2 = 0;
16 for (int i = 1; i <= n; ++i) {
17 if (a[i] == 'a') suma[i] = suma[i - 1] + 1;
18 else suma[i] = suma[i - 1];
19 if (a[i] == 'c') sumc[i] = sumc[i - 1] + 1;
20 else sumc[i] = sumc[i - 1];
21 if (a[i] != 'b') newa[++cnt1] = a[i];
22 if (b[i] != 'b') newb[++cnt2] = b[i];
23 }
24
25 if (cnt1 != cnt2) {
26 cout << "NO" << endl;
27 return;
28 }
29 for (int i = 1; i <= cnt1; ++i) {
30 if (newa[i] != newb[i]) {
31 cout << "NO" << endl;
32 return;
33 }
34 }
35 cnt1 = 0, cnt2 = 0;
36 for (int i = 1; i <= n; ++i) {
37 if (a[i] == 'b') posa[++cnt1] = i;
38 if (b[i] == 'b') posb[++cnt2] = i;
39 }
40 if (cnt1 != cnt2) {
41 cout << "NO" << endl;
42 return;
43 }
44 for (int i = 1; i <= cnt1; ++i) {
45 int x = posa[i], y = posb[i];
46 if (x < y) {
47 if (suma[y] - suma[x - 1] != 0) /*前缀和判断a的位置*/
{
48 cout << "NO" << endl;
49 return;
50 }
51 }
52 if (x > y) {
53 if (sumc[x] - sumc[y - 1] != 0) {
54 cout << "NO" << endl;
55 return;
56 }
57 }
58
59 }
60 cout << "YES" << endl;
61 }
62 int tt;
63 signed main() {
64 ios::sync_with_stdio(false);
65 cin.tie(0);
66 cout.tie(0);
67
68 cin >> tt;
69
70 while (tt--)solve();
71 return 0;
72 }
73 /*
74
75 */
主要是通过前缀和来判断两个pos之间是否存在'a'或者'c'的操作
