1. 从“蓝桥杯2021国赛CB题解”说起一份迟到的复盘与深度拆解最近在整理资料时翻到了2021年蓝桥杯国赛C B组以下简称CB组的题目。虽然时隔几年但作为国内覆盖面最广的编程赛事之一其国赛真题依然具有极高的参考价值。对于正在备赛的同学它是最好的模拟战场对于已经参赛过的选手它是一次绝佳的复盘机会能帮你查漏补缺看清自己思维上的盲区。今天我就以一名老选手和过来人的视角带大家重新走进这套题不光是给出答案更重要的是拆解每道题背后的核心考点、解题思路的构建过程以及那些在考场上容易忽略的“坑点”。我会假设你具备C语言基础和基本的算法知识目标是让你不仅能看懂“怎么做”更能理解“为什么这么做”以及“下次遇到类似的该怎么想”。这套题整体上延续了蓝桥杯“思维实现”并重的风格既有考验数学思维和逻辑推理的题目也有对代码实现细节和算法效率要求较高的题目。我们将按照题目顺序逐一进行深度剖析我会在讲解中融入我自己的解题心路历程和踩过的坑希望能给你带来一些不一样的启发。2. 试题A空间基础中的基础但别掉以轻心这道题通常是“送分题”考察的是最基础的计算机常识和单位换算。题目可能会给出类似“一个32位二进制整数在内存中占用多少字节”或者“256MB的存储空间可以存放多少个32位整数”这样的问题。2.1 核心考点与解题钥匙这里的核心就两个位(bit)、字节(Byte)、字(word)的关系以及二进制与十进制的换算。1 Byte 8 bits。这是铁律。32位整数意味着每个整数需要用32个二进制位来存储。所以一个32位整数占用的字节数 32 bits / 8 4 Bytes。如果题目问的是存储容量能放多少个比如“256MB的内存可以存放多少个32位整数” 解题步骤统一单位将容量全部转换为字节(B)。1 MB 1024 KB 1 KB 1024 B。所以 256 MB 256 * 1024 * 1024 B。计算整数个数总字节数 / 每个整数占用的字节数 (256 * 1024 * 1024) / 4。简化计算256 * 1024 * 1024 / 4 64 * 1024 * 1024。这其实就是 64M 个整数。这里“M”是数量单位百万(10^6)注意和容量单位MB(MegaByte)区分。2.2 考场上的“坑”与提速技巧这道题真正的难点不在于计算本身而在于考场的紧张环境下你是否能快且准。坑点1单位混淆。一定要看清题目给的是 MB, GB, KB 还是 bit。如果给的是 Mb (兆比特常用于网络带宽)那和 MB (兆字节) 相差8倍坑点21024 vs 1000。在计算机存储领域K, M, G 通常是以1024为进制即2^10。虽然有些场合如硬盘厂商会用1000但在蓝桥杯这类编程竞赛的语境下默认使用1024进制除非题目特别说明。提速技巧记住一些常用换算结果。例如2^10 1024, 2^20 ≈ 1e6 (1048576), 2^30 ≈ 1e9。对于上面的例子看到256MB和32位可以快速反应32位是4B256MB是 256 * 2^20 B。两者相除256/464结果就是 64 * 2^20即64M个。这样心算就能出答案节省大量时间。注意蓝桥杯填空题通常需要提交整数答案。对于64 * 1024 * 1024这种要老老实实算出来是67108864不要直接填64*1024*1024或64M。3. 试题B卡片模拟与思维边界“卡片”题是蓝桥杯非常经典的一类题通常给你一堆数字卡片比如数字0-9各有若干张问你从1开始拼数字最多能拼到哪个数字。2021年这题也不例外但往往藏着一些需要仔细推敲的细节。3.1 问题建模与朴素解法假设我们拥有数字卡片0-9每种卡片2021张这是2021年题目的一个特色数字。我们从1开始拼出数字1消耗一张‘1’卡片拼出数字2消耗一张‘2’卡片……以此类推直到某种卡片不够用为止。最直接的思路就是模拟初始化一个长度为10的数组cnt[10]记录0-9每种卡片的剩余数量初始值均为2021。设一个变量i 1开始循环。对于当前数字i将其每一位数字分解出来。例如i123分解出 ‘1‘ ’2‘ ’3‘。检查cnt[1],cnt[2],cnt[3]是否都大于0。如果都大于0则将这些计数减1表示消耗了这些卡片然后i继续下一个数字。如果某一位数字d对应的cnt[d] 0说明卡片d已经用完无法拼出数字i。那么能拼出的最大数字就是i-1。3.2 代码实现与细节#include iostream using namespace std; int main() { int cnt[10]; for (int i 0; i 10; i) cnt[i] 2021; // 初始化每种卡片2021张 int num 1; // 从1开始拼 while (true) { int temp num; // 分解数字num的每一位 while (temp 0) { int digit temp % 10; // 取出个位 if (cnt[digit] 0) { // 卡片不够用了 cout num - 1 endl; // 能拼到的最大数字是前一个 return 0; } cnt[digit]--; // 消耗一张卡片 temp / 10; // 去掉个位 } num; } return 0; }3.3 深入思考为什么不是“1”最先用完很多同学直觉上会觉得数字‘1’用得最多因为它出现在1, 10, 11, 12..., 21, 31... 等多个数字中。模拟结果也往往确实是‘1’最先耗尽。但这并不是绝对的真理它取决于初始卡片的数量。如果‘1’卡片给得特别多而其他某个数字比如‘0’给得很少那么瓶颈就可能转移。这道题的精髓在于模拟的准确性和对“耗尽”条件的判断。在循环中必须对当前数字num的每一位进行“预检查”或“即时检查并回滚”确保不会出现部分位数卡片被消耗后后几位卡片不足导致状态错误的情况。上面的代码采用的就是“即时检查并消耗”的方式一旦发现某一位不足立刻宣布num无法拼出此时num-1就是答案。一个常见的错误是先消耗所有位数的卡片然后再判断。如果数字是101你先消耗了‘1’和‘0’然后发现‘1’卡片不够了假设只剩1张但此时‘0’卡片已经被错误地消耗掉了一张。这会导致后续计数不准。所以要么在消耗前做完全检查要么像上面代码一样在消耗每一位时立即判断一旦失败整个数字num就失败了且因为我们是顺序尝试之前的状态都是正确的。4. 试题C直线几何、精度与去重这道题是当年讨论度很高的题目它要求计算平面上一系列给定整点比如0 x, y 19的网格点所能确定的不同直线的数量。这题完美融合了数学、编程和思维严谨性。4.1 思路分析如何表示一条直线两点确定一条直线。最直观的想法是枚举所有点对(A, B)然后求出它们确定的直线最后去重。关键就在于“如何表示一条直线”以便于去重。常用的表示方法有斜截式y kx b。用(k, b)作为直线的“指纹”。但这里有个大坑斜率不存在竖直线的情况需要单独处理。一般式Ax By C 0(A, B不同时为0)。可以约化为最简形式即A, B, C除以它们的最大公约数并保证第一个非零系数为正。这样(A, B, C)的三元组可以作为唯一标识。两点式衍生使用(Δx, Δy, x0, y0)或其他组合但本质上还是要归一化。我推荐使用一般式因为它能统一处理所有情况包括竖直线。对于两点(x1, y1)和(x2, y2)A y2 - y1B x1 - x2// 注意这里是 x1 - x2这样A*x1 B*y1 C 0推导时符号正确C x2*y1 - x1*y2得到A, B, C后我们需要将其化为最简形式计算g gcd(gcd(A, B), C)。gcd是求最大公约数的函数。如果g ! 0令A/g, B/g, C/g。符号标准化为了使同一条直线有唯一的表示我们约定让第一个非零的系数为正数。遍历A, B, C找到第一个不为0的数如果它是负数则将A, B, C同时乘以-1。4.2 代码实现与去重技巧#include iostream #include set #include cmath using namespace std; struct Point { int x, y; }; int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); } int main() { vectorPoint points; // 假设网格点是 x, y 从 0 到 19 for (int x 0; x 19; x) { for (int y 0; y 19; y) { points.push_back({x, y}); } } settupleint, int, int lines; // 使用集合自动去重 int n points.size(); for (int i 0; i n; i) { for (int j i 1; j n; j) { // j从i1开始避免重复枚举同一点对 Point p1 points[i]; Point p2 points[j]; int A p2.y - p1.y; int B p1.x - p2.x; int C p2.x * p1.y - p1.x * p2.y; // 化为最简整数比 int g gcd(abs(A), gcd(abs(B), abs(C))); if (g ! 0) { A / g; B / g; C / g; } // 符号标准化让第一个非零系数为正 if (A 0 || (A 0 B 0) || (A 0 B 0 C 0)) { A -A; B -B; C -C; } lines.insert({A, B, C}); } } cout lines.size() endl; return 0; }4.3 浮点数陷阱与整数化的必要性如果你尝试用double类型的(k, b)来存储斜截式你会遇到灾难性的精度问题。因为点的坐标是整数计算出的k和b可能是分数。由于浮点数存储和比较的不精确性两条数学上相同的直线其k和b的浮点表示可能略有不同导致set或map认为它们是不同的直线从而造成错误计数。例如由点 (0,0) 和 (2,1) 确定的直线斜率k0.5。由点 (0,0) 和 (4,2) 确定的直线斜率k0.5。理论上它们应该相同。但在浮点数计算中(double)1/2和(double)2/4在内存中的二进制表示可能完全一致也可能因为中间运算过程不同而产生极其微小的差异。依赖运算符或直接存入setdouble是不可靠的。因此必须使用整数来表示直线的参数并通过最大公约数GCD进行归一化才能保证比较的绝对准确性。这是解决此类几何计数问题的核心技巧。5. 试题D货物摆放数论与因子枚举这道题是经典的因子组合问题。题目通常会给一个很大的整数N例如2021041820210418问有多少种不同的三元组(a, b, c)满足a * b * c N并且考虑顺序即(1,1,2)、(1,2,1)、(2,1,1)算作不同的方案。5.1 暴力枚举的不可行性最傻的办法是三层循环枚举a, b, c但N的规模巨大10^16量级这显然会超时。我们必须寻找更聪明的方法。5.2 优化思路枚举因子关键在于意识到如果a * b * c N那么a、b、c都必须是N的因子。因此我们可以先求出N的所有因子存储在一个数组factors中。然后三层循环枚举factors中的元素作为a,b,c。检查a * b * c N计数。这样循环次数就从O(N^(3/2))降到了O(d(N)^3)其中d(N)是N的因子个数。对于N在10^16这个量级其因子个数通常不会超过几万个实际上远小于这个数这使得枚举成为可能。5.3 高效求所有因子与代码实现求所有因子可以通过遍历1到sqrt(N)来实现。#include iostream #include vector #include cmath using namespace std; typedef long long LL; int main() { LL N 2021041820210418LL; vectorLL factors; // 求N的所有因子 for (LL i 1; i sqrt(N); i) { if (N % i 0) { factors.push_back(i); if (i ! N / i) { // 避免重复添加平方根 factors.push_back(N / i); } } } LL ans 0; int size factors.size(); // 三层循环枚举因子 for (int i 0; i size; i) { for (int j 0; j size; j) { // 一个小优化如果 a*b 已经大于 N那么 c 必然小于1不可能为整数因子可以跳过 // 但更简单的是直接枚举c因为因子个数不多 for (int k 0; k size; k) { if (factors[i] * factors[j] * factors[k] N) { ans; } } } } cout ans endl; return 0; }5.4 进一步优化与思维延伸上述代码在因子个数较多时例如几千个三层循环O(d^3)可能还是有点慢。可以进一步优化我们可以只枚举a和b然后计算c N / (a * b)。只需要判断c是否为整数即N % (a*b) 0即可。这样复杂度降为O(d^2)。更进一步由于因子是成对出现的枚举时可以做一些剪枝。但就蓝桥杯的时限和N的具体数值而言O(d^3)的暴力枚举通常也能在1秒内完成。这道题考察的就是选手能否从“暴力枚举所有数”的思维跳跃到“只枚举因子”的思维。这是一种非常重要的优化思路在解决与整除、因子相关的问题时非常常用。6. 试题E路径图论与最短路“路径”题通常是一个图论最短路问题。题目描述了一个有N个节点编号1到N的图节点a和节点b之间有一条边边权是lcm(a, b)a和b的最小公倍数。要求计算从节点1到节点N的最短路径长度。6.1 问题抽象与建图这是一个标准的单源最短路问题。图的顶点是1, 2, ..., N。对于任意两个不同的顶点a和b如果它们满足某种条件比如abs(a-b) 21这是2021年题目的一个关键约束那么它们之间就有一条无向边边权为lcm(a, b)。如果没有abs(a-b) 21这个限制那么这就是一个完全图边数约为N^2/2对于N2021来说边数超过200万虽然仍可处理但内存和时间消耗较大。加上这个限制后每个节点只与附近最多21个节点相连总边数约为21N大大减少了计算量。6.2 算法选择Dijkstra 算法由于边权均为正数最小公倍数肯定为正求单源最短路的标准算法是Dijkstra 算法。我们可以使用优先队列堆优化的版本时间复杂度为O((VE) log V)其中V是顶点数NE是边数~21N对于N2021来说非常快。6.3 代码实现细节#include iostream #include vector #include queue #include climits using namespace std; typedef long long LL; typedef pairLL, int P; // (距离, 节点编号) LL lcm(LL a, LL b) { return a / __gcd(a, b) * b; // 先除后乘防止溢出 } int main() { const int N 2021; const int MAX_DIFF 21; // 建图邻接表 vectorvectorP graph(N 1); for (int a 1; a N; a) { for (int b a 1; b N b - a MAX_DIFF; b) { LL weight lcm(a, b); graph[a].push_back({weight, b}); graph[b].push_back({weight, a}); // 无向图 } } // Dijkstra vectorLL dist(N 1, LLONG_MAX); vectorbool visited(N 1, false); priority_queueP, vectorP, greaterP pq; // 最小堆 dist[1] 0; pq.push({0, 1}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (visited[u]) continue; visited[u] true; if (u N) break; // 找到终点提前结束 for (auto [w, v] : graph[u]) { if (!visited[v] dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } cout dist[N] endl; return 0; }6.4 注意事项与常见错误边权计算lcm(a, b) a * b / gcd(a, b)。注意计算顺序a*b可能会溢出int范围2021*2021约4百万在int范围内但先乘后除是良好习惯。使用long long更安全。无向图记得添加双向边。Dijkstra的标记使用visited数组来标记已确定最短距离的节点是必要的可以避免重复入队和错误更新。从优先队列中取出的节点如果其距离值大于当前记录的dist[u]说明这是旧的、无效的队列条目直接跳过。终点优化当从队列中取出的节点u就是终点N时它的距离已经是最短距离可以直接跳出循环。这是一个有效的优化。这道题是经典的模板题考察的是选手对基础图论算法Dijkstra的掌握和实现能力以及对问题抽象和建图的理解。7. 试题F时间显示模拟与取模运算这是一道简单的模拟题考察对时间单位换算和取模运算的掌握。题目会给一个毫秒级的时间戳从1970年1月1日00:00:00开始经过的毫秒数要求你输出这个时间戳对应的HH:MM:SS格式忽略年月日只显示时分秒并且毫秒部分要四舍五入或直接舍去具体看题目要求通常是直接舍去。7.1 解题步骤分解去除整天数1天 24小时 24 * 60 * 60 * 1000 毫秒。用总毫秒数t对这个值取模得到当天内的毫秒数t_day。t_day t % (24 * 60 * 60 * 1000)。计算小时1小时 60 * 60 * 1000 毫秒。用t_day除以这个数得到小时数HH。HH t_day / (60 * 60 * 1000)。计算分钟从t_day中减去小时部分占用的毫秒数得到剩余毫秒数t_remain。然后1分钟 60 * 1000 毫秒。用t_remain除以这个数得到分钟数MM。MM t_remain / (60 * 1000)。计算秒再从t_remain中减去分钟部分占用的毫秒数得到最后的毫秒数再除以1000得到秒数SS。注意题目要求通常直接取整舍去毫秒即SS t_remain / 1000。7.2 代码实现与格式化输出#include iostream #include iomanip using namespace std; typedef long long LL; int main() { LL t; cin t; // 输入时间戳毫秒 // 1. 去除整天数得到当天内的毫秒数 LL millisecondsPerDay 24 * 60 * 60 * 1000; LL t_in_day t % millisecondsPerDay; // 2. 计算小时、分钟、秒 LL millisecondsPerHour 60 * 60 * 1000; LL millisecondsPerMinute 60 * 1000; LL millisecondsPerSecond 1000; LL hours t_in_day / millisecondsPerHour; t_in_day % millisecondsPerHour; LL minutes t_in_day / millisecondsPerMinute; t_in_day % millisecondsPerMinute; LL seconds t_in_day / millisecondsPerSecond; // 直接舍去毫秒 // 3. 格式化输出不足两位补0 cout setfill(0) setw(2) hours : setw(2) minutes : setw(2) seconds endl; return 0; }7.3 易错点分析数据范围时间戳t可能很大必须使用long long(或int64_t) 来存储。取模运算的理解t % (24*60*60*1000)这一步是关键它直接去掉了所有“天”的影响只留下不足一天的余数。很多同学会先除以1000转换成秒再计算这也可以但要注意在转换过程中不要丢失精度或溢出。四舍五入 vs 直接舍去务必仔细阅读题目要求。蓝桥杯的这道题通常要求直接舍去毫秒而不是四舍五入。所以seconds t_remain / 1000是整数除法直接截断小数部分。格式化输出输出必须是HH:MM:SS的两位数字格式需要用setw(2)和setfill(0)来控制。这是基础但容易忘记的细节。这道题是典型的“签到题”旨在稳定军心。只要细心确保单位换算和取模运算正确就能稳稳拿分。8. 试题G砝码称重动态规划或DFS这是一道经典的**动态规划DP**问题也可能用深度优先搜索DFS配合记忆化来解决。题目通常给出若干种重量的砝码每种有若干个问用这些砝码可以放在天平左右两边能称出多少种不同的正整重量。8.1 问题理解与状态定义关键点在于砝码可以放在天平左右两边。放在左边物品盘相当于“加”放在右边砝码盘相当于“减”。因此每个砝码有三种状态不用、放左边w、放右边-w。我们可以把问题转化为给定一个可正可负的砝码重量集合通过给每个砝码分配一个系数-1 0 1求所有可能的系数组合下总和的绝对值有多少种不同的正整数值。定义DP状态dp[i][j]表示考虑前i个砝码这里的“个”是指种类需要处理数量能否称出重量j。由于重量可能为负我们需要一个偏移量Bias将负下标映射到正数。j的范围是[-sum, sum]其中sum是所有砝码总重量之和。更常见的做法是定义dp[i][j]为前i种砝码能否称出重量jj为偏移后的非负索引。8.2 动态规划转移方程假设我们有n种砝码第i种重量为w[i]数量为c[i]。 总重量上限M sum(w[i] * c[i])。 偏移量B M这样dp数组的第二维大小设为2*M1下标j对应实际重量j - B。初始化dp[0][B] true一个砝码都不用能称出重量0。对于第i种砝码我们有c[i]个。这是一个多重背包问题。我们可以将其转化为“二进制拆分”的01背包或者直接进行三重循环但效率较低。对于蓝桥杯的规模直接三重循环遍历种类、遍历状态、遍历该种类砝码的使用个数有时也能过。简化版假设每种砝码只有一个即01背包的状态转移dp[i][j] dp[i-1][j] || dp[i-1][j-w[i]] || dp[i-1][jw[i]]意思是当前状态j可以由前i-1个砝码直接称出不用第i个或者由前i-1个砝码称出j-w[i]第i个放左边或者称出jw[i]第i个放右边。对于多重砝码我们需要在最内层循环中遍历使用该种砝码k个k从0到c[i]并且每个砝码可以加可以减情况会复杂一些。更清晰的做法是使用布尔DP结合滚动数组优化。8.3 代码实现示例布尔DP#include iostream #include vector #include bitset using namespace std; int main() { int n; cin n; vectorint w(n), c(n); int total 0; for (int i 0; i n; i) { cin w[i] c[i]; total w[i] * c[i]; } int B total; // 偏移量 int SIZE 2 * total 1; // 使用bitset优化空间和时间dp[j]表示当前能称出偏移后的重量j bitset200005 dp; // 大小根据total估算这里假设total最大为10万 dp.set(B); // 初始化重量0对应下标B是可达的 for (int i 0; i n; i) { // 遍历砝码种类 for (int k 0; k c[i]; k) { // 对于每个砝码逐个处理转化为01背包 // 注意因为砝码可以放左或右我们需要同时更新加和减的状态 // 使用临时bitset记录本轮更新避免新状态影响本轮其他状态的判断 bitset200005 temp dp; dp | (temp w[i]); // 放左边加 dp | (temp w[i]); // 放右边减 } } // 统计能称出的正整重量种类排除重量0 int ans 0; for (int j B 1; j B total; j) { // 只统计正重量部分 if (dp[j]) { ans; } } cout ans endl; return 0; }8.4 使用bitset的巧妙之处上面的代码使用了bitset这是一个非常强大的工具尤其适合这种布尔状态的DP。dp.set(B)将第B位设为1表示重量0可达。temp w[i]表示将所有可达状态“加”上w[i]。temp w[i]表示将所有可达状态“减”去w[i]。dp | ...将新的可达状态合并到原状态中。这种方法高效且代码简洁完美地处理了砝码可加可减的情况。最终dp中所有为1的位就代表了所有可以称出的重量带偏移。我们只需要统计偏移后大于B即实际重量为正的位有多少个即可。这道题是动态规划的经典应用考察选手将实际问题转化为背包模型并运用位运算技巧进行优化的能力。9. 总结与备赛建议复盘2021年蓝桥杯国赛CB组的题目我们可以清晰地看到其考察脉络从基础的计算机原理和模拟A, B, F到数学几何与算法思维C, D再到经典的图论和动态规划算法E, G。题目难度梯度明显既有送分题保证基础分也有需要深入思考和精巧实现的题目来拉开差距。对于备赛的同学我有以下几点建议吃透基础像A、B、F这类题目标必须是满分。任何单位换算、模拟细节、格式化输出的错误都是不可原谅的。平时练习就要追求一次通过培养“零失误”的稳定心态。掌握核心算法模板最短路Dijkstra, Floyd、动态规划背包、线性DP、搜索DFS, BFS、并查集、最小生成树、二分查找等必须做到熟练默写理解其适用场景和变种。试题E和G就是模板的直接或变形应用。提升数学与思维能力试题C和D要求更高的思维水平。C题考验的是在几何问题中处理精度和唯一性的能力D题考验的是将暴力枚举优化为因子枚举的洞察力。这需要平时多做题多总结看到“求方案数”、“有多少种”这类问题要下意识地想到排列组合、因子、容斥原理等数学工具。注意数据范围与精度这是蓝桥杯也是所有算法竞赛的永恒考点。看到题目先看数据范围决定使用int还是long long。涉及浮点数比较时优先考虑能否转化为整数运算如C题。涉及大数运算时考虑是否会溢出。实战模拟与时间管理在最后冲刺阶段一定要进行全真模拟。用历年真题设定4小时倒计时完整地做一套。练习如何分配时间简单题快速通过30分钟内中等题稳扎稳打60-90分钟难题尽力而为。切忌在一道题上卡死过久。国赛的舞台比拼的不仅是知识储备更是心态、速度和准确性。希望这份针对2021年CB组的超详细题解能帮助你更好地理解题目背后的思维逻辑和实现细节。真正的提升来自于动手实践不妨现在就打开编译器把这几道题自己从头到尾实现一遍遇到卡壳的地方再回来看解析这样的收获才是最大的。祝你在未来的比赛中取得理想的成绩