企业官网建设流程全解析

1. 搜索算法的整体认知与竞赛定位

先聊一个很多竞赛选手都踩过的坑：拿到一道搜索题，第一反应是“不就是DFS和BFS吗”，然后直接开写，写着写着发现超时，再回来加剪枝，加完剪枝发现过不了样例，最后对着代码发呆半小时，骂自己当初为什么不把状态设计得再想想。

搜索在信息竞赛里是一门“看着简单、用到极深处极难”的算法。它的内核是穷举状态的策略，但又远不止穷举——剪枝、估价、双向、迭代加深、状态压缩、记忆化、启发式搜索，每一个方向都能单独撑起一道省选甚至国赛级别的题目。进阶指南里的“搜索相关”模板，恰恰就是把这些散落的技巧整理成一套可以直接套用的框架，让我们在考场上不至于从零开始摸着石头过河。

从竞赛定位来看，搜索通常出现在两个位置：一是暴力分，二是正解。暴力分的搜索往往要求你快速写出能拿部分分的版本，这时候模板化的DFS/BFS框架能帮你节省大量调试时间；正解的搜索则要求你把搜索作为一种高级算法来使用，比如状态空间的巧妙压缩、启发式函数的精确设计。很多选手忽视了后者，导致只会写“裸搜”，题目一变就僵住。

这篇文章我打算按自己的实战经验，从搜索的底层模板开始，一层层往上拆：基础DFS/BFS怎么写得又稳又快、状态压缩搜索的常见套路、剪枝的几大方向、启发式搜索（IDA*、A*）的比赛应用、双向搜索和迭代加深的具体写法，最后附上我自己的刷题路径和避坑清单。每个部分都给出可直接复制的模板代码和针对性的解释，保证不是贴一段代码就完事，而是把“为什么这么写”讲透。

2. 基础DFS与BFS模板的精细化写法

2.1 DFS模板：从递归框架到回溯细节

DFS（深度优先搜索）是所有搜索算法的基础。竞赛里的DFS模板看起来都差不多，但真正能稳拿分的写法有几个关键细节必须注意。

先说通用模板，我们以“n皇后问题”这类经典回溯题为例：

#include <bits/stdc++.h> using namespace std; int n, ans; int col[20], diag1[40], diag2[40]; // 列、主对角线、副对角线 void dfs(int row) { if (row == n) { ans++; return; } for (int c = 0; c < n; c++) { if (col[c] || diag1[row + c] || diag2[row - c + n]) continue; col[c] = diag1[row + c] = diag2[row - c + n] = 1; dfs(row + 1); col[c] = diag1[row + c] = diag2[row - c + n] = 0; // 回溯 } } int main() { cin >> n; dfs(0); cout << ans << '\n'; return 0; }

这个模板最核心的地方在于回溯时状态的恢复。很多新手会在递归后忘记把标记恢复，导致同一状态被重复使用，答案直接错掉。记住一个口诀：进入递归前“占坑”，出递归后“还坑”——这是DFS能正确枚举所有路径的前提。

另一个容易出错的是对角线的表示。我们用row + c表示主对角线（从左上到右下），用row - c + n表示副对角线（从右上到左下），加n是为了把负数下标偏移到非负。这个技巧其实是一个通用的坐标变换套路，后面在做状态压缩搜索时还会遇到类似思维。

在实际竞赛中，DFS模板还应具备几个“保命”优化：

• 用位运算替代布尔数组。在n不超过20的题目里，可以用整数或bitset来存储状态，回溯时也只需要^=操作，比数组快一个量级。后面会单独讲状态压缩。
• 提前定义好搜索顺序。比如“每一步尽量先尝试限制更多的分支”，这在剪枝中叫做“优先搜索可行性较小的分支”，往往能极大提升剪枝效果。
• 递归参数尽量少。能通过全局变量/引用传参时，不要用值传递。竞赛里递归深度可能上万，参数拷贝会带来无谓开销。

2.2 BFS模板：队列与状态的入队规范

BFS（广度优先搜索）通常用于求最短路、最少步数，以及“状态可以抽象成图”的题目。模板的核心是“逐层扩展”，保证第一次访问到目标状态时就是最优解。

一个典型的BFS模板（以棋盘走迷宫为例）：

#include <bits/stdc++.h> using namespace std; struct State { int x, y, step; }; const int dx[4] = {1, -1, 0, 0}; const int dy[4] = {0, 0, 1, -1}; int n, m; char grid[105][105]; bool vis[105][105]; int bfs(int sx, int sy, int tx, int ty) { queue<State> q; q.push({sx, sy, 0}); vis[sx][sy] = true; while (!q.empty()) { State cur = q.front(); q.pop(); if (cur.x == tx && cur.y == ty) return cur.step; for (int k = 0; k < 4; k++) { int nx = cur.x + dx[k], ny = cur.y + dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (grid[nx][ny] == '#') continue; if (vis[nx][ny]) continue; vis[nx][ny] = true; q.push({nx, ny, cur.step + 1}); } } return -1; } int main() { cin >> n >> m; int sx, sy, tx, ty; for (int i = 0; i < n; i++) { cin >> grid[i]; for (int j = 0; j < m; j++) { if (grid[i][j] == 'S') sx = i, sy = j; if (grid[i][j] == 'T') tx = i, ty = j; } } cout << bfs(sx, sy, tx, ty) << '\n'; return 0; }

BFS模板的核心细节有三点：

第一，入队即标记。很多新手习惯在出队时才标记访问，这会导致同一层的节点被重复入队，队列膨胀好几倍，甚至MLE。正确做法是：一旦一个状态被生成且合法，就立刻在vis中标记。这是BFS模板最关键的“纪律”。

第二，状态中直接携带步数。虽然也可以用dist数组来记录，但直接把步数作为结构体成员往往更直观，尤其当状态本身包含多维信息（比如行政坐标+钥匙状态）时，结构体更加灵活。

第三，边界检查放在最前面。不要先判断是否能走再判断边界，那样容易漏判数组越界。正确顺序是：先判坐标是否在界内，再判障碍、再判已访问。次序错了，小数据没事，大数据一来就RE。

3. 状态压缩与记忆化搜索的进阶模板

3.1 位运算状态压缩的核心模式

当搜索的状态可以用一个整数来表示时，状态压缩就派上了用场。最经典的场景是“旅行商问题（TSP）”、 “子集枚举”、 “图上的状态转移”。在竞赛题中，经常出现n <= 20这类限制，一旦看到这种范围，就要立刻想到状态压缩DP或状态压缩搜索。

举个最常用的模板——基于状态压缩的回溯（比如“分配问题”：给n个人分配m项任务，每个人做每项任务有不同收益，求最大总收益，要求每个人最多一项任务）：

int n; int a[20][20]; int dp[1 << 20]; // 记录当前使用的人的状态 void dfs(int task, int mask, int sum) { // 剪枝：当前收益 + 未来最大可能收益 <= 已知最优 // 记忆化：dp[mask] 记录到达这个状态的最大收益 }

实际上状态压缩搜索往往直接转成记忆化搜索（Memoization）或DP更优，但竞赛中我们经常“先搜索+记忆化”，因为记忆化就能实现类似DP的效果，又比纯DP更直观——尤其是状态维度多、转移顺序不显然时。

一个典型的记忆化搜索模板（以数位DP的简单版为例，比如统计[0, x]中不含4的数字个数）：

int dp[20][2]; string s; int dfs(int pos, int tight) { if (pos == s.size()) return 1; if (dp[pos][tight] != -1) return dp[pos][tight]; int limit = tight ? s[pos] - '0' : 9; int res = 0; for (int d = 0; d <= limit; d++) { if (d == 4) continue; res += dfs(pos + 1, tight && (d == limit)); } return dp[pos][tight] = res; } int solve(int x) { if (x < 0) return 0; s = to_string(x); memset(dp, -1, sizeof(dp)); return dfs(0, true); }

这个模板是数位DP中非常常用的“记忆化搜索”写法。它的精髓在于用tight表示“当前位是否受上界约束”。很多人第一次看到这个参数会觉得绕，但你只要理解：tight=1时，当前位只能取0~limit，否则可以取0~9。通过记忆化，所有pos和tight的状态只被计算一次，复杂度从指数级降到O(位数×状态数)。

记忆化搜索和状态压缩相结合时，常见场景是“棋盘覆盖”、“八数码”、“推箱子”这类游戏类问题。每个棋盘状态可以编码成整数（如把棋盘按行展开成二进制），再用unordered_map<int, int>或map记录到达该状态的最少步数。关键点是状态的编码与解码必须可靠，建议用宏或内联函数统一封装，避免手写出错。

注意：记忆化搜索中，dp的维度一定要覆盖所有影响后续决策的参数。漏掉一个参数（比如漏掉tight），会导致状态错误合并，答案错得离谱。建议在写记忆化搜索前，先把“状态由哪几个参数唯一确定”写在草稿纸上。

3.2 状态压缩BFS：如何用整数表示复杂局面

有些BFS题目，状态不仅仅是坐标，还包含一些开关状态、钥匙状态、蛇的身体等。这时我们可以将整个局面编码为一个整数，配合vis数组/哈希表去重。

经典模板（以“带钥匙的迷宫”为例）：地图上有若干钥匙，某些门需要特定钥匙才能通过。求从起点到终点的最短路径。

struct State { int x, y, keyMask, step; }; bool vis[ N ][ N ][ 1 << K ]; // K为钥匙种数 void bfs() { queue<State> q; q.push({sx, sy, 0, 0}); vis[sx][sy][0] = true; while (!q.empty()) { State cur = q.front(); q.pop(); // 到达终点返回 for (int dir = 0; dir < 4; dir++) { int nx = cur.x + dx[dir], ny = cur.y + dy[dir]; if (越界 || 墙) continue; int nk = cur.keyMask; if (地图[nx][ny] == 'a'+k) nk |= (1 << k); // 捡钥匙 if (地图[nx][ny] == 'A'+k && !(nk & (1 << k))) continue; // 没钥匙过不去 if (vis[nx][ny][nk]) continue; vis[nx][ny][nk] = true; q.push({nx, ny, nk, cur.step + 1}); } } }

这里的关键是keyMask用二进制位来表示携带的钥匙集合。比如有4种钥匙，mask=0b1010就表示有第1种和第3种钥匙（从低位数）。当拾取钥匙时做nk |= (1 << idx)，判断是否有钥匙时做nk & (1 << idx)。这套位运算非常自然，配合vis数组的第三维，就可以正确处理“同一位置但携带钥匙不同”的状态。

在竞赛中，状态压缩BFS的坑主要是空间。vis数组的第三维大小等于1 << K，当K较大（比如10以上）时，内存可能爆掉。这时要么用unordered_map来记录已访问状态，要么进一步压缩状态（如把坐标也编码进整数）。我的建议是：如果N*N*(1<<K)超过 1e7，就果断用哈希表，虽然慢一点但能保命。

4. 剪枝优化的四大方向与实操模板

4.1 可行性剪枝与最优性剪枝

搜索的暴力版谁都会写，但能让搜索在限定时间内跑完的，全靠剪枝。剪枝可以分成两大类：可行性剪枝（这个分支不可能到达答案）和最优性剪枝（这个分支就算走下去，也不会比当前最优解更好）。

我见过不少选手在写DFS时只想着“能不能提前return”，但很少系统地分析剪枝的维度。实际上，一个高效的搜索算法应该同时考虑多个剪枝条件，而不是只靠一个“金剪子”。

典型的可行性剪枝例子：搜索组合数时，如果当前选了几个，剩下的不够凑满目标，就剪掉。模板：

void dfs(int start, int cnt, int sum) { if (cnt + (n - start + 1) < need) return; // 剩下的全选都不够 if (sum > target) return; if (cnt == need && sum == target) { ... } for (int i = start; i <= n; i++) { if (sum + a[i] > target) continue; // 最优性剪枝 dfs(i + 1, cnt + 1, sum + a[i]); } }

这里的cnt + (n - start + 1) < need就是典型的可行性剪枝——判断“就算把后面所有元素都选上，数量是否够”。像这种剪枝往往能极大减少搜索树的分支，而且代码就一行，性价比极高。

最优性剪枝的常见形式是“当前步数 >= 已知最优解时 return”。在“最少步骤”类题目中，我们通常初始化ans = INF，每次dfs传入当前的步数，如果step >= ans就直接剪掉。这种剪枝简单粗暴，但配合迭代加深使用时，比单纯判断step更有效。

4.2 顺序剪枝与上下界剪枝

搜索顺序对剪枝效果影响巨大。同样一组数据，一个良好的搜索顺序可能让时间从超时降到几十毫秒。竞赛中常用“从大往小搜”或“优先搜索约束最多的分支”。这听起来抽象，我举一个“木棒拼接”的经典例题：

题目是：给定若干根散木棒的长度，要把它们拼成若干根等长的完整木棒，求可能的最小原始木棒长度。这是一个典型的搜索+剪枝题。很多新手直接按输入顺序搜索会超时，而正确的做法是：

• 把所有木棒按长度从大到小排序，搜索从大到小选；
• 记录上一次尝试失败的木棒长度，相同长度不在同一个位置重复尝试；
• 当拼好一根新木棒时，如果第一根木棒就失败，直接回溯到上层。

其中“相同长度不重复尝试”就是顺序剪枝，而“第一根失败直接回溯”属于上下界的隐含剪枝。这些技巧在竞赛模板中非常常见。

bool dfs(int idx, int cnt, int curLen) { if (cnt == k) return true; for (int i = idx; i < n; i++) { if (used[i] || curLen + a[i] > target) continue; if (a[i] == a[i-1] && !used[i-1]) continue; // 相同长度跳过 used[i] = true; if (curLen + a[i] == target) { if (dfs(0, cnt + 1, 0)) return true; } else { if (dfs(i + 1, cnt, curLen + a[i])) return true; } used[i] = false; if (curLen == 0 || curLen + a[i] == target) return false; // 关键剪枝 } return false; }

这个模板几乎就是“木棒拼接”的标准解法。其中if (curLen == 0 || curLen + a[i] == target) return false;是极其重要的几个剪枝之一。它的原理是：如果在一根全新木棒的开头就失败，那么这根木棒无论怎么换别的组合都无法成功，因为后面的木棒没有能替代当前开头位置的；同理，如果当前木棒刚好被填满却无法完成剩余任务，那么这根小棒也不能被其他方案替代。这两个剪枝可以让指数级搜索瞬间瘦身。

4.3 剪枝的成效评估思路

剪枝不是越多越好，因为每次剪枝判断本身也有开销。如果某个剪枝条件很少触发，却每次进入循环都要计算，反而拖慢程序。我一般会在混合剪枝时给每个剪枝打一个“触发频率”的标签：

• 高频且计算便宜：直接放在循环内部开头。
• 低频但计算复杂：放在函数入口处，先判断再进入循环。
• 极端情况剪枝：只在特定数据上需要，平时可能用不上，但写上无妨。

实际做题时，我会先在暴力版本上加上最简单的可行性/最优性剪枝，看能否通过部分测试点；如果超时，再逐步加入更复杂的剪枝，并用随机数据测试剪枝后的扩展节点数。这种方法比盲目堆剪枝高效得多。

5. 启发式搜索：IDA* 与 A* 的实战模板

5.1 A*的估价函数与优先队列实现

A* 算法是带有优先级的BFS，它的核心公式是f(n) = g(n) + h(n)，其中g(n)是到达当前状态的实际代价，h(n)是对从当前状态到目标状态的代价估计。只要h(n)不大于真实代价（即“可采纳”），A* 就能保证第一次出队的目标状态是最优解。

A* 在竞赛中的典型场景是求带权图最短路径、八数码问题等。以八数码为例，状态是3x3棋盘，g是已经走的步数，h可以采用曼哈顿距离之和。模板如下：

#include <bits/stdc++.h> using namespace std; struct State { string board; // 棋盘编码成字符串 int g, h; bool operator<(const State& other) const { return g + h > other.g + other.h; // 小顶堆 } }; int manhattan(const string& board) { int sum = 0; for (int i = 0; i < 9; i++) { if (board[i] == '0') continue; int target = board[i] - '1'; // 期望位置 int x1 = i / 3, y1 = i % 3; int x2 = target / 3, y2 = target % 3; sum += abs(x1 - x2) + abs(y1 - y2); } return sum; } int solve(string start) { priority_queue<State> pq; unordered_map<string, int> dist; pq.push({start, 0, manhattan(start)}); dist[start] = 0; string goal = "123456780"; while (!pq.empty()) { State cur = pq.top(); pq.pop(); if (cur.board == goal) return cur.g; if (dist[cur.board] < cur.g) continue; // 旧状态跳过 int pos = cur.board.find('0'); int x = pos / 3, y = pos % 3; for (int dir = 0; dir < 4; dir++) { int nx = x + dx[dir], ny = y + dy[dir]; if (nx < 0 || nx > 2 || ny < 0 || ny > 2) continue; string nxt = cur.board; swap(nxt[pos], nxt[nx * 3 + ny]); int ng = cur.g + 1; if (dist.count(nxt) && dist[nxt] <= ng) continue; dist[nxt] = ng; pq.push({nxt, ng, manhattan(nxt)}); } } return -1; }

这个模板里有几个竞赛细节值得注意：

• board用string编码，查找0的位置用find，交换直接用swap，编写极其方便。虽然比整数编码略慢，但胜在清晰，适合赛时快速实现。
• priority_queue的排序规则是反直觉的，operator<返回g + h > other.g + other.h才能让f最小的先出队。很多人第一次写容易反掉，建议直接记住这个写法。
• unordered_map记录dist是为了处理“同一个状态被不同路径到达”的情况。当发现新的g不比记录的dist小，就跳过，避免无效扩展。

A* 的难点不在模板，而在h的设计。竞赛中常用h有：曼哈顿距离、欧氏距离、模式数据库等。一般来说h越接近真实代价，搜索节点越少；但同时计算h的开销也越大。对于类似八数码的问题，曼哈顿距离是一个很好的折中。

5.2 IDA*：迭代加深与启发式结合的递归写法

IDA*（Iterative Deepening A*）是“迭代加深DFS”与“A启发式”的结合。它不用优先队列，而是把阈值作为DFS的深度限制，不断加大阈值直到找到解。其优势在于：不需要维护dist哈希表，空间占用小；递归结构简单，代码比A短。缺点是可能重复搜索很多次，但对许多题目来说仍然高效。

以“数独”或“骑士周游”类问题为例，IDA*的模板是这样的：

int maxDepth; bool dfs(int depth, int pos, int totalCost) { if (depth + estimate(pos) > maxDepth) return false; // 超出阈值 if (isGoal(pos)) return true; for (每个后继状态 nxt) { if (dfs(depth + 1, nxt, ...)) return true; } return false; } void solve() { maxDepth = 0; while (true) { if (dfs(0, start, 0)) break; maxDepth++; } }

关键点在于depth + estimate(pos) > maxDepth这个判断。这里estimate是从当前状态到目标状态的最少步数估计，它必须要小于等于真实步数。每一步迭代maxDepth+1，其实就是把搜索树的半径加大一圈，并通过启发式估计来避免探索“死活到不了目标”的分支。

我在做迭代加深题目时，有一个经验是：maxDepth的递增步长不一定非要是1，有时候可以加2甚至加3。因为如果答案在很远的地方，每次只加1会导致大量重复搜索；但步长过大又可能首超一定距离，错过更优解。一般先从1开始，如果估计答案距离较长，可以改成“当前深度+估计值”作为新的阈值，这样收敛更快。

IDA* 适合那些“状态很多、路径很长、但估计函数较好”的题目。比如“骑士到达目标”的题，用IDA就比BFS更简洁。因为骑士的棋盘状态太大，BFS会MLE，而IDA用DFS天然省空间。

6. 双向搜索与迭代加深的模板与适用场景

6.1 双向BFS：正向和逆向同时扩展

双向BFS用来解决“起点和终点都明确，状态空间巨大”的最短路问题。它的思想是：从起点和终点同时各扩展一层，当两边状态相遇时，把步数相加得到最短路径。复杂度从b^d降到2 * b^(d/2)，提升不是一点点。

模板（以单词变换为例，每次改变一个字母，问最少步数）：

int bfs(string start, string target) { if (start == target) return 0; unordered_map<string, int> dist1, dist2; queue<string> q1, q2; q1.push(start); q2.push(target); dist1[start] = 0; dist2[target] = 0; while (!q1.empty() && !q2.empty()) { // 每次扩展较小的队列 if (q1.size() > q2.size()) { swap(q1, q2); swap(dist1, dist2); } int sz = q1.size(); for (int i = 0; i < sz; i++) { string cur = q1.front(); q1.pop(); int d = dist1[cur]; for (每个可能的变换 next) { if (dist1.count(next)) continue; if (dist2.count(next)) return d + 1 + dist2[next]; dist1[next] = d + 1; q1.push(next); } } } return -1; }

双向BFS的模板有几个关键技巧：

• 每次优先扩展队列元素较少的一侧，这可以保证总扩展量尽量小。实现上直接swap两个队列和对应的距离表，代码很简洁。
• 当生成的后继状态已经在对方距离表中出现时，说明双方搭上了桥，此时d + 1 + dist2[next]就是最短路径。
• 距离表用unordered_map，因为状态总数通常比较大，数组不方便。

双向BFS并不适用于所有题型。它要求“逆向搜索”也能进行，即我们要能从目标状态反推前驱。例如迷宫类问题通常可以从终点反向走，但如果题目给的是“操作序列”，反向操作和正向操作往往不等价，这时就要小心设计逆向生成函数。

6.2 迭代加深DFS的经典写法

迭代加深DFS（IDDFS）是另一种应对“深度未知”的搜索策略。它通过限制搜索深度，从小到大递增，来解决“DFS会一条路走到黑，BFS空间太大”的问题。它在状态空间为树形时非常高效，因为每层节点数通常是指数增长的，重复搜索上层带来的额外代价往往可以接受。

模板（以“埃及分数”为例，把真分数拆成若干个单位分数之和）：

bool dfs(int depth, int maxDepth, long long a, long long b, long long lastDeno) { if (depth == maxDepth) { if (a == 0) { // 记录答案 return true; } return false; } // 从 lastDeno+1 开始枚举分母 for (long long i = max(lastDeno + 1, (b + a - 1) / a); i <= (maxDepth - depth) * b / a; i++) { long long na = a * i - b; long long nb = b * i; if (na < 0) continue; if (dfs(depth + 1, maxDepth, na, nb, i)) return true; } return false; }

这里(b + a - 1) / a是保证当前分数a/b不小于1/i的最小分母，而(maxDepth - depth) * b / a是保证剩余项都能用单位分数表示。这套上下界也是迭代加深搜索中“启发式剪枝”的体现。

迭代加深与IDA的关系非常紧密：当迭代加深DFS中加入“剩余深度下界”剪枝时，就升级成了IDA。我的建议是：如果题目不需要复杂估价函数，就直接用IDDFS；如果需要优化，在IDDFS里加一个estimate()函数变成IDA*，代码改动很小但效果明显。

7. 竞赛实战中的搜索题解构套路

7.1 从题目条件快速判断搜索类型

在拿到一道题时，不要急着写代码，先花两分钟判断它适合哪种搜索类型。我总结了一套“选拔标准”：

• 数据范围极小（n <= 8）：一般直接用DFS全排列枚举，配合剪枝。如数独、八皇后、排列组合。
• n <= 20：状态压缩搜索或状态压缩DP。
• 需要最短步数且状态空间较大：优先考虑双向BFS、A或IDA。尤其是题目给定了明确的目标状态（如华容道、魔方），启发式搜索几乎是必选项。
• 求是否存在一种方案，而不需求最优：DFS往往足够，注意剪枝。
• 每条状态转移代价都相等：BFS；代价不等则用A*或IDDFS。

这个判断不是百分百准确，但它能帮你快速确定大方向。很多高级题实际上是多种搜索类型的组合，例如“迭代加深+剪枝+状态压缩”，这时候就需要综合运用多个模板。

7.2 一个典型综合案例：十六宫格数字谜题

我拿一个常见的“十六宫格数字谜题”（15-puzzle）来演示综合解构的思路。这道题把1~15的数字放在4x4方格中，留一个空位，每次将空位移到相邻位置，要求恢复为有序排列。

如果直接用BFS，状态总数为16! / 2，大约是1.05e13，显然存不下。此时我们需要用IDA*。估价函数可以用“每个数字的曼哈顿距离之和”，因为每一步最多将一个数字的曼哈顿距离减少1，所以这个估价是可采纳的。同时还需要一个奇偶性判断：对于一个目标排列，若逆序对数的奇偶性与空位行号满足特定关系，则无解，可以在进入搜索前直接排除，避免无限迭代。

这就是一个典型的“搜索选择+估价函数+可行性判断”的组合。我在模拟赛时写过这个题，当时卡在内存上，后来改成IDA*，从几秒优化到几百毫秒，深刻体会到选对搜索框架的重要性。

7.3 竞赛中的搜索调试技巧

搜索算法的调试比普通算法更痛苦，因为一旦答案不对，很难定位是“剪枝剪多了”还是“状态编码错了”。我自己的调试套路是这样：

• 先跑小数据，关闭所有剪枝，对比暴力和优化版本的结果是否一致。
• 如果一致，再逐步打开剪枝，观察答案是否变化。一旦变化，说明新打开的剪枝有逻辑漏洞。
• 记录搜索树深度和扩展节点数的调试信息（比如在dfs入口累计调用次数），用来对比剪枝效果。
• 对状态压缩类题目，写一个解码函数，打印出每个状态对应的实际局面，方便肉眼观察。

这些小技巧虽然不直接改变算法，但能大幅节省调bug的时间。竞赛场上，调通一道题往往比想出算法更耗时间。

8. 从模板到高分的进阶训练路线

模板只是起点，真正的高分需要把模板内化成自己的“肌肉记忆”，并在各种题目里灵活变形。我个人比较推荐的三阶段训练法是：

第一阶段：裸模板过题。找十几道不同类型的搜索题，包括DFS、BFS、状态压缩、双向BFS、IDA*，每类至少两题。这个阶段不追求效率，只求把模板写熟。写的时候手不要看代码，自己要能默写出来。

第二阶段：剪枝强化。选一些经典的搜索难题（题目名一般带“搜索”、“剪枝”关键词），比如木棒拼接、靶形数独、生日蛋糕。做完之后，对比题解中的剪枝，看看自己的搜索树大了多少倍。不断尝试优化，直到时间和题解接近。

第三阶段：综合变形。做涉及搜索的省选/国赛题目，这些题往往不裸考搜索，而是把搜索作为某个环节的工具，比如“在DP中转移时用搜索枚举子集”、“用搜索预处理状态”。这时候训练的是把搜索与其他算法结合的能力。

我自己的体验是：很多选手卡在第一阶段到第二阶段之间，因为他们觉得“模板我都会了，剪枝太玄学”。但剪枝不是玄学，它的本质是尽量不重复计算，并用数学上下界排除无用分支。遇到一道题，多问自己几个问题：当前状态有没有无解的可能？当前解有没有已经是次优的可能？后面可选的元素还够不够？这些问题想清楚了，剪枝自然就出来了。

还有一个高频问题：刷搜索题是否需要大量时间？我的回答是，搜索是性价比极高的算法类型。你花两周专项训练，之后遇到绝大多数穷举类题目都会有清晰的思路。而且搜索对代码能力的要求很综合，练搜索的同时，递归、位运算、STL容器、复杂度分析都会得到提升。

9. 常见搜索错误速查表与避坑清单

我把过去几年刷题时遇到的搜索报错/答案错，整理成了一张速查表，每一条都是血泪经验。

这里重点说一下“启发式搜索超时”的问题。我最早写A*时，h随便写了一个“相同数字个数”，要是没有正确性和强约束力，导致搜索几乎退化成BFS，五分钟后跑不出来。后来意识到h必须是“到目标的距离下界”，而且要尽量大。曼哈顿距离在网格问题中如此好用，核心原因就是它既是下界，又比“相同数字个数”大得多。这个原则适用于所有博弈和路径类搜索。

最后还有一个容易被忽略的细节：搜索题的数据读入和输出往往也有很多坑。比如多组测试数据时，全局变量和距离表没有清空；字符串包含空格导致cin读入失败；状态编码时没有统一起始位置等等。建议把读入和状态初始化封装成函数，每组数据调用一次，减少人为遗漏。

信息竞赛里的搜索模块，内容远比想象中丰富。从基础DFS到IDA*，每往上走一层，对状态空间的理解就加深一层。模板的意义是让你在赛场上不慌，但真正决定水平的是你对状态空间的洞察力：知道哪些状态可以合并、哪些分支可以剪掉、哪个方向值得先去搜。把这些点想明白，再配合本文给出的模板勤加练习，搜索难题也会变得有章可循。