AtCoder Regular Contest 166——A - Replace C or Swap AB

//A - Replace C or Swap AB
/*每个字符串的长度为N，由A, B和C组成。
通过对X执行以下三种操作任意次数(可能为零)，确定是否有可能使X与y重合。

操作(1):选择X中的字符C替换为字符A。
操作(2):在X中选择字符C替换为字符B。
操作(3):选择X中的子字符串AB，替换为BA。更正式地说，选择一个使x的第i和(i+1)个字符分别为A和B，并将前者替换为B，后者替换为A。
你有T个测试用例需要解决。

约束
1≤T≤2×10
5

1≤N≤2×10
5
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#define MAXN 200009
using namespace std ;

int N , T ;
vector<int> Ax , Ay , Cx ;//记录X，Y每个块中的A和C出现位置 
string x , y ;
bool flag ;//判断是否不可实现 

void Clear() {//处理完一个块后清空 
    while( !Ax.empty() )
        Ax.pop_back() ;
    while( !Ay.empty() )
        Ay.pop_back() ;
    while( !Cx.empty() )
        Cx.pop_back() ;
}

void check() {
    if( Ax.size()+Cx.size() < Ay.size() || Ax.size() > Ay.size() ) {//块中出现X的A加C不够，或者X中的A过多 
        flag = 1 ;
        return ;
    }
    int cnt = 0 ;
    while(Ax.size()<Ay.size()) {//贪心处理，将位置最小的C变成A 
        Ax.push_back(Cx[cnt]) ;
        cnt ++ ; 
    }
    /*for( int i = 0 ; i < Ay.size()-Ax.size() ; ++ i )//经典错误，错误原因在于Ax push_back后长度增加 
        Ax.push_back(Cx[i]) ; */
    sort(Ax.begin(),Ax.end());
    for( int i = 0 ; i < Ay.size() ; ++ i ) {
        if( Ax[i] > Ay[i] ) {//比较X中每个A是否都小于Y中的A，如果有不小于的，说明这个A无法滑动至与Y中的A对齐 
            flag = 1 ;
            return ;
        } 
    }
    return ;
}

void Solve() {
    for( int i = 0 ; i < N ; ++ i ) {
        if( y[i] == 'C' ) {
            if( x[i] != 'C' ) {
                flag = 1 ;
                break ;
            }
            check() ;
            x[i] = 'D' ;//防止切割点C被纳入用于填充的C 
            if( flag ) break;
            Clear() ;
        }
        if( y[i] == 'A' )//记录A的位置 
            Ay.push_back(i) ;
        if( x[i] == 'A' )
            Ax.push_back(i) ;
        if( x[i] == 'C' )//记录C的位置 
            Cx.push_back(i) ;
    }
    check();
    return ;
}

int main() {
    scanf("%d", &T );
    for( int t = 1 ; t <= T ; ++ t ) {
        Clear() ;
        flag = 0 ;
        scanf("%d", &N );
        cin >> x >> y ;
        Solve() ;
        if( flag == 1 )
            printf("No\n");
        else printf("Yes\n");
    }
}