B4555 [GESP202606 三级] 加密

题目描述

小杨同学有一串数字，想把它们变成另一串数字，这个过程叫做加密。

他有一本密码本，密码本告诉你：每个数字应该变成哪个数字。

数字一共有 $10$ 个：$0$、$1$、$2$、$3$、$4$、$5$、$6$、$7$、$8$、$9$。

密码本会依次告诉你：

• $0$ 要变成什么
• $1$ 要变成什么
• $2$ 要变成什么
• ……
• $9$ 要变成什么

请你按照密码本，把原来的每个数字都换成新的数字，然后输出。

输入格式

输入共有 $3$ 行。

第一行：一个整数，表示有多少个数字需要加密；

第二行：这些需要加密的数字；

第三行：密码本，一共 $10$ 个数字。

这 $10$ 个数字的意思是：

• 第 $1$ 个数字：表示 $0$ 加密后变成什么；
• 第 $2$ 个数字：表示 $1$ 加密后变成什么；
• 第 $3$ 个数字：表示 $2$ 加密后变成什么；
• ……
• 第 $10$ 个数字：表示 $9$ 加密后变成什么。

输出格式

输出加密后的数字。

也就是：把输入第二行里的每个数字，都按照输入第三行的密码本换掉后输出。

输入输出样例 #1

输入 #1

7
0 2 0 3 4 1 9
9 0 1 2 3 4 5 6 7 8

输出 #1

9 1 9 2 3 0 8

说明/提示

第二行要加密的数字是：
$$0203419$$

第三行密码本是：
$$9012345678$$

它的意思是：

• $0$ 变成 $9$
• $1$ 变成 $0$
• $2$ 变成 $1$
• $3$ 变成 $2$
• $4$ 变成 $3$
• $5$ 变成 $4$
• $6$ 变成 $5$
• $7$ 变成 $6$
• $8$ 变成 $7$
• $9$ 变成 $8$

所以：

• $0$ 变成 $9$
• $2$ 变成 $1$
• $0$ 变成 $9$
• $3$ 变成 $2$
• $4$ 变成 $3$
• $1$ 变成 $0$
• $9$ 变成 $8$

最后得到：
$$9192308$$

数据范围

需要加密的数字个数不超过 $20000$ 个，且均为 $0$ 到 $9$；密码本中的数字不重复，且均为 $0$ 到 $9$。

题解

这道题是简单的映射替换问题。我只需要读入待加密的数字序列和密码本，然后按照密码本中规定的映射关系，将每个原数字替换成对应的新数字即可。

解题步骤非常直接：

1. 读入需要加密的数字个数 n。
2. 读入这 n 个数字，存入数组 b（下标从 1 开始方便对应位置）。
3. 读入密码本，共 10 个数字，存入数组 a，其中 a[i] 表示数字 i 加密后变成的数字（因为密码本第 1 个对应 0，第 2 个对应 1，……，第 10 个对应 9，所以直接按顺序读入到 a[0] 到 a[9] 即可）。
4. 遍历每个待加密数字 b[i]，输出 a[b[i]]（即用原数字作为下标去密码本中查找替换结果），数字之间用空格隔开。

时间复杂度为 O(n)，n 最大 20000，完全可行；空间复杂度为 O(n + 10)，非常小。

注意事项：

• 密码本中的数字不重复，且均为 0~9，因此无需额外校验。
• 输出格式要求每个加密后的数字之间用空格分隔，末尾可以有一个空格（不影响评测，但规范起见保留）。

---

带注释的源代码

#include <bits/stdc++.h>
using namespace std;

int n;                  // 需要加密的数字个数
int a[10];              // 密码本，a[i] 表示数字 i 加密后变成的数字
int b[20005];           // 存储待加密的原始数字序列

int main() {
    cin >> n;           // 读入数字个数

    // 读入待加密的数字序列
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }

    // 读入密码本，共 10 个数字，依次对应 0~9 的加密结果
    for (int i = 0; i < 10; i++) {
        cin >> a[i];
    }

    // 依次对每个原始数字进行加密，并输出结果
    for (int i = 1; i <= n; i++) {
        // 原数字 b[i] 加密后为 a[b[i]]，输出并用空格分隔
        cout << a[b[i]] << " ";
    }

    return 0;
}