企业官网建设流程全解析

这是一篇实战向的备赛记录整理。我直接按这段时间的真实刷题节奏来写，覆盖了题型复盘、动态规划常见变体、图论易错点、踩坑记录和后续计划，内容都是可复现的，希望对正在准备算法竞赛的朋友有帮助。

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_queue<P, vector<P>, greater<P>> 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 常见问题速查表

我把这段时间遇到的问题整理成了一张表，方便后面复习时一眼找到对应解法。

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是核心，要让数据覆盖小范围边界、大范围极值、随机分布。我一般先生成一批极小的数据，比如n=1或n=2的情况，再慢慢扩大。对于动态规划题，小数据暴力搜索可以枚举所有方案；对于图论题，生成随机边时特意加入自环和重边，检验模板的鲁棒性。一旦对拍发现WA，把对应那组input.txt保存下来单独调试，定位效率会高很多。

6. 下一阶段的备战方向和练习计划

这段时间的训练让我对动态规划和图论有了更细的体感，但也暴露了一些盲区。接下来的备战方向不是继续无脑刷题，而是有针对性地补弱项。

6.1 查漏补缺优先级

目前我最需要补的是字符串算法和基础数论。字符串方向里，KMP、Trie树、字符串哈希都应该掌握，蓝桥杯里“匹配”“前缀”“回文”相关的题目并不少见。数论方向要会写素数筛、快速幂、最大公约数、组合数和逆元，这些知识点单独看不难，但经常藏在其他题型的“数学计算”环节里。

我给自己定的优先级是：字符串算法大于数论，数论大于构造题。因为字符串题的模板性很强，学会了很容易稳定拿分；数论知识则更碎片化，需要靠练习量来巩固。构造题更多是思维层面的训练，比赛时能不能做出来取决于临场状态，不适合投入太多时间专门刷。

6.2 真题模拟和限时训练安排

接下来每周仍然保持一次真题限时模拟，但模拟完会增加一个“错题复盘”环节。我会把每道错题标记成两类：一类是“知识点不会”，另一类是“会做但没时间”。对于后者，模拟时必须在题目分配上调整策略；对于前者，记录到待补清单里，专门抽时间解决。

单题时间控制上，新题如果30到40分钟还没有完整思路，我会先看题解，然后合上题解自己重新写一遍。这个“重写”过程比重复刷十道简单题更有效，因为只看题解不落地，下回遇到同类型还是会卡在代码实现上。

一些个人的体会

刷到这个阶段，我慢慢意识到备赛比的是谁能更早发现自己的盲区，以及在发现盲区之后能不能用稳定的节奏把它补上。一次AC不值得太兴奋，因为比赛里的AC标准更严苛；一次WA也不必沮丧，因为每一道错题都在提醒我某个细节还没掌握。

最后分享一个小建议：准备一个固定的笔记文件，把每天遇到的易错点、边界条件、状态定义随手记下来。到考前最后两周，翻这个文件比重新刷题更有价值。竞赛里的高分，往往不取决于你做过多少题，而取决于你在高压环境下能把多少细节稳稳做对。