欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【NOIP2018 模拟赛day1】古代密码

程序员文章站 2024-03-19 11:47:10
...

【题目描述】

古罗马帝国有一个拥有各种部门的强大*组织。其中一个部门
就是保密服务部门。 为了保险起见, 在省与省之间传递的重要文件中
的大写字母是加密的。 当时最流行的加密方法是替换和重新排列。
替换方法是将所有出现的字符按照一个规则替换, 比如
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;
}
相关标签: 刷题之路