Link

ARC166 A Replace C or Swap AB

Qustion

给出两个长度相同的由 \(A，B，C\) 组成的字符串 \(X\) 和 \(Y\) 。需要使用一些操作使得 \(X\) 和 \(Y\) 一样

将 \(X\) 中的 \(C\) 换成 \(A\)
将 \(X\) 中的 \(C\) 换成 \(B\)
将 \(X\) 中的 \(AB\) 换成 \(BA\)

Solution

我们先讨论没有 \(C\) 的情况

通过观察，我们发现，\(A\) 只能往右边移动 \(B\) 只能往左边移动

那么，只需要观察每一位，如果这一位之前 \(Y\) 中 \(B\) 的个数多余 \(X\) 中 \(B\) 的个数，那么就是 No

反过来看，如果这一位之后 \(Y\) 中 \(A\) 的个数多余 \(X\) 中 \(A\) 的个数，那么就是 No

再考虑 \(X\) 中有 \(C\) 的情况

因为\(A\) 只能往右边移动 \(B\) 只能往左边移动，先计算出几个 \(C\) 转换成 \(A\) 几个转换成 \(B\) ，那么贪心，把前面的 \(C\) 改成 \(A\) 后面的 \(C\) 改成 \(B\)

最后考虑 \(Y\) 中有 \(C\) 的情况

按照 \(Y\) 中的 \(C\) 分段处理就好了

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
int T,N,flg;
string X,Y;
bool check(){
    int num_xa,num_xb,num_ya,num_yb,num_xc;
    cin>>N>>X>>Y;
    X="C"+X+"C";
    Y="C"+Y+"C";
    N=X.size();
    int L=0,R=0;
    num_xa = num_xb = num_xc = num_ya = num_yb = 0;
    for(int i=0;i<N;i++)
        if(Y[i]=='C'){
            if(X[i]!='C') return 0;
            if(num_xa > num_ya) return 0;
            if(num_xb > num_yb) return 0;
            L=R;R=i;
            int C_A = num_ya - num_xa;
            for(int j=L;j<=R;j++)if(Y[j] != 'C' && X[j] == 'C'){
                if(C_A) X[j] == 'A', C_A--;
                else X[j] == 'B';
            }
            num_xb = num_yb = num_xc = 0;
        }
        else {
            num_xb += (X[i]=='B'); num_xc += (X[i]=='C'); num_xa += (X[i]=='A');
            num_yb += (Y[i]=='B'); num_ya += (Y[i]=='A');
        }
    
    num_xb = num_yb = 0;
    for(int i=0;i<N;i++)
        if(Y[i]=='C'){
            num_xb = num_yb = 0;
        }
        else {
            num_xb += (X[i]=='B');num_yb += (Y[i]=='B');
            if(num_xb > num_yb) return 0;
        }
    
    num_xa = num_ya = 0;
    for (int i=N;i>=0;i--)
        if(Y[i]=='C'){
            num_xa = num_ya = 0;
        }
        else {
            num_xa += (X[i]=='A');num_ya += (Y[i]=='A');
            if(num_xa > num_ya) return 0;
        }
    return 1;
}
int main(){
    freopen("A.in","r",stdin);
    cin>>T;
    while(T--){
        printf("%s\n",check()?"Yes":"No");
    }
    return 0;
}