【题目来源】洛谷B4555 [GESP202606 三级] 加密 - 洛谷【题目描述】小杨同学有一串数字想把它们变成另一串数字这个过程叫做加密。他有一本密码本密码本告诉你每个数字应该变成哪个数字。数字一共有10 1010个0 00、1 11、2 22、3 33、4 44、5 55、6 66、7 77、8 88、9 99。密码本会依次告诉你0 00要变成什么1 11要变成什么2 22要变成什么……9 99要变成什么请你按照密码本把原来的每个数字都换成新的数字然后输出。【输入】输入共有3 33行。第一行一个整数表示有多少个数字需要加密第二行这些需要加密的数字第三行密码本一共10 1010个数字。这10 1010个数字的意思是第1 11个数字表示0 00加密后变成什么第2 22个数字表示1 11加密后变成什么第3 33个数字表示2 22加密后变成什么……第10 1010个数字表示9 99加密后变成什么。【输出】输出加密后的数字。也就是把输入第二行里的每个数字都按照输入第三行的密码本换掉后输出。【输入样例】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【核心思想】问题分析给定n nn个待加密数字和一个长度为10 1010的密码本映射表密码本的第i ii个数字表示原数字i − 1 i-1i−1加密后变成的值。需要将每个待加密数字按映射表替换后输出。本质是**离散映射Discretization Mapping**问题即通过一个固定的查找表完成一对一的数值替换。算法选择直接映射哈希表 / 数组建立0 ∼ 9 0 \sim 90∼9到目标数字的映射关系对待加密序列进行O ( 1 ) O(1)O(1)的查表替换顺序处理按输入顺序读取、查表、输出无需复杂数据结构关键步骤读取待加密序列读入n nn和数组a [ 1.. n ] a[1..n]a[1..n]构建映射表读入10 1010个数字建立mp[i]表示数字i ii加密后的值i ∈ [ 0 , 9 ] i \in [0, 9]i∈[0,9]逐位替换输出遍历i ii从1 11到n nn输出mp[a[i]]时间/空间复杂度时间复杂度O ( n 10 ) O ( n ) O(n 10) O(n)O(n10)O(n)构建映射表O ( 10 ) O(10)O(10)替换输出O ( n ) O(n)O(n)空间复杂度O ( n 10 ) O ( n ) O(n 10) O(n)O(n10)O(n)存储待加密数组和映射表直接映射的核心思想查找表LUT思想将规则计算转化为直接查表利用密码本预先计算好所有可能输入仅10 1010个数字的对应输出实现O ( 1 ) O(1)O(1)单次替换定义域有限性由于数字仅为0 ∼ 9 0 \sim 90∼9映射表大小固定为10 1010与待加密数字个数n nn无关空间开销极小顺序无关性每个数字的加密操作相互独立无需考虑相邻数字的影响因此可以边读取边输出或统一处理后再输出哈希表与数组的等价性本题中mapint, int可用普通数组int mp[10]完全替代因为键的范围是连续的0 ∼ 9 0 \sim 90∼9数组实现更优O ( 1 ) O(1)O(1)访问且无额外开销适用于有限定义域上的离散映射、替换密码、编码转换等基础查表类问题【算法标签】#入门 #模拟【代码详解】#includebits/stdc.husingnamespacestd;constintN20005;// 常量数组最大容量intn;// n: 需要加密的数字个数mapint,intmp;// mp[x]: 数字 x 加密后的映射结果inta[N];// a[i]: 第 i 个需要加密的数字intmain(){cinn;// 读入需要加密的数字个数for(inti1;in;i)// 读入 n 个需要加密的数字cina[i];for(inti0;i9;i)// 读入密码本第 i 个数字表示 i 加密后变成什么cinmp[i];for(inti1;in;i)// 逐个输出加密后的数字coutmp[a[i]] ;// 根据密码本映射输出数字间用空格分隔coutendl;// 输出换行return0;}【运行结果】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