本文共 1173 字，大约阅读时间需要 3 分钟。

因为$ab->aababb->ba$

且$ba->aababb->ab$

说明$ab$和$ba$之间可以相互转化

考虑所有变化不包括字符$c$,所以原串分为若干段,我们比较每一段是否能进行转换

我们先把所有的$aa,bb$消除,最后会得到一串形如

$ababab....$的串,或者是$bababa.....$

如果串长度奇偶性质不同显然无法转化,因为所有操作都是改变偶数个字母

又因为我们可以把$ba->ab$

而且有操作消除$abab$或者插入$baba$,也就是消除偶数个$a$和$b$

那么假设串长为偶数

这么操作最后会得到$ab$,或者$ba$,或者空串

显然$ab,ba$可以相互转化,却不能凭空变成空串

假设长为奇数

这么操作会得到$a$,或者$b$,或者$aba$,或者$bab$

而$aba$可以转化为$b$,而$bab$可以转化为$a$

显然判断一下是否相同即可

所以我们得到结论,如果两个串的$a,b$奇偶性质有一个不同就不能转化,否则可以

#include 
   
    using namespace std;const int maxn = 1e6+10;char a[maxn],b[maxn];vector
    
     get(char a[]){
   	int n = strlen( a+1 ), sum = 0;	vector
     
      ans; ans.clear();	for(int i=1;i<=n+1;i++)	{
   		if( a[i]=='c' || i==n+1 )	ans.push_back( sum ), sum = 0;		else	sum ^= a[i];	}	return ans;}int main(){
   	while( cin >> ( a+1 ) >> (b+1) )	{
   		if( get(a)==get(b) )	cout << "Yes\n";		else	cout << "No\n";	}	return 0;}
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116541163 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！