i:   0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
明文: 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
密文: C  S  P  A  B  D  E  F  G  H  I  J  K  L  M  N  O  Q  R  T  U  V  W  X  Y  Z
解密：D  E  A  F  G  H  I  J  K  L  M  N  O  P  Q  C  R  S  B  T  U  V  W  X  Y  Z

（也就是：A→C, B→S, C→P, D→A, E→B, F→D, …, O→M, P→N, Q→O, R→Q, S→R, T→T, …, Z→Z）

3) 读入字符串并“解码”

cin >> st; 读入全大写字符串（假设只有 A–Z）。
对每个字符 st[i]：用 decoder[st[i]-'A'] 还原成明文。
输出解码后的明文。

4) 小例子

若输入：CSP
解码过程：C→A, S→B, P→C，输出：ABC。
若输入：ABCD
解码：A→D, B→E, C→F, D→G，输出：DEFG。

5) 正确性与边界

encoder 最终包含 26 个互不重复的字母 ⇒ 双射，因此一定可逆。
时间复杂度：构表部分 O(26×26) 常数级；解码 O(|st|)。
需要注意：输入必须是大写 A–Z。若有小写或非字母字符，decoder[st[i]-'A'] 会越界/错误。实际使用应加判断或统一转大写。

6) 一句话总结

用关键字 CSP 构造一个“关键字字母表”（先放 C、S、P，再按字母表补齐剩余字母），然后用其逆映射把输入的密文转换回明文。

#include <cstdlib>   // 这里其实没用到，可以去掉
#include <iostream>
using namespace std;

// 定义编码表（明文 → 密文），初始关键字是 C S P
// 其余位置先填 0，后续再补齐
char encoder[26] = {'C','S','P',0};

// 定义解码表（密文 → 明文）
char decoder[26];

// 输入字符串
string st;

int main() {
    int k = 0;  // 记录当前 encoder 已经填了多少个字母

    // 统计 encoder[0..25] 中非零的个数
    // 初始时就是 3（CSP）
    for (int i = 0; i < 26; i++) 
        if (encoder[i] != 0) ++k;

    // 从 'A' 到 'Z' 遍历所有字母
    for (char x = 'A'; x <= 'Z'; ++x) {
        bool flag = true;  // 假设 x 没有出现过
        // 检查 x 是否已经在 encoder 中
        for (int i = 0; i < 26; ++i)
            if (encoder[i] == x) {
                flag = false; // 找到了，说明已经用过
                break;
            }
        // 如果没出现过，就把它加入 encoder
        if (flag) {
            encoder[k] = x;
            ++k;
        }
    }

    // 构造 decoder 表（密文 → 明文）
    // encoder[i] 表示 "明文 'A'+i" 映射到的密文字母
    // 所以 decoder[encoder[i]-'A'] = i+'A'
    // 就是“密文字符”映射回“明文字符”
    for (int i = 0; i < 26; ++i)
        decoder[ encoder[i] - 'A' ] = i + 'A';

    // 输入一个大写字母串（密文）
    cin >> st;

    // 解码过程：把每个密文字母替换成对应的明文
    for (int i = 0; i < st.length(); ++i)
        st[i] = decoder[ st[i] - 'A' ];

    // 输出解码后的明文
    cout << st << endl;

    return 0;
}

Previous Lesson

Back to Lesson

Next Topic

信息学奥赛历年真题

代码解析：阅读程序-1

1) 构造替换表 encoder

2) 构造反查表 decoder

3) 读入字符串并“解码”

4) 小例子

5) 正确性与边界

6) 一句话总结

1) 构造替换表 `encoder`

2) 构造反查表 `decoder`