2018湘潭邀请赛 G

题目：输入两个只含有a、b、c的字符串，判断在通过对第一个字符串进行插入或删除aa、bb、abab后是否能变成第二个字符串

如果可以则输出yes，否则输出no

例如：ab

输出 yes 因为 ab—》aababb—》ba

输出 no

分析：由于插入和删除的对象只能是aa bb abab，所以如果c的数目不同，则不能转换；

可以先对字符串进行化简，也就是把所有的aa bb消去（在前一次消去后，都可能又一次出现aa bb 所以需要循环操作，如abba 消去bb后aa就在一起了又可以消去）

然后可以确定最后剩下的是abababab....或者babababa... ，abab和baba（ba相当于ab因为ba—》babb—》aababb—》ab）都可以消去，所以可以选择对4求余，看剩下的是否满足条件

易知剩下的字符数可能是0，1，2，3，如果取余后的数有一个是偶数，那么必须要两个剩下字符数目的相同，因为最后剩下的只能是ab或者ba或者空，而ab与ba是可以相互转换的

如果取余是奇数，而且字符数相同，那么只要第一个字符相同即可，因为最后只能出现a或者b或者aba或者bab

如果取余是奇数，而且字符数不同，那么只要第一个字符不同即可，因为ab与ba可以相互转换（选择后两个），然后就可以消去aa或者bb从而使剩下的字符串相互转换（易知最后剩下的是a、b、aba、bab，那么bab—》bba—》a）

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
#define LL long long
#define N 10005
char S[N],T[N];
string simplify(string s)   //把原串化简为ababab……或者 bababa……的串
{
	string ans = "";   
	while(1) {
		bool flag = 1;
		int len = s.length();
		for(int i=0;i<len;i++) {
			int cot = 0;
			for(int j=i+1;j<len;j++) {
				if(s[j]==s[i]) cot++,flag = 0;
				else break;
			}
			if(cot%2==0) ans+=s[i];
			i+=cot;
		}
		if(flag) break;
		s = ans;
		ans = "";
	}
	return ans;
}

int main()
{
	while(~scanf("%s",S)) {
		scanf("%s",T);
		int c1 = 0,c2 = 0;
		int l1 = strlen(S);
		int l2 = strlen(T);
		for(int i=0;i<l1;i++) if(S[i]=='c') c1++;
		for(int i=0;i<l2;i++) if(T[i]=='c') c2++;
		if(c1 != c2) {    //如果c的个数不等，则不能转化
			puts("No");
			continue;
		}	
		bool flag = 0;
		int p1=0,p2=0;
		for(int i=0;i<c1;i++){ //以c为分界将字符串分解成多个小字符串，并存储起来
			string s1 = "",s2 = "";
			while(S[p1]!='c') {
				s1 += S[p1++];
			}
			p1++;
			while(T[p2]!='c') {
				s2 += T[p2++];
			}
			p2++;
			s1 = simplify(s1);  //化简
			s2 = simplify(s2);
			int len1 = s1.length()%4; // 对四取余 
			int len2 = s2.length()%4;
			if(len1%2==0 || len2%2==0) {  //如果两个串的取余后的长度有一个为偶数
				if(len1 != len2) {    //则两个串长度必须相等，才能转化
					flag = 1; 
					break;
				}
			}else {                       //如果两个串的取余后的长度都为奇数
				if(len1 == len2) {
					if(s1[0] != s2[0]){ //若长度相等，则要求两个串的第一个字符 相等 才能转换；
						flag = 1;
						break;
					}
				}else {                      //若长度不等，则要求两个串的第一个字符 不等 才能转换
					if(s1[0] == s2[0]){
						flag = 1;
						break;
					}
				}
			}
		}
		string s1 = "",s2 = "";
			while(p1<l1) {
				s1 += S[p1++];
			}
			while(p2<l2) {
				s2 += T[p2++];
			}
			s1 = simplify(s1);
			s2 = simplify(s2);
			int len1 = s1.length()%4;
			int len2 = s2.length()%4;
			if(len1%2==0 || len2%2==0) {
				if(len1 != len2) {
					flag = 1;
				}
			}else {
				if(len1 == len2) {
					if(s1[0] != s2[0]){
						flag = 1;
					}
				}else {
					if(s1[0] == s2[0]){
						flag = 1;
					}
				}
			}
			if(flag) puts("No");
			else puts("Yes");
	}   
	return 0;
}

秒客网

2018湘潭邀请赛 G

相关文章