|
题解 P1906 【凯撒密码】
SadLava
2019-10-20 10:16:39
Solution
## 前言
这题好坑！（我好菜）
## 分析
本题考查凯撒密码。首先我们了解几个基本名词：**密文、明文、密钥**。
密文顾名思义就是**被加密过的文字**，明文指的是**原始信息**，密钥指的是**用来加密或是解密的信息**（现代复杂密码中，**一个密钥可能只能加密不能解密**，详见百度）。
了解了这个，我们看题中的示范：
```python
明文：I Need Soldiers
密文：K Pggf Uqnfkgtu
密钥：
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
```
我们可以看到，**第二行密钥中的K对应第一行中的I，P对应N，g对应e......u对应s**，按这个思路，密文就被解密成了**I Need Soldiers**。
“可我们没有密钥啊！”
看官们稍安勿躁，凯撒密码的致命缺陷就来自英语本身，众所周知，26个字母，在一句**长文章中**每个字母都将**出现很多次**。出于玄学原因，西方人酷爱**字母E**，大量含有e的词汇、短语被造出来，使得**E在一篇长文字中出现的次数是最多的**（**说明/提示**里的表其实就是在告诉我们e出现的几率高达12.68%位列第一）。
因此，我们求出所给句子中**出现最多的字母**，这个字母就有**大概率对应明文中的E**！
“只知道E对应啥有啥用？？？”
我们在这里**把字母表想象为一个环**，把凯撒密码的密钥想象成两个同心环（均按照相同的方向排列，遵循字母表顺序，约定内环为明文表外环为密文表），假设我们知道**E在密文中是J**，那么我们转动外环，**使外环上的J和内环上的E对齐**，这时整个密钥表也就出来了，
**为了方便表示**，我们将**密文最多字母**与**E**的差**约定为t**，这个值代表我们的**外环转动的格数**（内外环事先按A对A的方式对齐）
## 程序流程
PS：本题有一点特坑（本人有一点特菜），我看见了“**Caesar会不时更换t的值**”就误以为每个begin和end之间的t是不一样的t......其他坑点见代码注释。
程序流程总结之后如下：
$$ \text{读入全部数据}$$
$$ ↓$$
$$ \text{统计各字母出现的次数}$$
$$ ↓$$
$$ \text{找出出现最多的}$$
$$ ↓$$
$$ \text{算出t}$$
$$ ↓$$
$$ \text{根据t完成解密}$$
## AC代码
```cpp
#include
using namespace std;
int t;
map ma;
//计算t（偏移值）
int calcT(string s)
{
long long maxv=-1,maxk=0;
//下面的玄乎操作不用太纠结，用一个大小为26+的数组效果一样
for(map::iterator iter=ma.begin(); iter!=ma.end(); iter++) {
//标准的找最大元素操作
if(iter->second>maxv) {
maxv=iter->second;
maxk=iter->first;
}
}
return maxk-'E';//t，t是怎么算的关系到解密
}
//解密
string enc(string s,int t)
{
for(int i=0; i='A'&&s[i]'Z') s[i]-=26;
if(s[i]>be;//读START
cin.clear();//没啥用，吧
if(be=="ENDOFINPUT") break;
/*
下两行是创世巨坑
我们前面cin>>be后，be里是不会有'\n'的，因此缓冲区还存着1个换行！！！
getline只会读到换行！！！
我们第一个getline只能读到空串！！！
我们必须getline两次！！！
*/
getline(cin,text);
getline(cin,text);
for(int i=0; i='a'&&text[i]en;//读END
}
t=calcT(text);//找出出现最多的字母
for(int i=0;i |