P1079 Vigenère 密码
题目描述
16 世纪法国外交家 Blaise de VigenèreBlaisedeVigene`re 设计了一种多表密码加密算法―― VigenèreVigene`re 密码。 VigenèreVigene`re 密码的加密解密算法简单易用,且破译难度比较高,曾在美国南北战争中为南军所广泛使用。在密码学中,我们称需要加密的信息为明文,用 M 表示;称加密后的信息为密文,用 C 表示;而密钥是一种参数,是将明文转换为密文或将
密文转换为明文的算法中输入的数据,记为 k 。 在 VigenèreVigene`re 密码中,密钥 k 是一个字母串, k=k1,k2,…,kn 。当明文 M=m1,m2,…,mn 时,得到的密文 C=C=c1,c2,…,cn ,其中 ci = mi ® ki ,运算®的规则如下表所示:
VigenèreVigene`re 加密在操作时需要注意:
-
®运算忽略参与运算的字母的大小写,并保持字母在明文 MM 中的大小写形式;
-
当明文 M 的长度大于密钥 k 的长度时,将密钥 k例如,明文 M=Helloworld ,密钥 k=abc 时,密文 C=Hfnlpyosnd 。
输入输出格式
输入格式:
共 2 行。
第一行为一个字符串,表示密钥 kk ,长度不超过 100 ,其中仅包含大小写字母。
第二行为一个字符串,表示经加密后的密文,长度不超过 1000 ,其中仅包含大小写字母。
输出格式:
一个字符串,表示输入密钥和密文所对应的明文。
输入输出样例
说明
【数据说明】
对于 100%的数据,输入的密钥的长度不超过 100100 ,输入的密文的长度不超过 10001000 ,且都仅包含英文字母。
NOIP 2012 提高组 第一天 第一题
解题分析:
题目中说不区分大小写,所以输入后我们可以将两字符串转为相同的大小写,这里全部转为小写。
注意:大小写转换函数 大写strupr() 小写strlwr() 不可用,需要手写。
然而输出时需要以密文的大小写判断输出的大小写,所以另开一个数组储存密文,以便于输出判断大小写。
然后,考虑题目图中的密码规律,以Z-Z为分界线,你会发现左上角每一个字符用不相同的两组 字符 表示,两组字符ASCII码相加相等,同样右下角也这样。
根据这个规律,我们可以预处理出每两个字符组表示的字符(下边贴有代码)。
然后有了密文,有了密钥,我们又已经处理出来来了表示的字符,相反的推理回去,得出明文(注意大小写判断)
预处理部分:
最小相加为 a+a=194,最大z+z=244.
第一行处理左上角,第二行处理右下角。
for(int i=194;i<=219;i++)ans[i]=char(i-'a'); for(int i=220;i<=244;i++)ans[i]=ans[i-26];
AC代码
#include <iostream> #include <cstring> #include <cstdio> #include <queue> using namespace std; #define N int(100+2) #define M int(1000+2) char a[M],b[M],c[M],ans[250]; int main() { scanf("%s",a+1);int la=strlen(a+1); scanf("%s",b+1);int lb=strlen(b+1); for(int i=1;i<=lb;i++)c[i]=b[i]; for(int i=1;i<=la;i++)if(a[i]<='Z'&&a[i]>='A')a[i]+=32; for(int i=1;i<=lb;i++)if(b[i]<='Z'&&b[i]>='A')b[i]+=32; if(la<lb) { for(int i=la+1;i<=lb;i++)a[i]=a[i-la]; //要密钥和密文一样长度,注意数组大小。 } for(int i=194;i<=219;i++)ans[i]=char(i-'a'); //预处理部分。 for(int i=220;i<=244;i++)ans[i]=ans[i-26]; for(int i=1;i<=lb;i++) { for(int j=194;j<=244;j++) { if(b[i]==ans[j]&&j-a[i]<='z'&&j-a[i]>='a') { if(c[i]<='Z'&&c[i]>='A')printf("%c",j-a[i]-32); else printf("%c",j-a[i]); } } } }