信息学竞赛普及组C组模拟赛复盘：基础算法与失分点全解析

2020年4月15日我参加了信息学竞赛普及组模拟赛C组的第26场。说实话当时选这场不是为了刷排名而是想用一套难度相对可控的题目认真测一测自己的基础算法到底牢不牢。C组在整个模拟赛体系里属于偏向入门阶段的组别题目不追求偏、难、怪更多是看你能否稳定处理模拟、排序、搜索、简单动态规划这些常规考点。如果你也在准备普及组或者刚开始练复赛真题这篇总结里的题解思路、失分分析和复盘方法应该都能直接用上。这次我拿到了290分左右放进大半个赛季里不算亮眼但赛后我把四道题重新做了一遍发现丢分的每一处都很有代表性值得展开说一说。1. 比赛概况与整体策略1.1 C组模拟赛的定位与参赛目的先说清楚C组的定位。模拟赛通常会按水平分成A、B、C几档A组题目往往偏向提高组难度B组适中C组则更贴近普及组初学者的知识范围。C组不会故意用冷门算法卡人考察重点集中在进制转换、排序与贪心、图遍历、线性DP这些高频知识点上。我参加这场的目的有三个第一验证自己能不能在3小时内稳定完成前两题第二检查搜索和DP的代码实现是否熟练而不是只会看题解第三训练比赛节奏尤其是面对不会做的题时能不能果断跳过去。C组第26场是在一个常规训练周期里进行的前面已经连续刷了不少模拟题所以这次更多是当一次阶段测验为后续专项复习提供依据。1.2 3小时怎么拆时间分配的现场还原模拟赛时长3小时共4道题。按我的经验比较合理的时间切分是这样的题目目标类型计划用时实际耗时最后得分T1进制转换15分钟18分钟100T2活动安排25分钟40分钟90T3最大连通块40分钟55分钟60T4网格路径计数50分钟45分钟40这个表格已经很说明问题T1算是稳住了T2在排序比较逻辑上反复琢磨严重超时导致T3时间被挤压只写出了主流程、漏了边界情况。所以整体节奏并不是“题目做不完”而是“中间卡壳后没有及时止损”。我给自己定的规则是一道题连续调试超过20分钟没有进展立刻放下去做下一题能拿的部分分。事实证明这条规则执行得不够彻底T2就消耗了太多时间。1.3 本场难度曲线与得分分布四道题难度是逐级抬升的但抬升的幅度很平缓。T1属于纯送分T2需要一点贪心直觉T3考验遍历算法和细节处理T4则是典型的动态规划入门题。理论上认真准备过普及组基础算法的人T1和T2应该拿满T3拿满分也不难T4至少能写出部分分。从得分分布也能看到自己的真实水平边界前两题合计190分说明常规题型基本掌握了但尚未达到“闭眼全对”的火候后两题100分说明搜索和DP不是不会而是现场做题时缺少对边界条件和复杂度取舍的提前判断。普及组拿奖拼的往往是前两题但想要分数有竞争力后面两题至少要有完整解题能力这正是我下一步要解决的问题。2. 逐题复盘四道题的核心算法与易错点2.1 T1 进制转换看似送分处处是坑T1题面按常见套路是这样的给定一个非负整数X和一个进制K其中K在2到16之间要求输出X在K进制下的表示。X为0也必须正常输出。核心做法很简单不断用X除以K将余数转换为对应字符最后倒序输出。关键是处理余数大于等于10的情况需要用A到F表示以及X等于0的特判。大部分人会写一个while循环循环条件是X大于0但忘记X为0时应该直接输出0于是样例只要不包含0这个问题就完全暴露不出来。if (x 0) { cout 0 \n; return 0; } string s; while (x 0) { int d x % k; if (d 10) s.push_back(char(0 d)); else s.push_back(char(A d - 10)); x / k; } reverse(s.begin(), s.end()); cout s \n;这段代码看起来简单实际写的时候容易出三个问题一是字符转换时忘记ASCII偏移量二是倒序处理做成了正序拼接三是K进制下数字的每一位计算方式不熟。我建议新手每次写进制转换都用几组特殊数据自测比如0转成任意进制、10转成16进制、255转成16进制覆盖正数和字母混合情况。2.2 T2 活动安排贪心策略的选择依据T2是一类经典区间问题给N个活动的开始时间和结束时间要求选出尽量多的活动使它们互不重叠并且一个活动结束后可以立刻开始下一个活动。这题的通用解法是按结束时间从小到大排序然后从左往右扫描只要当前活动的开始时间不小于上一个选中活动的结束时间就选择当前活动。为什么一定要按结束时间排序而不是按开始时间或持续时间排序我一开始也踩过这个坑总想着开始越早的越先选后来发现一个活动如果开始很早但跨度很长会占用大量时间反而不如选若干个短的活动划算。按结束时间排序可以保证每一步留下的剩余时间尽可能多这是贪心能成立的关键。sort(a 1, a n 1, cmp); int last 0, cnt 0; for (int i 1; i n; i) { if (a[i].s last) { cnt; last a[i].e; } }这题我拿了90分扣在排序比较逻辑上。写自定义比较函数时如果不小心把结束时间相等的情况处理成按开始时间降序会影响同样结束时间下一组活动的选择顺序在特殊数据下会出问题。还要注意“开始时间等于结束时间”算不算重叠题意如果允许无缝衔接判断条件就用大于等于不允许则用大于。这类细节读题时就要确认不能靠猜。2.3 T3 最大连通块BFS与DFS的取舍T3给了一个M行N列的0/1矩阵要求找出所有由1组成的四连通区域中面积最大的那个是多少。思路很直接遍历每一个点遇到没访问过的1就进行一次搜索把所有相邻的1都标记同时统计个数最后更新最大值。实现上我强烈建议用BFS而不是DFS。矩阵规模如果达到1000乘1000DFS递归深度可能非常深很容易栈溢出即使不崩溃递归调用本身也比BFS慢。BFS用队列做逻辑清晰代码也容易调试queuepairint, int q; q.push({x, y}); vis[x][y] 1; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; while (!q.empty()) { auto [cx, cy] q.front(); q.pop(); cnt; for (int i 0; i 4; i) { int nx cx dx[i], ny cy dy[i]; if (nx 1 || nx m || ny 1 || ny n) continue; if (vis[nx][ny] || grid[nx][ny] 0) continue; vis[nx][ny] 1; q.push({nx, ny}); } }这题我只拿了60分问题出在标记访问的时机。最开始我把vis[x][y]放在出队时代码里也就是从队列弹出时才标记这会导致同一个点被相邻的多个点重复加入队列最坏情况下队列里全是重复元素运行时间会显著变大。正确做法是在入队前立刻标记。另外矩阵输入的行列顺序也是经典坑点题面说M行N列读入和循环时容易写反结果样例能过、大数据全错。对这类题建议把行列变量名分开比如用rowCnt和colCnt而不是简单用n和m。2.4 T4 网格路径计数动态规划入门题T4题面很标准从网格左上角出发只能向右或向下走中间有一些障碍物不能经过求到达右下角的不同路径数量结果需要对一个较大质数取模。这题如果用DFS暴力搜索每个点都可能往后延伸两条分支复杂度接近指数级矩阵范围稍大就会超时。正确做法是动态规划用dp[i][j]表示从起点走到第i行第j列的方案数。由于只能向右和下走到达某个点的方案数等于从上方来的方案数加从左侧来的方案数即dp[i][j]dp[i-1][j]dp[i][j-1]。遇到障碍物则dp值直接为0。for (int i 1; i n; i) { for (int j 1; j m; j) { if (blocked[i][j]) dp[i][j] 0; else if (i 1 j 1) dp[i][j] 1; else dp[i][j] (dp[i-1][j] dp[i][j-1]) % MOD; } }我最开始写这题时只想到递推公式却忽略了第一行和第一列的初始化。实际上第一行只能从左往右走第一列只能从上往下走一旦某个位置是障碍它后面所有位置都不可达必须把dp值清成0。另一个容易错的地方是取模时机有些选手只在最后取模中间计算爆掉了int范围导致答案变成负数。正确习惯是每一步都取模并且必要的时候用long long。2.5 本场知识点对普及组考纲的映射复盘完四道题可以明显看出普及组复习的侧重点。这里整理一张知识点映射表方便大家对照自己的薄弱项题号核心考点考查能力对应复习方向T1进制转换基础模拟、循环与字符处理数学推导、字符串处理T2区间贪心排序算法、贪心正确性贪心证明、排序自定义规则T3二维矩阵遍历BFS/DFS、空间与时间取舍搜索专项、队列使用T4网格路径DP状态设计、边界初始化线性DP、递推方程这张表对我的最大提示是普及组的总知识面其实很窄不需要追求难题怪题但每个高频考点都必须达到能“快速默写”的程度。这个“快速默写”不是背代码而是看到题面就能判断出考点、写出框架、然后集中精力处理边界。3. 失分原因与常见Bug实录3.1 藏在样例里的边界条件模拟赛和正式比赛中样例往往都是“友好型”数据专门为了让新手能跑通。比如T1的样例大概率会给一个普通正整数不会特意去测X等于0T4的样例大概率也会避开起点就是障碍这种极端情况。我丢分的重灾区几乎都集中在这些样例没有覆盖的边界上。处理边界条件最有效的方法是在写完代码后主动构造边界数据自测。我常用的边界数据清单包括最小数值、最大数值、0值、重复值、空数组、单元素数组、全障碍网格等。针对T1至少要测一次X0针对T4至少要测一次起点为障碍、终点为障碍、第一行中间有障碍这种特殊情况。3.2 数组越界与初始化问题数组越界是新手最容易犯、也最隐蔽的错误。比如T3里如果行列范围没看清矩阵大小开成全0访问时就会出现越界本地跑可能没事评测机上结果随机。初始化问题在T4里暴露最明显没有把dp数组全部初始化为0也没有处理起点格子的初始值导致递推过程中出现随机垃圾值。我现在的习惯是每道题都先确认数据范围然后按最大范围再留一点余量来开数组。比如最大N是1000就开成1005或1010避免访问1到N之外还要看判别。所有用到的数组在开始处理前都用一个循环显式清零再按实际情况赋值不要依赖全局变量默认清空。3.3 超时的七成原因是重复计算T3里面如果把访问标记放在出队时队列会存在大量重复节点导致同样的点被处理多次这就是重复计算T2如果不知道要排序直接在原顺序上两两判断复杂度会是O(N²)N一大就超时T4如果坚持用DFS递归枚举所有路径更是会直接指数爆炸。赛后我反复想很多超时并不是算法选错而是“看着能跑”的暴力方案没有被提前否掉。正确做法是看到数据范围后先估算复杂度如果N是10的5次方O(N²)基本不可能过如果矩阵是1000乘1000O(N²)也有风险要往线性或NlogN方向想。复杂度估算不是竞赛的高阶能力而是保底技能普及组想拿奖必须先过这一关。3.4 常见错误速查表把本场出现的错误整理成一张速查表下次比赛前翻一翻能省下不少调试时间错误现象可能原因建议处理输出多个前导0循环条件没有特判0先独立处理X0排序后答案不对排序键选错或比较符写反按结束时间升序相等时稳定次要条件BFS超时或栈溢出出队时才标记/递归过深入队时标记尽量使用BFS路径数出现负数中间结果溢出int使用long long并逐步取模样例能过但提交全WA行列读反或数组开小用变量名区分按最大范围开数组并测试边界这样做成对照表比自己对着报错信息猜要高效得多。每次模拟赛后把新遇到的错误类型补充进去等于给自己建了一个专属的避坑手册。4. 三种有效的自查与排错技巧4.1 小数据手算验证法程序写完不一定正确尤其是看着逻辑没问题的时候。我常用的验证方法不是直接提交而是构造一个非常小的数据用手算推演一遍再和程序输出对照。以小数据作为例子T4可以构造一个3乘3的网格中间加一个障碍然后自己在纸上写出dp表看程序输出是否一致。这种方法有几个好处数据规模小能逐行检查循环逻辑手动计算能倒逼自己真正理解算法过程而不是靠感觉手算过程还能发现代码里的坐标偏移问题。很多人比赛时不敢“浪费时间”手算结果提交后全WA再回头调试浪费的时间更多。程序员的直觉告诉我宁可多花两分钟自测也不要赌样例能代表一切。4.2 对拍脚本的实用写法日常训练中对拍是一个非常实用的工具。对拍的意思是写一个能确保正确但可能较慢的标准程序再写一个待验证的优化程序用随机数据不断比较两者输出是否一致。如果结果不一致就说明优化程序出错了而且还能拿到一组最小复现数据。for ((i1; i10000; i)); do ./gen in.txt ./std in.txt std.txt ./my in.txt my.txt if ! diff -q std.txt my.txt; then echo 找到差异测试编号: $i break fi done其中gen是随机数据生成器std是暴力的标准程序my是你要检查的程序。比赛现场不可能做对拍但平时练习时一定要用它能把T3那种“标记时机错误”在几分钟内暴露出来比自己用几十组手写数据测试快得多。4.3 时间复杂度估算与STL选择很多选手对时间复杂度没有概念只会在超时后干瞪眼。这里给一个实用参考表数据规模可承受复杂度常用做法N≤20O(2^N)或O(N!)状态压缩、全排列枚举N≤100O(N^3)简单动态规划、Floyd思想N≤1000O(N^2)双重循环枚举N≤10^5O(NlogN)排序、二分、堆N≤10^6O(N)线性扫描、队列把复杂度估算养成习惯后看到题目就不会盲目上暴力。关于STLT2的sort、T3的queue是高频工具sort自定义比较函数必须熟练queue的push、pop、front、empty四件套也要形成肌肉记忆不要现场翻文档。4.4 模块化代码与注释习惯平时我会把代码分成几个函数读入、处理、输出。这样调试时可以在关键位置输出中间变量也不会把逻辑搅成一团乱麻。T3的BFS部分和T4的DP部分让它们各自成为一个独立函数后续想打印队列状态或dp表时改动只影响局部不用重写整个程序。注释也不能省。不需要写长篇大论但要在关键步骤旁标一句话说明。比如在“vis[x][y]1”旁边写“入队前标记防重复入队”下次再看到这段代码就知道为什么这样写。比赛时注释还能帮自己快速回忆思路不至于读到一半忘了当时的想法。5. 赛后复盘与下一阶段备赛思路5.1 每次比赛结束后必须做的事比赛结束后第一件事不是看排行榜而是趁热打铁把四道题重新做一遍。我给自己定的顺序是先不看题解独立把没AC的题补到AC再对照题解审视自己的解法看是否有更优思路最后整理错因把新学到的边界条件写进个人错题本。这个过程最忌讳的是“只重做不总结”。重做只能证明你看懂了题解总结才能保证下次遇到同类题时不犯同一个错误。我一般会用几个关键词记录错因比如“T3失利关键词BFS标记时机、行列顺序”。这些关键词比大段文字更容易在赛前快速扫一眼。5.2 根据本场问题定补强计划本场暴露的问题集中在三块贪心排序的细节、BFS的标记时机、DP的边界初始化。针对性地定计划比盲目刷题更有效。我计划用一周时间每天做两道区间贪心类题目重点是写对自定义排序条件和区间重叠判断再刷三到四道矩阵遍历题练习BFS并刻意把每个点的访问标记时机提前到入队时DP则从“路径计数”这一类简单题起步先熟悉状态定义再逐步增加限制条件。补强计划要具体到题型和数量但不能排得太满。每天能稳定保证一到两小时的专注训练比周末突击五小时效果好得多。我宁可每天少做一点也要求自己能彻底讲清楚每道题的推导过程用“教别人”的方式检验理解程度。5.3 容易被忽略的赛场习惯复盘不只是看算法还要看比赛习惯。我整理了几个容易被忽略、但影响很大的细节第一数据范围要写在代码注释开头防止做到一半忘记限制。第二养成先做T1和T2的习惯不要在难题上死磕太久正如本场T2超时后T3就跟着遭殃。第三每写完一题花30秒确认输入输出格式尤其注意是否有空格、换行、大小写要求输出格式不过关题解再对也拿不到分。另外平时训练就要用比赛用的编译方式和环境不要依赖本地特有功能。提交前检查一遍是否读入正确、是否忘记去掉调试输出这些看起来都是小事但每一条都可能在关键时刻改变整场比赛的分数。等我把这四题完整复现、把那些边界条件重新整理了一遍之后发现最值钱的不是“这题我学会了”而是“我以后看到什么条件会下意识警惕”。看到进制转换就想到0看到区间活动就按结束时间排看到大矩阵就优先用BFS并注意入队标记看到网格路径就想到DP初始化。这种条件反射就是靠一场场模拟赛练出来的。下次再参加模拟赛我不求分数一次飞涨只求别在同一类坑上摔第二次。