1. 从“国赛B组”说起一次算法竞赛的实战复盘最近整理硬盘翻到了2021年参加蓝桥杯国赛的代码和笔记。那一年C/C大学B组的题目现在回头看依然能感受到赛场上的那种紧张和烧脑。很多朋友尤其是正在备赛的学弟学妹经常问我有没有当年的题解网上能找到的要么是零散的代码片段要么是过于简略的思路缺少那种“手把手带你过一遍”的临场感。所以我决定把当年的解题过程结合这几年做项目和带学生的经验完整地复盘一次。这不仅仅是一份“答案”我更想分享的是在有限的时间里面对一道陌生的题目如何快速分析、设计、编码和调试的完整思考链路。无论是为了备战下一届蓝桥杯还是单纯想提升自己的算法实战能力相信这份来自“战场一线”的回顾都能给你带来一些不一样的启发。2. 国赛B组试题的整体印象与策略选择那年的国赛B组题目给我的第一感觉是“稳中有变侧重思维”。它没有在冷门的数据结构上刁难人但几乎每道题都对问题转化、数学建模和边界处理提出了不低的要求。我记得开考后我花了大概15分钟快速浏览了所有题目A到J共10道并做了一个简单的策略分级第一梯队必须拿下通常是前几道填空题和基础编程题。这类题往往思路直接考察基本语法和经典算法如排序、查找、简单DP。目标是快速、准确地拿分为后面难题争取时间。第二梯队争取高分中段的编程大题。题目描述可能稍长涉及中等难度的算法如BFS/DFS、贪心、动态规划、简单数论等。需要仔细设计避免掉入陷阱。第三梯队挑战与突破最后两道左右的压轴题。往往综合性强可能需要组合多种算法或者有非常巧妙的思维点。时间充裕则攻坚否则先保证前面题目的正确性。对于B组而言目标不是AK全部做对而是在有限时间内拿到尽可能高的分数。因此合理的策略比死磕一道题更重要。我的习惯是看到题目先预估一个“信心指数”和“耗时指数”优先做信心高、耗时短的。比如一道有清晰递推关系的DP题即使代码量稍大但因为思路明确也属于优先处理范围。注意蓝桥杯是OI赛制没有实时反馈提交后才知道对错。所以编写代码时的严谨性和自测能力至关重要。一定要自己构造一些边界数据最小、最大、特殊值进行测试不能依赖“感觉对了”。3. 核心题目详解思路、代码与避坑指南由于无法完全还原原题我将根据常见的题型和当年考后讨论的热点模拟几道具有代表性的题目进行拆解。我会重点讲清“为什么这么想”以及“怎么实现才不容易错”。3.1 典型填空题日期计算与数位处理这类题是送分题但也是“送命题”因为细节极多。模拟题例计算从2000年1月1日到2021年12月31日之间有多少个日期其年月日数字连起来的8位数如20211231是一个完全平方数思路拆解问题转化核心是枚举日期并检查其拼接数字是否为完全平方数。直接枚举所有日期大约是365*22 ≈ 8000天计算量很小暴力枚举完全可行。关键点1日期枚举。如何正确、不重不漏地枚举所有日期自己写闰年判断和月份天数循环容易出错。一个稳健的方法是使用编程语言自带的日期库或者从起点日期开始一天一天地加。在蓝桥杯环境中C可以用tm结构体和mktime但更简单的是自己实现一个“天数累加器”。关键点2数字拼接。将年、月、日整合成一个整数。例如year2021, month12, day31拼接成20211231。公式为num year * 10000 month * 100 day。这里要注意月份和日期小于10时需要补零否则2021-1-1会变成202111而非20210101。所以更安全的做法是num year * 10000 month * 100 day这个公式本身要求month和day必须是两位数所以在计算前需要确保它们以两位形式存在或者直接用sprintf格式化成字符串再转整数。关键点3完全平方数判断。给定一个整数num判断其是否为完全平方数。最直接的方法是int s sqrt(num); return s*s num;。但这里有个巨坑sqrt的参数和返回值都是浮点数存在精度误差。对于较大的整数比如本题的8位数sqrt的结果可能因为浮点误差导致s*s与num在比较时出错。绝对安全的做法是进行整数域的二分查找或者使用long long类型计算s*s再比较。参考代码实现 (C)#include iostream #include cmath using namespace std; // 判断闰年 bool isLeapYear(int year) { return (year % 4 0 year % 100 ! 0) || (year % 400 0); } // 获取某年某月的天数 int daysOfMonth(int year, int month) { if (month 2) { return isLeapYear(year) ? 29 : 28; } if (month 4 || month 6 || month 9 || month 11) { return 30; } return 31; } // 安全的完全平方数判断整数二分法 bool isPerfectSquare(long long num) { if (num 0) return false; long long left 0, right num; while (left right) { long long mid left (right - left) / 2; long long square mid * mid; if (square num) { return true; } else if (square num) { left mid 1; } else { right mid - 1; } } return false; } int main() { int count 0; // 枚举日期2000-01-01 到 2021-12-31 for (int year 2000; year 2021; year) { for (int month 1; month 12; month) { int days daysOfMonth(year, month); for (int day 1; day days; day) { // 拼接成8位数注意补零逻辑已内置于整数运算中因为month和day是整数我们需要的是数值不是显示 // 但为了确保是8位对于month和day小于10的情况拼接时相当于在十位补了0例如 1月 - 01 在计算中就是 1 但 year*10000 1*100 day 等价于 year*10000 100 day 这会把1月变成100而不是1。所以必须显式补零。 // 更清晰的做法直接计算数值 long long num year * 10000 month * 100 day; // 错误2021年1月1日会变成202111而不是20210101 // 正确做法 long long num year * 10000 month * 100 day; // 这仍然是错的因为1月用1表示而不是01。 // 必须用num year * 10000 month * 100 day; 的前提是month和day已经是两位数格式。所以我们不能直接用循环变量。 int month_display month; int day_display day; // 实际上我们需要的是两位数的数值意义所以应该用 // long long num year * 10000 month * 100 day; // 这行是原错误逻辑 // 修正重新计算拼接整数 long long num year * 10000 month * 100 day; // 仍然不对 // 正确计算拼接值 long long num year * 10000 month * 100 day; // 错误根源在于1月1日 month1, day1, 得到20210101 我们算一下2021*1000020210000, 1*10020210100, 120210101。 咦对了因为1*100就是100相当于在月份位填了“01”中的“1”在百位不对20210101是两千万我们的计算是年份占4位月份占2位日期占2位。 year*10000 把年份放到了千万位和百万位前四位 month*100 把月份放到了百位和十位中间两位day放到了个位和十位不对day是个位数时只占了个位。所以2021年1月1日2021*1000020210000, 1*10020210100, 1 20210101。完美我之前的顾虑是多余的。这个计算对于1~9的月份和日期自动实现了“补零”的数值效果因为乘100和加个位数的组合正好构成了两位数的数值表示。所以最初的公式是对的浮点误差才是真坑。 // 因此只需要用这个公式然后进行安全的完全平方判断即可。 long long num year * 10000 month * 100 day; if (isPerfectSquare(num)) { count; // 可以输出查看一下 // printf(%04d%02d%02d\n, year, month, day); } } } } cout count endl; return 0; }避坑指南日期枚举务必自己实现或严格测试闰年和月份天数的逻辑。一个错误的daysOfMonth函数会导致结果全盘皆输。整数溢出拼接后的8位数最大约为99991231在int范围内约21亿但计算平方时mid * mid可能溢出int所以相关变量建议使用long long。浮点误差这是最隐蔽的坑。在竞赛中凡是涉及开根号后取整或比较的一律使用整数二分法来避免精度问题这是血泪教训。补零逻辑仔细验证数值拼接公式像上面代码中的自我质疑和验算过程在考场上最好在草稿纸上完成确保逻辑无误。3.2 动态规划DP问题状态定义与转移方程DP是蓝桥杯的常客B组通常不会考特别复杂的状压DP但线性DP和背包DP的变形是重点。模拟题例给定一个长度为N的整数数组你可以进行最多K次操作每次操作可以选择一个数将其乘2。问最终数组的最大和是多少思路拆解贪心尝试第一反应可能是每次选最小的数乘2这样增长幅度最大。这对吗对于正数数组这显然是正确的。但如果数组中有负数呢乘2会使负数的绝对值变大更负从而减少总和。所以我们需要分类讨论核心思想是让操作带来的收益最大化。问题转化一次操作对于一个数a[i]带来的收益是a[i]因为a[i]*2 - a[i] a[i]。所以每次操作应选择当前数组中最大的正数如果存在因为它的收益最大。如果没有正数全是非正数那么操作只会让和变小所以最优策略是一次也不操作如果操作必须进行K次则选择绝对值最小的负数使其负面影响最小。动态规划视角但题目可能更复杂比如K次操作不一定全用在同一个数上因为一个数被多次乘2后收益即该数当前的值会变化。例如数组[3, 4] K2。贪心第一次选4-8收益4数组变[3,8]第二次选8-16收益8总收益12。但如果第一次选3-6收益3数组变[6,4]第二次选6-12收益6总收益9。不如贪心。然而如果初始是[1, 10], K2。贪心第一次10-20收益10第二次20-40收益20总收益30。如果先操作11-2收益12-4收益2总收益3远小于30。所以贪心每次选当前最大值似乎是正确的。更严谨的DP定义我们可以定义dp[i][j]表示考虑前i个数使用了j次操作时能达到的最大和。但转移方程需要考虑每个数可以被操作多次。这类似于“分组背包”每个数是一个物品组组内有K1种选择操作0次、1次...k次但不超过K。状态转移方程为dp[i][j] max(dp[i-1][j - t] a[i] * (1 t))其中t是对第i个数进行的操作次数0 t min(j, 某个上限)。 这里a[i] * (1 t)是操作t次后该数的值。时间复杂度为O(N * K * K)如果K不大比如几百是可以接受的。优化与实现实际上对于这种“每个元素独立操作次数可分配”的问题有一个更优的解法使用优先队列最大堆。初始将所有数放入堆中。进行K次操作每次取出堆顶当前最大值将其乘2后再放回堆中。最后求和。这本质上是贪心但正确性需要证明可以使用“差值法”或反证法。在竞赛中对于此类直观的贪心题目如果想不到严谨证明在时间紧迫时可以基于样例和直觉先实现贪心并通过大量随机数据对拍DP暴力解法来验证。参考代码实现 (C 优先队列贪心版)#include iostream #include queue #include vector using namespace std; int main() { int N, K; cin N K; priority_queuelong long pq; // 最大堆 long long sum 0; for (int i 0; i N; i) { long long x; cin x; sum x; pq.push(x); // 这里push的是原始值注意我们贪心的是“当前值” } // 进行K次操作 for (int i 0; i K; i) { if (pq.empty()) break; long long top pq.top(); pq.pop(); long long new_val top * 2; sum sum - top new_val; // 更新总和减去旧值加上新值 pq.push(new_val); } cout sum endl; return 0; }避坑指南贪心正确性这是本题的关键。如果题目明确所有数为正贪心无疑。如果包含负数上述贪心就不对了。务必仔细审题明确数据范围。如果题目没说正数则需要用DP来保证正确性。数据范围与溢出操作后数值可能翻倍很多次a[i] * (1 t)很容易超出int范围必须使用long long。DP的复杂度如果采用DP要估算N*K*K是否超时。通常蓝桥杯B组N和K在10^3级别O(N*K^2)可能达到10^9会超时。这时就需要优化或者寻找贪心策略。3.3 搜索与图论路径与状态遍历B组常考DFS/BFS可能是迷宫问题也可能是更抽象的状态搜索。模拟题例在一个N x M的网格中每个格子有一个数字0-9。你从左上角(0,0)出发每次可以向右或向下移动一格目标是到达右下角(N-1, M-1)。求所有路径中路径上格子数字连起来形成的数字串其对应的整数能被一个给定的数P整除的路径有多少条结果对1e97取模。思路拆解暴力DFS最直接的想法是DFS所有路径每走到终点就检查数字串对应的整数能否被P整除。但路径总数是组合数C(NM-2, N-1)当N, M达到20左右时路径数巨大必然超时。动态规划这是一道典型的“数字DP”或“带模数的路径计数DP”。难点在于路径形成的数字串是不断拼接的我们不能保存整个数字串会太大必须在过程中维护其对P取模的结果。状态定义定义dp[i][j][r]表示走到格子(i, j)时路径数字串对应的整数对P取模余数为r的路径数量。状态转移假设我们从(i-1, j)上方走到(i, j)上一步的余数为r_prev格子(i, j)的数字为d。那么新的数字串相当于旧的数字串末尾添加了一位数字d。如果旧数字串对应的整数为X则新整数为X * 10 d。因此新的余数r_new (r_prev * 10 d) % P。同理从左边(i, j-1)转移过来也是一样。 转移方程dp[i][j][r_new] (dp[i][j][r_new] dp[i-1][j][r_prev]) % MODdp[i][j][r_new] (dp[i][j][r_new] dp[i][j-1][r_prev]) % MOD其中对于每个来源状态dp[i-1][j][r_prev]和dp[i][j-1][r_prev]r_new (r_prev * 10 grid[i][j]) % P。初始化起点(0,0)路径数字串就是grid[0][0]本身所以dp[0][0][grid[0][0] % P] 1。答案dp[N-1][M-1][0]即到达终点时余数为0的路径数。参考代码实现 (C)#include iostream #include vector using namespace std; const int MOD 1e9 7; int main() { int N, M, P; cin N M P; vectorvectorint grid(N, vectorint(M)); for (int i 0; i N; i) { for (int j 0; j M; j) { cin grid[i][j]; } } // dp[i][j][r] vectorvectorvectorlong long dp(N, vectorvectorlong long(M, vectorlong long(P, 0))); // 初始化起点 dp[0][0][grid[0][0] % P] 1; for (int i 0; i N; i) { for (int j 0; j M; j) { if (i 0 j 0) continue; // 起点已初始化 int d grid[i][j]; for (int r 0; r P; r) { long long ways 0; // 从上方转移 if (i 0) { int r_prev_from_up (r - (d % P) P) % P; // 逆向推导出上一步的余数 // 更直接的方式在上一步的循环中计算新的余数。这里我们换一种写法在遍历当前r时计算从上一步哪些r_prev能转移过来。 // 实际上更高效的写法是遍历上一步的所有r_prev计算新的r_new并累加。 } } } } // 上面的转移写法有点绕。更清晰的写法是遍历所有格子对于每个格子遍历所有余数r_prev更新它所能到达的下一个格子的状态。 // 重新写一个清晰的版本 vectorvectorvectorlong long dp2(N, vectorvectorlong long(M, vectorlong long(P, 0))); dp2[0][0][grid[0][0] % P] 1; for (int i 0; i N; i) { for (int j 0; j M; j) { int d grid[i][j]; for (int r 0; r P; r) { long long cur dp2[i][j][r]; if (cur 0) continue; // 没有路径到达当前状态跳过 // 向右走 if (j 1 M) { int new_r (r * 10 grid[i][j1]) % P; dp2[i][j1][new_r] (dp2[i][j1][new_r] cur) % MOD; } // 向下走 if (i 1 N) { int new_r (r * 10 grid[i1][j]) % P; dp2[i1][j][new_r] (dp2[i1][j][new_r] cur) % MOD; } } } } cout dp2[N-1][M-1][0] endl; return 0; }避坑指南取模运算状态转移中的(r * 10 d) % P是核心务必确保计算顺序和取模正确。C中负数取模可能得到负数所以当涉及减法时要(a % P P) % P来确保非负。空间与时间DP状态数是N * M * P。如果N, M在50左右P在100左右状态数就是25万可以接受。如果更大需要考虑优化例如P很大时可能要用其他方法。初始化起点的状态要小心处理。一条“路径”在起点时数字串就是第一个数字本身。方向限制题目规定只能向右或向下这保证了DP的无后效性可以按行或列顺序遍历。3.4 数学与数论思维巧解国赛B组往往有一道题需要一些数学洞察力。模拟题例定义f(x)为x的十进制表示中每个数字的平方和。例如f(123) 1^2 2^2 3^2 14。给定一个正整数n求有多少个不超过n的正整数x满足x能被f(x)整除。思路拆解暴力法遍历1到n计算每个x的f(x)判断x % f(x) 0。时间复杂度O(n * log10(n))。当n很大比如10^9时必然超时。寻找规律/缩小范围f(x)的值域是有限的。对于一个d位的数字f(x)最大是d * 9^2 81d。对于10^9以内的数最多10位f(x)最大不超过810。这是一个非常重要的上界问题转化我们不是要枚举x而是要枚举f(x)的可能值s1 s 810。对于每一个s问题变成有多少个不超过n的正整数x满足f(x) s且x % s 0。数位DP这是一个经典的数位DP问题。我们需要统计[1, n]区间内满足两个条件的数的个数1) 数位平方和为s2) 数本身模s余0。 定义DP状态dp[pos][sum][mod][isLimit]表示pos: 当前正在处理第几位从高位到低位。sum: 当前已处理的数位平方和。mod: 当前数已处理部分对目标s取模的结果。isLimit: 是否受到n的当前位限制如果前面几位都和n一样那么当前位不能超过n的对应位。算法流程外层循环枚举s(1 到 810)。对于每个s使用数位DP计算满足f(x)s且x % s 0的x的个数。将所有s的结果累加。复杂度枚举s最多810次每次数位DP的状态数约为位数(10) * sum上限(s) * mod上限(s) * 2 ≈ 10*810*810*2 ≈ 1300万但实际sum和mod的上限是s平均下来远小于这个值且可以通过记忆化搜索避免重复计算在合理剪枝下可以在规定时间内运行。参考代码框架 (C 数位DP)#include iostream #include cstring #include vector using namespace std; long long dp[11][825][825][2]; // pos, sum, mod, isLimit vectorint digits; int target_sum; // 当前枚举的s long long dfs(int pos, int sum, int mod, bool isLimit) { if (pos digits.size()) { // 所有位处理完 return (sum target_sum mod 0) ? 1 : 0; } if (!isLimit dp[pos][sum][mod][isLimit] ! -1) { return dp[pos][sum][mod][isLimit]; } long long res 0; int up isLimit ? digits[pos] : 9; for (int d 0; d up; d) { int new_sum sum d * d; if (new_sum target_sum) continue; // 剪枝平方和已经超过目标s后续只会更大 int new_mod (mod * 10 d) % target_sum; res dfs(pos 1, new_sum, new_mod, isLimit d up); } if (!isLimit) { dp[pos][sum][mod][isLimit] res; } return res; } long long solve(long long n, int s) { target_sum s; digits.clear(); while (n) { digits.push_back(n % 10); n / 10; } reverse(digits.begin(), digits.end()); // 高位在前 memset(dp, -1, sizeof(dp)); return dfs(0, 0, 0, true); } int main() { long long n; cin n; long long ans 0; for (int s 1; s 810; s) { // 81 * 10 810 ans solve(n, s); } cout ans endl; return 0; }避坑指南状态定义与初始化数位DP的记忆化数组dp其维度含义一定要清晰。isLimit这个维度必须参与记忆化因为受限制和不受限制情况下后续的选择空间完全不同结果也不同。剪枝if (new_sum target_sum) continue;这个剪枝能大幅提升效率因为平方和一旦超过目标s就不可能满足条件了。模运算new_mod (mod * 10 d) % target_sum;这里是对target_sum即s取模因为我们要判断x % s 0。注意s可能为0吗题目中x是正整数f(x)至少为1因为至少有一位数字所以s从1开始枚举。时间复杂度虽然枚举s有810次但数位DP记忆化后对于不同的s状态空间是独立的需要重新初始化dp数组。总体计算量不小但对于n 10^9在蓝桥杯的环境下通常时间限制2秒左右经过优化是可以过的。如果n更大可能需要进一步优化。4. 考场实战策略与调试技巧理解了题目怎么做在考场上如何高效地把它变成分数是另一门学问。代码模板准备赛前准备好常用算法的代码模板如快速幂、并查集、Dijkstra、素数筛、数位DP框架等。但切记模板是工具理解才是根本。考试时一定要根据题目具体修改模板不能生搬硬套。输入输出与测试多用scanf/printf在C中对于大量数据输入输出scanf/printf比cin/cout快得多。可以在主函数开头加ios::sync_with_stdio(false); cin.tie(0);来关闭同步提升cin/cout速度但混用scanf/cin可能导致问题建议统一用一种。文件测试在本地编写代码时一定要将样例输入复制到in.txt文件使用重定向 (freopen(“in.txt”, “r”, stdin)) 进行测试。比赛提交时记得注释掉这行。构造边界数据样例过了不代表对了。要自己构造最小情况如N1, M1、最大情况题目给的数据上限、特殊值如全0、负数、递增/递减序列。调试与查错输出中间变量这是最朴素的调试方法。在怀疑的逻辑点输出关键变量的值看是否符合预期。** rubber duck debugging**如果一时找不到错可以尝试向“橡皮鸭”或者自己默念解释你的每一行代码在干什么。很多时候在解释的过程中自己就能发现逻辑漏洞。对拍对于不确定的题目可以写一个绝对正确但效率低的暴力程序O(n^2)或枚举用随机数据生成器产生大量小规模数据分别用你的优化程序和暴力程序跑对比结果。这是发现算法逻辑错误的大杀器。时间管理先易后难拿到题目先快速判断难度把有把握的、代码量小的先做完。敢于放弃如果一道题卡了30分钟以上还没有清晰思路先标记去做其他题。全部有把握的题目做完后再回头攻坚。检查最后至少留出20分钟检查。重点检查文件名、类名、输入输出格式、数组大小、初始化、边界条件、取模运算、long long溢出。特别是填空题答案可能就一个数字一旦写错前功尽弃。回看2021年的那场比赛最大的感触是基础知识和思维灵活度同样重要。很多题目披着复杂的外衣内核依然是基础的算法思想。备赛时与其盲目刷偏题怪题不如把枚举、排序、二分、贪心、DFS/BFS、DP、简单数论和字符串处理这些基础算法练到肌肉记忆。在考场上冷静分析把复杂问题分解成你熟悉的小模块才是取胜的关键。希望这份迟到的“题解”能成为你备赛路上的一块有用的垫脚石。