P2636 密码破解者

    • 34通过
    • 153提交
  • 题目提供者 cy2017
  • 评测方式 云端评测
  • 标签 字符串 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    1941年12月7日凌晨,珍珠港驻守美军通信员截获了一份日军电报。早上8时日军的正式进攻就会展开,为了减少太平洋战场伤亡,你被指派去协助破解密文。情报部门已得知了密文加密的层数和每层加密的方法。由于时间紧急,你只剩1秒的时间来破解日军的密文。

    题目描述

    据情报得知日军共有3种加密方式:

    一、栅栏密码:

    所谓栅栏密码,就是把要加密的明文分成L个一组,然后把每组的第1个字连起来,形成一段无规律的话。一般比较常见的是2栏的棚栏密码。 

    比如明文:THERE IS A CIPHER  

    去掉空格后变为:THEREISACIPHER  

    两个一组,得到:TH ER EI SA CI PH ER  

    先取出第一个字母:TEESCPE  

    再取出第二个字母:HRIAIHR  

    连在一起就是:TEESCPEHRIAIHR  

    这样就得到我们需要的密码了。  

    但也可能有更多的栏数。

    注:若明文长度不能整除栏数,则分组后剩下的单独为一组,如:

    THERE IS A CIPHER 3栏加密分组为:THE REI SAC IPH ER

    先后取出第一二三个字母(最后一组只能取前两个),加密后为:

    TRSIE HEAPR EICH(去掉空格)。

    二、维吉尼亚(Vigenère)密码:

    维吉尼亚密码首先应用了“密钥”的思想,其在密码届具有十分重要的意义。

    在密码学中,我们称需要加密的信息为明文,用 M 表示;称加密后的信息为密文,用 C 表示;而密钥是一种参数,是将明文转换为密文或将密文转换为明文的算法中输入的数据,记为 k。 在 Vigenère 密码中,密钥 k 是一个字母串,k=k1k2…kn。当明文 M=m1m2…mn 时,得到的密文 C=c1c2…cn,其中 ci=mi®ki,运算®的规则如下表所示:

    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

    A -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

    B -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 A

    C -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

    D -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 C

    E -E F G H I J K L M N O P Q R S T U V W X Y Z A B C D

    F -F G H I J K L M N O P Q R S T U V W X Y Z A B C D E

    G -G H I J K L M N O P Q R S T U V W X Y Z A B C D E F

    H -H I J K L M N O P Q R S T U V W X Y Z A B C D E F G

    I -I J K L M N O P Q R S T U V W X Y Z A B C D E F G H

    J -J K L M N O P Q R S T U V W X Y Z A B C D E F G H I

    K -K L M N O P Q R S T U V W X Y Z A B C D E F G H I J

    L -L M N O P Q R S T U V W X Y Z A B C D E F G H I J K

    M -M N O P Q R S T U V W X Y Z A B C D E F G H I J K L

    N -N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

    O -O P Q R S T U V W X Y Z A B C D E F G H I J K L M N

    P -P Q R S T U V W X Y Z A B C D E F G H I J K L M N O

    Q -Q R S T U V W X Y Z A B C D E F G H I J K L M N O P

    R -R S T U V W X Y Z A B C D E F G H I J K L M N O P Q

    S -S T U V W X Y Z A B C D E F G H I J K L M N O P Q R

    T -T U V W X Y Z A B C D E F G H I J K L M N O P Q R S

    U -U V W X Y Z A B C D E F G H I J K L M N O P Q R S T

    V -V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

    W -W X Y Z A B C D E F G H I J K L M N O P Q R S T U V

    X -X Y Z A B C D E F G H I J K L M N O P Q R S T U V W

    Y -Y Z A B C D E F G H I J K L M N O P Q R S T U V W X

    Z -Z 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

    Vigenère 加密在操作时需要注意: 

    当明文 M 的长度大于密钥 k 的长度时,将密钥 k 重复使用。 

    例如,明文 M=Helloworld,密钥 k=abc 时,密文 C=Hfnlpyosnd。 

    三、QWE键盘码:

    随着键盘普及,也出现了相应的键盘码。

    这是一个常见的键盘,在左边字母区有三行字母分别为:

    QWERTYUIOP

    ASDFGHJKL

    ZXCVBNM

    从第一排第一列开始分别用Q替代A,W替代B……M替代Z以此类推。

    如 CODING 加密后即为 EGROFU.

    这对于现在来说算是简单的加密方法,但对于键盘不普及的二战时期却是一大难题。

    输入输出格式

    输入格式:

    输入第一行为一个正整数N 表示截获的密文共用了N重密码加密。

    第二行为一个字符串S表示加密后的密文。

    以下3-N+2行共N行每行开头一个正整数K(1<=K<=3)表示对应的加密方式。

    给出的加密方式按顺序给出,即给出的第I重加密为实际加密过程的第I重(1<=I<=N)。

    若K=1则表示用栅栏密码加密,之后一个正整数L表示加密所用栏数。

    若K=2则表示用维吉尼亚码加密,之后一个字符串T表示密钥。

    若K=3则表示用QWE键盘码加密。

    输出格式:

    共一行。一个字符串,表示破解N重加密后的明文。

    输入输出样例

    输入样例#1: 复制
    2
    YSLTRIQXSHTQTR
    1 2
    3
    输出样例#1: 复制
    FULLSPEEDAHEAD

    说明

    n<=1000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。