[NOIP2009-提高] 潜伏者

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

扫描样例对建立“原字母→密字”字典，同一原字母冲突或 26 字母不成双射即输出 Failed，否则用逆表逐字符翻译电报。

OJ: roj

题目 ID: 3572

难度:普及-

标签:字符串模拟python

创建: 2026-10-02 08:25

更新: 2026-10-06 14:14

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

SS 国用大写字母替换密码：每个字母对应唯一密字，不同字母密字不同，密字可与原字母相同。给出一对已掌握的等长加密串与原串（第 1、2 行，长度 11 到 100100）以及待破译电报（第 3 行），要求破译密码并翻译电报；若推断时出现矛盾，或 AA-ZZ 中有字母未在原串出现，输出 Failed，否则输出电报的原文。

样例 1：AA / AB / EOWIE → Failed；样例 2：QWERTYUIOPLKJHGFDSAZXCVBN / ABCDEFGHIJKLMNOPQRSTUVWXY / DSLIEWO → Failed；样例 3：MSRTZCJKPFLQYVAWBINXUEDGHOOILSMIJFRCOPPQCEUNYDUMPP / YIZSDWAHLNOVFUCERKJXQMGTBPPKOIYKANZWPLLVWMQJFGQYLL / FLSO → NOIP。

思路

按位扫描样例对，记录「原字母 → 密字」及逆表「密字 → 原字母」：同一原字母映射到不同密字、或不同原字母共用同一密字，都判 Failed；扫描后若 2626 个字母未全部出现也输出 Failed。否则密码表是双射，逆表对任意密字都有定义，逐字符翻译电报即可。

参考代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 08:25
# update_at: 2026-10-02 08:25

import sys


def solve() -> None:
    """从样例对推导 26 字母的替换置换并译出电报；规则冲突或字母缺失输出 Failed。"""
    cipher, plain, msg = sys.stdin.read().split()

    key: dict[str, str] = {}  # 原字母 -> 密字
    for x, y in zip(plain, cipher):
        conflict = key.setdefault(x, y) != y  # 同一个原字母却给出了两个不同密字
        if conflict:
            print('Failed')
            return

    # 情形 2/3：26 个原字母必须都出现，且密字两两不同（满射即双射）
    is_bijection = len(key) == len(set(key.values())) == 26
    if not is_bijection:
        print('Failed')
        return

    decode = {y: x for x, y in key.items()}  # 反向：密字 -> 原字母
    print(''.join(decode[y] for y in msg))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 14:14
 * update_at: 2026-10-06 14:14
 */
#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

string cipher_text; // 第 1 行：已掌握的加密信息
string plain_text;  // 第 2 行：加密信息对应的原信息
string telegram;    // 第 3 行：待破译的电报

int to_cipher[26]; // to_cipher[x] 表示原字母 x 的密字，-1 表示还没确定
int to_plain[26];  // to_plain[y] 表示密字 y 对应的原字母，破译时使用

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> cipher_text >> plain_text >> telegram;

    for (int i = 0; i < 26; i++) {
        to_cipher[i] = -1;
        to_plain[i] = -1;
    }

    ll len = plain_text.size();
    for (ll i = 0; i < len; i++) {
        int x = plain_text[i] - 'A';   // 原字母
        int y = cipher_text[i] - 'A';  // 对应的密字

        // 同一个原字母给出了两个不同密字，规则自相矛盾
        if (to_cipher[x] != -1 && to_cipher[x] != y) {
            cout << "Failed" << '\n';
            return 0;
        }
        // 两个不同原字母共用了同一个密字
        if (to_plain[y] != -1 && to_plain[y] != x) {
            cout << "Failed" << '\n';
            return 0;
        }

        to_cipher[x] = y;
        to_plain[y] = x;
    }

    // 26 个字母必须全部出现，密码表才是 26 个字母上的双射
    for (int i = 0; i < 26; i++) {
        if (to_cipher[i] == -1) {
            cout << "Failed" << '\n';
            return 0;
        }
    }

    // 双射成立时逆表对所有密字都有定义，逐字符翻译电报
    ll m = telegram.size();
    for (ll i = 0; i < m; i++) {
        int y = telegram[i] - 'A';
        char original = 'A' + to_plain[y]; // 由逆表得到原字母
        cout << original;
    }
    cout << '\n';

    return 0;
}