ACM基础算法模板工程化：图论、数据结构与字符串常见坑位全梳理

简介《ACM基础算法模板2》是一份面向算法竞赛初学者和ACM选手的便携模板集覆盖快速读入、高精度四则运算、快速幂、组合数与排列数、质数判定、分解质因数、欧拉筛等常考基础模块并附有GCD/LCM与整数二分查找模板适合日常刷题和赛前速查对刚接触算法竞赛的读者尤为友好。包内共1个PDF文件压缩包仅513KB体积小巧便于按目录快速定位、对照抄写或打印携带。已有225人学习浏览适合需要系统夯实数论与高精度基础的读者。文件中每个模板都给出可直接调用的C函数实现并对关键边界做了注释例如快读兼容负数、高精度除法的余数通过引用返回、欧拉筛利用最小质因子退出循环等能帮助理解原理而非死记代码。高精度系列突出进位/借位处理数学部分给出模运算与逆元预处理写法可作为长期留存的备赛笔记整体实用性强。1. 为什么每位 ACM 选手都在持续维护一份《ACM基础算法模板2》一场五小时的四小时提交队列里前六十分钟大家都能写出最短路和最小生成树真正拉开差距的是谁能在最后一百分钟把后缀自动机、费用流这类高难度模板从编辑器里调出来直接改。所谓《ACM基础算法模板2》并不是给你一份复制粘贴即 AC 的「葵花宝典」而是帮助你沉淀一套有分类、有参数、有边界条件、可快速改写的数据结构与算法的代码骨架。它解决的核心问题只有一个把「从零写一遍」变成「改一改参数跑通」把赛场上最贵的思考时间留给题目本身。这套模板适合正在准备区域赛或校赛的选手也适合想系统梳理常见算法套路、并在笔试或面试中快速验证思路的开发者。它的价值不在于代码本身有多漂亮而在于你能否在压力下准确调用并且知道每一行背后为什么这么写。如果你见过那些 .cpp 文件动辄两千行、命名乱到查都查不到的选手你就明白模板工程化和「能用」之间差着一条血泪经验的鸿沟。接下来我会按我的实际维护思路把这套体系打散重讲从组织方式、核心模块、参数边界到避坑点逐一拆开。2. 模板工程化的第一步分类骨架、命名规范与代码复用策略2.1 先设计目录骨架按算法类别分文件而不是按题号存代码ACM 基础算法模板的组织方式决定你赛场上找代码的速度。常见做法是把代码按类别拆成独立的 .h 或 .cpp 片段放到同一个目录里集中管理。我一般用的目录骨架是acm-templates/ ├── math/ # 数论、组合、线性基、FFT ├── graph/ # 最短路、网络流、匹配、树相关 ├── string/ # KMP、AC 自动机、后缀数组、Manacher ├──>// tools/FastIO.h 片段 #pragma once #include bits/stdc.h using namespace std; struct FastScanner { static const int BUFSIZE 1 20; int idx, size; char buf[BUFSIZE]; FastScanner(): idx(0), size(0) {} inline char getChar() { if (idx size) { size fread(buf, 1, BUFSIZE, stdin); idx 0; if (size 0) return \0; } return buf[idx]; } template typename T bool readInt(T out) { char c; T sign 1; T num 0; c getChar(); if (c \0) return false; while (c ! - (c 0 || c 9)) { c getChar(); if (c \0) return false; } if (c -) { sign -1; c getChar(); } for (; c 0 c 9; c getChar()) num num * 10 (c - 0); out num * sign; return true; } };这段代码的核心思路是用自定义缓冲区替代标准cin的逐字符解析减少 I/O 库内部开销。参数说明BUFSIZE一般取 120 即 1MB太大浪费内存太小会增加fread调用次数readInt返回false表示读到文件末尾因此在多组数据场景里你可以用while (fs.readInt(n))作为循环条件。注意T sign使用模板类型而不是long long是为了保持整数类型一致避免赋值时产生符号位扩展的隐式转换问题。3. 图论与数据结构模板的实战写法从最短路到并查集3.1 用链式前向星封装图结构数组化存储保证内存连续图论模板的地基是图存储方式。我们常说邻接表用vectorint adj[N]简洁易读但 ACM 赛场上更常见的做法是链式前向星因为它在处理多组测试数据时不需要频繁clear()只需要重置head数组和cnt即可并且内存连续对缓存友好。// graph/LinkedForwardStar.h const int MAXN 100005; const int MAXM 200005; struct Edge { int to, next, weight; } edges[MAXM]; int head[MAXN], cnt; void initGraph(int n) { cnt 0; memset(head, -1, sizeof(int) * (n 1)); } void addEdge(int u, int v, int w) { edges[cnt].to v; edges[cnt].weight w; edges[cnt].next head[u]; head[u] cnt; } void addUndirectedEdge(int u, int v, int w) { addEdge(u, v, w); addEdge(v, u, w); }逻辑说明head[u]存储的是从 u 出发的第一条边的下标next指向下一条边。每次新增边都插入链表的头部所以遍历顺序和输入顺序相反但这不影响算法正确性。初始化时把head前n1个位置置为 -1避免对整个数组做memset当题目n很小但数组很大时能省下不少时间。参数注意MAXM对于无向边要开两倍大小这是最容易被新手忽略的前提。3.2 Dijkstra 堆优化模板INF 的取值与模板参数传递在链式前向星之上写堆优化的 Dijkstra 是区域赛最常用的路径模板。代码中使用priority_queue维护当前距离最小的节点配合vis数组标记是否已确定最短路。// graph/Dijkstra.h #include queue #include cstring struct Status { int u; long long dist; bool operator(const Status other) const { return dist other.dist; // 小顶堆 } }; void dijkstra(int start, int n, long long dist[], int pre[]) { const long long INF 0x3f3f3f3f3f3f3f3fLL; for (int i 1; i n; i) { dist[i] INF; pre[i] -1; } priority_queueStatus pq; dist[start] 0; pq.push({start, 0}); while (!pq.empty()) { Status top pq.top(); pq.pop(); if (top.dist ! dist[top.u]) continue; // 跳过过期状态 for (int e head[top.u]; e ! -1; e edges[e].next) { int v edges[e].to; long long nd top.dist edges[e].weight; if (nd dist[v]) { dist[v] nd; pre[v] top.u; pq.push({v, nd}); } } } }两个细节值得说明。第一INF 0x3f3f3f3f3f3f3f3fLL而不是INT_MAX是因为dist要做加法运算用INT_MAX加上一个正边权会溢出成负数进而被错误地当作更短路径。0x3f3f3f3f 这个十六进制的每字节都是 0x3f两个这样的值相加仍然小于 64 位有符号整数上限这是竞赛圈最常用的「安全无限大」。第二pre数组用于路径回溯不需要时可以传nullptr但保留它能在你怀疑答案错误时快速打印路径做核对。3.3 并查集的路径压缩与按秩合并两个优化缺一不可并查集看起来简单但模板里同时写路径压缩和按秩合并能保证find操作接近常数级别复杂度。单独使用路径压缩时find的均摊复杂度已经接近常数但如果遇到极端构建的退化树递归深度仍可能让栈溢出按秩合并则进一步控制树高。//>//>// string/KMP.h vectorint buildNext(const string pattern) { int m (int)pattern.size(); vectorint next(m 1, 0); for (int i 1, j 0; i m; i) { while (j 0 pattern[i] ! pattern[j]) j next[j]; if (pattern[i] pattern[j]) j; next[i 1] j; } return next; } vectorint kmpSearch(const string text, const string pattern) { vectorint next buildNext(pattern); vectorint matches; int m (int)pattern.size(); for (int i 0, j 0; i (int)text.size(); i) { while (j 0 text[i] ! pattern[j]) j next[j]; if (text[i] pattern[j]) j; if (j m) { matches.push_back(i - m 1); j next[j]; } } return matches; }这套模板采用的是next[i1] j的写法next[i]代表模式串前 i 个字符的最长相等前后缀长度。失配时j next[j]的含义是当前已匹配到模式串第 j 个字符0 基前 j 个已成功匹配那就用这前 j 个字符的最长前后缀长度作为下一次继续比对的位置。参数说明当j m时表示匹配成功记录起始位置i - m 1然后把j置为next[m]相当于复用已匹配前缀中的后缀部分继续寻找下一个重叠匹配。4.2 快速幂与模运算小心负数取模和乘法溢出数论模板里最基础也最常用的是快速幂应用范围覆盖模逆元计算、矩阵快速幂前置步骤、指数取模等场景。这里需要注意 C 的取模运算对负数并非数学意义上的取模因此模板里要单独处理负数情况。// math/QuickPow.h long long quickPow(long long base, long long exp, long long mod) { long long res 1 % mod; base % mod; if (base 0) base mod; // 处理负数底数 while (exp 0) { if (exp 1) { res (res * base) % mod; } base (base * base) % mod; exp 1; } return res; } long long modAdd(long long a, long long b, long long mod) { a % mod; b % mod; if (a 0) a mod; if (b 0) b mod; return (a b) % mod; }逻辑说明快速幂把指数拆成二进制位底数每移位一次就自乘一次只有在当前二进制位为 1 时才把累积结果乘上底数的当前幂。这样做的时间复杂度是 O(log exp)。参数注意mod为 1 时1 % mod等于 0避免返回 1 导致错误base ^ 2在long long范围内相乘如果mod接近 1e18需要改用快速乘将乘法拆位相加来避免溢出这是模板里最容易被忽略的隐藏风险。4.3 Z 算法与 Manacher什么时候值得放进进阶模板如果你的《ACM基础算法模板2》定位是区域赛冲奖级别那么字符串章节至少还要加入 Z 算法、Manacher 和 AC 自动机。Z 算法的核心思想是维护一个[l, r]区间记录已匹配的最靠右的相同前缀区间。它的实现比 KMP 更短且更直观但使用率低于 KMP所以我会将它放在同一文件中作为备选函数。// string/ZAlgorithm.h vectorint zFunction(const string s) { int n (int)s.size(); vectorint z(n); int l 0, r 0; for (int i 1; i n; i) { if (i r) z[i] min(r - i 1, z[i - l]); while (i z[i] n s[z[i]] s[i z[i]]) z[i]; if (i z[i] - 1 r) { l i; r i z[i] - 1; } } return z; }z[i]表示从 i 开始的子串与整个字符串s的最长公共前缀长度。注意当i r时可以直接从已经计算过的z[i-l]继承初始值但不能超过r - i 1这个区间边界。该模板用于「在一个文本串中查找模式串的所有出现位置」时常用做法是把模式串和文本串用分隔符合并成一个字符串再对合并后的字符串求 Z 数组识别出 Z 值等于模式串长度的位置。5. 避坑排查手册模板复用时最常翻车的五个环节5.1 现象多组数据之间状态残留导致答案诡异地递增或错乱每次使用模板前忘记重置全局数组是 ACM 赛场上最常见的犯傻方式。链式前向星的cnt没有归零Dijkstra 的dist数组只初始化了前 n 个可上一次数据 n 更大时留下尾部脏数据这些并不会直接编译报错而是让算法结果变得完全不可预测。解决方法是统一封装一个reset函数并在每组数据输入后第一时间调用养成肌肉记忆先读 n再 reset再读边。5.2 现象堆优化的 Dijkstra 在使用visited标记后偶尔 WAvisited数组在 Dijkstra 中的作用本应是防止重复处理节点但是在优先队列中一个节点可能被多次松弛后 push 进去。正确写法是使用if (top.dist ! dist[top.u]) continue;而不是在 pop 时检查visited。原因是当节点被更长的路径再次更新时visited已经被置为 true你会跳过所有后续的松弛机会。这类 bug 非常隐蔽因为小数据跑几次都能过一旦数据量上来就随机翻车。5.3 现象线段树的懒惰标记只在更新时下推查询时忘记推导致区间查询错误懒标记设计的要点是「用到哪个节点就推哪个节点」。很多人写的update函数有pushDown调用但query函数里却漏掉了导致上层节点保留了未下推的 lazy 值又直接返回了过时的sum。排查方式写一个小型暴力对拍程序随机生成区间加和区间求和操作比对线段树结果和朴素数组的结果是否一致。此类问题一旦复现你的模板会在压力测试下暴露原型。5.4 现象KMP 匹配在模式串最后一个字符失配时越界下标部分选手把 next 数组实现为长度 m 而不是 m1在j next[j]时如果j恰好等于 m下一次访问pattern[j]就会越界。因此在匹配循环的while (j 0 text[i] ! pattern[j])之前必须先保证j m或者直接使用 m1 长度的 next 数组并让next[m]有意义。这是字符串模板的小坑老选手通常靠记忆规避但建议在文档注释里写清楚next的下标约定。5.5 现象模运算结果为负数导致判题返回 WAC 的%运算符对负数返回负数比如(-5) % 3在数学上期望是 1但 C 返回 -2。如果你在计算组合数模 p、逆元等场景没有做修正就会得到完全错误的结果。通用修正是result (result % mod mod) % mod。这个修正不是可有可无的需要写进所有数学模板的公共工具函数里。6. 让模板成为肌肉记忆压力测试与赛前自检的实用技巧模板写完之后并不能直接上赛场你需要通过若干轮「模板题」检验每个算法片段是否在紧张环境下仍然能快速适配。我的习惯是每个月从在线评测系统的题目集里挑出十道模板型题目覆盖最短路径、并查集、线段树、KMP、快速幂和维护最值这几类高频依赖每道题限定二十分钟内完成调通。这不仅仅是为了验证代码正确更是为了强迫自己记住模板的关键改动点比如 Dijkstra 的模板里pre数组是否需要打开线段树的lazy是否需要long longKMP 的 next 长度是 m 还是 m1。第二个技巧是为每个模板文件编写「改动清单」注释。在文件头部注释里写清楚这个算法的常见变体比如「Dijkstra 改边权为负时要用 SPFA不可用本模板」「线段树区间取最大值时要同时维护 min 和 max 两个值」「KMP 若匹配模式串本身为前缀需要在循环末尾检查 j 是否为 0」。这些注释的价值在于当你半年后重新打开这份模板时能迅速回忆起当初踩过的坑而不是重新陷入漫长的代码考古。最后值得一提的是模板的多版本管理。我不建议把每个算法的旧写法删掉重写而应该用注释保留一个基础版本和一个优化版本。比如并查集可以同时保留递归 find 和循环 find 两种实现递归版代码短但深度有风险循环版稍长但更稳。赛后复盘时看到哪些模板被高频修改就定期把那些常用改法固化到主模板里。我自己曾经在区域赛模拟赛上因为快速幂模板没有处理 mod 1 的边界而丢掉一整道题的分从此以后每份模板都带上了边界测试注释。希望帮到你。本文还有配套的精品资源点击获取