arc 166 a

#include<bits/stdc++.h>
using namespace std;
using VI = vector<int>;
using ll = long long;
const int mod = 998244353;
//当只有ab的时候，看作把a可以向右移动
//1 - x 是a  1 - y a
//x中的 a 的 下标 <= y 中 a 的下标
//这样就可以通过位移得到
// c - c  这种情况是不可能进行移动的，所以就考虑在 c - c 将x y  分界
//考虑如何变 a , b    首先数量都是对的 ， 然后将a尽量放在左边
void solve(){int n;cin>>n;string x,y;cin>>x>>y;bool ok = true;for(int i = 0 ; i < n ; i++){if(x[i] != 'C' && y[i] == 'C'){ok = false;}}x += 'C';y += 'C';int amax = 0 ;//把所有的c变成a的数量int amin = 0 ;//纯a的数量for(int i = 0 ; i <= n ; i++){if(x[i] == 'A'){amax ++;amin ++;}else if(x[i] == 'C'){amax++;}if(y[i] == 'C'){if(amin > 0)ok = false;amax = 0 ;amin = 0 ;}else if(y[i] == 'B'){}else if(y[i] == 'A'){amax--;amin--;amin = max(amin , 0);if(amax < 0) ok = false;}//if(amax < amin) ok = false;}if(ok)cout<<"Yes\n";else cout<<"No\n";}int main(){int t;cin>>t;while(t--){solve();}}

首先将考虑只有ab的时候，可以发现a是可以不断向右移动的

可以证明只有当 X中a的数量 = y中a的数量  且对于 Xk <= Yk  （X中第k个A的下标 小于等于 Y的第k个A下标）

对于存在C

X[i] = Y[i] = C 时的点是不能动的 ， 以次为边界，将字符串进行分割，每一段都要分别满足

考虑每一段该如何构造，考虑两种情况是不满足的

1. a太多了 ,  即使c不变a也分不掉，

BAAACAB

BAAABBB

这种情况用amin代表有多少个A没被分配到  ，不断统计X中a的数量  ,  Y中出现就  -1

当分界时候 如果还有a没被分掉，就代表false

2.a+c 太少了，在某一个点就不够分 ，

BABBBCB

BBAAABA

amax统计a + c 的数量， 如果Y中出现 a 就 - 1 ，

如果变成负数，就代表不够分