CF1697C awoo's Favorite Problem


题目传送门

思路:

首先观察题面:

在一个操作中,您可以执行其中之一:

选择 s 中出现的 ab 并将其替换为 ba ;

选择 s 中出现的 bc 并将其替换为 cb 。

从操作一中可以发现,$a$ 字符的位置只能向后移动;从操作二可以发现,$c$ 字符的位置只能向前移动

那么假如我们忽略掉字符 $b$,举样例为例,即:

1:
s: ca_
t: ca_

2:
s: a
t: _

3:
s: a__a_c
t: __aac_

4:
s: _caa_a_a_c
t: c__a_a_aac

5:
s: _a
t: a_

再根据输出的结果,你会发现:只要字符 $a$ 和字符 $c$ 的相对位置不变,则可以将字符串 $s$ 转化为字符串 $t$

但是我们再看样例 5,虽然字符 $a$ 的相对位置没有变化,那为什么答案是 NO 呢?

如果再回去看我们之前得出来的结论( $a$ 的位置只能向后移动),就可以得出这个答案了(当然 $c$ 同理)。

AC CODE:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
inline int read(){//快读优化 
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
signed main(){
	n=read();
	while(n--){
		string s1,s2;
		int len=read(),cnt1=0,cnt2=0;
		cin>>s1>>s2;//读入 s t 串 
		for(int i=0;i<len;i++){
			if(!(s1[i]^'b'))cnt1++;//记录 s 串中 b 字符的个数 
			if(!(s2[i]^'b'))cnt2++;//记录 t 串中 b 字符的个数 	
		}
		if(cnt1^cnt2)puts("NO");//当两个字符串的 b 字符个数不相同,则直接输出 NO 
		else{
			int x=0,f=0;
			for(int i=0;i<len;i++){
				if(!(s1[i]^'b'))continue;//只处理当前字符为 a,c 的情况 
				while(!(s2[x]^'b'))x++;//找到下一个不为 b 的字符 
				if(s1[i]^s2[x]||(!(s1[i]^'a')&&i>x)||(!(s1[i]^'c')&&i<x)){f=1;puts("NO");break;}//当相对位置不相同,或者 s 串中的 a 在 t 串中的 a 后面( a 的相对位置相同 ),或者 s 串中的 c 在 t 串中的 c 前面( c 的相对位置相同 ),则标记无解,输出 NO 并跳出循环 
				x++;
			}
			if(!f)puts("YES");//有解则输出 YES  
		}
	}
	return 0;
}

文章作者: alex_liu
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 alex_liu !
  目录