ACM51个经典算法大全：分层训练与C++模板实战指南

简介这份《ACM51个经典算法大全》面向ACM竞赛选手与算法学习者是一份系统梳理经典算法题目的中文文档适合希望夯实算法基础、提升编程思维的中高级学习者。资源包内含1个doc文档共126页压缩包约1.77MB以题目、解题思路、分析过程与可运行源码为主线组织内容。文档覆盖递归、图论、动态规划、搜索与组合优化等多个方向具体包括河内之塔、费式数列、巴斯卡三角形、三色棋、老鼠走迷宫、骑士走棋盘、八皇后、八枚银币、生命游戏、字串核对、双色与三色河内塔、背包问题、蒙地卡罗法求PI、Eratosthenes筛选求质数、超长整数运算等51个经典案例每个案例均配有思路拆解与源码实现。目前已有406人学习下载适合作为竞赛备赛与算法专题训练的参考材料帮助读者按目录逐项练习、对照源码理解算法细节并查漏补缺。1. 从“51 个经典算法”说起一份 ACM 训练清单到底该怎么用很多人第一次看到“ACM51个经典算法大全”这类标题会下意识当成一份可以背下来的题库。真打过区域赛的人都知道算法不是背出来的而是练出来的。这 51 个算法覆盖的是竞赛里反复出现的核心套路排序、二分、贪心、动态规划、图论最短路、字符串匹配、数论、计算几何入门、搜索剪枝。它们不是孤立的 51 个知识点而是一张互相咬合的能力网。这份清单真正的价值在于它给出了一个可执行的训练顺序。新手容易犯的错是从 KMP 或线段树直接开冲结果连复杂度分析都写不利索老手则容易只刷自己熟的题型遇到网络流或数位 DP 就卡壳。合理的用法是把它当成一张地图先按难度分层再按专题成组刷每道题都逼自己写出复杂度、边界条件和反例。下面几章就按这个思路把这份清单拆成能落地的训练路径、代码模板和调试方法。2. ACM51个经典算法大全的分层与专题归类2.1 为什么不能按 1 到 51 顺序刷清单本身没有严格难度排序如果按编号硬刷很容易在早期撞上计算几何或后缀数组这类门槛较高的内容挫败感直接劝退。常见做法是按“基础数据结构 → 基础算法思想 → 图论 → 字符串 → 数论 → 进阶专题”重新分组每组内部再按难度递增。我一般把 51 个算法分成四层。第一层是排序、二分查找、前缀和、双指针、简单贪心这些是几乎所有题的基础设施。第二层是动态规划、BFS/DFS、并查集、堆、哈希属于竞赛主力。第三层是最短路、最小生成树、拓扑排序、KMP、快速幂、扩展欧几里得。第四层是网络流、线段树、树状数组、数位 DP、计算几何、博弈论。分层之后每层刷透再进下一层节奏会稳很多。2.2 用一张表把 51 个算法映射到训练优先级层级代表算法建议投入典型题型L1 基础冒泡/归并/堆排序、二分查找、前缀和12 周模拟、查找、区间统计L2 主力动态规划、BFS/DFS、并查集、堆34 周背包、网格搜索、连通性L3 进阶最短路、MST、KMP、快速幂34 周图论建模、字符串匹配L4 高阶网络流、线段树、数位 DP、计算几何4 周以上区间维护、计数、几何判定这张表不是绝对标准但能帮你判断当前该把时间花在哪。判断依据很简单如果一道 L2 题你要想 40 分钟才有思路就别急着碰 L4。2.3 每个算法要练到什么程度才算过关过关的标准不是“看懂题解”而是三个动作能独立完成第一能在 10 分钟内写出无 bug 的模板第二能说清时间复杂度和空间复杂度并知道在什么数据规模下会超时第三能构造出至少一个让朴素写法出错的反例。以二分查找为例很多人以为自己会但边界处理经常翻车。下面是一个我常用的左闭右开模板// 在有序数组 a 中查找第一个 target 的位置 // 左闭右开区间 [lo, hi)返回下标找不到返回 hi int lowerBound(vectorint a, int target) { int lo 0, hi a.size(); while (lo hi) { int mid lo (hi - lo) / 2; // 防止 lohi 溢出 if (a[mid] target) lo mid 1; else hi mid; } return lo; }逻辑说明循环不变量是“答案始终落在 [lo, hi) 内”。当a[mid] target时mid 及其左侧都不可能是答案所以lo mid 1否则 mid 可能是答案hi mid。参数上lo (hi - lo) / 2比(lo hi) / 2更安全避免大下标相加溢出。这个模板稍作改动就能变成查找最后一个 target的位置建议自己推一遍。3. 用 C 把高频算法模板跑通的最小命令3.1 本地编译与对拍环境准备竞赛代码大多用 C本地验证离不开编译和对拍。最小环境只需要 g 和一个终端。编译命令建议固定成下面这样把警告全开很多边界 bug 在编译期就能暴露# -O2 开启优化-Wall -Wextra 打开警告-stdc17 指定标准 g -O2 -Wall -Wextra -stdc17 -o sol sol.cpp ./sol input.txt参数说明-O2是竞赛常用优化级别能显著加快 STL 和循环-Wall -Wextra会提示未使用变量、符号比较等隐患-stdc17保证结构化绑定、auto推导等特性可用。如果本地跑得动但评测机超时先检查是不是忘了开-O2。对拍是验证算法正确性的关键手段。写一个暴力程序brute.cpp和一个随机数据生成器gen.cpp用脚本循环比对for i in $(seq 1 1000); do ./gen input.txt ./sol input.txt out1.txt ./brute input.txt out2.txt if ! diff -q out1.txt out2.txt /dev/null; then echo WA on case $i; break fi done逻辑说明gen每次生成一组小规模随机数据两个程序分别跑出结果diff不一致就说明找到反例。参数上随机数据规模要小到暴力能秒出同时覆盖边界比如 n1、全相同元素、已排序、逆序等。3.2 排序与二分从冒泡到归并的复杂度跃迁排序是清单里出现频率最高的基础算法。冒泡、插入、选择是 O(n²)归并和堆排序是 O(n log n)快排平均 O(n log n) 但最坏 O(n²)。竞赛里几乎不会手写冒泡但理解它的交换次数对逆序对问题有帮助。归并排序的模板值得背下来因为它顺带能求逆序对long long mergeSort(vectorint a, int l, int r) { if (r - l 1) return 0; int mid (l r) / 2; long long cnt mergeSort(a, l, mid) mergeSort(a, mid, r); vectorint tmp; int i l, j mid; while (i mid j r) { if (a[i] a[j]) tmp.push_back(a[i]); else { cnt mid - i; tmp.push_back(a[j]); } // 右侧元素小左侧剩余都构成逆序 } while (i mid) tmp.push_back(a[i]); while (j r) tmp.push_back(a[j]); copy(tmp.begin(), tmp.end(), a.begin() l); return cnt; }逻辑说明归并过程中当右侧元素a[j]小于左侧a[i]时左侧从 i 到 mid-1 的所有元素都与a[j]构成逆序对数量是mid - i。参数上返回类型用long long因为逆序对数量在 n1e5 时可达约 5e9int 会溢出。这是很多人第一次写逆序对时踩的坑。3.3 图论三件套最短路、最小生成树、拓扑排序图论是 ACM 的重头戏。最短路里 Dijkstra 处理非负权Bellman-Ford 和 SPFA 能处理负权Floyd 适合小规模全源最短路。最小生成树用 Kruskal 配合并查集最省事。拓扑排序用入度队列即可。Dijkstra 的堆优化模板typedef pairint,int PII; // (距离, 节点) vectorint dijkstra(int n, vectorvectorPII g, int s) { vectorint dist(n, INT_MAX); priority_queuePII, vectorPII, greaterPII pq; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; // 过期状态直接跳过 for (auto [v, w] : g[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } return dist; }逻辑说明优先队列按距离升序弹出if (d dist[u]) continue是懒删除的关键避免处理已经过期的状态。参数上INT_MAX作为无穷大时加法前要确保dist[u]不是无穷否则会溢出稳妥做法是判断dist[u] ! INT_MAX。边权为负时不能用 Dijkstra这是选型红线。4. 动态规划与搜索剪枝的实战调参4.1 背包问题的状态设计与空间压缩动态规划是清单里占比最大的部分而背包是 DP 的入门范式。0/1 背包、完全背包、多重背包的状态转移只差一个循环方向但含义完全不同。0/1 背包内层倒序完全背包内层正序这个细节每年都有人写反。// 0/1 背包容量 W物品重量 w[i]价值 v[i] vectorint dp(W 1, 0); for (int i 0; i n; i) for (int j W; j w[i]; j--) // 倒序保证每件物品只用一次 dp[j] max(dp[j], dp[j - w[i]] v[i]);逻辑说明倒序遍历容量保证dp[j - w[i]]还是上一轮未选当前物品的状态。如果正序就变成完全背包每件物品可以重复选。参数上dp数组大小是W1初始化为 0 表示不选任何物品时价值为 0。若要求恰好装满则除dp[0]0外其余初始化为负无穷。4.2 剪枝算法在 DFS 中的三个必调参数搜索题不剪枝基本必超时。剪枝的核心是提前判断当前分支不可能产生更优解。常见三类可行性剪枝、最优性剪枝、搜索顺序剪枝。以“数的划分”或“埃及分数”这类题为例三个关键参数是当前深度、剩余目标值、可选的起始值。// 以组合求和为例从 start 开始选数剩余 target当前已选路径 path void dfs(int start, int target, vectorint path) { if (target 0) { /* 记录一组解 */ return; } for (int i start; i target; i) { if (i target) break; // 可行性剪枝 path.push_back(i); dfs(i, target - i, path); // 允许重复选下一层从 i 开始 path.pop_back(); } }逻辑说明i target保证剩余值不会被选成负数这是最基本的可行性剪枝。搜索顺序上从start开始避免重复组合。参数上如果题目不允许重复选下一层传i 1如果要求去重还要加同层跳过相同元素的判断。剪枝效果好不好取决于你把“最可能出解”的分支排在前面。4.3 用对拍验证 DP 与搜索的正确性DP 和搜索最容易出的错是状态定义错、边界漏、重复计数。对拍时暴力程序用最朴素的递归或枚举主程序用优化后的 DP。随机数据要覆盖小规模全范围比如 n 从 1 到 8值域从 1 到 10。跑上几百组基本能暴露大部分逻辑错误。提示对拍发现 WA 后先把出错的那组数据单独存下来手动模拟一遍状态转移比盯着代码看快得多。5. 字符串与数论算法的进阶技巧5.1 KMP 的 next 数组到底在算什么KMP 是字符串匹配的经典算法核心是 next 数组也叫失配函数。它记录的是“模式串前缀与后缀相等的最大长度”。理解这一点匹配时失配就不用回退主串指针。vectorint buildNext(const string p) { int m p.size(); vectorint nxt(m, 0); for (int i 1, j 0; i m; i) { while (j 0 p[i] ! p[j]) j nxt[j - 1]; // 回退到上一个可能匹配的位置 if (p[i] p[j]) j; nxt[i] j; } return nxt; }逻辑说明j表示当前已匹配的前缀长度。当p[i] ! p[j]时回退到nxt[j-1]即缩短前缀继续尝试。参数上nxt[i]的含义是子串p[0..i]的最长相等前后缀长度。匹配主串时失配就令j nxt[j-1]主串指针不回退整体复杂度 O(nm)。5.2 快速幂与扩展欧几里得的边界处理数论题里快速幂和扩展欧几里得是高频工具。快速幂要注意指数为 0、模数为 1 的边界扩展欧几里得要注意负数取模和 gcd 为 0 的情况。long long qpow(long long a, long long b, long long mod) { long long res 1 % mod; // mod 为 1 时结果应为 0 a % mod; while (b 0) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; }逻辑说明res初始化为1 % mod而不是 1是为了处理 mod1 时结果必须为 0 的边界。a % mod防止底数过大溢出。参数上b用long long接收因为指数可能很大。扩展欧几里得求逆元时要保证模数与求逆元素互质否则逆元不存在。5.3 数论题的常见溢出与取模陷阱数论题最隐蔽的坑是中间乘法溢出。两个 1e9 级别的数相乘会超过 int甚至超过 long long 的安全范围。稳妥做法是用__int128或先取模再乘。另一个坑是负数取模C 中-1 % 3结果是 -1需要手动加模数调整到正数。写数论题时建议把取模封装成函数统一处理。陷阱错误写法正确做法中间乘法溢出res res * a % mod用__int128或先转 long long负数取模x % mod(x % mod mod) % mod逆元不存在直接调用 exgcd先判断 gcd(a, mod) 16. 把 51 个算法变成稳定得分的训练节奏清单刷到后期拼的不是会不会而是稳不稳。一个具体技巧是建立自己的“模板库 错题本”双文件。模板库存放经过对拍验证的代码按专题分类比赛时直接复制改错题本记录每道 WA 的原因比如“二分边界写错”“DP 初始化漏了负无穷”“Dijkstra 没判 INT_MAX”。每周复盘一次错题本比盲目刷新题有效得多。另一个技巧是限时模拟。按区域赛 5 小时 10 题的节奏每周做一场虚拟赛强制自己在压力下分配时间。通常前 1 小时解决签到题和简单题中间 2 小时攻中等题最后 2 小时留给难题或检查。如果一道题卡了 40 分钟还没思路果断换题这是很多队伍的得分分水岭。最后验证自己是否真的掌握某个算法标准是能不能在 15 分钟内从零写出模板并通过对拍。做不到就回到第 2 章的分层表把它降一级重新练。51 个算法不是终点而是让你在遇到新题时能快速判断它属于哪一类、该调用哪个工具。本文还有配套的精品资源点击获取