POJ 2159 Ancient Cipher
比较水的一道题，判断明文和密文是否有可能是匹配的。
原题地址：http://poj.org/problem?id=2159
POJ 2159 古老的密码
问题描述
有两种比较简单的加密方式。一种是将明文的每个字母一一映射到另一个字母，还有一种加密方式是打乱字母顺序。
这两种加密方式如果单独使用，加密的效果是非常差的。如果把这两种加密同时使用，加密效果就好多了。
问题的目标就是判断给出的明文和密文是否可能是匹配的。
输入数据
第一行是密文，第二行是明文。
输出数据
如果明文和密文匹配则输出“YES”，否则输出“NO”。
样例输入
JWPUDJSTVP VICTORIOUS
样例输出
YES
解题思路
只要判断明文中每个字母出现的次数和密文中的每个字母出现的次数是否相同就可以了。就是说，比如样例中密文出现过的字母 J, W, P, U, D, S, T, V 分别是 2, 1, 2, 1, 1, 1, 1, 1 次，明文出现过的字母 V, I, C, T, O, R, U, S 分别是 1, 2, 1, 1, 2, 1, 1, 1 次，排序之后，这些次数都是 2, 2, 1, 1, 1, 1, 1, 1 次，所以它们可能是匹配的。
在 POJ 的 Discuss 里，有人提出了，统计两个数组中每个元素的个数、每个元素的和、每个元素的平方和，然后分别比对，如果都相等，则可判定两个数组所组成的集合是相等的（要求两个数组中的元素是自然数）。这个我不知道怎么证明……不过看起来好像比较有用。
源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | #include <cstdlib> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; char a[1000], b[1000], *p; size_t la, lb, ta[26], tb[26], i; int main() { memset(ta, 0, sizeof(ta)); memset(tb, 0, sizeof(tb)); scanf("%s%s", a, b); la = strlen(a); lb = strlen(b); if (la != lb) { printf("NO\n"); return 0; } for (p = a; *p; ++p) ++ta[*p-'A']; for (p = b; *p; ++p) ++tb[*p-'A']; sort(ta, ta + 26); sort(tb, tb + 26); for (i = 0; i < 26; ++i) if (ta[i] != tb[i]) break; if (i == 26) printf("YES\n"); else printf("NO\n"); return 0; } |
原创文章，转载请注明来源：http://euyuil.com/2394/poj-2159-ancient-cipher/
即使是打乱了顺序，某个字母映射的个数是一样的（比如A即使转为Z，在A出现的地方，必定转化为Z，但是Z的个数一定等于A的个数，而与其出现的位置无关），因为他们是一一对应，那么平方和一定会相等。很有趣的题目呀~
如果它们一样那么平方和相等这是显然的。但是如果它们平方和相等、个数相等、和相等，那么能判定它们是一样的集合，这才是奇葩之所在。