本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-07-29 00:05:56

我还是太菜了啊啊啊啊。

A

显然 $6 = 3!$。
也就是说所有 abc,acb,cab 之类的排列都可以解决，刚好对应 6 个子序列。
可以划分出 $[1,n],[n+1,2n],[2n+1,3n]$ 三个区间。

直接搞就行了。

#include <bits\/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
char s[maxn * 3];
int n;
char ord[4];
int ans[maxn*3];
int main()
{
    scanf("%d", &n);
    scanf("%s", s + 1);
    ord[1]='A';
    ord[2]='B';
    ord[3]='C';
    int num=0;
    do
    {
        num++;
        int minsum=0;
        int sum1=0,sum2=0,sum3=0;
        for(int i=1;i<=n;i++)
        {
            if(ans[i])continue;
            if(s[i]==ord[1])sum1++;
        }
        for(int i=n+1;i<=2*n;i++)
        {
            if(ans[i])continue;
            if(s[i]==ord[2])sum2++;
        }
        for(int i=2*n+1;i<=3*n;i++)
        {
            if(ans[i])continue;
            if(s[i]==ord[3])sum3++;
        }
        minsum=min(sum1,min(sum2,sum3));
        sum1=sum2=sum3=0;
        for(int i=1;i<=n;i++)
        {
            if(ans[i])continue;
            if(s[i]==ord[1])
            {
                if(sum1==minsum)continue;
                sum1++;
                ans[i]=num;
            }
        }
        for(int i=n+1;i<=2*n;i++)
        {
            if(ans[i])continue;
            if(s[i]==ord[2])
            {
                if(sum2==minsum)continue;
                sum2++;
                ans[i]=num;
            }
        }
        for(int i=2*n+1;i<=3*n;i++)
        {
            if(ans[i])continue;
            if(s[i]==ord[3])
            {
                if(sum3==minsum)continue;
                sum3++;
                ans[i]=num;
            }
        }
    } while (next_permutation(ord+1,ord+4));
    for(int i=1;i<=3*n;i++)
    {
        printf("%d",ans[i]);
    }
    return 0;
}  

B

由于操作可逆，可以把两个串向同一方向转化。

题目给定的 3 个可以互相转化的字符串统一成 abc，或其他的也行。

模拟一下可以看到，这些 abc 可以与其他任意字符交换。

所以做法：先把两个字符串的 abc,bca,cab 统一转化成 abc，转化出一个就删除一个，看最后两个字符串剩下的是否相等。

#include <bits\/stdc++.h>
using namespace std;
const int maxn=5e5+5;
char a[maxn],b[maxn];
int n;
bool vis[maxn];
bool vis2[maxn];
int main()
{
    scanf("%d",&n);
    scanf("%s",a+1);
    scanf("%s",b+1);
    vector<char> final_a,final_b;
    for(int i=1;i<=n;i++)
    {
        final_a.emplace_back(a[i]);
        int cnt=final_a.size();
        if(final_a.size()>=3)
        {
            string s={final_a[cnt-3],final_a[cnt-2],final_a[cnt-1]};
            if(s=="ABC" or s=="BCA" or s=="CAB")
            {
               final_a.pop_back();
               final_a.pop_back();
               final_a.pop_back(); 
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        final_b.emplace_back(b[i]);
        int cnt=final_b.size();
        if(final_b.size()>=3)
        {
            string s={final_b[cnt-3],final_b[cnt-2],final_b[cnt-1]};
            if(s=="ABC" or s=="BCA" or s=="CAB")
            {
               final_b.pop_back();
               final_b.pop_back();
               final_b.pop_back(); 
            }
        }
    }
    if(final_a.size()!=final_b.size())
    {
        puts("NO");
        return 0;
    }
    bool no=0;
    for(int i=0;i<final_a.size();i++)
    {
        no|=(final_a[i]!=final_b[i]);
    }
    puts(no?"NO":"YES");
    return 0;
}  

C 以后

还没看题。