[AGC055B] ABC Supremacy 题解

题目描述

给定两个长度为 (n) 的字符串 (a)(b)

你可以进行若干次以下操作:

  • 若 (a) 中的一个子串为 ABCBCA 或 CAB,那么可以将这个子串替换为 ABCBCA 或 CAB

求能否将 (a) 变成 (b),输出 YES 或 NO

解析

不难发现,我们可以根据一些变换将ABCBCA 或 CAB 和单个字母 A 换位置。

具体操作如下:

[A overline{ABC}rightarrow overline{ABC}A \ Boverline{ABC}rightarrow BCAB rightarrow overline{ABC}B\ Coverline{ABC} rightarrow overline{ABC}C ]

BCA CAB 都可以转换成 ABC

我们可以把字符串 (a)(b) 所有的 ABCBCA 或 CAB 移动到最前面,剩余部分如果一样就可以转换。

实现

我们不需要真的把所有的 ABCBCA 或 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.cnblogs.com/hfjh/p/17468908.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!