首页 > ACM题库 > HDU-杭电 > HDU 4357-String change-字符串-[解题报告]HOJ
2015
05-23

HDU 4357-String change-字符串-[解题报告]HOJ

String change

问题描述 :

In this problem you will receive two strings S1 and S2 that contain only lowercase letters.
Each time you can swap any two characters of S1. After swap,both of the two letters will increase their value by one. If the previous letter is ‘z’,it will become ‘a’ after being swapped.
That is to say ,"a" becomes "b","b" becomes "c"….."z" becomes "a" and so on.
You can do the change operation in S1 as many times as you want.
Please tell us whether you can change S1 to S2 after some operations or not.

输入:

There are several cases.The first line of the input is a single integer T (T <= 41) which is the number of test cases.Then comes the T test cases .

For each case,the first line is S1,the second line is S2.S1 has the same length as S2 and the length of the string is between 2 and 60.

输出:

There are several cases.The first line of the input is a single integer T (T <= 41) which is the number of test cases.Then comes the T test cases .

For each case,the first line is S1,the second line is S2.S1 has the same length as S2 and the length of the string is between 2 and 60.

样例输入:

3
ab
ba

bac
ddb

aaabb
cbccd

样例输出:

Case #1: NO
Case #2: YES
Case #3: YES
Hint
For the first case,it's impossible to change "ab" to "ba" . For the second case,swap(S1[0],S1[2])->swap(S1[1],S1[2]),meanwhile:bac->dac->ddb. For the third case,swap(S1[0],S1[3])->swap(S1[1],S1[2])->swap(S1[2],S1[3])->swap(S1[3],S1[4]), meanwhile:aaabb->caabb->cbbbb->cbccb->cbccd.

题意:

给定a串b串,问能否把a变成b串

方法:任选a的2个字母,ascil+=1 然后交换位置,可以操作任意多次。

3个及3个以上一定可以T^T

2个就暴力判一下

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 66;
char a[N], b[N];
bool check() {
	int n = 60;
	while(n -- > 0) {
		swap(a[0], a[1]);
		a[0] ++;
		a[1] ++;
		if(a[0] > 'z') a[0] = 'a';
		if(a[1] > 'z') a[1] = 'a';
		
		if(a[0] == b[0] && a[1] == b[1]) return true;
	}
	return false;
}

int main() {
	int T, cas = 0;
	scanf("%d", &T);
	while(T-- > 0) {
		scanf("%s%s", a, b);
		int n = strlen(a);
		bool ok = 0;
		if(n == 2) {
			if(check()) ok = 1;
			else ok = 0;
		} else {
			int s1 = 0, s2 = 0;
			for(int i = 0; i < n; i ++) {
				s1 += a[i] - 'a';
				s2 += b[i] - 'a';
			}
			if((s1+s2)&1) ok = 0;
			else ok = 1;
		}
		if(ok) printf("Case #%d: YES\n", ++cas);
		else printf("Case #%d: NO\n", ++cas);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/qq574857122/article/details/39961263