MYF

UVa 1339 Ancient Cipher

Posted on | In | | Visitors

题目链接

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");
    }
}