题解洛谷P1071【潜伏者】

Dear 丶 2023-08-17 17:33 75阅读 0赞

**题目链接：[https://www.luogu.org/problem/P1071][https_www.luogu.org_problem_P1071]**

题意概括：给你一段原来截获的英文密码和与之对应的明文，如果密码表非F♂A法，输出"Failed" ，否则翻译现在给你的一句密文并输出。（所有字母均为大写）

有两种情况视为密码表非法：

1、 所有信息扫描完毕，但发现有字母在原信息中没有出现（密码表脱漏）。

2、 扫描中发现掌握的信息里有明显的自相矛盾或错误（密码表错乱）。

这道题主要思想可以利用数组打表，首先我们定义一个数组code作为密码表

然后进行密码表制作，比如一个密文是“DDYAKIOI”，明文是“SSDPOLKL”（首先声明一点，这只是为了便于理解写的短样例，这个样例实际上已经非法了）

可见code\['D'\]（即code\[68\]）为'S'，code\['Y'\]为'D'，以此类推。

现有密文为"DOAI"，根据一对一原则，翻译出来就是"SKPL"。

下面详细解释一下两种非法情况：

一、密码表脱漏

很好理解，就是有的密文位没有相对应的明文字母。排除方法：因为本题常数较小，考虑使用直接扫描的方法判断

![1640301-20190911172901838-1089119432.png][]

二、密码表错乱

这种情况又分为两种小情况：一对多和多对一

一对多：一个密文位对应多个明文字母。排除方法：压入明文制表过程中判断，发现与当前占位被不同字母抢占则判定非法![1640301-20190911180109181-508899349.png][]

![1640301-20190911181030626-932617314.jpg][]

多对一：多个密文对应一个明文字母。排除方法：全表从头至尾扫描，发现与当前明文占位不同明文相同的则判定非法![1640301-20190911184326932-1592526297.jpg][]

![1640301-20190911190333969-1202374960.jpg][]

# （此图大雾） #

接下来是愉快的贴代码时间，**是好孩子的话就不要抄袭题解呢……（微笑）**

1 //Stand up for the faith!
     2 #include<bits/stdc++.h>
     3 using namespace std;
     4 #define ll long long
     5 
     6 char myst[400],word[400];
     7 char sent[400],code[400];
     8 //分别代表密文、明文、需译语句、密码表 
     9 signed main(void)
    10 {
    11     scanf("%s%s",myst,word);
    12     int len1=strlen(myst);
    13     int len2=strlen(word);
    14     for(int i=0;i<=400;i++) code[i]='\0'; //初始化密码表，方便判断脱漏 
    15     if(len1!=len2||len1<26) //初步判断 
    16     {
    17         puts("Failed");return 0;
    18     }
    19     /*此处明确几点：
    20     1、如果密文和明文长度不等，100%无法一一对应，视为非法 
    21     2、如果长度少于26，一定无法A-Z全部对应，直接非法 
    22     3、如果长度多于26，不一定非法（比如有两次等价对应）*/
    23     for(int i=0;i<len1;i++)
    24     {
    25         if(code[myst[i]]>='A'&&code[myst[i]]<='Z'&&code[myst[i]]!=word[i]) 
    26         //判断不同字母对应相同密字（此前已有其他不同的字母占位） 
    27         {
    28             puts("Failed");return 0;
    29         }
    30         for(int j='A';j<='Z';j++)
    31         {
    32             if(code[j]==word[i]&&j!=myst[i])
    33             //判断相同字母对应不同密字（在不同占位上含有相同的字母） 
    34             {
    35                 puts("Failed");return 0;
    36             }
    37         }
    38         code[myst[i]]=word[i];
    39     }
    40     for(int i='A';i<='Z';i++)
    41     {
    42         if(code[i]=='\0') //判断是否有字母没有出现 
    43         {
    44             puts("Failed");return 0;
    45         }
    46     }
    47     scanf("%s",sent);
    48     int len=strlen(sent);
    49     for(int i=0;i<len;i++)
    50     {
    51         cout<<code[sent[i]]; //逐个输出对应字母
    52     }
    53 }

## **作者：KGB1331** ##

## **2019-09-11 19:13:36** ##

转载于:https://www.cnblogs.com/KGB1331/p/11508161.html

[https_www.luogu.org_problem_P1071]: https://www.luogu.org/problem/P1071#submit
[1640301-20190911172901838-1089119432.png]: /images/20230808/ee7244e1c6ea465f90f7f53f9bb5f42d.png
[1640301-20190911180109181-508899349.png]: /images/20230808/b7903c6961bc407d9a7813cd1d7b78da.png
[1640301-20190911181030626-932617314.jpg]: /images/20230808/ee27d8e491e5483ebf60c3dbaa788d03.png
[1640301-20190911184326932-1592526297.jpg]: /images/20230808/ac8f413773c94a428d16ed283a0b4daa.png
[1640301-20190911190333969-1202374960.jpg]: /images/20230808/a7a1516b81854b86b7f755eaf3e91c13.png