[atAGC055B]ABC Supremacy

将第$i$个字符在$A->C->B->A$这个环上操作$i$次，而此时的操作也即将$AAA,BBB$或$CCC$变为其中的另一个字符串

通过操作$XXXY->YYYY->YXXX$，即可以将$XXX$向右移动一位，同时其还可以变为任意字符，那么不妨将其删除并在最后（任意位置）插入一个形如$XXX$的字符串

具体的，令$f(S)$表示不断在$S$中删除形如$XXX$的字符串（直至不存在），则$f(S)$是良定义的

这里的良定义，即删除顺序不会影响$f(S)$（$f(S)$是可确定的）

按$|S|$进行归纳，并对当前$S$分类讨论：

1.若$S$中不存在形如$XXX$的字符串，那么即可结束，显然有$f(S)=S$

2.若$S$中仅存在1个形如$XXX$的字符串，那么只能将其删除，则$f(S)=f(S')$

3.若$S$中存在不少于1个形如$XXX$的字符串，任取其中两个并记将两者删除后的字符串为$S_{1}$和$S_{2}$，那么证明$f(S_{1})=f(S_{2})$即可，下面对两者分类讨论：

(1)两者无公共部分，那么定义$S_{0}$为将两者均删除后的字符串，由归纳假设$f(S_{1})=f(S_{2})=f(S_{0})$，即得证

(2)两者有公共部分，那么不难发现最后剩下的均相同，也即有$S_{1}=S_{2}$，显然成立

进一步的，$S$能变为$T$当且仅当$f(S)=f(T)$

必要性：注意到$S$操作后（注意不是删除）$f(S)$不变（均先删除操作的部分即可）

充分性：先从$S$得到$f(S)$，再按$T$得到$f(T)$的逆序插入$XXX$也即可得到$T$（次数显然相同）

关于如何对于$S$求出$f(S)$，维护一个栈即可实现

时间复杂度为$o(n)$，可以通过

#include<bits/stdc++.h>
using namespace std;
#define N 500005
int n,ns,nt,a[N],b[N];
char s[N],t[N];
int main(){
    scanf("%d%s%s",&n,s+1,t+1);
    for(int i=1;i<=n;i++){
        int x=(s[i]-'A'+n-i)%3;
        if ((ns>1)&&(a[ns]==x)&&(a[ns-1]==x))ns-=2;
        else a[++ns]=x;
    }
    for(int i=1;i<=n;i++){
        int x=(t[i]-'A'+n-i)%3;
        if ((nt>1)&&(b[nt]==x)&&(b[nt-1]==x))nt-=2;
        else b[++nt]=x;
    }
    if (ns!=nt){
        printf("NO
");
        return 0;
    }
    for(int i=1;i<=ns;i++)
        if (a[i]!=b[i]){
            printf("NO
");
            return 0;
        }
    printf("YES
");
    return 0;
}