1. 赛题回顾与整体感受时间过得真快距离2020年那场特殊的蓝桥杯国赛已经过去好几年了。作为当年B组C/C的参赛者现在回想起来那场比赛的题目风格和难度依然记忆犹新。那一年因为众所周知的原因很多比赛都受到了影响蓝桥杯能如期举办实属不易题目也相应地透露出一些“求稳”和“回归基础”的意味但其中也不乏几道让人眼前一亮的“硬骨头”。今天我就以一个过来人的身份和大家一起复盘一下那套题聊聊解题思路更重要的是分享一些在高压竞赛环境下如何调整策略、规避陷阱的实战经验。无论你是正在备赛的选手还是对算法竞赛感兴趣的朋友希望这篇深度解析能给你带来一些实实在在的启发。那届国赛B组的题目整体上给我的感觉是“广而不深但坑点不少”。它没有在某一两个极端复杂的算法上死磕而是广泛覆盖了动态规划、搜索、数学、字符串处理、模拟等多个基础领域。这意味着对选手的基本功和代码实现稳定性提出了很高的要求。很多题目看起来思路直接但想要AC完全正确却需要格外小心数据范围和边界条件。接下来我们就挑几道有代表性的题目一层层剥开来看。2. 试题A美丽的2送分题中的“细节检验器”这道题通常是第一题属于简单的模拟题意在让选手快速进入状态并拿到基础分。题目大意是在1到2020包含这些整数中有多少个数字包含数字‘2’。2.1 暴力枚举与实现要点最直接的思路就是遍历1到2020检查每个数的每一位是否包含‘2’。代码非常简短#include iostream using namespace std; int main() { int cnt 0; for (int i 1; i 2020; i) { int x i; while (x) { if (x % 10 2) { cnt; break; // 找到2就跳出当前数字的判断 } x / 10; } } cout cnt endl; return 0; }这里有一个关键的“避坑点”内层循环中一旦发现某位是2就要立即break跳出对当前数字的检查。否则如果一个数字像“222”这样包含多个2就会被重复计数。这是新手很容易忽略的细节虽然在这道题里数据量小错误可能不明显但这种思维习惯在后续更复杂的题目中会导致灾难性后果。2.2 思维延伸与常见变体这道题虽然简单但它是一个经典的“数位统计”问题的雏形。我们可以借此思考更一般的问题求1到N之间数字k0-9出现的次数。这就引出了经典的“数位DP”问题。在竞赛中简单的题往往是更复杂问题的一个提示或铺垫。即使本题不需要了解其背景也能帮助你在看到类似模式时更快反应。个人心得国赛的前一两题目标不仅仅是做对更是要“快速且稳健”地做对。这能为后面的难题节省宝贵的时间。我当时的策略是即使题目再简单写完后也一定要用几个临界值比如1 10 2020自己快速心算验证一下。养成这个习惯能避免很多低级失误。3. 试题B扩散BFS/DFS模拟的典型应用这道题“扩散”是那场比赛中的一个亮点它完美结合了模拟、搜索和空间想象。题目描述大致是在一个无限的网格中最初有四个点处于黑点状态。每一分钟每个黑点会使其上下左右四个相邻格点也变黑。问经过2020分钟后有多少个黑点。3.1 问题抽象与算法选择这是一个典型的“多源广度优先搜索BFS”问题。我们可以把每一分钟看作BFS向外扩散一层。关键难点在于空间的“无限”性。我们无法真正模拟一个无限大的网格必须估算一个足够的边界。为什么选择BFS而不是DFS因为扩散过程是按“时间层数”均匀推进的BFS天然保证了我们按时间顺序处理所有点方便统计第2020分钟时的状态。DFS则更适合探索一条路径到底不适合这种均匀扩散的场景。边界估算初始点坐标题目会给出假设为(0,0), (2020,11), (11,14), (2000,2000)等具体值需回忆。每个点经过2020分钟最远能影响到曼哈顿距离2020以外的点。因此我们需要一个能够包含所有初始点坐标加上/减去2020的网格范围。例如若初始点x坐标在[0, 2000]那么模拟的网格x轴范围至少需要[-2020, 20002020]。为了保险起见通常会设置一个更大的偏移量比如2500。3.2 具体实现与关键技巧#include iostream #include queue using namespace std; // 定义方向数组 int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int main() { // 假设初始点坐标 pairint, int starts[4] {{0,0}, {2020,11}, {11,14}, {2000,2000}}; // 计算边界和偏移量将坐标映射到正数数组索引 const int OFFSET 2500; // 偏移量确保索引非负 const int N OFFSET * 2 5000; // 网格大小应足够大 bool grid[N][N] {false}; // 标记是否变黑 int dist[N][N]; // 记录变成黑点的分钟数也可用bool但dist更通用 // 初始化dist为-1表示未访问 memset(dist, -1, sizeof(dist)); queuepairint, int q; // 将初始点加入队列并标记 for (auto p : starts) { int nx p.first OFFSET; int ny p.second OFFSET; grid[nx][ny] true; dist[nx][ny] 0; q.push({nx, ny}); } long long ans 4; // 初始有4个黑点 // BFS过程 while (!q.empty()) { auto [x, y] q.front(); q.pop(); int current_step dist[x][y]; if (current_step 2020) { continue; // 已经扩散到2020分钟不再从此点继续 } for (int i 0; i 4; i) { int nx x dirs[i][0]; int ny y dirs[i][1]; // 检查是否在模拟边界内通常没问题因为边界设得很大 if (nx 0 || nx N || ny 0 || ny N) continue; if (dist[nx][ny] -1) { // 首次访问 dist[nx][ny] current_step 1; grid[nx][ny] true; ans; // 新的黑点 q.push({nx, ny}); } } } cout ans endl; return 0; }重要优化与注意事项使用dist数组记录时间这比单纯用bool数组更好。当current_step 2020时该点不会继续扩散但它在第2020分钟时已经是黑点应被计入总数。我们的BFS在遇到第2020分钟的点时只是不再将其邻居入队但该点本身在之前已被计入ans。答案数据类型经过2020轮扩散黑点数量会非常庞大int很可能溢出。务必使用long long来存储答案ans。空间与时间二维数组grid和dist的大小是N*NN可能达到几千这是内存消耗的大头bool数组约N*N字节int数组约4*N*N字节。需要合理估算N既要保证够用又不能太大导致内存超限MLE。这是竞赛中权衡空间与安全性的经典案例。踩坑实录我第一次模拟时只用了bool数组标记是否访问没有记录步数。结果在判断“是否继续扩散”时遇到了麻烦队列里同一层的点可能被不同路径重复访问如果只根据bool判断无法知道当前点是第几分钟变黑的。这要么导致提前停止扩散如果遇到一个更早被其他源点染黑的点要么导致无限扩散无法停止。引入dist数组记录分钟数问题就迎刃而解。这个教训让我深刻理解到在BFS中当“层数”或距离、时间本身就是问题的核心约束时记录它往往是必须的。4. 试题C阶乘约数数论与质因数分解的巧妙结合这是一道披着“阶乘”外衣的数论题。题目要求定义n!的约数个数为f(n)求f(100!)的值或者类似的大数阶乘。直接计算100!然后枚举约数是不可能的因为100!是一个158位的天文数字。4.1 核心原理约数个数定理解决这道题需要掌握一个重要的数论定理约数个数定理。 对于一个正整数N将其质因数分解为N p1^a1 * p2^a2 * ... * pk^ak其中p1, p2, ..., pk是互不相同的质数。 那么N的正约数个数d(N)为d(N) (a1 1) * (a2 1) * ... * (ak 1)理解这个公式对于质因数pi它的指数可以是0, 1, 2, ..., ai共(ai1)种选择。所有质因数指数的选择相互独立根据乘法原理总的约数个数就是这些(ai1)的乘积。4.2 从阶乘到质因数指数现在问题转化为求100!的质因数分解形式即求出所有质数p在100!中对应的指数a是多少。有一个经典的公式勒让德定理可以计算n!中质数p的指数a floor(n/p) floor(n/p^2) floor(n/p^3) ...直到p^k n为止。这个公式怎么来的直观理解1*2*...*n中每隔p个数就有一个p的倍数贡献至少一个因子p这样的数有floor(n/p)个。但像p^2, p^3, ...的倍数它们在前一步中只被算了一次实际上贡献了多个因子p所以需要加上floor(n/p^2)、floor(n/p^3)等来补上。4.3 计算过程与代码实现我们不需要真的算出100!只需要找出所有不超过100的质数并计算它们在100!中的指数。#include iostream #include vector #include cmath using namespace std; int main() { int n 100; vectorint primes; vectorbool isPrime(n 1, true); // 埃拉托斯特尼筛法求质数 for (int i 2; i n; i) { if (isPrime[i]) { primes.push_back(i); for (int j i * i; j n; j i) { isPrime[j] false; } } } long long ans 1; // 约数个数用long long防止溢出 for (int p : primes) { int exponent 0; long long power p; // 计算质数p在n!中的指数 while (power n) { exponent n / power; power * p; // 注意这里可能溢出对于大n需要小心 } ans * (exponent 1); } cout ans endl; return 0; }计算细节与验证 以质数5为例floor(100/5) 20(5, 10, 15, ..., 100)floor(100/25) 4(25, 50, 75, 100)floor(100/125) 0(125100) 所以指数a 20 4 24。将所有质数对应的(指数1)相乘即得到最终的约数个数。个人心得这道题是典型的“知识迁移”题。如果你不知道约数个数定理和阶乘质因数指数的计算方法几乎无从下手。但一旦知道就变成了一个简单的编程实现。这提醒我们算法竞赛中基础数论知识质数、约数、同余是必备的武器库。平时积累这些“小公式”、“小定理”关键时刻能省下大量思考时间。5. 试题D本质上升序列动态规划的经典变体这道题“本质上升序列”是动态规划DP应用的典范题目通常给出一个长度不小的字符串比如100个字符以内要求计算其所有“本质不同的上升子序列”的个数。这里的“上升”指的是子序列中字符的ASCII码单调递增“本质不同”指的是即使子序列内容相同只要在原串中位置不同也算不同。5.1 状态定义与转移方程这是子序列计数DP的经典问题。定义dp[i]表示以字符串中第i个字符结尾的、且满足严格递增条件的本质不同子序列的个数。这里的关键是“以i结尾”和“本质不同”。为了处理本质不同我们通常规定对于相同的字符我们只考虑最后一次出现的位置以避免重复计数。但更通用的方法是利用DP转移的特性。转移方程 对于当前位置i我们需要看它前面所有位置j (0 j i)。 如果s[j] s[i]那么所有以s[j]结尾的递增子序列后面加上s[i]都能形成一个新的以s[i]结尾的递增子序列。因此dp[i] dp[j]此外s[i]自己本身也是一个长度为1的子序列所以dp[i]还需要加1。 如果s[j] s[i]这里就需要小心处理重复。一个常见的技巧是当我们从前往后计算dp[i]时如果遇到s[j] s[i]我们不应该简单地将dp[j]加给dp[i]因为以更早的相同字符s[j]结尾的子序列在后面遇到s[i]时再拼接可能会和直接以s[i]自身产生或其他路径产生的子序列重复。更严谨的做法是定义last[c]记录字符c最近一次出现时的dp值或者其索引。在计算dp[i]时我们累加所有小于s[i]的字符c对应的sum_dp[c]其中sum_dp[c]是所有以字符c结尾的子序列个数之和。当遇到一个新的s[i]时dp[i] 1 sum_{c s[i]} sum_dp[c]。然后更新sum_dp[s[i]] dp[i]。同时为了处理重复当再次遇到相同字符时我们需要用新的dp[i]去覆盖旧的贡献而不是累加。因为新位置i包含了所有旧位置能形成的子序列通过转移以及以新位置i自身开始的新子序列。5.2 简化思路与清晰实现对于竞赛环境一个更清晰、不易出错的实现思路是设字符串长度为n。初始化dp数组全为0dp[i]表示以s[i]结尾的本质不同上升子序列数。初始化一个last数组大小为26对应小写字母记录每个字符上一次出现时它所贡献的“以它结尾的子序列总数”是多少。初始为0。遍历字符串的每个位置i计算dp[i] 1。这代表子序列{s[i]}本身。遍历所有ASCII码小于s[i]的字符c在‘a’到‘z’范围内dp[i] sum_dp[c]。这里sum_dp[c]是所有以字符c结尾的子序列总数它需要动态维护。现在dp[i]计算完毕。我们需要更新sum_dp[s[i]]。但注意如果s[i]这个字符之前出现过那么旧的sum_dp[old]里包含的子序列其实已经被新的位置i“代表”了因为从那些旧子序列转移过来会形成包含新位置i的、但本质相同的子序列。更准确地说为了避免重复我们应该让sum_dp[s[i]]直接等于最新的、以当前字符s[i]结尾的子序列总数。也就是说sum_dp[c]记录的就是字符c最后一次出现时计算出的那个dp值。因此在更新时我们直接令sum_dp[s[i]] dp[i]。注意这不是累加而是赋值。最终答案就是所有sum_dp[c]c从‘a’到‘z’的总和。因为每个本质不同的上升子序列都有一个最后的结尾字符。#include iostream #include string #include vector using namespace std; int main() { string s tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl; // 示例长字符串 int n s.length(); vectorlong long dp(n, 0); vectorlong long sum_dp(26, 0); // 记录每个字符‘a’-‘z’对应的最新dp和 for (int i 0; i n; i) { dp[i] 1; // 字符本身作为一个子序列 for (int c 0; c 26; c) { if (c (s[i] - a)) { dp[i] sum_dp[c]; } } // 关键更新当前字符对应的sum_dp为dp[i]覆盖非累加 sum_dp[s[i] - a] dp[i]; } long long ans 0; for (int c 0; c 26; c) { ans sum_dp[c]; } cout ans endl; return 0; }为什么这样做可以避免重复核心在于sum_dp[c]始终只记录字符c最后一次出现时计算出的dp值。假设字符‘a’在位置2和位置5都出现了。位置2的dp[2]计算了所有以位置2的‘a’结尾的子序列。当计算位置5的dp[5]时它会累加sum_dp[‘a’]即dp[2]吗不会因为我们的循环c (s[i]-‘a’)只累加严格小于当前字符的sum_dp。对于相同字符‘a’不会累加。计算完dp[5]后我们令sum_dp[‘a’] dp[5]。这意味着现在sum_dp[‘a’]代表的是以位置5的‘a’结尾的所有子序列。而以位置2的‘a’结尾的子序列并没有被直接加入到最终答案中吗注意以位置2的‘a’结尾的子序列如果是上升的那么它可能被位置5的‘a’“继承”了吗并没有直接继承关系因为‘a’不大于‘a’。实际上以位置2的‘a’结尾的子序列和以位置5的‘a’结尾的子序列如果序列内容相同比如都是单独的‘a’它们就是重复的“本质相同”子序列。我们的算法通过sum_dp[‘a’] dp[5]覆盖了dp[2]相当于在最终累加sum_dp时只计入了以最后一个‘a’结尾的那些子序列。而以更早的‘a’结尾的子序列如果它本身不是其他更长子序列的结尾即它后面没有更大的字符那么它就被“丢弃”了这似乎有问题。让我们重新审视“本质不同”的定义。题目通常要求即使子序列在原串中的下标选择不同只要选出来的字符序列相同就视为同一个。例如字符串“aba”子序列选第一个和第三个字符“aa”与选第二个和第三个字符“aa”是同一个本质子序列。所以对于相同的结尾字符‘a’我们只应该计算一次所有可能的“前缀”加上这个‘a’形成的序列。而“前缀”是指原串中在这个‘a’之前的部分。因此对于同一个字符只有最后一次出现时它才能“代表”所有以该字符结尾的本质不同子序列。因为最后一次出现时它之前的前缀是最长的包含了所有可能的前序选择。所以用最后一次出现的dp值来代表这个字符的贡献是正确的。更直白的理解想象我们按顺序扫描字符串。当我们遇到一个字符ch时我们计算以这个位置的ch结尾的新子序列数量。这个数量取决于在它之前、且比它小的所有字符各自最后出现时所代表的子序列数量sum_dp[smaller_ch]。然后我们更新sum_dp[ch]为这个新计算的值。这意味着sum_dp[ch]始终表示基于当前已扫描的部分以字符ch结尾的本质不同上升子序列有多少种。当后面再次遇到ch时我们会用新的、更大的值覆盖它因为新的位置能形成所有旧位置能形成的子序列通过相同的前缀还可能形成一些新的因为前缀更长了。最终扫描完整个字符串后sum_dp[ch]就是整个字符串中以字符ch结尾的本质不同上升子序列总数。将它们加起来就是答案。这个思路非常巧妙将复杂度降到了O(26*n)对于长度1000的字符串也游刃有余。踩坑点重复计数最易错的就是对相同字符的处理。如果简单地对所有j i且s[j] s[i]的dp[j]求和当字符串有重复字符时会重复计算许多本质相同的子序列。初始化与答案dp[i]初始为1代表单个字符的子序列。最终答案不是dp数组的和而是sum_dp数组的和因为dp[i]可能被后续相同字符覆盖其贡献。数据范围结果可能非常大需要用long long。这道题是动态规划中状态设计和去重的经典案例理解其背后的原理比背下代码更重要。6. 试题E玩具蛇深度优先搜索与回溯算法“玩具蛇”是一道经典的深度优先搜索DFS回溯题目也常被称为“网格哈密顿路径计数”问题。题目通常在一个4x4或类似大小的网格上要求放置一条长度为16即填满所有格子的“蛇”蛇身不能交叉或重叠需要计算有多少种不同的摆放方案。蛇头起点可以任意选择。6.1 问题建模与搜索策略我们可以把4x4的网格看成16个格子。题目等价于在16个格子的图中找出一笔画不重复经过任何点覆盖所有格子的路径总数。因为蛇的每一节必须与前一节在网格上相邻上下左右。算法选择DFS 回溯。因为我们需要枚举所有可能的路径。状态表示用一个4x4的bool数组visited记录格子是否已被占用。路径蛇的当前长度len。当前蛇头所在的坐标(x, y)。搜索过程初始化遍历16个格子每个格子都作为起点蛇头进行一次DFS。DFS函数dfs(x, y, len)如果len 16说明找到一条完整路径方案数ans返回。否则标记当前(x, y)为已访问。向四个方向上、下、左、右探索下一个格子(nx, ny)。如果(nx, ny)在网格内且未被访问则递归调用dfs(nx, ny, len1)。回溯在递归返回后取消当前(x, y)的访问标记以便尝试其他路径。6.2 代码实现与优化#include iostream #include cstring using namespace std; const int N 4; bool vis[N][N]; int ans 0; int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; void dfs(int x, int y, int step) { if (step N * N) { ans; return; } vis[x][y] true; for (int i 0; i 4; i) { int nx x dirs[i][0]; int ny y dirs[i][1]; if (nx 0 nx N ny 0 ny N !vis[nx][ny]) { dfs(nx, ny, step 1); } } vis[x][y] false; // 回溯 } int main() { for (int i 0; i N; i) { for (int j 0; j N; j) { // 以每个格子为起点开始搜索 memset(vis, 0, sizeof(vis)); // 每次搜索前清空访问标记 dfs(i, j, 1); // 起点算第一步 } } cout ans endl; return 0; }重要优化利用对称性4x4网格具有对称性旋转、镜像。以(0,0)为起点搜索得到的路径数和以(0,3)、(3,0)、(3,3)为起点的是相同的通过对称变换。同样(0,1)和(1,0)、(1,3)、(2,0)等位置也是对称的。我们可以只计算几个不对称等价类的起点方案数然后乘以相应的对称位置数量从而大幅减少DFS调用次数。更进一步的优化是“剪枝”如果当前剩下的空格子与当前蛇头位置不连通即无法一笔画走完那么可以提前终止搜索。但这需要额外的判断实现稍复杂。对于4x4的规模朴素的DFS已经可以在可接受时间内几秒内完成。个人实战经验在竞赛中遇到这种规模较小的搜索题格子数16如果时间允许写一个干净、正确的暴力DFS是性价比很高的选择。先确保拿到分再去想优化。我当时的做法就是直接暴力DFS在本地运行了大概几秒钟出结果。在代码正确的前提下这种“暴力美学”往往是可靠的。当然提交前要确认一下时间限制。如果格子更大比如5x5就必须考虑对称性剪枝或更高级的搜索优化如Meet-in-the-Middle了。7. 其他题目掠影与备赛建议由于篇幅所限无法对当年所有题目都进行如此详细的拆解。但其他题目也各有特点例如可能涉及大型模拟与文件读写要求从文件中读入复杂格式的数据进行多步骤处理最后输出。这类题考察代码的稳健性和细心程度。贪心或思维题需要先证明或直觉出一个贪心策略然后实现。往往代码简单但想通策略是关键。动态规划优化状态转移方程比较清晰但数据范围大需要用滚动数组、斜率优化等技巧来降低空间或时间复杂度。回顾整场国赛给我的核心启示是基础为王动态规划、深度/广度优先搜索、数论基础、字符串处理、排序与查找这些是构成大部分题目的基石。务必做到对经典模型如背包问题、LIS、网格DFS/BFS、质数筛法的代码了如指掌。细节决定成败很多题目失分不是算法不会而是边界条件没处理好如数组越界、整数溢出、特殊情况没考虑如空串、极值、输出格式错误。编码时养成“防御性编程”习惯对输入数据的范围保持警惕多用long long仔细阅读题目描述中的每一个字。时间分配策略国赛题量不小合理的时间分配至关重要。我的建议是先用较短时间比如30-40分钟通读所有题目对难度和类型有个大致判断。然后从最简单的、最有把握的题开始做快速建立信心和分数基础。遇到卡壳的题不要死磕超过30分钟可以先写下部分思路或暴力代码标记后去做其他题。最后留出时间检查已做题的输入输出和边界情况。调试与验证编写代码时同步思考一些小的测试用例包括常规情况、边界情况最小输入、最大输入、特殊情形全相同、递增、递减。对于填空题如果可能用暴力程序或数学计算进行交叉验证。心态调整国赛现场压力很大。遇到难题时深呼吸回顾一下题目涉及的知识点尝试将其分解为更小的子问题。即使不能AC争取拿到部分分比如写出正确但超时的算法也是胜利。蓝桥杯国赛不仅仅是一场编程能力的比拼更是对心理素质、策略选择和基础扎实程度的全面检验。希望这篇针对2020年B组C/C国赛的复盘能帮助你更好地理解竞赛题目的出题思路和解题技巧。真正的提升来自于对每一道做过的题进行深度总结和举一反三。祝你在未来的比赛中取得理想的成绩