【NOIP2018 模拟赛day1】古代密码
【题目描述】
古罗马帝国有一个拥有各种部门的强大*组织。其中一个部门
就是保密服务部门。 为了保险起见, 在省与省之间传递的重要文件中
的大写字母是加密的。 当时最流行的加密方法是替换和重新排列。
替换方法是将所有出现的字符按照一个规则替换, 比如
ABCDEFGHIJKLMNOPQRSTUVWXYZ 到 BCDEFGHIJKLMNOPQRSTUVWXYZA, 如
果原词是 “VICTORIOUS” 则它变成 “WJDUPSJPVT”。
排列方法改变原来单词中字母的顺序。 例如: 将顺序<2, 1, 5, 4,
3, 7, 6, 10, 9, 8>应用到 “VICTORIOUS” 上, 则得到”IVOTCIRSUO”。
人们很快意识到单独应用替换方法或排列方法加密, 都是很不保
险的。 但是如果结合这两种方法, 在当时就可以得到非常可靠的加密
方法。 所以, 很多重要信息先使用替换方法加密, 再将加密的结果用
排列的方法加密。 用两种方法结合就可以将”VICTORIOUS” 加密成
“JWPUDJSTVP”。
考古学家最近在一个石台上发现了一些信息。 初看起来它们毫无
意义, 所以有人设想它们可能是用替换和排列的方法被加密了。 人们
试着解读了石台上的密码, 现在他们想检查解读的是否正确。 他们需
要一个计算机程序来验证, 你的任务就是写这个验证程序。
- 【输入描述】
输入有两行。 第一行是石台上的文字。 文字中没有空格, 并且只
有大写英文字母。 第二行是被解读出来的加密前的文字。 第二行也是由大写英文字母构成的。
两行字符数目的长度都不超过 100。 - 【输出描述】
如果第二行经过某种加密方法后可以产生第一行的信息, 输出
“YES”, 否则输出”NO”。 - 【样例】
JWPUDJSTVP
VICTORIOUS
YES - 【数据范围】
对于 30%的数据: 字符串长度<=10
对于 50%的数据: 字符串长度<=50
对于 100%的数据: 字符串长度<=100
题解
–题目中,原文的加密方法既要交换字母,又要随机排序,其实就与顺序无关了,反而简化了问题:只需要判断明文与密文各个字母的出现次数就行了。
–如果密码要可以成功匹配,显然明文与密码中所有各自要交替的字母的出现次数要相同,所以在保存下每个字母的出现次数后,用sort排序,在比对两个数组是否相同就行了。
–不过神奇的事情是,第一次是我还加了一个特判,然后WA了,可能是想多了吧……
代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=105;
string s1,s2;
int l1,l2;
int a1[MAXN],a2[MAXN];
bool comp(const int &a,const int &b){
return a>b;
}
bool solve(){
for(int i=1;i<=27;i++)
if(a1[i]!=a2[i])
return 0;
return 1;
}
int main(){
// freopen("cryptogram.in","r",stdin);
// freopen("cryptogram.out","w",stdout);
cin>>s1>>s2;
l1=s1.length();
l2=s2.length();
for(int i=0;i<l1;i++){
int b=s1[i]-'A'+1;
a1[b]++;
}
for(int i=0;i<l2;i++){
int b=s2[i]-'A'+1;
a2[b]++;
}
sort(a1+1,a1+27,comp);
sort(a2+1,a2+27,comp);
if(!solve())
cout<<"NO";
else
cout<<"YES";
return 0;
}
推荐阅读
-
【NOIP2018 模拟赛day1】古代密码
-
【NOIP2018模拟赛2018.8.28】plutotree
-
【NOIP2018模拟赛2018.8.28】video
-
【NOIP2018模拟赛2018.8.28】 chance
-
CSP模拟赛20191111 密码(数位DP)
-
2020 CCPC Wannafly Winter Camp Day1 B 密码学( 模拟)
-
NOIP 2018模拟赛(数学 打表) 2018 11 3 B组 Day1 T1
-
NOIP模拟赛20191111 T3 密码【库默尔定理,DP计数】
-
备战Noip2018模拟赛11(B组)T2 Gcd 最大公约数
-
NOIP 2018模拟赛() 2018 11 3 Day1 T1