培养信心练手题,POJ2159题目描述如下:
这题乍一看挺简单,但我还是掉了一个坑ORZ。
解题思路其实就是求一下加密前和加密后的字符串是否等价,两种加密方法,第二种换位置法显然只是一个烟雾弹,只对排列顺序做改变,不对替换法之后的序列中字母本身(即涉及的字母有哪些以及每种字母有几个)做出改变。
我最一开始没有仔细读题,被举的例子误导,以为替换法是整体字符串统一加一个任意常数k,就把转换前后的两个字符串从A到Z排序之后对对应位做差,如果每一位差都相等说明可以通过转换得到对方,反之不能,WA了很久想不明白错在哪里,后来又仔细读了一遍题发现替换法并不是整个字符串统一加一个随机常数k,而是无规律的随便用字母替换原先字符串中的字母(只要保证被替换字母相同的位置替换后字母也相同即可) 因此就只能通过计算每个字母出现的个数,去比对前后两个字符串中出现k次的字母个数是否相同,相同即可被替换,代码如下:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{char before[101], after[101];cin >> after >> before;int alpha_before[26] = { 0 }, alpha_after[26] = { 0 };int len = strlen(before), i = 0, flag = 0;for (i = 0; i < len; i++){alpha_before[before[i] - 'A']++;alpha_after[after[i] - 'A']++;}sort(alpha_before, alpha_before + 26);sort(alpha_after, alpha_after + 26);for (i = 0; i < 26; i++){if (alpha_before[i] != alpha_after[i]){flag = 1;cout << "NO" << endl;break;}}if (flag == 0)cout << "YES" << endl;return 0;
}