【题目来源】

洛谷：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$ 加密后变成什么。

【输出】

输出加密后的数字。

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

【输入样例】

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

【输出样例】

9 1 9 2 3 0 8

【核心思想】

1. 问题分析：给定 $n$ 个待加密数字和一个长度为 $10$ 的密码本（映射表），密码本的第 $i$ 个数字表示原数字 $i-1$ 加密后变成的值。需要将每个待加密数字按映射表替换后输出。本质是**离散映射（Discretization Mapping）**问题，即通过一个固定的查找表完成一对一的数值替换。

2. 算法选择：

   • 直接映射（哈希表 / 数组）：建立 $0\sim 9$ 到目标数字的映射关系，对待加密序列进行 $O(1)$ 的查表替换
   • 顺序处理：按输入顺序读取、查表、输出，无需复杂数据结构

3. 关键步骤：

   • 读取待加密序列：读入 $n$ 和数组 $a[\mathrm{1..}n]$
   • 构建映射表：读入 $10$ 个数字，建立 mp[i] 表示数字 $i$ 加密后的值（$i\in [0,9]$）
   • 逐位替换输出：遍历 $i$ 从 $1$ 到 $n$，输出 mp[a[i]]

4. 时间/空间复杂度：

   • 时间复杂度：$O(n+10)=O(n)$，构建映射表 $O(10)$，替换输出 $O(n)$
   • 空间复杂度：$O(n+10)=O(n)$，存储待加密数组和映射表

5. 直接映射的核心思想：

   • 查找表（LUT）思想：将"规则计算"转化为"直接查表"，利用密码本预先计算好所有可能输入（仅 $10$ 个数字）的对应输出，实现 $O(1)$ 单次替换
   • 定义域有限性：由于数字仅为 $0\sim 9$，映射表大小固定为 $10$，与待加密数字个数 $n$ 无关，空间开销极小
   • 顺序无关性：每个数字的加密操作相互独立，无需考虑相邻数字的影响，因此可以边读取边输出，或统一处理后再输出
   • 哈希表与数组的等价性：本题中 map<int, int> 可用普通数组 int mp[10] 完全替代（因为键的范围是连续的 $0\sim 9$），数组实现更优（$O(1)$ 访问且无额外开销）
   • 适用于有限定义域上的离散映射、替换密码、编码转换等基础查表类问题

【算法标签】

#入门 #模拟

【代码详解】

#include <bits/stdc++.h>
using namespace std;
const int N = 20005;               // 常量：数组最大容量

int n;                             // n: 需要加密的数字个数
map<int, int> mp;                  // mp[x]: 数字 x 加密后的映射结果
int a[N];                          // a[i]: 第 i 个需要加密的数字

int main()
{
    cin >> n;                      // 读入需要加密的数字个数

    for (int i = 1; i <= n; i++)  // 读入 n 个需要加密的数字
        cin >> a[i];

    for (int i = 0; i <= 9; i++)  // 读入密码本：第 i 个数字表示 i 加密后变成什么
        cin >> mp[i];

    for (int i = 1; i <= n; i++)  // 逐个输出加密后的数字
        cout << mp[a[i]] << " ";   // 根据密码本映射输出，数字间用空格分隔

    cout << endl;                  // 输出换行

    return 0;
}

【运行结果】

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