华师一附中OI组

标题: P1071 潜伏者 [打印本页]

---

作者: admin    时间: 2018-6-29 16:38
标题: P1071 潜伏者
https://www.luogu.org/problemnew/show/P1071

题目描述
R 国和 S 国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。历尽艰险后，潜伏于 S  国的 R 国间谍小 C  终于摸清了 S国军用密码的编码规则：

1． S 国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容与加密后所得的内容均由大写字母‘ A ’-‘ Z ’构成（无空格等其他字符）。

2． S 国对于每个字母规定了对应的“密字”。加密的过程就是将原信息中的所有字母替换为其对应的“密字”。

3． 每个字母只对应一个唯一的“密字”，不同的字母对应不同的“密字”。“密字”可以和原字母相同。

例如，若规定‘ A’的密字为‘ A ’，‘ B ’的密字为‘ C ’（其他字母及密字略），则原信息“ ABA ”被加密为“ ACA ”。

现在，小 C通过内线掌握了 S 国网络上发送的一条加密信息及其对应的原信息。小 C 希望能通过这条信息，破译 S 国的军用密码。小 C 的破译过程是这样的：扫描原信息，对于原信息中的字母 x （代表任一大写字母），找到其在加密信息中的对应大写字母 y ，并认为在密码里 y 是 x 的密字。如此进行下去直到停止于如下的某个状态：

1． 所有信息扫描完毕，‘ A’-‘ Z’ 所有 26 个字母在原信息中均出现过并获得了相应的“密字”。

2． 所有信息扫描完毕，但发现存在某个（或某些）字母在原信息中没有出现。

3． 扫描中发现掌握的信息里有明显的自相矛盾或错误（违反 S 国密码的编码规则）。例

如某条信息“ XYZ ”被翻译为“ ABA ”就违反了“不同字母对应不同密字”的规则。

在小 C 忙得头昏脑涨之际， R 国司令部又发来电报，要求他翻译另外一条从 S 国刚刚截取到的加密信息。现在请你帮助小 C：通过内线掌握的信息，尝试破译密码。然后利用破译的密码，翻译电报中的加密信息。

输入输出格式
输入格式：
共  3 行，每行为一个长度在 1 到 100 之间的字符串。

第 1 行为小 C 掌握的一条加密信息。
第 2 行为第 1 行的加密信息所对应的原信息。
第 3 行为 R 国司令部要求小 C 翻译的加密信息。

输入数据保证所有字符串仅由大写字母‘ A ’-‘ Z ’构成，且第 1 行长度与第 2 行相等。

输出格式：
共 1 行。

若破译密码停止时出现 2,3 两种情况，请你输出“ Failed ”（不含引号，注意首字母大写，其它小写）。
否则请输出利用密码翻译电报中加密信息后得到的原信息。

输入输出样例
输入样例#1：
AA
AB
EOWIE

输出样例#1：
Failed

输入样例#2：
QWERTYUIOPLKJHGFDSAZXCVBN
ABCDEFGHIJKLMNOPQRSTUVWXY
DSLIEWO
输出样例#2：
Failed

输入样例#3：
MSRTZCJKPFLQYVAWBINXUEDGHOOILSMIJFRCOPPQCEUNYDUMPP
YIZSDWAHLNOVFUCERKJXQMGTBPPKOIYKANZWPLLVWMQJFGQYLL
FLSO
输出样例#3：
NOIP

NOIP 2009 提高组 第一题

---

作者: GTR    时间: 2018-7-25 22:00

1. #include<iostream>
   
2. #include<string>
   
3. using namespace std;
   
4. string ori, match, translate;
   
5. char oric[26], matchc[26];
   
6. int size = 0;
   
7. int isInori(char a);
   
8. bool isInmat(char a);
   
9. int isInori(char a)
   
10. {
    
11.     for(int i=0; i<size; i++)
    
12.     {
    
13.         if(oric[i]==a) return i;
    
14.     }
    
15.     return -1;
    
16. }
    
17. bool isInmat(char a)
    
18. {
    
19.     for(int i=0; i<size; i++)
    
20.     {
    
21.         if(matchc[i]==a) return true;
    
22.     }
    
23.     return false;
    
24. }
    
25. int main()
    
26. {
    
27.     getline(cin, ori);
    
28.     getline(cin, match);
    
29.     int sizeo = ori.length();
    
30.     int sizem = match.length();
    
31.     int tag = 0;
    
32.     if(sizeo!=sizem) cout<<"Failed";
    
33.     else if(sizeo<26) cout<<"Failed";
    
34.     else
    
35.     {
    
36.         for(int i=0; i<sizeo; i++)
    
37.         {
    
38.             if((int)ori[i]>64 && (int)ori[i]<91 && (int)match[i]>64 && (int)match[i]<91)   
    
39.             {
    
40.                 if(isInmat(match[i])) continue;
    
41.                 else
    
42.                 {
    
43.                     matchc[size] = match[i];
    
44.                     if(isInori(ori[i])!=-1) tag = 1;  
    
45.                     oric[size] = ori[i];
    
46.                     size++;
    
47.                 }
    
48.             }
    
49.         }
    
50.         if(size!=26 || tag==1) cout<<"Failed";
    
51.                 else
    
52.         {
    
53.             getline(cin, translate);
    
54.             int t = translate.length();
    
55.             for(int i=0; i<t; i++)
    
56.             {
    
57.                 if(isInori(translate[i])!=-1) cout<<matchc[isInori(translate[i])];   
    
58.             }
    
59.         }
    
60.     }
    
61.     return 0;
    
62. }

复制代码

---

作者: admin    时间: 2018-7-27 19:57
此题是训练初学者循环，数组和字符串的好题，涉及到跳转标处理对应关系，数组统计次数，冲突处理等几个方面。
我们分步来做此题：
1、对应关系处理：读的两串字符时候 ，用字符数组tzb记录变化之后的密码，比如tzb0就是A变化后的密码 tzb25就是Z变化后的密码，这个简单
tzb【si-‘A’】=ti就行！
2、统计A-Z26个字母是否都出现过，可以使用时数组app表示，app0==1表示A出现过，app25==0表示Z 没有出现过，然后统计app里面所有数字的和是不是26就可以。
3、冲突处理，一个对应着两个的问题，每次找对应关系的时候，检查下以前是否曾经找过，要是出现过，就比较一下，两次的不同则停止并输出failed
4、通过检测之后的话把第三个串直接进行对应输出，即输出tzb【ssi-‘A’】

---

作者: admin    时间: 2018-7-27 20:17

1. #include<iostream>
   
2. using namespace std;
   
3. string s,t,ss;  ///输入的三个串
   
4. char  tzb[26];  ///密码对应关系
   
5. int app[26];///每个字符是否出现
   
6. int i,j,k,l,x;
   
7. bool b;
   
8. int main()
   
9. {
   
10.     cin>>s>>t>>ss;
    
11.     l=s.size();
    
12.     b=1;
    
13.     for (i=0; i<=l-1; i++)
    
14.     {
    
15.         x=s[i]-'A';///字符序号
    
16.         if (app[x]==0)  ///以前没有出现过
    
17.         {
    
18.             app[x]=1;///标记出现过
    
19.             tzb[x]=t[i];///tzb记录
    
20.         }
    
21.         else if (tzb[x]!=t[i]) {b=0;break;}
    
22.     }
    
23.     for (k=i=0; i<=25; i++) k=k+app[i]; ///统计出现的字母数
    
24.     ///cout<<k;
    
25.     ///for (i=0; i<=25; i++) cout<<app[i];
    
26.     if (k!=26) b=0;
    
27.     if (!b) cout<<"Failed";
    
28.     else
    
29.         for (i=0; i<=ss.size()-1; i++)
    
30.         {
    
31.             x=ss[i]-'A';
    
32.             cout<<tzb[x];
    
33.         }
    
34.     return 0;
    
35. }
    

复制代码

---

作者: 吴语林    时间: 2018-7-29 23:54

1. #include <cstdio>
   
2. #include <algorithm>
   
3. #include <iostream>
   
4. #include <cmath>
   
5. #include <cstring>
   
6. #include <set>
   
7. using namespace std;
   
8. int main() {
   
9.         char a[100],b[100],c[100],d[27]={0};
   
10.         int i=0,e=1,j;
    
11.         scanf("%s\n%s\n%s",a,b,c);
    
12.         int n=strlen(a)-1;
    
13.         int m=strlen(c)-1;
    
14.         for(i=0;i<=n;i++)
    
15.         {
    
16.                 if(d[a[i]-64]==0||d[a[i]-64]==b[i])
    
17.                 d[a[i]-64]=b[i];
    
18.                 else
    
19.                 e=0;
    
20.         }
    
21.         if(e!=0)
    
22.         for(i=1;i<=26;i++)
    
23.         {
    
24.                 if(d[i]==0)
    
25.                 {
    
26.                         e=0;
    
27.                         break;
    
28.                 }
    
29.                 else
    
30.                 {
    
31.                         for(j=i+1;j<=26;j++)
    
32.                         {
    
33.                                 if(d[i]==d[j])
    
34.                                 {
    
35.                                         e=0;
    
36.                                         break;
    
37.                                 }
    
38.                                 if(e==0)
    
39.                                 break;
    
40.                         }
    
41.                 }
    
42.         }
    
43.         if(e!=0)
    
44.         for(i=0;i<=m;i++)
    
45.         {
    
46.                 if(d[c[i]-64]!=0)
    
47.                 c[i]=d[c[i]-64];
    
48.                 else
    
49.                 e=0;
    
50.         }
    
51.         if(e==0)
    
52.         {
    
53.                 printf("Failed");
    
54.         }
    
55.         if(e!=0)
    
56.         {
    
57.                 for(i=0;i<=m;i++)
    
58.         {
    
59.                 printf("%c",c[i]);
    
60.         }
    
61.         }
    
62.         return 0;
    
63. }

复制代码

---

作者: walk_alone    时间: 2018-8-1 19:59

1. #include <cstdio>
   
2. #include <cstring>
   
3. using namespace std;
   
4. int f[31],g[31];
   
5. int main()
   
6. {
   
7.         char a[101],b[101],c[101];
   
8.         scanf("%s\n%s\n%s",a,b,c);
   
9.         int len=strlen(a);
   
10.         int length=strlen(c);
    
11.         for(int i=0;i<len;i++)
    
12.         {
    
13.                 if(f[a[i]-64]==0 && g[b[i]-64]==0)
    
14.                 {
    
15.                         f[a[i]-64]=b[i]-64;
    
16.                         g[b[i]-64]=a[i]-64;
    
17.                 }
    
18.                 if((f[a[i]-64]!=0 && f[a[i]-64]!=b[i]-64) || (g[b[i]-64]!=0 && g[b[i]-64]!=a[i]-64))
    
19.                 {
    
20.                         printf("Failed");
    
21.                         return 0;
    
22.                 }
    
23.         }
    
24.         for(int i=1;i<=26;i++)
    
25.                 if(f[i]==0)
    
26.                 {
    
27.                         printf("Failed");
    
28.                         return 0;
    
29.                 }
    
30.         for(int i=0;i<length;i++)
    
31.                 printf("%c",f[c[i]-64]+64);
    
32.         return 0;
    
33. }

复制代码

---

作者: 黄煦喆    时间: 2018-8-1 22:39

1. #include<iostream>
   
2. #include<map>
   
3. using namespace std;
   
4. string m,c,ss;
   
5. map<char,char>mp1,mp2;
   
6. int main()
   
7. {
   
8.     cin>>m>>c>>ss;
   
9.     int len=m.size();
   
10.     for(int i=0; i<len; i++)
    
11.     {
    
12.         if(mp1[m[i]]==c[i]&&mp2[c[i]]==m[i])continue;
    
13.         if((mp1[m[i]]!=c[i]&&mp1[m[i]]>='A'&&mp1[m[i]]<='Z')||
    
14.                 (mp2[c[i]]!=m[i]&&mp2[c[i]]>='A'&&mp2[c[i]]<='Z'))
    
15.         {
    
16.             cout<<"Failed";
    
17.             return 0;
    
18.         }
    
19.         mp1[m[i]]=c[i];
    
20.         mp2[c[i]]=m[i];
    
21.     }
    
22.     for(char i='A'; i<='Z'; i++)
    
23.         if(mp1[i]<'A'||mp1[i]>'Z')
    
24.         {
    
25.             cout<<"Failed";
    
26.             return 0;
    
27.         }
    
28.     for(int i=0; i<ss.size(); i++)cout<<mp1[ss[i]];
    
29.     return 0;
    
30. }
    

复制代码

---

作者: admin    时间: 2018-8-1 23:48
你们的都对了吗我怎么错了一组？

---

作者: zhwang    时间: 2018-8-2 09:20

1. #include<cstdio>
   
2. #include<cstring>
   
3. struct node
   
4. {
   
5.     char Fault;
   
6.     char True;
   
7. }letter[151];
   
8. char f[151];
   
9. char t[151];
   
10. char waaa[151];
    
11. int lent;
    
12. int lenf;
    
13. int lenwaaa;
    
14. int biao;
    
15. int yy;
    
16. char a[27]={'0','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'};
    
17. int main()
    
18. {
    
19.     scanf("%s",f);
    
20.     scanf("%s",t);
    
21.     scanf("%s",waaa);
    
22.     lenf=strlen(f);
    
23.     lent=strlen(t);
    
24.     lenwaaa=strlen(waaa);
    
25.     if(lenf<26)
    
26.     {
    
27.         printf("Failed");
    
28.         return 0;
    
29.     }
    
30.     for(int i=0;i<=lenf-1;i++)
    
31.     {
    
32.         letter[i+1].Fault=f[i];
    
33.         letter[i+1].True=t[i];
    
34.     }
    
35.     for(int i=0;i<=lenf-1;i++)
    
36.     {
    
37.         for(int j=0;j<i;j++)
    
38.         {
    
39.             if((f[i]==f[j]&&t[i]!=t[j])||(f[i]!=f[j]&&t[i]==t[j]))
    
40.             {
    
41.                 printf("Failed");
    
42.                 return 0;
    
43.             }
    
44.         }
    
45.     }
    
46.     for(int i=0;i<=lenf-1;i++)
    
47.     {
    
48.         biao=1;
    
49.         for(int j=0;j<i;j++)
    
50.         {
    
51.             if(f[i]==f[j])
    
52.             {
    
53.                 biao=0;
    
54.             }
    
55.         }
    
56.         if(biao==1)
    
57.         {
    
58.             yy++;
    
59.         }
    
60.     }
    
61.     if(yy<26)
    
62.     {
    
63.         printf("Failed");
    
64.         return 0;
    
65.     }
    
66.     for(int i=0;i<=lenwaaa-1;i++)
    
67.     {
    
68.         for(int j=1;j<=lenf;j++)
    
69.         {
    
70.             if(letter[j].Fault==waaa[i])
    
71.             {
    
72.                 printf("%c",letter[j].True);
    
73.                 break;
    
74.             }
    
75.         }
    
76.     }
    
77.     return 0;
    
78. }

复制代码

---

作者: 七夜劫年    时间: 2018-8-2 11:53
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
map<char,char>d;
map<char,char>p;
char t;
string a,b,c;
int u=0;

int main()
{
        //freopen("s.in","r",stdin);
        //freopen("s.out","w",stdout);
       
        cin>>a>>b>>c;
       
        t='A';
       
        while( t <= 'Z' )
        {
                d[t]='0';
                p[t]='0';
                t++;
        }
       
        for(int i=0;i<=a.size()-1;i++)
        {
                if( d[a[i]] == '0' )
                {
                        d[a[i]]=b[i];
                }
                else if( d[a[i]] != '0' && d[a[i]] != b[i] )
                {
                        u=1;
                        break;
                }
        }
       
        for(int i=0;i<=a.size()-1;i++)
        {
                if( p[b[i]] == '0' )
                {
                        p[b[i]]=a[i];
                }
                else if( p[b[i]] != '0' && p[b[i]] != a[i] )
                {
                        u=1;
                        break;
                }
        }
       
        t='A';
        while( t <= 'Z' )
        {
                if( d[t] == '0' )
                {
                        u=1;
                        break;
                }
                t++;
        }
       
       
        if( u == 1 )
        {
                cout<<"Failed"<<endl;
        }
        else if( u == 0 )
        {
                for(int i=0;i<=c.size()-1;i++)
                {
                        cout<<d[c[i]];
                }
        }
          
        return 0;
}

---

作者: universehyf    时间: 2018-10-25 21:26

1. <div class="blockcode"><blockquote>#include<iostream>
   
2. #include<cstdio>
   
3. #include<algorithm>
   
4. #include<string>
   
5. using namespace std;
   
6. #define FOR(i,a,b) for(int i=a;i<=b;i++)
   
7. string a,b,c;
   
8. int l,ll,s[26],tt,t;
   
9. int main()
   
10. {
    
11.     cin>>a>>b>>c;
    
12.     l=a.size();ll=c.size();
    
13.     FOR(i,0,25) s[i]=-1;
    
14.     FOR(i,0,l-1)
    
15.     {
    
16.         t=a[i]-'A';
    
17.         tt=b[i]-'A';
    
18.         if(s[t]!=-1&&s[t]!=tt) {cout<<"Failed";return 0;}
    
19.         FOR(j,0,25) if(t!=j&&s[j]==tt) {cout<<"Failed";return 0;}
    
20.         s[t]=tt;
    
21.     }
    
22.     FOR(i,0,25) if(s[i]==-1) {cout<<"Failed";return 0;}
    
23.     FOR(i,0,ll-1) cout<<char('A'+s[c[i]-'A']);
    
24.     return 0;
    
25. }

复制代码

---

作者: universehyf    时间: 2018-10-25 21:27

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<algorithm>
   
4. #include<string>
   
5. using namespace std;
   
6. #define FOR(i,a,b) for(int i=a;i<=b;i++)
   
7. string a,b,c;
   
8. int l,ll,s[26],tt,t;
   
9. int main()
   
10. {
    
11.     cin>>a>>b>>c;
    
12.     l=a.size();ll=c.size();
    
13.     FOR(i,0,25) s[i]=-1;
    
14.     FOR(i,0,l-1)
    
15.     {
    
16.         t=a[i]-'A';
    
17.         tt=b[i]-'A';
    
18.         if(s[t]!=-1&&s[t]!=tt) {cout<<"Failed";return 0;}
    
19.         FOR(j,0,25) if(t!=j&&s[j]==tt) {cout<<"Failed";return 0;}
    
20.         s[t]=tt;
    
21.     }
    
22.     FOR(i,0,25) if(s[i]==-1) {cout<<"Failed";return 0;}
    
23.     FOR(i,0,ll-1) cout<<char('A'+s[c[i]-'A']);
    
24.     return 0;
    
25. }

复制代码

---

作者: admin    时间: 2019-3-20 10:48
楼上的同学  做的很好！

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2