1. 从一道填空题看算法竞赛的思维转变最近在整理历年算法竞赛的真题翻到了2020年蓝桥杯国赛C B组的填空题部分。和很多刚接触竞赛的同学一样最初我也觉得填空题就是“送分题”把答案算出来填进去就行比后面的大题编程简单多了。但真正静下心来研究这几道题才发现它们恰恰是检验一个选手基础是否扎实、思维是否灵活的试金石。填空题没有过程分答案对就是全对错就是零分这种“一锤定音”的特性要求我们在解题时必须有极高的准确性和对问题本质的深刻理解。今天我就结合这几道题和大家聊聊在算法竞赛中尤其是面对填空题时应该如何构建解题思路以及从“暴力求解”到“数学优化”的思维跃迁过程。无论你是正在备赛的选手还是对算法感兴趣的开发者相信这些从真题中提炼出的经验都能让你有所收获。2. 真题回顾与核心考点拆解2020年蓝桥杯国赛C B组的填空题通常有2-3道虽然题目描述可能不长但每一道都指向一个或几个核心的算法与数学知识点。我们不能仅仅满足于得到答案更要明白题目背后在考察什么。下面我将对可能出现的题型进行归类和分析并给出通用的解题框架。2.1 典型题型一日期与模拟计算这类题目往往涉及闰年判断、星期几计算、日期合法性验证等。例如给出一个起始日期和经过的天数要求计算目标日期或者计算两个日期之间的间隔再或者像“高斯日记”这类经典问题。其核心考点是模拟计算的准确性和边界处理能力。解题心法统一时间基准在处理日期时一个非常实用的技巧是选择一个固定的“锚点日期”比如公元1年1月1日将所有日期都转换为距离该锚点的天数。这样日期差计算就变成了简单的整数减法。模块化函数务必编写独立的、经过充分测试的辅助函数。至少包括isLeapYear(year): 判断闰年。四年一闰百年不闰四百年再闰daysOfMonth(year, month): 返回某年某月的天数。dateToDays(year, month, day): 将日期转换为累计天数。daysToDate(days): 将累计天数转换回日期。警惕边界在循环累加天数或进行日期回推时要特别注意月份和年份的进位与借位。最好的方法是利用上面提到的“天数转换法”避免直接操作年月日带来的复杂逻辑。注意蓝桥杯的填空题答案通常是数字或特定格式的日期直接提交字符串可能判错务必看清题目要求的输出格式例如20201120。2.2 典型题型二数论与整数性质这是填空题的“大户”可能考察最大公约数(GCD)、最小公倍数(LCM)、质数判断、质因数分解、同余运算、快速幂等。题目可能伪装成其他形式比如“寻找满足某种条件的最小整数”、“某个数的幂的最后几位是多少”等。解题心法GCD/LCM的灵活应用记住公式LCM(a, b) a * b / GCD(a, b)。对于多个数可以两两求解。这类问题常与“周期”、“相遇”等场景结合。质数筛法的选择判断单个大数是否为质数可以用试除法遍历到sqrt(n)。如果需要找出一个范围内比如1e6以内的所有质数埃氏筛或欧拉筛线性筛是必备技能。欧拉筛的效率更高能在线性时间内完成。快速幂模运算当题目要求计算a^b mod m且b很大时比如b 1e9直接计算会溢出且超时。快速幂模板必须熟练掌握其核心思想是二分幂次将时间复杂度从O(b)降至O(log b)。// 快速幂取模 (a^b % mod) 的典型实现 long long fastPow(long long a, long long b, long long mod) { long long result 1; a % mod; // 初始取模防止后续乘法溢出 while (b 0) { if (b 1) { // 如果b的二进制最低位是1 result (result * a) % mod; } a (a * a) % mod; // a自乘 b 1; // b右移一位相当于除以2 } return result; }2.3 典型题型三组合数学与排列计数“有多少种可能”、“有多少种方法”是这类题目的典型问法。可能涉及简单的排列组合公式、容斥原理、卡特兰数或者需要通过动态规划(DP)或DFS搜索来计数。解题心法先判断是否可直接公式计算如果问题结构清晰符合经典模型如从n个中选m个、插板法、错位排列等直接套用公式。但要小心数据范围可能需要用long long甚至高精度。DFS搜索计数当问题规模不大状态空间在1e6量级以内且难以直接推导公式时DFS是可靠的选择。关键是要设计好状态参数和递归边界并利用记忆化搜索避免重复计算极大提升效率。动态规划(DP)计数对于有“递推”性质的计数问题DP是更优解。定义dp[i][j]表示在某种状态下达到(i, j)的方案数然后寻找状态转移方程。填空题的DP通常维度不高但思维要缜密。2.4 典型题型四枚举与优化题目要求寻找满足多个条件的一个数或一组数。最直接的想法是暴力枚举但数据范围往往使得纯暴力会超时。这时就需要“优雅的暴力”即枚举剪枝或利用数学性质缩小枚举范围。解题心法分析数据范围与时间复杂度先估算最坏情况下的循环次数。如果超过1e8在竞赛的1秒时限内通常很危险。寻找枚举变量尽量枚举维度低、范围小的变量。有时可以通过等式变形将枚举两个变量转化为枚举一个变量。剪枝策略可行性剪枝当前部分解已经不可能构成最终解时直接返回。最优性剪枝在求最优解问题中当前解已经比已知最优解差时直接返回。数学约束剪枝利用题目中隐含的数学关系如整除、奇偶性、范围等大幅减少枚举量。3. 实战推演以一道虚构赛题为例为了将上述心法融会贯通我们不妨基于常见的考点虚构一道有代表性的填空题并一步步推演解题过程。题目描述定义一种运算F(n)对于正整数nF(n)表示将n的所有数字十进制按从小到大排序后得到的新整数忽略前导零。例如F(3210) 123F(2024) 224F(1000) 1。 现在对于一个正整数k我们定义数列a_ia_1 ka_{i1} F(a_i)。 可以证明该数列从某一项开始会进入循环。记S(k)为该数列中不同数字的个数即直到开始循环前的所有项加上循环节内的项去重后的数量。 求S(2020)的值。解题推演理解题意与模拟验证首先我们必须完全理解F(n)和数列的定义。拿例子验证a_1 2024,a_2 F(2024)224,a_3 F(224)224... 从第二项开始就恒定不变了循环节就是[224]。S(2024)就是{2024, 224}两个不同数字所以是2。再试32103210 - 123 - 123S2。试43214321 - 1234 - 1234S2。看起来很简单别急k2020可能不同。设计算法框架核心是模拟数列生成并检测循环。这是一个经典的弗洛伊德判圈法或哈希表记录的应用场景。方法一哈希集合用一个unordered_setint记录所有出现过的a_i。不断计算a_{i1} F(a_i)并检查a_{i1}是否已在集合中。如果存在说明遇到了循环起点此时集合的大小就是S(k)。这种方法直观且不易错。方法二快慢指针节省空间但实现稍复杂对于填空题必要性不大。实现关键函数F(n)int F(int n) { string s to_string(n); sort(s.begin(), s.end()); // 处理前导零排序后0会在前面需要找到第一个非零字符 int start 0; while (start s.length() s[start] 0) { start; } // 如果全是0那么n本身就是0但题目说n是正整数所以这里start不会等于length string sorted_num s.substr(start); // 如果sorted_num为空理论上不会因为n0则返回0 return sorted_num.empty() ? 0 : stoi(sorted_num); }这里有个坑直接stoi(s)会把”00123“转换成123自动处理了前导零。但为了逻辑清晰显式处理是更好的习惯。模拟计算S(2020) 让我们手动或写个小程序模拟a1 2020a2 F(2020)。数字是2020排序后是0022去掉前导零是22。a3 F(22)。数字是2 2排序后是22。此时a3 a2循环出现。 数列为2020, 22, 22, 22, ...不同数字有{2020, 22}数量为2。所以S(2020) 2等等题目会这么简单吗这似乎和k2024没区别。我们可能低估了题目。让我们重新审视F(n)它排序的是所有数字。对于n1234F(1234)1234确实不变。但对于一些数变化可能不止一步。例如k5173随机举例5173 - 13571357 - 1357停了。 还是两步。我们需要找一个能产生更多不同项的k。尝试k9898:9898 - 8999(数字排序9,8,9,8 - 8,8,9,9)8999 - 8999停了。 两步。看起来F(n)操作具有很强的“收敛性”。因为排序后数字变得有序再应用F很可能不变。事实上只有当n的各位数字不是非降序排列时F(n)才会改变它。一旦n的各位数字是非降序的如123,224,8999F(n)n数列就稳定了。因此数列长度最多为2第一项是k第二项是F(k)从第三项开始就循环了。所以S(k)要么是1如果k本身各位就是非降序要么是2。2020的各位是2020不是非降序所以S(2020)2。经过这样一番推理我们甚至不需要写程序通过数学分析就得到了答案。但在考场上如果分析没把握编写一个可靠的模拟程序进行验证是绝对正确的选择。最终答案2。这道虚构的题目综合了模拟、数学观察和逻辑推理。它告诉我们面对填空题先通过小规模样例理解过程然后尝试寻找数学规律或不变性是最高效的路径。如果规律不明显再诉诸于稳健的编程模拟。4. 填空题的应试策略与常见“坑点”基于多年的刷题和教学经验我总结出以下几条应对蓝桥杯填空题的实战策略以及那些容易让你丢分的“坑”。4.1 时间分配与答题顺序填空题虽然单题分值可能不如编程大题但因其“全有或全无”的特性性价比很高。建议在比赛开始后用前20-30分钟快速浏览所有填空题。对于思路清晰的题目可以立即着手解决心算、草稿纸演算或编写小型测试程序。对于一时没有头绪的做好标记先跳过。切忌在一道填空题上耗费超过15分钟。4.2 验证答案的多种方法填空题的答案往往可以通过多种方式交叉验证这是确保正确性的关键。小数据验证用题目给的例子或自己构造的更小的、易手算的样例验证你的算法逻辑和程序输出。反向验证如果题目是求一个数有时可以将你的答案代入题目条件检查是否满足。估算验证对答案有一个大致的数量级估计例如是一个几位数末尾数字可能是几如果计算结果严重偏离估算立即复查。独立代码验证如果时间允许用不同的思路或另一种编程语言重写核心计算部分对比结果。4.3 高频“坑点”清单整数溢出这是C选手的“头号杀手”。计算中间结果特别是阶乘、组合数、连续乘积时即使最终答案在int64_t范围内中间过程也可能溢出。解决方案默认使用long long(int64_t)。在乘法前判断是否可能溢出if (a LLONG_MAX / b) { // 处理溢出 }。对于取模运算使用(a % mod) * (b % mod) % mod。浮点数精度填空题极少要求输出浮点数但如果涉及比较时不要用要用fabs(a-b) 1e-12这样的方式。尽量避免浮点数运算全用整数进行。边界条件日期计算中的闰年、2月29日循环的起始和结束值搜索或枚举时是否包含了所有情况n0或n1这类特殊输入。读题失误看错题目要求输出的格式是数字还是字符串是否需要补零误解关键定义比如“互质”和“质数”的区别。务必用手指或笔尖逐字阅读题目至少两遍。编译器差异在本地环境如Visual Studio和比赛环境通常为Linuxgcc下某些未定义行为的结果可能不同。例如对负数取模、vector未初始化就访问等。确保你的代码是标准且健壮的。5. 从填空题到编程题的思维桥梁很多人觉得填空题和编程题是割裂的其实不然。填空题锻炼的正是解决编程题核心模块的能力。一道编程大题往往可以分解为几个关键的子问题这些子问题的解法恰恰就是填空题的常见考点。编程题的数据预处理可能就是一个日期计算、质数筛选或者组合数预处理的填空题。编程题的核心算法可能是快速幂求模、GCD求最大公因数这些也是填空题的常客。编程题的优化关键编程题中决定你是否能通过全部测试数据的关键往往在于你能否想到填空题中那种“数学优化”或“巧妙枚举”从而将O(n²)的算法优化到O(n log n)或O(n)。因此认真对待每一道填空题深入理解其解法背后的原理就是在为你解决更复杂的编程题积累“武器库”和“思维模式”。当你拿到一个编程题能迅速识别出其中包含的“填空题型”子问题并套用成熟、高效的解法你的解题速度和正确率都会大幅提升。练习时我建议建立一个错题本不仅记录填空题的答案更要记录最初的错误思路是什么正确的突破口在哪里涉及了哪个知识点有哪些可以总结为模板或技巧如日期转换函数、快速幂模板、质数筛模板久而久之你会发现所谓的“灵光一现”其实都是这些扎实的基本功和模式识别能力在起作用。2020年的国赛填空题无论具体题目是什么其价值都在于引导我们进行这样一场思维的训练。希望这篇长文的分析框架和实战心得能帮助你在下一次比赛中更加从容地面对试卷上的那些“空白格”稳稳地将分数收入囊中。