企业官网建设流程全解析

每年准备机试的同学翻到《王道论坛计算机考研机试指南》第五章，基本都会觉得一股劲上来了。前面几章还在讲排序、字符串、数据结构，本质上都是“已知套路 + 熟练调用”，到了搜索这一章，题目突然变得“活”起来：不再有明显的公式套路，更多是要求你自己设计状态、选择搜索方式、控制复杂度。这也是为什么很多人都说，第五章是整本书的分水岭，跨过去，机试才算真正入门。

这篇笔记，我按照自己阅读第五章的节奏来写。内容会围绕“搜索”这个核心展开，包括枚举、BFS、DFS、剪枝几个大块，也会补充一些做题时的实际反馈和排查经验。如果你正在备战考研机试，或者刚开始刷算法题、想把搜索基础打扎实，这篇内容可以直接当作导读使用。

1. 第五章在整本书里的定位，以及为什么它值得单独写一篇笔记

1.1 从“会写代码”到“会算法设计”的转折点

前几章的排序、查找、字符串处理，核心都在“掌握一种数据结构或一个现成 API，然后正确调用”。学完那些内容，你对一门语言的基本功会有底，但这种能力本质上还是“照着说明书操作”。到了第五章，搜索类题目要求的是：把问题抽象成状态空间，然后决定用什么方式去遍历这个空间。这个过程不再有标准答案，同一个题，你既能用枚举硬算，也能用 BFS 求最短路，还可以用 DFS 回溯加剪枝。选择不同，代码长度、时间消耗、正确率都会差很多。

我在读这一章的时候，最大的感受是：代码量本身并不大，真正的难点在于“想到了什么”。比如一个看起来像数学题的倒水问题，本质上竟然是一张图上的最短路；一个拼接木棍的判定题，绕来绕去最后要靠深度优先搜索加剪枝才能跑完。这种思维转换，才是这一章真正想练的东西。

1.2 机试里搜索题为什么常考

搜索题在机试里出现频率高，有两个原因。第一，它几乎不需要超纲的知识背景。排序、图论、动态规划都有可能因为知识点没学而卡住，但搜索的本质是“穷举所有可能”，只要你懂递归、懂队列、懂状态标记，任何题你都能至少写出一个暴力版本。第二，搜索题特别适合考查“复杂度控制能力”。很多搜索题的朴素算法一定能得到正确答案，但一定会超时，这时候就要靠剪枝、优化枚举范围、选择 BFS 而非 DFS 来解决问题。这种能力没法靠背模板获得，所以考官喜欢用它来区分考生。

书中这一章的选题也很有代表性。它没有一上来就甩难题，而是用几个经典例子把“广度优先搜索”“深度优先搜索”“枚举优化”这几个分支逐个打通。读完之后，你再去做题库里的搜索题，至少能判断出“该用哪种搜索、核心状态是什么、大概需要什么级别的优化”。

1.3 这一章的知识结构拆解

我自己读下来的结构，大致可以分成三块：

1. 枚举法。这是最朴素的搜索，核心是“确定搜索空间、找到缩小空间的规律”。书中用了一些常见题来展示，比如判断一个范围内的特殊数字、查找满足条件的组合。这部分内容偏简单，但非常重要，因为后面很多剪枝思路本质上是“在枚举的过程中提前去掉无效分支”。
2. 广度优先搜索（BFS）。核心是“队列 + 分层扩展”，适合求最短步数、最少操作次数这类无权重最短路问题。本章用倒水、迷宫、最少步数等题目做载体，强调状态标记的重要性。
3. 深度优先搜索（DFS）与回溯。核心是“递归深入 + 状态恢复”，适合求方案数、判断是否存在可行解、回溯枚举所有排列组合。这部分相对难，需要用剪枝来对抗指数级的状态增长。

后面我会按照这个结构，逐个展开我实际做题时遇到的问题和总结的模板。

2. 枚举法：先把“暴力”这件事做到极致

2.1 枚举之前，先算一笔复杂度账

很多人提到枚举就想到 for 循环套 for 循环，然后直接开跑。这个习惯在刷题时很危险，因为机试的评测环境通常有 1 到 3 秒的时间限制，你写的程序必须在限制内跑完所有测试数据。我一般会在写枚举代码前先估算一下复杂度：如果状态总量小于 10 的 7 次方，直接暴力大概率没问题；如果接近 10 的 8 次方，就要考虑常数和剪枝；如果超过 10 的 9 次方，基本不能再无脑枚举了。

举一个书里最常见的例子：给定一个范围，要找出满足某条件的所有数字。如果直接遍历区间内每一个数，区间长度是 n，每次判断条件需要 O(1) 或者 O(log n)，总复杂度就是 O(n) 或 O(n log n)。在 n 达到 10 的 6 次方时完全没问题；但如果你内层还套了一个遍历，复杂度变成 O(n²)，那 n 一旦上万就很容易超时。所以枚举不是不能写，而是写之前一定要知道当前的数据量级。

2.2 缩小枚举量的三个实用方向

书里没有刻意总结，但我在做题后归纳出三个最常用的优化方向：

第一，缩小范围。很多题目里，某个变量的取值其实有明确的上下界，甚至可以根据数学关系直接算出来。比如百钱买百鸡这种经典题，与其让三个变量都在 0 到 100 之间循环，不如先固定两个量，第三个量用总数减去前两个得到，这样直接少一层循环。

第二，利用对称性。有些问题里，枚举的对象存在顺序无关性，比如组合问题。如果 A、B、C 三个值的顺序不影响结果，就可以强行要求 A ≤ B ≤ C，这样能减少大量重复状态。我一开始经常忽略这一点，结果同样的组合被枚举了好几遍，白白浪费时间。

第三，提前终止。如果题目问的是“是否存在”，一旦找到答案就可以直接结束循环；如果是求最小值的枚举，也可以在找到一个可行解后继续尝试更优解，但不必等待所有情况都跑完。这里需要注意编码方式：不要在循环内部频繁调用重函数，能拆出来的计算放到循环外。

2.3 枚举题的一个易错点：边界条件

枚举题代码简单，容易让人的警惕性下降。实际上，边界条件是枚举题最容易翻车的地方。一个区间如果题目说的是“大于等于 a 且小于 b”，代码里就应该写成i = a; i < b; i++，少一个等号，结果就全错。我之前做题时遇到过一种情况：题目要求找某个范围内的“回文数”，我循环写成了从 1 到 n，但没注意到 n 本身也是两位数，回文判断函数里取每一位的逻辑在特殊输入上出了 bug，最后在评测时才暴露。为了避免这种情况，建议在写完枚举代码后，专门用最小边界、最大边界、恰好等于边界的数据各测一遍。

2.4 枚举和后面所有搜索的关系

读这一章时不要觉得枚举太简单，就跳过。实际上，BFS 本质上是一种“按层枚举”的搜索，DFS 本质上是“沿着一条路径枚举到底”。剪枝所要做的事情，就是在枚举过程中删掉不可能产生答案的分支。如果你枚举时就没有“状态空间”的意识，后面学 BFS、DFS 时很容易把代码写得一团乱。我建议把枚举题当作练手，刻意训练自己分析状态空间的能力：这个题有多少个变量，每个变量的取值范围是什么，总状态数是多少，哪些状态可以合并。这个习惯养成了，后面所有搜索题都会好写很多。

3. BFS：把“最短步数”问题变成队列的层层推进

3.1 什么时候该用 BFS

BFS（广度优先搜索）最典型的应用场景，是在一个“无权重图”上求最短路径。所谓“无权重”，是指每次操作带来的代价相同，比如走一步、倒一次水、按一次按钮。机试题里很多描述是“最少需要几次操作才能从初始状态到达目标状态”，这类问题十有八九要用 BFS。

一个很容易踩的坑是：看到“最少”“最短”就直接上最短路算法或动态规划，却忽略了状态空间本身可能就是一张隐式图。书里的倒水问题就是这样，表面上是倒来倒去，实际上每个“两个杯子的水量组合”就是一个节点，“倒一次水”就是一条边，起点是初始水量状态，终点是目标水量状态。这时候用 BFS 天然合适，因为每个操作代价都是 1，第一次到达目标状态的层数就是最少操作次数。

3.2 BFS 的固定模板骨架

我习惯把 BFS 模板固定成四步：

1. 定义状态结构体。结构体里放当前状态的所有关键信息，比如坐标 x、y，或者两个杯子的当前水量。
2. 定义标记数组。标记数组用来记录哪些状态已经访问过，避免重复入队。
3. 初始化队列，把起点状态入队，并标记起点。
4. 循环处理队列：弹出队首，判断是否为目标，如果是则返回距离；如果不是，则生成下一步的所有可能状态，能入队的入队。

代码骨架大致长这样：

struct State { int x, y; int step; }; int bfs(State start, State target) { queue<State> q; bool visited[MAXN][MAXN] = {false}; q.push(start); visited[start.x][start.y] = true; while (!q.empty()) { State cur = q.front(); q.pop(); if (cur.x == target.x && cur.y == target.y) { return cur.step; } // 枚举所有下一步状态 for (int i = 0; i < nextCount; i++) { State next = generateNext(cur, i); if (valid(next) && !visited[next.x][next.y]) { visited[next.x][next.y] = true; next.step = cur.step + 1; q.push(next); } } } return -1; // 无解 }

这个模板看起来简陋，但实际做题时，最花时间的地方往往不是在模板本身，而是“怎么生成下一步”和“怎么标记状态”。尤其是后者，如果标记维度不够，BFS 就会陷入死循环。

3.3 状态设计是 BFS 的关键

很多初学者写 BFS，标记数组只考虑了一个维度。比如迷宫题里只用visited[x][y]标记坐标，倒水题里却只记录第一个杯子当前水量。这种情况非常容易出错。倒水问题里，第二个杯子的水量不同，即使第一个杯子水量相同，后续还能到达的状态也是完全不同的，如果只按第一个杯子去重，就会漏掉很多分支，甚至得到错误的最少次数。

正确的做法是：用完整的状态向量做标记。坐标题就用visited[x][y]，杯子题就用visited[a][b]表示两个杯子的水量组合。有些更复杂的状态还需要增加维度，比如记录当前剩余油量、当前朝向等。标志位越多，状态区分越细，搜索就越不容易出错，但也会更占内存。所以要在正确性和空间开销之间取一个平衡。

3.4 从倒水题理解“隐式图”

书里的倒水题给我留下很深的印象。题面大致是：有两个容量固定的杯子，初始有一定水量，允许的操作是“把一个杯子的水倒入另一个杯子，直到源杯为空或目标杯满”，要求最少的倒水次数让某个杯子达到指定水量。

当时我看到这个题的第一反应是列数学方程，想了半天也没理清。后来才意识到，这就是一个 BFS：状态是(a, b)，也就是两个杯子的当前水量；从每个状态出发，可能的下一步是有限的，最多只有几种倒法；目标状态是满足a == target || b == target的任意状态。用 BFS 一层层扩展，第一次遇到目标状态时的步数就是答案。

这个例子很好地说明了为什么 BFS 比数学推导更通用。数学方法可以解决特定条件的问题，但一旦题目改了杯子数量、操作方式，数学解法可能就失效了，BFS 却还能继续工作，只是状态维度变多一点。

3.5 多组输入下最容易犯的错：忘记清空标记数组

机试题目很多都是“多组测试数据”，也就是程序会循环读入多组输入。我第一次做 BFS 题时，把标记数组定义成了全局变量，结果只在程序开头初始化了一次，后续每组新数据都会带着上一组的访问记录，导致明明有解的搜索返回了 -1。排查了很久才发现是visited没清空。

解决方式有两种：一种是在每组数据输入后手动memset重置标记数组；另一种是用“时间戳标记法”，也就是额外开一个visTime数组，每次使用前把当前组号写入对应位置，判断时检查该位置存的值是不是当前组号。第二种方法在多次 BFS 时效率更高，因为不用每次把整个数组清零。

4. DFS 与回溯：递归里的“状态恢复”是灵魂

4.1 DFS 的核心思想：一条路走到黑，再回头

DFS（深度优先搜索）和 BFS 的区别，在于遍历状态树的顺序。BFS 是逐层扩散，DFS 则是从起点开始，尽可能深地往下走，走不通再返回，换一条路继续。机试题里，DFS 常用于三类问题：判断是否存在可行解、统计所有可行方案、枚举排列组合。

一个常见的误解是 DFS 一定比 BFS 慢。其实不一定。如果问题要求“输出所有可行方案”，BFS 往往要保存大量中间状态，内存爆炸；DFS 则每次只维护一条路径，空间开销小得多。所以当题目要求的是方案数而不是最短步数时，DFS 反而更合适。

4.2 回溯时，改了什么就一定要还回去

写 DFS 最容易出错的地方，是“状态恢复”。递归深入一层时，你可能修改了一个全局标记、往列表里加了一个元素、把某个位置改为已占用；当从深层返回时，这些修改必须全部撤销，否则会影响同一层的其他分支。

有一个经典例子：用若干根长度不一的棍子拼一个正方形。DFS 的写法是为每根棍子安排位置，如果当前位置已经摆满了，就换下一根。这个过程中，如果不恢复“某根棍子已使用”的标记，那么后面的分支就会错误地认为这根棍子已经被用掉了，导致本来能拼成的方案被判为不可能。

我在学习时总结了一个口诀：进入递归前做了什么修改，退出递归后一定做对应的逆操作。而且逆操作必须在函数返回之前执行，顺序要严格对应。如果修改了两处，恢复时也要按相反顺序恢复两处。这个细节写错，排查起来非常痛苦，因为错误往往只在某些输入组合下才会出现。

4.3 剪枝：把不可能的分支提前砍掉

DFS 的原始版本，本质上是在一棵指数级规模的树上做遍历。如果不加任何限制，状态稍微多一点，程序就会卡死。剪枝是 DFS 的灵魂，也是这个章节里让我收获最大的一部分。

剪枝分两大类。第一类是可行性剪枝：发现某个分支已经不可能产生合法解，直接不进入。例如拼棍子问题中，如果当前剩余长度小于下一根棍子的长度，就不用考虑这根棍子了。第二类是最优性剪枝：即使某个分支可能产生合法解，但它的代价已经超过当前已知最优解，也可以提前终止。这类剪枝常见于求最大/最小值的 DFS 中。

还有一个实际技巧：排序之后再 DFS。很多组合问题里，数据从小到大或从大到小排序后，剪枝效率会有明显提升。书中拼棍子的题就是一个例子，按棍子长度从大到小排序后优先尝试长棍，这样能更快地填满一条边，也能更早暴露不可能的分支，减少搜索量。

4.4 递归深度过大怎么办

DFS 用递归写比较直观，但有些题目搜索深度很大，递归层数可能超过几万甚至几十万。大多数评测环境默认的递归栈空间有限，递归层数太高会导致栈溢出。

应对方式有三种。第一，改用显式栈模拟 DFS。这种写法代码会复杂一些，但完全规避了递归栈深度问题。第二，有些题目可以在设计状态时压缩深度，比如倒水问题里，很多加水倒水操作并不产生新的有效状态，可以用状态合并减少递归深度。第三，确认题目限制。机试题一般不会给特别深的搜索空间，如果递归深度确实让人担心，优先考虑用 BFS 或优化状态设计。

4.5 一个常见的 DFS 模板：排列组合式枚举

后来的很多题都用到“逐个位置尝试”的 DFS 写法。模板大致是：

void dfs(int pos) { if (pos > n) { // 已经生成一个完整方案，检查并记录 checkAndRecord(); return; } for (int i = 1; i <= n; i++) { if (!used[i]) { used[i] = true; array[pos] = i; dfs(pos + 1); used[i] = false; // 状态恢复 } } }

这个模板可以用来生成全排列、组合、子集等。我读第五章时，最常做的练习就是自己动手把全排列、组合、子集都各写一遍，然后比较它们在状态空间上的差异。这样后面遇到实际问题，就能快速判断“这个题本质上是在枚举全排列，还是组合，还是子集”。

5. 做这一章习题时，我反复踩过的几个坑

5.1 问题与排查速查表

读这一章期间，我整理了五六个高频问题，放在这里当作速查清单。

这里面最隐蔽的是状态恢复问题。因为普通规模的数据下，错误分支可能不影响最终结果，只有特定数据组合才会暴露。我的建议是在调试 DFS 时，打印出每一次递归调用的当前状态和标记数组，肉眼观察哪一步恢复出了问题。

5.2 关于 STL 使用的几个建议

写搜索题时，STL 是必需品，但使用方式有讲究。

第一，queue的front和pop要小心。很多人弹出一个元素后，还想着通过引用修改队列内部数据，这是不安全的。建议每次先复制一份State cur = q.front()，再q.pop()，后续操作在cur上进行。

第二，如果 DFS 需要记录当前路径，vector不要频繁在递归中拷贝。可以把路径存在全局数组里，用push_back和pop_back维护，递归返回时自动恢复。

第三，deque和queue都能完成 BFS，但queue语义更清晰。题目不需要双端操作时，直接用queue就够了，别为了花哨引入不必要的数据结构。

5.3 调试搜索题的一个土办法

搜索题的 bug 很难通过单元测试覆盖，因为状态空间太大。我自己常用的调试手段是“小数据 + 打印”。先构造一个非常小的测试用例，比如迷宫缩小到 3×3、棍子只有 3 根，然后在关键位置输出当前状态和步数。这样能直观看到搜索是不是朝着预期的方向推进。

如果程序在某种输入下陷入死循环，不要急着加各种判断，先在 BFS 的入队位置打印状态，确认是否真的出现了重复状态。如果是，基本就是标记数组没生效或状态设计不完整。

6. 读完这一章之后，你可以继续往哪个方向走

6.1 把“模板”变成“思考习惯”

我的建议是，不需要死记 BFS 模板或者 DFS 模板，更重要的是形成一套做题时的分析路径：看到题目，先用一两句话描述状态空间；判断这个状态空间是“逐层扩展”还是“一条路走到底”；再决定用 BFS 还是 DFS；最后考虑标记和剪枝。这个分析过程比代码模板更重要，因为模板是固定的，分析思路才是活的。

为了让这个思路固定下来，我平时刷题时会专门用一个笔记记录每道题的状态定义、搜索方式、剪枝条件。每道题只写三四行，但写完就印象深刻。后面复习时，比重新读一遍代码效率高很多。

6.2 相关知识点可以提前预热

搜索这一章绝不是学完就结束。它和后面的动态规划、图论都有联系。最典型的是“记忆化搜索”：用 DFS 搜索时，如果某个状态的最优结果已经被计算过，就可以直接返回，避免重复计算。这个技巧本质上就是动态规划。所以读这一章时，可以稍微留意哪些搜索题里存在大量重复状态，提前感受一下“用数组缓存结果”这种思路。

另外，图论里的连通块计数、环检测、最短路径，很多底层也都依赖 DFS 或 BFS。基础搜索学扎实了，后面学图算法会轻松很多。

6.3 我的一个小习惯：每种搜索至少动手写三遍

读这一章时，我要求自己把书里的经典题在理解之后，不看答案，完整地写三遍。第一遍写完能过样例就停，第二遍优化结构和剪枝，第三遍把代码换成不同风格（比如把递归 DFS 改成栈模拟）。三遍写下来，很多细节才能真正变成自己的东西。

书里第五章的练习题数量不算多，但每一题都有很强的代表性。我个人觉得，这个章节最值得花时间的反而不是“刷更多题”，而是把已经出现的题吃透，能把题目的状态空间讲清楚。能做到这一点，机试里的搜索题基本不会成为障碍。