蓝桥杯赛前补题(二): 2021年C/C++省赛真题个人题解 A ~ E
A. ASC(签到题)
已知大写字母 A 的 ASCII 码为 65，请问大写字母 L 的 ASCII 码是多少？
时间复杂度: O(1)
B.空间(签到题)
小蓝准备用 256MB 的内存空间开一个数组，数组的每个元素都是 32 位 二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问 256MB 的空间可以存储多少个 32 位二进制整数？
分析: 我们知道8个bit为一个字节byte, 所以一个32位二进制数需要 4 个字节, 而 256MB 相当于 256 * 1024 * 1024 个 byte, 所以直接利用除法就可以得出答案了:
时间复杂度: O(1)
C.卡片(模拟)
小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。
小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。
小蓝想知道自己能从 1 拼到多少。
例如，当小蓝有 30 张卡片，其中 0 到 9 各 3 张，则小蓝可以拼出 1 到 10，
但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。
现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1 拼到多少？
提示：建议使用计算机编程解决问题。
分析: 我们可以用一个数组存放各卡片的个数， 然后进行模拟统计各卡片的个数, 当有卡片的数量为 0 时当前数字就是最大的了。
时间复杂度: O(n)
D.相乘 (模拟)
【问题描述】小蓝发现，他将 1 至 1000000007 之间的不同的数与 2021 相乘后再求除以
1000000007 的余数，会得到不同的数。小蓝想知道，能不能在 1 至 1000000007 之间找到一个
数，与 2021 相乘后再除以 1000000007 后的余数为 999999999。如果存在，请在答案中提交这个数；如果不存在，请在答案中提交 0
1000000007 * 2021 可能会溢出, 所以要用到乘法取模的数学性质避免数据溢出:
(a * b) % p = ( (a % p) * (b % p) ) % p
算法复杂度: O(n)
E.路径(动态规划 || 图论)
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。
小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
分析: 求最短路径的算法有很多， 其中最简单的就是 Floyd 暴力法了(也是对我来说最好理解的)， 算法复杂度为 O(n^3) (这是一道填空题不害怕超时...).
我们根据题意进行建树, 这里我用了邻接矩阵的方式， 定义邻接矩阵map, 每个节点的边权就是最短路径, 那么我们的答案就是 map[1][2021]了。
最后提一下Floyd的基本核心, 就是先枚举每一个节点看看是不是"中转站"， 如果是的话则进行松弛操作， 这样我们就保证了最短路径的子路径是最短的, 核心代码如下:
那么完整代码为:
当然，单源最短路径建议还是用 Dijkstra:
时间复杂度: O(n^2):
下面我们考虑用动态规划, 我们先定义我们的状态:
dp[i] : 从 1 到 i 的最短路径，我们用闫式dp法来分析一下(最近跟y总学的dp小技巧), 首先我们的问题是要在一个包含所有路径的有限集合(集合)中找到一条最短路径(属性), 我们现在来考虑最后一个合法的状态，对于 dp[i] 包含了21个子集(因为题目说两个节点大于 21，则两个结点之间没有边相连), dp[i] 是从 dp[i - 1], dp[i - 2] , ... , dp[i - 21] 转移过来的 (满足不重不漏), 这是变化的部分(因为dp[i]表示的子集最后一个元素一定是 i (也就是本题中路径的终点一定是 i), 而前面部分不是固定的)。假设从 k 转移过来, 那么不变的部分就是 lcm(k, i)了.
当dp[i]为空时代表我们还没有访问过这条路径, 那么此时 dp[i] = lcm(k, i)。
当dp[i]不为空时 dp[i] = min(dp[k], dp[k] + lcm(k, i))
时间复杂度: O(n ^ 2)
