这是一篇实战向的备赛记录整理。我直接按这段时间的真实刷题节奏来写覆盖了题型复盘、动态规划常见变体、图论易错点、踩坑记录和后续计划内容都是可复现的希望对正在准备算法竞赛的朋友有帮助。1. 这一阶段的刷题复盘题型覆盖与训练节奏这是备战蓝桥杯刷题学习记录的第6篇。进入这个阶段之后我的刷题重心从“什么都看一点”慢慢转成“把高频算法啃透”这两周时间主要集中在动态规划和图论两个大块顺带用模拟、二分、贪心保持手感。和前面几篇相比这半个月最大的变化是AC率提上来了但每道题的思考时间也在增加很多时候一道题需要反复改两三轮才能过这种状态其实比单纯追求刷题数量更有价值。如果你也在备赛尤其是刚把基础语法过完、准备往算法层面推进的话这篇记录里的题目类型、现场踩过的坑、整理好的模板可以直接拿来参考。我不打算罗列题号而是把“题型特征”和“解题套路”拆开讲因为蓝桥杯省赛的难度恰恰就体现在这里考的不是冷门算法而是把常见算法换一个包装让你在考场上快速识别出它原本的样子。1.1 这段时间主刷的三条线第一主线是动态规划。背包类题目我从01背包和完全背包开始过渡到分组背包、依赖背包然后补了区间DP和数位DP。动态规划的问题很容易一眼看懂题目、但一写就错所以我在每道题后面都补了一段“状态定义说明”哪怕代码只改了十行这个说明也能帮我下一次遇到同类题时快速找回思路。第二主线是图论与搜索。最短路、DFS记忆化、简单拓扑排序都有涉及。图论的代码本身并不算长难的是建模这一步题目里的“关系”“依赖”“连通”这些词要用图的语言转译过来。这个转译过程我会在后面的章节里专门举例子说。第三条线是基础算法保温。每天至少做一道模拟题或二分题不追求难度只为了保持对代码细节的敏感度。这类题往往不需要高级算法但特别容易因为粗心丢分比如读入格式、循环边界、多组数据的初始化。1.2 时间怎么分配才不会手忙脚乱我目前的训练安排是每天两到三小时分三段走。前20分钟翻前一天做错的题不看题解尝试自己重新写一遍。中间一小时做1到2道新题优先做自己刚学完的算法专项。最后30分钟整理笔记把今天接触到的状态定义、边界条件、容易踩的坑写下来。周末抽一个完整的下午做模拟训练用往年省赛真题限时2小时模拟真实考场的作答节奏。这个固定动作很重要因为平时刷题可以慢慢想但比赛时必须在有限时间内分配好每个题的取舍。我习惯先花3分钟扫一遍所有题目按难度简单排个序先把能稳拿分的题做掉再回头啃大题。这个策略在多次模拟中明显比按顺序做题更稳。2. 动态规划刷得最多的高频考点动态规划在蓝桥杯里的出镜率很高而且题型花样很多但翻来覆去核心就几类。我这两周集中解决了三个方向背包变体、区间DP、数位DP。这三个方向恰好对应了三种不同的“状态设计思路”分别是“选与不选”“合并与分割”“按位枚举”。2.1 背包变体分组背包和依赖背包的区别先聊背包。01背包和完全背包的核心区别在循环方向这个大多数人都知道01背包容量倒序遍历完全背包正序遍历。但分组背包和依赖背包就更容易搞混了我一开始就分不清楚。分组背包的特征是“若干组物品每组内部最多选一个”。它的循环顺序必须是先枚举组别再枚举容量最后枚举组内物品。为什么要先枚举组别因为每一组是一个整体容量维度的内层循环要确保“这一组最多选一个”这个限制生效。如果先枚举容量再枚举组就会出现同一组里多个物品被依次选入的情况逻辑上等于把同组物品当成了可以同时选的多件物品就错了。依赖背包则更复杂一点典型特征是“要选某个物品必须先选它的主件”。处理方式是把依赖关系转化成树形结构在主件上做一次分组背包的决策。比如主件下面有两个附件那么主件和附件之间的组合方式可以看成若干个“套餐”每个套餐内部是一个固定的搭配然后对主件做一次分组背包选择。实际做题时我建议先判断题目里到底有没有“依赖”关系如果没有只是分了组那就老老实实写分组背包。for (int g 0; g groupNum; g) { for (int c capacity; c 0; --c) { // 容量倒序保证每组只能选一次 for (int k 0; k items[g].size(); k) { // 组内物品枚举放最里层 int v items[g][k].v; int w items[g][k].w; if (c v) dp[c] max(dp[c], dp[c - v] w); } } }我实际踩过的一个坑是分组背包的组内物品枚举放最里层但很多题解里把物品枚举写在容量循环外面看起来也能过其实是利用了数据范围的偶然性。老老实实按“组-容量-物品”这个顺序写逻辑上才肯定没错。2.2 区间DP的环形处理套路区间DP的特点是从小区间合并成大连通区间典型场景是合并石子、矩阵连乘、括号匹配。代码模板很固定先枚举区间长度再枚举左端点然后枚举分割点。for (int len 2; len n; len) { for (int i 1; i len - 1 n; i) { int j i len - 1; dp[i][j] INF; for (int k i; k j; k) { dp[i][j] min(dp[i][j], dp[i][k] dp[k 1][j] cost); } } }这里最容易被忽略的是“区间长度必须是最外层循环”。有些人写三层循环时会先把左端点放最外层右端点放第二层分割点放内层结果算出来的值是不完整的。因为区间DP依赖更短的区间如果长度不是从1慢慢递增后面的状态就无法保证已经计算完毕。环形区间DP的处理有两个办法。第一个是把数组复制成两倍长度然后在长度n的区间里取最优解第二个是枚举环的断点把环转化成链。我比较推荐复制数组的办法因为实现简单不容易漏情况。比如石子合并问题里n堆石子围成一个圈我先开一个2n的数组将原数组连续放两遍再用标准区间DP跑长度为n的所有窗口最后取最小值或最大值即可。2.3 数位DP记忆化搜索写法最顺手数位DP解决的是“区间[L, R]内满足某种数字性质的个数”这类问题比如统计不含某个数字、相邻数字差满足条件的数量。这类题的搜索特征很强烈所以我直接用记忆化搜索写比纯递推好理解得多也不容易写错。我在做某道“统计区间内相邻两位数字之差至少为2的数字个数”的题时设计的状态是dp[pos][pre]其中pos表示当前处理到哪一位pre表示上一位数字是什么。记忆化搜索除了pos和pre外还需要维护两个临时标记limit表示当前位是否受到上界限制lead表示是否有前导零。long long dp[20][11]; int num[20]; long long dfs(int pos, int pre, bool limit, bool lead) { if (pos -1) return 1; if (!limit !lead dp[pos][pre 1] ! -1) return dp[pos][pre 1]; long long res 0; int up limit ? num[pos] : 9; for (int d 0; d up; d) { if (lead || abs(d - pre) 2) { res dfs(pos - 1, d, limit d up, lead d 0); } } if (!limit !lead) dp[pos][pre 1] res; return res; }这个pre 1是存储时的偏移处理因为初始前一位可以理解成-1为了不访问负下标统一加1存进去。lead用来跳过前导零的影响因为前导零前面并没有真的“数字”不应该参与相邻差判断。记忆化时只记录pos和pre不记录limit和lead这个很多人不理解。原因在于limit true和lead true的路径都受具体输入数字限制具有唯一性缓存它们没有意义真正会被大量复用的是那些既不受上界约束、也不是前导零状态的普通状态所以只用两个维度就够了。3. 图论与搜索易错点比套路更值钱图论这部分我在代码实现上栽过不少跟头。存图方式选错、初始化漏写、堆优化最短路里少判断一行都会导致惨痛的WA。下面把这段时间实际碰到的关键点拆开说。3.1 存图方式邻接表还是链式前向星存图常用两种方式vector邻接表和链式前向星。邻接表好写好调试加边就是g[u].push_back({v, w})遍历也直观。链式前向星则用几个数组模拟邻接表核心是head[u]存储从u出发的第一条边的编号to[i]存储第i条边指向的点nxt[i]存储下一条边的编号边权可以单独用w[i]存。void addEdge(int u, int v, int w) { to[edgeCnt] v; weight[edgeCnt] w; nxt[edgeCnt] head[u]; head[u] edgeCnt; } for (int e head[u]; e; e nxt[e]) { int v to[e]; int w weight[e]; // 处理u到v这条边 }链式前向星的优势是静态数组不需要动态扩容在数据量很大时更“竞赛向”。但我的建议是比赛时如果没有明确的内存压力直接用邻接表省下的调试精力很宝贵如果是在训练模板题链式前向星值得练一练能加深对“边编号”的理解。因为有些网络流模板也需要用类似的思想存反向边提前熟悉没有坏处。3.2 堆优化Dijkstra的两个初始化细节堆优化Dijkstra是最短路题目最常用的模板之一但两个细节特别容易被忽视。第一个是dist数组初始化除了起点是0其他点都应该是无穷大如果题目给了重边你插入边表时可以直接保留最短路算法会自己取最小值不用手动去重。第二个是出队时要做两步判断否则同样的点可能被反复处理多次。void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, 0, sizeof(vis)); dist[s] 0; priority_queueP, vectorP, greaterP pq; pq.push({0, s}); while (!pq.empty()) { P cur pq.top(); pq.pop(); long long d cur.first; int u cur.second; if (d ! dist[u]) continue; if (vis[u]) continue; vis[u] true; for (int e head[u]; e; e nxt[e]) { int v to[e]; long long w weight[e]; if (dist[v] d w) { dist[v] d w; pq.push({dist[v], v}); } } } }代码里的if (d ! dist[u]) continue就是经典的“旧更新出队跳过”判断。当同一个点被多次入队时旧的那一次出队的距离已经不再等于当前dist[u]直接跳过避免重复松弛。vis数组则保证已经确定最短路的点不会被再次处理。这两者可以同时存在也可以只用其中一种但一定至少留一个否则大数据下复杂度会退化得很厉害。3.3 记忆化搜索的剪枝和状态设计图论里有一类问题表面是DFS遍历实际上要用记忆化搜索优化典型的就是矩阵中从一个点出发能走的最长路径。暴力DFS每次搜索都会把路径重新走一遍重复计算严重一旦矩阵稍微大一点就会超时。记忆化的做法是把每个点的计算结果保存下来下次访问直接返回。设计状态时要注意dp[x][y]应该表示“从(x, y)出发能够获得的最优结果”而不是“走到(x, y)已经获得的临时结果”。这两者的区别决定了搜索时是先递归还是先更新答案。我的习惯是先处理递归边界再遍历四个方向从相邻状态拿回结果后累加更新当前状态最后写入记忆化数组。int dfs(int x, int y) { if (dp[x][y] ! -1) return dp[x][y]; int best 1; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 1 || nx n || ny 1 || ny m) continue; if (grid[nx][ny] grid[x][y]) continue; best max(best, dfs(nx, ny) 1); } return dp[x][y] best; }记忆化搜索还有一个好处是代码和思路对应关系非常清晰。递推写法要考虑循环顺序但记忆化搜索天然是按照状态之间的依赖关系来的只要你保证递归会终结状态转移写对正确性就很有保障。对于初学者我建议优先掌握记忆化搜索再学递推优化因为两者最终写出来的结果可以互相验证。4. 刷题踩坑实录这些问题笔试现场最容易遇到这一节是真正从WA和TLE里堆出来的经验。算法思路对但代码细节不对照样一分拿不到。4.1 整型溢出和负数取模有相当一部分题目会要求结果取模而且中间过程会涉及很大的数。前几天做一道组合背包优化题我一开始用int存DP数组本地样例都过了提交上去直接WA。后来发现问题出在乘法溢出dp[j] dp[j - v]两个数量级正常的int相加可能在某一组数据里超过2的31次方减1变成一个负数。解决办法是把涉及累加、乘法的变量都声明成long long如果乘法出现在表达式中也可以写成1LL * a * b。取模操作如果遇到负数要写成(res % mod mod) % mod因为在大多数语言里负数的取模结果仍然是负数直接输出不符合题意。这里没得商量凡是看到数据范围超过1e9只要可能会做乘法和加法直接long long起步省得后面排查溢出问题。4.2 多组测试数据的初始化遗漏蓝桥杯的题经常是T组数据每组数据会重新给出参数。我一开始写习惯不好把全局数组初始化写在读入T之前结果第二组数据开始就全部错乱。常见需要重置的有dist、vis、dp数组以及链式前向星里的head数组和边计数器edgeCnt。有一个笨办法但很有效每次写完循环后把循环体内用到的数组列一张表在每一轮开始前统一重置。比如链式前向星里edgeCnt忘了清零新加边会接在上一次后面遍历时会访问到脏数据有时候比数组没清空还难排查。memset用的时候也要注意0x3f是把int的每个字节设成0x3f结果是约1e9量级的一个大数适合作为初始“无穷大”。但如果要初始化dp为负值可以用memset(dp, -1, sizeof(dp))这会把每个字节设成0xFF恰好对应-1。4.3 二分边界写错导致死循环二分题在蓝桥杯里经常结合“最大值最小化”“最小化最大值”出现。写二分的常见死循环就出在边界更新和中间值的取法不匹配上。// 查找满足条件的第一个位置 while (l r) { int mid (l r) 1; if (check(mid)) r mid; else l mid 1; } // 查找满足条件的最后一个位置 while (l r) { int mid (l r 1) 1; if (check(mid)) l mid; else r mid - 1; }第二段代码里mid必须写成(l r 1) 1不能是(l r) 1。否则当l和r相邻时mid等于l如果check(mid)为真l mid不会产生任何移动就死循环了。这个细节我至少踩过三次现在每次写二分都要回头看一眼是哪一种情况。4.4 常见问题速查表我把这段时间遇到的问题整理成了一张表方便后面复习时一眼找到对应解法。现象可能的原因解决思路本地样例全过提交WA数组越界或未初始化检查数组大小是否与数据范围一致多组数据时重置全局变量程序超时向量的重复遍历或无效状态过多优先考虑记忆化、堆优化、预处理结果一直比答案小几初始化INF不够大被实际数据超越将dist和dp初始值改为0x3f3f3f3f3f或LONG_LONG_MAXDP结果全为0状态定义方向写反了检查dp表示的是“当前”还是“之后”的结果二分死循环mid取法与边界更新不匹配需要l mid时mid必须上取整递归栈溢出DFS层数过深把递归改成显式栈或者检查是否漏写终止条件5. 顺手整理的代码模板和对拍技巧训练到一定阶段后我开始意识到“稳定的代码手感”和“算法会写”同样重要。一套趁手的模板能省去大量重复输入的时间对拍脚本更是排查逻辑错误的神器。5.1 一套自用的快读和基础模板蓝桥杯虽然是本地评测但输入规模大的时候cin没有关同步会慢一截。我平时会直接用ios::sync_with_stdio(false); cin.tie(0);大多数情况下已经够用。如果输入量真的非常大比如百万级别再用快读会更稳。#include bits/stdc.h using namespace std; int read() { int x 0, f 1; char c getchar(); while (c 0 || c 9) { if (c -) f -1; c getchar(); } while (c 0 c 9) { x x * 10 c - 0; c getchar(); } return x * f; } int main() { ios::sync_with_stdio(false); cin.tie(0); return 0; }这里要说明一点ios::sync_with_stdio(false)和scanf/printf混用会导致输入输出顺序错乱所以用哪种风格就坚持到底不要混。快读一般只用于读整数遇到浮点数还是老老实实用标准输入。5.2 对拍脚本让两份代码互相比答案遇到一道题思路不明确时我常用对拍来验证优化代码的正确性。对拍的本质是写一份暴力但一定正确的代码再写一份待验证的优化代码用随机数据反复跑输出不一致就说明优化代码有问题。while true; do python3 gen.py input.txt ./force input.txt force_out.txt ./optimized input.txt opt_out.txt if diff force_out.txt opt_out.txt /dev/null; then echo AC else echo WA break fi done数据生成器gen.py是核心要让数据覆盖小范围边界、大范围极值、随机分布。我一般先生成一批极小的数据比如n1或n2的情况再慢慢扩大。对于动态规划题小数据暴力搜索可以枚举所有方案对于图论题生成随机边时特意加入自环和重边检验模板的鲁棒性。一旦对拍发现WA把对应那组input.txt保存下来单独调试定位效率会高很多。6. 下一阶段的备战方向和练习计划这段时间的训练让我对动态规划和图论有了更细的体感但也暴露了一些盲区。接下来的备战方向不是继续无脑刷题而是有针对性地补弱项。6.1 查漏补缺优先级目前我最需要补的是字符串算法和基础数论。字符串方向里KMP、Trie树、字符串哈希都应该掌握蓝桥杯里“匹配”“前缀”“回文”相关的题目并不少见。数论方向要会写素数筛、快速幂、最大公约数、组合数和逆元这些知识点单独看不难但经常藏在其他题型的“数学计算”环节里。我给自己定的优先级是字符串算法大于数论数论大于构造题。因为字符串题的模板性很强学会了很容易稳定拿分数论知识则更碎片化需要靠练习量来巩固。构造题更多是思维层面的训练比赛时能不能做出来取决于临场状态不适合投入太多时间专门刷。6.2 真题模拟和限时训练安排接下来每周仍然保持一次真题限时模拟但模拟完会增加一个“错题复盘”环节。我会把每道错题标记成两类一类是“知识点不会”另一类是“会做但没时间”。对于后者模拟时必须在题目分配上调整策略对于前者记录到待补清单里专门抽时间解决。单题时间控制上新题如果30到40分钟还没有完整思路我会先看题解然后合上题解自己重新写一遍。这个“重写”过程比重复刷十道简单题更有效因为只看题解不落地下回遇到同类型还是会卡在代码实现上。一些个人的体会刷到这个阶段我慢慢意识到备赛比的是谁能更早发现自己的盲区以及在发现盲区之后能不能用稳定的节奏把它补上。一次AC不值得太兴奋因为比赛里的AC标准更严苛一次WA也不必沮丧因为每一道错题都在提醒我某个细节还没掌握。最后分享一个小建议准备一个固定的笔记文件把每天遇到的易错点、边界条件、状态定义随手记下来。到考前最后两周翻这个文件比重新刷题更有价值。竞赛里的高分往往不取决于你做过多少题而取决于你在高压环境下能把多少细节稳稳做对。