算法竞赛入门算法串讲：构建你的“解题工具箱”

引言

初入算法竞赛，你可能会被各类名词淹没：DP、二分、并查集、KMP、线段树……但其实，绝大多数简单到中等难度的题目都建立在不超过十个基础算法之上。它们就像武学中的“太祖长拳”——招式朴实无华，但组合起来威力无穷。

本文不追求某个算法的深度，而是为你绘制一张入门算法全景地图。读完它，你将知道：

• 每类算法解决什么问题？

• 时间复杂度如何？

• 什么时候用它？什么时候换别的？

• 代码如何快速实现？

前置知识（快速自查）

在开始前，请确保你能熟练完成以下操作（任何一项卡住都请先补基础）：

• 用 C++ 写一个 for 循环，能正确输入输出。

• 理解数组下标、字符串操作、结构体。

• 会写递归函数（如求阶乘），明白递归调用栈。

• 会使用 STL 中的 vector、sort、queue、stack、priority_queue。

• 能估算一段代码的时间复杂度（大 O 记号）。

若以上没问题，我们开始。

第一章：暴力与枚举 —— “大力出奇迹，但必须用在刀刃上”

核心思想
枚举所有可能的候选答案，逐一验证。它是唯一能保证正确性的“万能算法”，但代价是指数级或多项式级的时间。

常见场景（按难度升序）：

优化技巧（暴力也要有智慧）：

• 剪枝（Pruning）：在DFS中，如果当前路径已经不可能产生最优解（如长度已超过已知最优），立即返回。

• 预排序：先排序，再枚举，可利用单调性提前 break。

• 折半搜索（Meet in the Middle）：将问题分成两半，分别枚举，再合并。典型例题：POJ 2785 4 Values whose Sum is 0（n=4000，四数组各取一个数和为0）。

复杂度等级：

• O(n²) —— n ≤ 5000 时可接受（约 2.5×10⁷ 次）。

• O(2ⁿ) —— n ≤ 25 时可接受（约 3.3×10⁷）。

• O(n!) —— 只适用于 n ≤ 11。

何时使用暴力？

• 当数据范围极小（题目明确给出小范围）。

• 作为验证其他算法的“对拍器”（生成随机数据，与自己写的正解对比）。

• 在想不到正解时，先写暴力拿部分分。

记忆口诀

数据小，暴力上；剪枝好，跑得快；折半搜，翻倍强。

第二章：模拟 —— “翻译题意为代码，一次过是本事”

核心思想
模拟就是“按题目描述一步一步执行”。它不考验算法思维，而是考验建模能力和细心程度。模拟题的变量往往很多，容易写错。

典型题型：

• 时间推进型：如“程序运行时间”、“病毒扩散”、“时钟走动”。通常用 while (cur_time <= limit) 循环。

• 矩阵操作型：如“旋转矩阵”、“蛇形填数”、“扫雷展开”。注意方向数组 dx[] = {1, -1, 0, 0}。

• 游戏规则型：如“扑克牌发牌”、“俄罗斯方块”、“生命游戏”。需要清晰定义“状态”和“状态转移函数”。

• 字符串解析型：如“计算器表达式”、“日期格式化”。常用 sscanf 或手写解析。

代码技巧：

• 函数拆分：将“移动”、“判断胜负”、“打印棋盘”等封装成函数，主函数只控制流程。

• 防御性编程：每次访问数组前检查边界，避免越界。

• 调试手段：中途输出关键变量，或写一个 print_state() 函数。

复杂度：通常是 O(总步数) 或 O(n×m)，与模拟轮次成正比。

易错点：

• 循环终止条件错误（如多跑一轮或少跑一轮）。

• 读题不仔细，忽略特殊规则（如“若同时发生则按X优先”）。

• 数组维度搞反（a[i][j] 与 a[j][i]）。

记忆口诀

题意读透再动笔，函数分离逻辑清；边界条件多检查，样例手动过一遍。

第三章：贪心 —— “局部最优，步步为营，但须证明”

核心思想
每一步都做当前最优的选择，希望最终结果最优。贪心算法不回溯，因此必须用数学方法证明其正确性（交换论证、归纳法、反证法）。

经典贪心模型：

判断是否贪心：

• 问题具有 贪心选择性质（局部最优能推出全局最优）。

• 问题具有 最优子结构（子问题的最优解能组合成原问题的最优解）。

如果无法证明，尝试用动态规划（DP）——贪心是DP的特例（每步决策只依赖局部信息）。

复杂度：通常为排序的 O(n log n) 或 O(n)。

常见陷阱：

• 贪心策略看似合理，实则有反例。例如“找零钱”用贪心并不总是正确（如面额 1, 3, 4，要凑 6，贪心取 4+1+1=3枚，但最优是 3+3=2枚）。

• 因此，贪心必须经过严格证明，不能凭感觉。

记忆口诀

贪心先看性质，证明之后才敢用；排序往往是前奏，反例一戳就破功。

第四章：二分与三分 —— “单调性是天赐的线索”

核心思想
二分：在单调函数中，通过不断缩小区间找到目标值或分界点。三分：在单峰/单谷函数中求极值点。

二分两大家族：

三分法：

• 用于求解凸函数或凹函数的极值点（如二次函数）。

• 取 mid1 = l + (r-l)/3，mid2 = r – (r-l)/3，比较 f(mid1) 和 f(mid2) 来缩小范围。

• 实数三分需设定迭代次数（如 100 次）或精度。

注意事项：

• 整数二分的边界：while (l < r) 与 mid = (l+r)/2 搭配，注意当 l 和 r 相邻时是否死循环。常用写法：

  cpp

  int l = 0, r = n; // [l, r)
  while (l < r) {
  int mid = (l + r) >> 1;
  if (check(mid)) r = mid;
  else l = mid + 1;
  }

• 实数二分：for (int i=0; i<100; ++i) 固定迭代次数，避免精度误差。

记忆口诀

单调数据二分查，答案可行二分判；凸函数用三分，极值就在区间里。

第五章：搜索（DFS / BFS）—— “状态空间遍历术”

深度优先搜索（DFS）

• 本质：递归枚举所有可能状态，直到边界或目标。

• 实现：递归函数，参数为当前状态。

• 剪枝三大类：

  • 可行性剪枝：当前状态已不可能达到目标（如剩余步数不够）。

  • 最优性剪枝：当前代价已超过已知最优解。

  • 对称性剪枝：避免重复搜索等价状态。

• 记忆化搜索：将 dfs(state) 的结果存起来（即“递归版DP”），避免重复计算。

广度优先搜索（BFS）

• 本质：逐层扩展，保证第一次到达目标时步数最少（在无权图中）。

• 实现：队列，vis 数组标记已访问。

• 空间优化：双向BFS（从起点和终点同时扩展，相遇时结束），可将状态数从 b^d 降到 2*b^(d/2)。

• 状态压缩：当状态可以用整数表示时，BFS 效率更高（如八数码用 Cantor 展开）。

二者对比与选择：

常见变形：

• 迭代加深 DFS（IDDFS）：限制搜索深度，逐步放宽，适用于深度未知且 BFS 空间过大的情况。

• *A 搜索**：引入估价函数，优先搜索最有希望的节点（需启发式）。

记忆口诀

DFS 递归带剪枝，BFS 队列求最短；双向 BFS 大法好，状态压缩省空间。

第六章：动态规划 —— “记住历史，避免重复劳动”

核心思想
将原问题分解为子问题，并存储子问题的解（状态），避免重复计算。DP 是算法竞赛中最灵活也最难的模块，但入门只需掌握几种经典模型。

五步分析法（硬背下来）：

入门必学的四大DP模型：

优化技巧（入门需了解）：

• 滚动数组：当只依赖上一行时，用一维数组代替二维。

• 前缀和优化：转移时需枚举 k，可用前缀和将 O(n³) 降为 O(n²)。

• 单调队列优化：用于带区间限制的 DP（如多重背包）。

记忆口诀

状态定义是关键，转移方程靠推导；初始化别漏掉，计算顺序要定好。

第七章：图论基础 —— “点与线构建的世界”

图的存储（重点掌握邻接表）：

cpp

vector<int> G[N]; // 无向图，双向加边
vector<pair<int,int>> G[N]; // 带权图

邻接矩阵仅用于稠密图且 n ≤ 500。

图的遍历：

• DFS/BFS 均可，求连通块个数（如岛屿数量）。

最短路算法（三大经典）：

最小生成树：

• Kruskal：边排序 + 并查集，O(E log E)。

• Prim：类似 Dijkstra，适合稠密图。

并查集（DSU）：

• 核心操作：find(x)（路径压缩）、union(a,b)（按秩合并）。

• 应用：连通性判断、Kruskal、动态连通性（离线逆序处理）。

拓扑排序（DAG）：

• Kahn 算法：入度为0的点入队，逐层删除。

• 用于判断是否有环、任务调度、DP 递推顺序。

记忆口诀

建图用邻接表，遍历 DFS/BFS；最短路堆优 Dijkstra，生成树 Kruskal 并查集；拓扑排序入度零，无环才是 DAG。

第八章：常用数据结构 —— “工欲善其事，必先利其器”

栈（Stack）

• LIFO，典型应用：

  • 括号匹配：左括号入栈，右括号弹出匹配。

  • 表达式求值（中缀转后缀）。

  • DFS 的显式栈（防止递归栈溢出）。

队列（Queue）

• FIFO，用于 BFS、滑动窗口（配合单调队列）。

• 双端队列 deque：支持两端插入删除，用于单调队列优化DP。

优先队列（Priority Queue）

• 内部为堆，自动维护极值。

• 应用：Dijkstra、哈夫曼树、多路归并、维护动态数据流的中位数（两个堆）。

哈希表（unordered_map / unordered_set）

• 平均 O(1) 查询，但常数较大。

• 注意：竞赛中可能被故意卡哈希（构造大量冲突），解决办法：自定义哈希函数，或使用 map（红黑树 O(log n)）。

set / map

• 有序容器，基于红黑树。

• 应用：动态维护有序集合，求前驱后继，区间查询。

bitset

• 位压缩，支持高效的位运算（与、或、异或、移位）。

• 常用于状压DP加速（如背包可行性）。

记忆口诀

栈后进先出，队先进先出；堆顶最值，哈希查找快；set/map 自动序，bitset 位操作强。

如何选择算法？（决策指南）

当你拿到一道题，按以下顺序思考：

结语

以上八大模块，覆盖了算法竞赛入门阶段的所有核心知识点。但知道 ≠ 掌握，唯有通过大量刷题，才能将这些知识内化为条件反射。建议按模块顺序，在洛谷、Codeforces、AtCoder 上分别刷 10~15 道相应标签的题，每道题都要想清楚它属于哪一类、用了什么优化。

当你能熟练识别题目类型并快速写出模板代码时，你已经迈过了算法竞赛的第一道门槛。接下来，就可以挑战更高级的算法（线段树、网络流、后缀自动机、多项式算法等）。但无论走多远，这些基础算法永远是你最坚实的后盾。

“算法竞赛的乐趣，不在于掌握多少高阶技巧，而在于能用简单的工具组合出解决复杂问题的方案。祝你在代码的世界里，越战越勇。”                                    

最后的最后：

一个AFO的oier希望看到这里的读者都能由此启发开启你的OI/ACM之路，路上的风景真的很美。这条路不会一帆风顺，你会在某个题上卡上几天，会在某场比赛中爆零到怀疑人生，会看着别人的高分代码羡慕不已。但请相信，每一个退役的选手都会告诉你：值得。

我的OI之路啊，那是一段小有遗憾的幸福时光啊

暴搜挂着机，打表出省一。骗分过样例，暴力出奇迹。
数学先打表，DP看运气。穷举TLE，打表UKE。
模拟MLE，贪心还CE。想要骗到分，就要有办法。
图论背模板，数论背公式。动规背方程，高精背代码。
如果都没背，干脆输样例！
七八个测试点，两三次CE前，旧时题解花样变，听取WA声一片