MYF

UVa 1339 Ancient Cipher

题目链接

UVa 1339

解题方法:字符串的处理

题目分析

题目大意

有两种加密方式:

1.Substitution 替换加密,比如把所有的字母换成字母表中的前一个字符。

2.Permutation 排列加密,把所有的字符按照一定顺序从原字符串取出,形成一个新的字符串。

However,这两种加密方式都太弱了,很容易被识破,所以把这两种方式结合起来使用。
那么,问题来了,给你一个密文,判断该密文是否可能是原文的密文。

解析

既然替换是随意的,排列是随意的,那么什么不是随意的呢?答案是每个字母的出现次数。至于这些次数是怎么排序的,无所谓。所以我们先统计一下每一个字符的出现次数,原文的存在数组a[]里,密文的存在数组b[]里,然后sort一下,如果这26个数字每一个数字都对应一致,那么就当这两个串是对应的。(感觉逻辑上有点问题,但是没有经过严谨证明,所以无法判断。管他呢,反正Ac了…)

代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define PI acos(-1)
#define debug printf("Hi----------\n")
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 10005
int main(){
char str1[105],str2[105];
while (scanf("%s %s",str1,str2)!=EOF) {
int cnt1[26]={},cnt2[26]={},ans=0;
for (int i=0; str1[i]; i++) {
cnt1[str1[i]-'A']++;
}
for (int i=0; str2[i]; i++) {
cnt2[str2[i]-'A']++;
}

sort(cnt1, cnt1+26);
sort(cnt2, cnt2+26);

for (int i=0; i<26; i++) {
if (cnt1[i]==cnt2[i]) {
ans++;
}
}

if (ans==26) {
printf("YES\n");
}
else
printf("NO\n");
}
}