HDU 4357

这道题写起来没难度，但这种题确实很难，这种字符串的题难在证明。以后也要注意。

奇偶性不同的字符串肯定不能转换，因为每一次交换都是字符串的和增加2。

当字符串长度为2时，可以模拟交换，最多26次。

否则，任选三个字母（x1,x2,x3）->(x1+1,x2,x3+1)......(1)

而且还有(x1,x2,x3)->(x1+2,x2,x3).....(2)

对于第一种变换，可以变换到至多只有一个字母不符合的情况，由于字符串奇偶性相同，则该字母相差为偶数，可以通过第二种变换得到。

#include <iostream>

#include <string.h>

#include <cstring>

#include <cstdio>

using namespace std;

char s1[70],s2[70];

int main(){

	int T,t=0;

	char tmp;

	scanf("%d",&T);

	while(++t<=T){

		scanf("%s",s1);

		scanf("%s",s2);

		int len=strlen(s1);

		printf("Case #%d: ",t);

		if(len==2){

			int i;

			for(i=0;i<26;i++){

				tmp=s1[1];

				s1[1]=s1[0];

				s1[0]=tmp;

				s1[0]=(s1[0]-'a'+1)%26+'a';

				s1[1]=(s1[1]-'a'+1)%26+'a';

				if(strcmp(s1,s2)==0)

				break;

			}

			if(i>=26)puts("NO");

			else puts("YES");

		}

		else{

			int sum1=0,sum2=0;

			for(int i=0;i<len;i++){

				sum1+=(s1[i]-'a');

				sum2+=(s2[i]-'a');

			}

			if(sum1%2==sum2%2)

			puts("YES");

			else puts("NO");

		}

	}

	return 0;

}

巴特西

HDU 4357

最新文章

热门文章