题解 P1906 【凯撒密码】

HanPi · 2020-12-23 21:14:54 · 题解

P1906 凯撒密码

这道题的提示是想告诉你,在一个英语中,字母 E 出现的频率最高,也就是说我们找到当前句子中出现最多的字母,它就代表了字母 E .知道这个对应关系后,我们把它相减,就得到每一个字母需要偏移的量.

设 \tt 'A'+ans 为找到的代表 'E' 的字符.

则 任意字符所对应的明文应为该字符加上 \tt 'E'-'A'-ans

题目提示既然这样说了,样例就应该会保证满足吧.

坑点:

• 出现次数不需要清空(见第2个句子 N 和 J 都是在该句出现6次)
• 如果使用gets读入,前4个测试点是 ENDOFINPUT\r ,最后一个测试点是 ENDOFINPUT.不特判你将会喜提TLE.
• 偏移后如果超出了范围,需要调整.
• 要转成大写字母

#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <string.h>
#include <malloc.h>
unsigned int dic[30] = {0};
int FindOffset(char* destStr)
{
    unsigned int i = 0, ans = 0;
    while (destStr[i++])
    {
        if ('a' <= destStr[i] && destStr[i] <= 'z')
        {
            destStr[i] = destStr[i] - 'a' + 'A';
            dic[destStr[i] - 'A']++;
        }
        else if ('A' <= destStr[i] && destStr[i] <= 'Z') dic[destStr[i] - 'A']++;
    }
    for (i = 0; i <= 26; i++)
    {
        //printf("%c %d\n", 'A' + i, dic[i]);
        if (dic[i] > dic[ans])
        {
            ans = i;
        }
    }
    return 'E'-'A'-ans;
}
char buf[500007],s;
int main()
{

    char* p,tmp;
    while (gets(buf))
    {
        p = buf;

        if (strcmp(buf, "ENDOFINPUT\r") == 0)break;
        if (strcmp(buf, "ENDOFINPUT") == 0)break;

        if (strcmp(buf, "END\r") == 0 || strcmp(buf, "START\r") == 0)continue;
        s = FindOffset(buf);
        while (*p)
        {
            tmp = *p;
            if ('A' <= *p && *p <= 'Z')
            {
                tmp+= s;
                if (tmp < 'A')tmp += 26;
                if (tmp > 'Z')tmp -= 26;
            }

            putchar(tmp);
            p++;
        }
        puts("");
    }
    return 0;
}