arc 166 a

#include
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 ，

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