潜伏者

GitHub跳转原题关系图返回列表

同时维护密文到明文和明文到密文映射，验证完整双射后翻译电报。

OJ: noi_openjudge

题目 ID: ch0107-11

难度:普及-

标签:字符串映射模拟python

日期: 2026-07-30 23:01

目录

  1. 题意
  2. 思路
  3. 代码
  4. Python代码
  5. C++代码
    1. 复杂度
    2. 总结

题意

已知一条密文及其原文，恢复代换密码并翻译新密文；映射必须是一一对应且覆盖全部 2626 个大写字母。

思路

cipher_to_plain 记录密字对应的原字，plain_to_cipher 记录反向关系。扫描已知对应时，两张表都不能和已有记录冲突。最后检查密文字母是否恰有 2626 个，才能翻译新信息。

代码

Python代码

python
ciphertext = input().strip()
plaintext = input().strip()
message = input().strip()

cipher_to_plain = {}
plain_to_cipher = {}
is_valid = True

for cipher, plain in zip(ciphertext, plaintext):
    if cipher_to_plain.get(cipher, plain) != plain or plain_to_cipher.get(plain, cipher) != cipher:
        is_valid = False
        break
    cipher_to_plain[cipher] = plain
    plain_to_cipher[plain] = cipher

if not is_valid or len(cipher_to_plain) != 26:
    print("Failed")
else:
    print("".join(cipher_to_plain[character] for character in message))

C++代码

cpp
/* 
 *  AC
 *  BB
 *
 * */
#include <cstdio>
#include <cstring>

char str1[500];
char str2[500];
char str3[500];
int _map[500] = {0};
int _map2[500] = {0};

int main(){
    scanf("%s",str1+1);
    scanf("%s",str2+1);
    scanf("%s",str3+1);
    int len = strlen(str1+1);
    int i,j;
    for (i=1;i<=len;i++){
        char c = str1[i];
        char d = str2[i];
        if(_map[c] == 0 && _map2[d] == 0 ){
            _map[c] = d;
            _map2[d] = c;
        }
        else if(_map[c] != 0 && _map[c] != d){
            printf("Failed");
            return 0;
        }
        else if( _map2[d] != 0 && _map2[d] != c){
            printf("Failed");
            return 0;
        }
    }
    for (i='A';i<='Z';i++){
        if( _map[i] == 0){
            printf("Failed");
            return 0;
        }
    }
    len = strlen(str3+1);
    for (i=1;i<=len;i++){
        printf("%c",_map[ str3[i]]);
    }
    return 0;

}

复杂度

设三行字符串总长度为 nn，时间复杂度为 O(n)O(n)，映射空间为 O(26)O(26)。

总结

一一映射校验应同时检查正向和反向，才能发现两个原字共用一个密字。