NOIP普及组模拟赛复盘：从DP到并查集的算法补强指南

5月2日的NOIP普及组模拟赛编号C组31是我在训练平台上参加的一场相当有参考价值的摸底。赛前一周我刻意压缩了训练量只做了模拟题和简单DP的专题为的是把基本分拿稳赛后才意识到这种“稳”其实掩盖了一堆边角问题。这篇文章不打算只列个分数交差而是把四道题从读题、试错到最终写出来的过程完整翻一遍把卡壳原因和正解思路放在一起顺便还原一下考场上的时间流和心态波动供同样在普及组段位挣扎的人对照自查。1. 赛前准备状态与四题得分总览1.1 赛前我复习了什么目标是什么赛前那几天我的复习思路很清楚普及组四题前两题基本是模拟和简单思维题后两题往往考搜索、DP或者基础图论。我给自己定的目标是T1、T2必须拿满T3能拿部分分就满足T4完全看临场反应。所以我把大部分时间花在数组计数、字符串处理和经典背包问题上刻意没有复习并查集和最小生成树总觉得这类题目放在普及组压轴频率不高而且真的遇到也可以现场推。这个判断在考试前半段还算成立到T4就狠狠打脸了。现在复盘我最大的问题不是某个算法不会而是对知识模块的“优先级排序”过于依赖猜题没有把常见考点铺开。模拟赛的意义就在于此分数是次要的它能把你的弱点从“可能不会”变成“确定不会”。1.2 四题得分与耗时对照表这场模拟赛是传统OI赛制四道题每题100分总分400。我的最终得分是245分放在同组别里属于中游偏上但丢分点非常集中T2浪费了太多时间却没拿满T4则是典型的会一半写一半最后卡在细节上。题目满分我的得分耗时主要问题T1 仓库盘点10010015分钟无T2 区间重复点1006045分钟走了暴力路线正解思路晚了一步T3 丰收之路1004040分钟DFS转DP不及时边界初始化出错T4 串联岛屿1004550分钟Kruskal主体会写但合并细节暴露了不熟练从表格可以看出我的时间分配非常不均衡。T2这种思维题花了45分钟本来应该控制在25分钟以内T3写DFS时已经意识到不对劲却还坚持调了一会儿最后草草改成DP边界又出了问题T4虽然留了50分钟但真正静下来思考并查集细节的时间不到20分钟。整场下来不是“不会做”而是“每个环节都慢半拍”。2. T1和T2复盘稳定拿分与思维跨越2.1 T1 仓库盘点模拟题的默认心态T1的题面很简单仓库里有n件货物每件货物有一个重量值w统计重量落在0~50、51~80、81~120、121~200、200以上五个区间内的货物数量。这就是一道非常典型的普及组签到题没有任何陷阱唯一要注意的是区间边界不要写错尤其是“200以上”这个区间到底包不包含200。我的做法是开一个长度为5的计数数组读入每个重量值后用if-else判断区间对应下标加1最后输出。整个过程15分钟包括读题、写代码、检查样例。这种题在比赛里拿满分的意义不只是那100分更重要的是它能帮你建立手感把键盘上的状态调整好。我见过有的选手在T1上磨蹭半小时反复改输入格式实际上完全没有必要只要题目给了样例先把样例跑通再手推一组边界数据验证区间就足够了。给新手一个建议T1不要追求“最简写法”要追求“一次写对”。比如区间判断用if-else虽然啰嗦但比一堆复杂的数学表达式更不容易错。如果要在比赛里争分简单直接比炫技重要得多。2.2 T2 区间重复点暴力之外的第一个正解T2是我这场比赛第一个真正卡壳的地方。题目是给定一个长度为n的序列a再给m次询问每次询问一个区间[l, r]要求判断这个区间内是否存在两个相同的数。数据范围是n和m都是10^5。看到题的第一反应是暴力对每次询问从l到r逐个检查。显然最坏情况下是O(n×m)即10^10级别肯定超时。但我一开始没有立刻去优化而是想“是不是可以用一个set每次把区间元素丢进去查重”。这个思路比纯暴力好一点但每次询问都要重建set仍然是O(n×m)的复杂度而且常数更大。卡了一会儿之后我意识到题目的关键不是“这个区间里有哪些数”而是“这个区间里是否存在某个数的两次出现”。于是我想到了预处理对于每个位置i记pre[i]为上一个和a[i]相同的数的下标如果不存在就记为0。那么询问[l, r]是否存在重复元素就等价于在i∈[l, r]中是否存在某个pre[i] ≥ l。这个转化是整道题的核心也是我当时在考场上没有完全想透的地方。我虽然想到了pre数组但接下来却不知道如何快速判断“区间内pre[i]的最大值是否≥l”。当时我对线段树和ST表都不熟脑子里没有“区间最大值查询”这个现成工具于是只好写了个暴力去查导致T2只拿了60分。正解其实很自然预处理pre数组后用ST表或线段树维护pre数组的区间最大值。每次询问直接查询区间[l, r]的最大值如果最大值≥l说明存在重复输出“是”否则输出“否”。查询复杂度可以做到O(1)或O(logn)整体复杂度O(nm)完全能过。核心代码如下#include bits/stdc.h using namespace std; const int N 100005; int n, m, a[N], pre[N]; unordered_mapint, int last; int st[N][20], lg[N]; int query(int l, int r) { int k lg[r - l 1]; return max(st[l][k], st[r - (1 k) 1][k]); } int main() { scanf(%d%d, n, m); for (int i 1; i n; i) { scanf(%d, a[i]); pre[i] last.count(a[i]) ? last[a[i]] : 0; last[a[i]] i; st[i][0] pre[i]; } for (int i 2; i n; i) lg[i] lg[i / 2] 1; for (int k 1; (1 k) n; k) for (int i 1; i (1 k) - 1 n; i) st[i][k] max(st[i][k - 1], st[i (1 (k - 1))][k - 1]); while (m--) { int l, r; scanf(%d%d, l, r); printf(query(l, r) l ? Yes\n : No\n); } return 0; }考后我重新想了一遍发现自己卡住的原因很典型我试图用一个数据结构直接维护“区间里有没有重复”却没有想到用pre数组把“重复”转化成“区间最大值”这种更标准的问题。这是典型的思维定势也是为什么模拟赛需要反复做。把这个转换记住之后以后遇到类似“区间内存在性判断”的题目方向就会清晰很多。3. T3和T4复盘DP与并查集的临场发挥3.1 T3 丰收之路从DFS到DP的弯路T3的题面是在一个n×m的农田网格里每个格子有一个收获值可能是负数。从左上角(1,1)出发每次只能向右或向下走走到右下角(n,m)求路径上格子收获值之和的最大值。n和m都不超过50。这题我一眼觉得可以DFS因为网格很小从起点到终点每步只有两种选择好像不会很多。但我忽略了一个关键事实路径长度是固定的nm-1步而每一步选择方向都会产生不同的路径总路径数是组合数级别的当nm50时这个数大得离谱DFS根本不可能跑完。我在考场上先写了DFS测小样例能过心里还挺高兴。直到我构造了一个20×20的网格试了试程序明显卡住我才意识到必须换思路。这时候距离我开始写T3已经过去了20分钟。正确的思路是动态规划。设dp[i][j]表示从(1,1)走到(i,j)的最大收获值转移方程为dp[i][j] max(dp[i-1][j], dp[i][j-1]) a[i][j]这个转移不需要考虑后效性因为每个格子只能从上方或左方过来。需要注意边界条件比如第一行只能从左边过来第一列只能从上边过来。还有一个很容易踩的坑如果收获值存在负数那么不存在的路径不能简单初始化为0否则会把“根本走不到”的格子当成收益为0的合法路径导致最终答案虚高。正确做法是把所有dp初始化为负无穷然后单独设置dp[1][1]a[1][1]再逐行逐列转移。我当时就是栽在这个边界初始化上。因为把整个dp数组初始化为0遇到全负数数据时自己构造的测试点输出是0但正确答案应该是某个负数。考完我在本地调试时才发现这个bug最终T3只靠若干常规样例拿了40分。这道题的教训很直白看到网格图只能向下向右求最优第一反应应该是DP而不是DFS。DFS不是不行但要先算复杂度普及组常考的搜索题目一般数据范围不会超过20一旦数据到50基本就是在提示你用DP。另外所有涉及到负数的题目初始化一定要谨慎用负无穷而不是0。3.2 T4 串联岛屿Kruskal实现中的细节陷阱T4是一道图论题有n个岛屿给出m条可以修建的桥梁每座桥有一个修建费用。另外还有h座已建成的桥费用看成0。要求用最少的费用把所有岛屿连通输出最小的总费用。数据范围是n≤1000m≤10000。看到“连通所有点”和“最小费用”很自然想到最小生成树。Kruskal的流程我也知道把边按费用从小到大排序然后用并查集维护连通性依次尝试加入每条边如果两个端点不在同一个集合里就合并同时累加费用。问题出在实现细节上。我犯的第一个错误是没有先把已建成的桥合并进并查集。我把它们当成普通边丢进排序数组这样确实也能得到正确答案但白白增加了排序和遍历的边数。更重要的是我没有意识到已建成的桥在并查集里处于一种“已经选中的边”的状态应该最先处理否则在构造数据时很容易出现重复合并的问题。第二个错误是并查集的合并写得有问题。我写的是“如果两个点不在同一个集合里就把两个集合合并同时累加答案”但合并时只更新了父节点没有处理秩数组。在数据随机的情况下这个错误不会立刻暴露但一旦出现链状的边find函数的递归深度就会变大程序出现栈溢出风险。这里的正确写法是路径压缩加按秩合并int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void unite(int x, int y) { x find(x); y find(y); if (x y) return; if (rk[x] rk[y]) swap(x, y); fa[y] x; if (rk[x] rk[y]) rk[x]; }第三个问题是我在遍历排序后的边时没有设置“已经选了n-1条边就提前结束”的退出条件。虽然这不会影响答案正确性但在边很多的时候会浪费大量时间导致最后几组较大的数据跑得异常缓慢。这道题最终拿了45分主要扣分集中在并查集合并细节和超时上。复盘之后我发现图论基础算法看起来会但一旦离开“教科书模板”到了需要自己处理已建边、重复边、边界条件的时候各种细节就全漏出来了。这提醒我考前复习不能只看算法思想一定要把模板题亲手写三遍以上并且针对各种边界情况构造测试。4. 整场比赛时间线里的卡壳时刻4.1 从开场到交卷各时段决策回顾比赛是从下午开始的前30分钟属于热身阶段。T1写得很顺15分钟完成并检查通过算是给整场开了一个好头。紧接着进入T2我的节奏就开始乱了。我在“用一个set暴力”和“用pre数组但不知道怎么查询区间最大值”之间反复横跳前前后后改了三次思路最后灰溜溜写回暴力。当比赛时间来到第60分钟时我甚至还没开始写T3。第60到100分钟我在T3上经历了一场“先DFS后DP”的自我拉扯。写DFS花了15分钟测试小样例用了5分钟发现卡死后又想了几分钟怎么改最后才开始重新写DP。DP写完后又因为初始化问题跟代码较劲到第100分钟时T3才勉强交了一个“可能有问题”的版本。第100到150分钟是T4的时间。读完题我就知道要用Kruskal但写并查集时反复检查fa数组初始化、排序结构体定义等细节加上没有在已建桥上果断合并写写停停最终在比赛结束前10分钟交了代码最后几分钟只够检查T1的输入输出格式。交完卷看到评测结果的那一刻其实已经能预感到T2、T3、T4各有各的问题都是“时间不够了”导致的典型症状。4.2 失分原因归类知识性、习惯性、心态性把T2、T3、T4的丢分放在一起看大致可以分成三类。知识性失分主要出现在T4并查集的秩数组处理、提前退出这类“模板外的细节”说明我对图论基础算法的理解停留在“能默写”而不是“能应变”的水平。习惯性失分出现在T3DFS写成习惯以后没有养成先估算复杂度再动手的条件反射白白葬送了至少15分钟。心态性失分则贯穿整场T2一旦卡住我潜意识里就一直惦记着那道题写T3的时候脑子里还在想T2的pre数组导致两边都没写好。这三类问题里知识性问题最容易被发现也最好解决习惯性和心态性问题才是真正拉开差距的地方。比如T2如果我能接受“先用暴力拿部分分回头再做优化”的节奏而不是死磕到思维僵化至少能把心态稳住给后面的题目留出更从容的思考空间。5. 这场比赛给我列出的补强清单5.1 知识模块哪些优先补哪些顺带补这场比赛结束后我给自己列了一张优先级清单。第一优先的是并查集和最小生成树因为T4已经明确暴露了问题必须把模板题练到条件反射。第二优先的是ST表、线段树这类“区间查询工具”T2正解说明我的数据结构工具箱太浅至少要掌握“区间最大值/最小值”的常见维护方式。第三优先的是负权DP的边界处理这个虽然是小知识点但在T3上造成了实质丢分必须通过构造负值样例来强化。顺带要补的是搜索与DP的复杂度估算。严格来说这不是某个知识点而是一种做题习惯动手写代码之前先算一下最坏情况的规模超过10^7就要停下来换思路。这个习惯比多刷几道题更能直接避免考场上的时间浪费。5.2 比赛习惯三个必须改的动作第一所有涉及负数的题目初始化一律用负无穷而不是0这个规则可以作为默认习惯写进代码模板。第二写完代码后必须手动构造一组极端小数据尤其是n1、m1、全是负数、全是相同数这类边界不能只看样例过了就算完。第三如果一道题超过20分钟还没有实质性进展立刻停止优化先写一个暴力版本拿部分分标记“待优化”然后进入下一题。这三条我在后面的模拟赛里逐一执行效果相当明显。5.3 下一次模拟赛前的准备模板我从这次模拟赛里总结出一个赛前准备模板先花一天把常考模板题全部重写一遍包括快速幂、并查集、最短路径、简单DP、ST表然后做两三套往年真题练手感最后一天不练新题只复盘错题。这个模板不一定适合所有人但方向是对的——模拟赛的价值不是排名是暴露问题暴露问题之后不去解决下一次还会在同样的地方跌倒。最后再分享一个小习惯每次模拟赛后当天不要急着对答案先凭记忆把四道题里自己“卡住但不完全不会”的题目重新想一遍写下当时的困惑点再去翻题解。这个“延迟对答案”的过程能让你更清楚自己的思维瓶颈在哪里比直接看题解有效得多。C组31这套卷子对我来说最大的收获就是逼我正视了这些平时不太愿意承认的问题。