[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 移動到最前面，只需要將他們洗掉，再比對剩余串，
用 vector 實作比較方便，
代碼
#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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/554775.html
標籤：其他
上一篇：RALB負載均衡演算法的應用
下一篇：返回列表