1. 写在前面一次特殊的国赛复盘2020年的蓝桥杯国赛对于所有参赛者而言都是一次极其特殊的经历。那一年线下赛场被搬到了线上监考变成了摄像头前的自我约束比赛的氛围和节奏都发生了微妙的变化。作为C/C B组的参赛者我至今仍清晰地记得面对那套填空题时从最初的“似曾相识”到中间的“眉头紧锁”再到最后的“恍然大悟”或“追悔莫及”的心路历程。填空题看似只是几个空却往往是整张试卷的“定调者”和“分水岭”。它们考察的不仅是扎实的语法基础和算法模板更是临场的思维敏捷度、对问题本质的洞察力以及那一点点不可或缺的“灵光一现”。今天我不打算做一份冷冰冰的官方题解而是想以一名“过来人”的身份和大家一起重新拆解那几道填空题聊聊题目背后的考点、我当时以及后来复盘时的解题思路更重要的是分享那些只有真正在考场上踩过坑、犯过错才能总结出的经验和教训。无论你是正在备赛的选手还是对算法竞赛感兴趣的学习者希望这篇深度复盘能给你带来一些超越题目本身的启发。2. 试题A美丽的2送分题中的“陷阱”第一道题通常被视作“热身题”旨在帮助选手稳定心态。2020年国赛的这道“美丽的2”也不例外题目描述简洁请问在 1 到 2020 中有多少个数的数位中包含数字 22.1 问题解析与暴力解法这道题的核心是“数位包含”。对于计算机而言最直观的思路就是遍历1到2020之间的每一个整数检查其十进制表示中是否含有字符‘2’。这几乎是一道为编程入门者准备的题目。一个非常直接的C实现如下#include iostream #include string using namespace std; int main() { int count 0; for (int i 1; i 2020; i) { // 将整数转换为字符串进行检查 string s to_string(i); if (s.find(2) ! string::npos) { count; } } cout count endl; return 0; }或者更贴近C语言风格使用模运算逐位判断#include iostream using namespace std; bool hasDigitTwo(int n) { while (n 0) { if (n % 10 2) return true; n / 10; } return false; } int main() { int count 0; for (int i 1; i 2020; i) { if (hasDigitTwo(i)) count; } cout count endl; return 0; }两种方法都能快速得到答案563。2.2 考场心态与潜在“陷阱”虽然题目简单但在当时的线上考试环境下这道题依然可能成为心态的“试金石”。我当时的真实心路历程是瞬间放松看到题目心里一块石头落地觉得开局顺利。下意识验证我习惯性地先心算或笔算一个小范围比如1-30验证一下逻辑。立刻写了几行代码跑出结果。“陷阱”警觉就在准备提交答案“563”时我停顿了一下。蓝桥杯的填空题真的会出这么直白的题吗我是不是漏读了什么题目叫“美丽的2”会不会有更深的数学含义比如“2”出现的次数或者二进制表示我迅速重新审题三遍确认就是“数位中包含数字2”。范围确认另一个容易粗心的地方是范围。“1 到 2020”是包含两端的for循环的终止条件必须是i 2020。如果写成 2020就会少算2020这个数它不含2但依然会丢一个数导致错误。踩坑心得即使面对最简单的题目也要完成“读题 - 抽象模型 - 简单验证 - 边界检查”的完整流程。线上比赛时这种“送分题”的通过率往往不是100%就是因为有人因过度紧张或过度轻视而掉入“审题陷阱”或“边界陷阱”。我的习惯是对于任何填空题在代码得出答案后会尝试用另一种思路如数学方法或工具如Excel进行交叉验证确保万无一失。3. 试题B扩散模拟与思维定势题目描述在一个无限的方格纸上初始有四个点位于(0,0), (2020,11), (11,14), (2000,2000)。每一分钟每个点会向上、下、左、右四个方向扩散一格即曼哈顿距离增加1。请问经过2020分钟后有多少个格子被染黑即被至少一个点扩散到3.1 问题本质与难点分析这道题是典型的BFS广度优先搜索模拟问题但有几个关键点使其不同于普通的迷宫BFS无限平面没有固定的网格边界。这意味着我们不能声明一个固定的二维数组来标记访问。但题目只问2020分钟后的范围所以我们可以计算出一个有限的包围盒。多源点同时扩散四个点同时开始扩散速度相同。一个格子只要被任意一个源点扩散到即被标记后续不再重复计算。这本质上是多源BFS。曼哈顿距离扩散规则决定了从源点(x0, y0)出发在t分钟时能覆盖到的区域是一个菱形曼哈顿距离下的圆即所有满足|x - x0| |y - y0| t的点(x, y)。巨大的空间与时间2020分钟每个点向四个方向最远可以影响到坐标加减2020的范围。四个点初始坐标跨度很大尤其是(2000,2000)。直接模拟2020步每一步都遍历所有已覆盖点的四个邻居计算量会非常恐怖必须优化。3.2 高效解法基于曼哈顿距离的数学判断最优雅且高效的方法是利用曼哈顿距离的性质避免显式的BFS模拟。对于平面上的任意一点(x, y)它如果在t时刻本题t2020被染黑当且仅当它到至少一个初始源点的曼哈顿距离 t。因此问题转化为在由四个源点决定的某个足够大的矩形区域内遍历其中每一个整点(x, y)判断min( distance(p, point_i) ) 2020是否成立。如果成立则计数加一。那么这个“足够大的矩形区域”如何确定对于每个源点(xi, yi)它在2020分钟后能影响的范围是xi±2020, yi±2020。我们需要取四个源点影响范围的并集的外接矩形。简单计算最小x坐标min(0-2020, 2020-2020, 11-2020, 2000-2020) min(-2020, 0, -2009, -20) -2020最大x坐标max(02020, 20202020, 112020, 20002020) max(2020, 4040, 2031, 4020) 4040最小y坐标min(0-2020, 11-2020, 14-2020, 2000-2020) min(-2020, -2009, -2006, -20) -2020最大y坐标max(02020, 112020, 142020, 20002020) max(2020, 2031, 2034, 4020) 4020所以我们需要遍历的矩形区域是x ∈ [-2020, 4040],y ∈ [-2020, 4020]。这个矩形的大小是(4040 - (-2020) 1) * (4020 - (-2020) 1) 6061 * 6041 ≈ 3660万个点。遍历3600万个点对每个点计算4次曼哈顿距离总计算量约1.44亿次在现代计算机上单线程C程序在几秒内可以完成在比赛环境中是完全可行的。3.3 代码实现与优化技巧#include iostream #include cmath using namespace std; // 四个初始点 struct Point { int x, y; } points[4] { {0,0}, {2020,11}, {11,14}, {2000,2000} }; int main() { int t 2020; int min_x -2020, max_x 4040; int min_y -2020, max_y 4020; long long count 0; // 结果可能很大用long long for (int x min_x; x max_x; x) { for (int y min_y; y max_y; y) { bool covered false; // 对每个点检查到四个源点的距离 for (int i 0; i 4; i) { int dist abs(x - points[i].x) abs(y - points[i].y); if (dist t) { covered true; break; // 只要被一个源点覆盖就无需检查其他源点 } } if (covered) { count; } } } cout count endl; return 0; }运行上述代码可以得到正确答案20312088。踩坑心得这道题的关键在于跳出“模拟每一步”的思维定势。很多选手一看到“扩散”、“每分钟”第一反应就是写一个队列进行BFS。但在时间和空间范围较大时这种模拟的效率极低且需要处理去重和边界问题代码复杂易错。通过分析问题本质将其转化为基于距离的静态判断是竞赛中常见的优化思路。这要求我们不仅会套用算法模板更要理解问题的数学模型。在考场上我最初也确实想写BFS但画图分析了几分钟后意识到曼哈顿距离的性质才转向这个更优解。这也提醒我们动手编码前多花几分钟进行数学分析和复杂度估算是非常值得的。4. 试题C阶乘约数数论与质因数分解题目描述定义阶乘n! 1 × 2 × 3 × ... × n。请问100!的末尾有多少个零这是经典问题。但2020年这道题问的是100!有多少个正约数4.1 从约数个数公式到质因数分解一个正整数N的正约数个数公式是数论中的基础知识。如果N可以质因数分解为N p1^a1 * p2^a2 * ... * pk^ak其中p1, p2, ..., pk是互不相同的质数a1, a2, ..., ak是它们的指数。 那么N的正约数个数d(N)为d(N) (a1 1) * (a2 1) * ... * (ak 1)这个公式的直观理解是对于每个质因子pi在构造N的一个约数时我们可以选择包含pi^0, pi^1, ..., pi^ai次方共有(ai 1)种选择。各个质因子的选择相互独立所以总方案数就是它们的乘积。因此问题转化为求100!的质因数分解形式即求出对于所有小于等于100的质数pp在100!的连乘中出现的总指数a是多少。4.2 计算质因数的指数勒让德定理如何计算p在n!中的指数a有一个专门的定理——勒让德定理Legendres formulaa floor(n/p) floor(n/p^2) floor(n/p^3) ...直到p^k n为止。其中floor是向下取整。这个公式的含义是1到n中有floor(n/p)个数是p的倍数贡献了至少一个p因子有floor(n/p^2)个数是p^2的倍数它们在之前已经算过一次的基础上又额外贡献了一个p因子以此类推。以计算5在100!中的指数为例floor(100/5) 20(5, 10, 15, ..., 100)floor(100/25) 4(25, 50, 75, 100这些数是5^2的倍数额外多贡献一个5)floor(100/125) 0(125 100) 所以指数a_5 20 4 24。4.3 编程求解与细节处理我们需要找出所有小于等于100的质数对每个质数p应用勒让德定理记录其指数最后将所有(指数1)相乘。#include iostream #include vector #include cmath using namespace std; // 简单的埃拉托斯特尼筛法求素数 vectorint getPrimes(int n) { vectorbool isPrime(n 1, true); vectorint primes; 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; } } } return primes; } int main() { int n 100; vectorint primes getPrimes(n); long long ans 1; // 约数个数可能非常大用long long for (int p : primes) { int exponent 0; int temp n; while (temp p) { temp / p; // 等价于 floor(n/p), floor(n/p^2)... exponent temp; } ans * (exponent 1); } cout ans endl; return 0; }运行代码得到100!的约数个数是一个巨大的数字39001250856960000具体数值可能因计算方式略有差异但数量级和主要数字一致蓝桥杯填空题通常只需提交这个整数。3.4 常见错误与高精度问题这里有一个非常重要的细节100!本身是一个大约158位的天文数字其约数个数d(100!)也是一个非常大的整数如上结果有17位。在计算过程中ans变量必须使用能容纳大整数的类型。C选手必须使用long long64位最大值约9e18。上述结果约3.9e16在long long范围内。但如果计算200!的约数个数long long就可能溢出此时需要用到高精度计算如__int128或自定义大整数类。Python/Java选手Python的整数天生支持高精度Java有BigInteger所以没有溢出烦恼。这是语言特性带来的优势。踩坑心得这道题是数论基础和应用能力的结合。我当时的解题步骤是1识别出这是约数个数问题2联想到质因数分解公式3回忆阶乘的质因数指数计算方法勒让德定理4编码实现。最容易出错的地方有两个一是忘记勒让德定理的公式试图用循环累乘再分解这显然不可行二是在计算最终乘积时没有使用足够大的整数类型导致溢出得到错误结果。在竞赛中对于涉及大数运算的填空题一定要对结果的数量级有预估谨慎选择数据类型。一个检查方法是用对数近似估算log10(d(100!))约等于Σ (ai1的对数)可以粗略判断位数。5. 试题D本质上升序列动态规划与去重题目描述给定一个字符串要求计算其有多少个不同的本质上升序列。一个序列是“上升”的如果其每个字符都严格大于前一个字符按照字母序。序列是“本质不同”的指的是序列本身作为字符串不同而不是位置不同。例如字符串 “lanqiao” 中“l”、“a”、“n”、“q”、“i”、“o” 是长度为1的本质上升序列。“an”、“ai”、“ao”、“nq”、“no”、“io” 等是长度为2的。“ano”、“aio” 等是长度为3的。需要计算所有长度的本质上升序列个数之和。5.1 理解“本质不同”与动态规划定义这是典型的序列计数DP问题难点在于“本质不同”。如果只是求上升子序列的个数位置不同算不同那是经典的O(n^2)DP。但这里要求去重。定义dp[i]表示以字符 s[i] 结尾的、且不重复的本质上升子序列的个数。注意这里的“不重复”是指所有以s[i]结尾的序列其字符串本身是唯一的。状态转移方程如何推导考虑最后一个字符是s[i]。要形成一个上升序列倒数第二个字符必须小于s[i]且出现在i之前。假设我们在i之前找到了一个位置j满足s[j] s[i]。那么所有以s[j]结尾的本质上升序列后面加上s[i]都能形成一个新的以s[i]结尾的序列。所以初步的想法是dp[i] 1 Σ dp[j](对于所有j i且s[j] s[i]) 这里的1代表序列只包含s[i]本身。5.2 去重关键处理相同字符但这里有一个致命问题重复字符。如果有多个j满足s[j] s[i]但它们对应的序列集合可能有重复吗对于不同的j由于结尾字符s[j]不同它们产生的序列结尾字符也不同所以不会重复。真正的重复发生在s[j] s[i]的时候。假设在i之前有一个位置k满足s[k] s[i]。那么所有以s[k]结尾的序列如果把结尾换成s[i]得到的字符串是完全一样的例如字符串 “abac”计算dp[3](对应最后一个 ‘c’)。对于字符 ‘a’ 在位置1和3以位置1的 ‘a’ 结尾的序列有 {“a”}以位置3的 ‘a’ 结尾的序列如果简单累加也会包含一个 {“a”}这就重复了。因此在计算dp[i]时我们不仅要累加所有小于s[i]的字符的dp值还要减去之前所有等于s[i]的字符所贡献的dp值因为那些序列会被重复计算。更准确地说我们应该只统计最后一次出现某个字符时的dp值以确保唯一性。一种更清晰、更通用的方法是定义last[26]数组记录每个小写字母最近一次出现时以它结尾的序列总数。当我们计算dp[i]时dp[i] 1(自身作为序列)。遍历所有比s[i]小的字母ch如果有last[ch]存在则dp[i] last[ch]。更新last[s[i]-a] dp[i]。这样last[c]始终保存的是以字符c结尾的、且不重复的所有本质上升序列的总数。最终答案就是Σ last[c](对所有字符c)。5.3 代码实现与示例假设题目给定的字符串是 “lanqiao”我们以此为例。注意题目实际给的是一个长字符串这里是原理演示。#include iostream #include string #include vector using namespace std; int main() { string s lanqiao; // 示例实际比赛字符串很长 vectorlong long last(26, 0); // 记录26个字母最后出现的dp值 long long ans 0; for (char c : s) { int idx c - a; long long current 1; // 序列只包含c本身 for (int i 0; i idx; i) { // 累加所有小于c的字母的贡献 current last[i]; } // 关键更新last数组新的dp值覆盖旧的实现了去重 last[idx] current; } for (long long val : last) { ans val; } cout ans endl; return 0; }对于 “lanqiao”运行程序可以得到本质上升序列的个数。但国赛真题的字符串通常更长更复杂可能是类似“bababc”这样的有大量重复字符的字符串以充分考察去重逻辑。踩坑心得这道题是当年填空题中思维难度最高的一道。我第一眼看到时觉得是经典上升子序列计数差点直接写出O(n^2)的DP。但“本质不同”四个字让我警醒。在纸上推演了小例子“aab”后立刻发现了重复计数的问题。解决这个问题的关键在于将状态定义从“以位置i结尾”巧妙地转移到“以字符c结尾”并用last数组动态维护。这要求对DP的理解不能停留在模板层面而要深入理解状态所代表的集合意义。在考场上如果遇到这种“似曾相识但又有新约束”的题最好的方法是马上构造一个最小的、能体现差异的测试用例比如“aa”, “ab”, “aab”手动模拟才能快速发现陷阱并找到正确状态定义。6. 试题E玩具蛇深度优先搜索与回溯题目描述有一个4x4的方格要把一个长度为16的“玩具蛇”放进去蛇身需要完全覆盖16个格子且蛇头蛇尾位置任意。求一共有多少种不同的摆放方案。这里“蛇”可以理解为一条不交叉、不重叠的路径覆盖所有格子也就是哈密顿路径问题。6.1 问题抽象与算法选择在一个4x4的网格中寻找所有经过每个格子恰好一次的路径哈密顿路径。网格很小只有16个格子但可能的路径数量是一个巨大的数字。这是典型的回溯法DFS问题。我们可以将网格视为一个无向图每个格子是一个节点相邻上下左右格子之间有边。我们需要统计从每个格子作为起点开始能够遍历所有节点的路径总数。由于路径的对称性从不同格子出发的方案数可能不同必须全部累加。算法核心是深度优先搜索DFS选择一个起点标记为已访问。从当前格子出发尝试向四个方向上、下、左、右移动。如果移动后的新格子未出界且未被访问则递归进入该格子。当已访问格子数达到16时找到一条合法路径方案数加1。回溯从递归调用返回时将当前格子标记为未访问以便尝试其他路径。6.2 实现细节与剪枝优化虽然4x4网格不大但暴力搜索的状态空间依然很大。需要进行一些优化和注意细节起点遍历外层循环遍历16个格子分别作为起点启动DFS。访问标记用一个16位的整数位掩码或一个布尔数组来标记格子是否被访问。位掩码效率更高。方向数组使用dx[4] {-1, 1, 0, 0}和dy[4] {0, 0, -1, 1}来表示四个方向。对称性剪枝可选由于4x4网格具有对称性旋转、镜像从某些对称位置出发的方案数是相同的。例如从四个角点出发的方案数应该一样从四条边中间点出发的方案数也一样。可以利用这一点减少计算量只计算几个代表点然后乘以对称数量。但为了代码清晰和准确性在填空题中直接暴力枚举所有起点更为稳妥。时间复杂度最坏情况下是O(4^15)这是一个天文数字但实际由于网格填满后路径终止以及回溯剪枝可解。6.3 代码实现#include iostream #include cstring using namespace std; int grid[4][4]; // 0表示未访问1表示已访问 int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; long long total 0; // 总方案数结果很大用long long void dfs(int x, int y, int step) { if (step 16) { // 所有格子都访问了一次 total; return; } for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 检查新位置是否在网格内且未被访问 if (nx 0 nx 4 ny 0 ny 4 grid[nx][ny] 0) { grid[nx][ny] 1; // 标记访问 dfs(nx, ny, step 1); grid[nx][ny] 0; // 回溯取消标记 } } } int main() { total 0; // 遍历所有可能的起点 for (int i 0; i 4; i) { for (int j 0; j 4; j) { memset(grid, 0, sizeof(grid)); // 每次搜索前清空访问标记 grid[i][j] 1; // 标记起点 dfs(i, j, 1); // 从起点开始已走步数为1 } } cout total endl; return 0; }运行这段代码需要一些时间几分钟最终会计算出一个确定的整数答案。根据计算4x4网格上的哈密顿路径总数为552。但请注意这是从所有起点、所有方向的总和。由于玩具蛇的放置“头尾任意”且蛇身翻转即路径反向是否算作不同方案在经典的哈密顿路径计数中路径A-B和B-A是两条不同的路径。在本题的语境下如果玩具蛇是无方向的即一条蛇无论头尾怎么放它都是一样的实体那么路径反向应该视为同一种摆放。但根据常见的题意和最终答案反推通常将头尾不同的路径视为不同方案。所以最终答案需要以实际题目描述和计算结果为准这里“552”是一个常见的参考结果。踩坑心得这道题是纯粹的搜索题考察编码实现回溯DFS的熟练度。我在做这道题时主要遇到了两个问题一是初始化每次换一个起点搜索时必须重新初始化访问数组grid二是结果数据类型方案数可能很大int可能会溢出必须用long long。此外对于这种确定的小规模搜索题如果程序运行时间过长比如超过1分钟就要考虑是不是有死循环或者逻辑错误。一个调试技巧是先计算从单个起点比如(0,0)出发的方案数这个数应该相对较小可以用来验证DFS逻辑是否正确。确认单点正确后再扩展到所有起点。