[AGC055B] ABC Supremacy 题解
题目描述
给定两个长度为 \(n\) 的字符串 \(a\)，\(b\)。
你可以进行若干次以下操作：
- 若 \(a\) 中的一个子串为
ABC，BCA或CAB，那么可以将这个子串替换为ABC，BCA或CAB。
求能否将 \(a\) 变成 \(b\)，输出 YES 或 NO。
解析
不难发现，我们可以根据一些变换将ABC，BCA 或 CAB 和单个字母 A 换位置。
具体操作如下：
\[A \overline{ABC}\rightarrow \overline{ABC}A \\
B\overline{ABC}\rightarrow BCAB \rightarrow \overline{ABC}B\\
C\overline{ABC} \rightarrow \overline{ABC}C
\]
BCACAB都可以转换成ABC
我们可以把字符串 \(a\)，\(b\) 所有的 ABC，BCA 或 CAB 移动到最前面，剩余部分如果一样就可以转换。
实现
我们不需要真的把所有的 ABC，BCA 或 CAB 移动到最前面，只需要将他们删除，再比对剩余串。文章来源：https://www.toymoban.com/news/detail-476793.html
用 vector 实现比较方便。文章来源地址https://www.toymoban.com/news/detail-476793.html
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
char ck[4][4]={{'0','0','0'},
{'A','B','C'},
{'B','C','A'},
{'C','A','B'}
};
int n,na,nb;
char a[N],b[N];
vector<char>q;
bool pd(int x){
for(int i = 1; i <= 3; ++i){
if(q[x] == ck[i][0] && q[x + 1] == ck[i][1] && q[x + 2] == ck[i][2]){
return 1;
}
}
return 0;
}
void op(char x[],int &nx){
q = vector<char>();
for(int i = 0; i < n; ++i){
q.push_back(x[i]);
while(q.size() >= 3 && pd(q.size() - 3)){
q.pop_back();q.pop_back();q.pop_back();
}
}
nx = q.size();
for(int i = 0;i < q.size(); ++i){
x[i] = q[i];
}
}
void output(){
if(na != nb){
cout<<"NO"<<'\n';
return ;
}
for(int i = 0;i < na; ++i){
if(a[i] != b[i]){
cout<<"NO"<<'\n';
return ;
}
}
cout<<"YES"<<'\n';
}
int main(){
cin>>n>>a>>b;
op(a,na);op(b,nb);
output();
return 0;
}
到了这里，关于[AGC055B] ABC Supremacy 题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
