蓝桥杯赛前补题(二): 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 至 之间的不同的数与 2021 相乘后再求除以 的余数，会得到不同的数。小蓝想知道，能不能在 1 至 之间找到一个 数，与 2021 相乘后再除以 后的余数为 。如果存在，请在答案中提交这个数；如果不存在，请在答案中提交 0 * 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)
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/39779.html
