1 介绍
1.1 竞赛算法概述
01.算法竞赛简介
a.主要竞赛
a.ACM-ICPC
国际大学生程序设计竞赛，团队赛。
b.NOI
全国青少年信息学奥林匹克竞赛。
c.Codeforces
在线编程竞赛平台，个人赛。
d.AtCoder
日本的在线编程竞赛平台。
b.竞赛特点
时间限制严格、题目难度大、需要快速实现。
02.竞赛算法分类
a.网络流
最大流、最小割、费用流。
b.高级数据结构
Splay树、树套树、莫队算法、树链剖分。
c.高级DP
基环树DP、插头DP、斜率优化。
d.计算几何
凸包、半平面交、旋转卡壳。
e.高级数学
莫比乌斯反演、FFT、生成函数。
03.竞赛准备
a.知识储备
掌握所有基础和进阶算法。
b.代码模板
准备常用算法的代码模板。
c.调试技巧
快速定位和修复bug。
d.时间管理
合理分配做题时间。
1.2 网络流基础
01.网络流概述
a.定义
网络流是一个有向图，每条边有容量限制，求从源点到汇点的最大流量。
b.基本概念
a.容量
边的最大流量限制。
b.流量
边上实际通过的流量。
c.残留网络
每条边的剩余容量。
c.最大流最小割定理
最大流等于最小割。
02.网络流应用
a.二分图匹配
转化为网络流问题。
b.多源多汇
添加超级源点和超级汇点。
c.费用流
在最大流基础上考虑费用最小。
03.常见算法
a.Ford-Fulkerson
不断寻找增广路，时间复杂度不稳定。
b.Edmonds-Karp
使用BFS寻找最短增广路，O(VE²)。
c.Dinic
分层图+多路增广，O(V²E)。
d.ISAP
改进的SAP算法，实际效率高。
1.3 高级数据结构体系
01.数据结构分类
a.基础数据结构
数组、链表、栈、队列、树、图、哈希表。
b.高级数据结构
平衡树、堆、并查集、线段树、树状数组。
c.专业数据结构
Splay树、树套树、LCT、后缀数组、AC自动机。
02.学习路线
a.第一阶段
掌握基础数据结构的实现和应用。
b.第二阶段
学习线段树、树状数组等高级数据结构。
c.第三阶段
学习平衡树、树链剖分等专业数据结构。
1.4 计算几何入门
01.基本概念
a.点和向量
点用坐标表示，向量表示方向和大小。
b.叉积
判断点的位置关系、计算面积。
c.点积
判断角度、计算投影。
02.常见问题
a.点与线段
判断点是否在线段上。
b.线段相交
判断两线段是否相交。
c.凸包
包含所有点的最小凸多边形。
03.应用场景
a.图形学
碰撞检测、可见性判断。
b.地理信息系统
路径规划、区域查询。
1.5 竞赛准备策略
01.知识储备
a.算法模板
整理常用算法的代码模板，比赛时快速调用。
b.数据结构
熟练掌握各种数据结构的实现。
c.数学知识
数论、组合数学、概率论基础。
02.刷题策略
a.按专题刷
集中练习同一类型题目，形成肌肉记忆。
b.做题后总结
整理解题思路和易错点。
c.参加模拟赛
定期参加Codeforces、AtCoder等在线比赛。
03.比赛技巧
a.快速读题
先浏览所有题目，选择擅长的先做。
b.时间分配
简单题快速通过，难题合理分配时间。
c.代码调试
使用样例测试，注意边界条件。
2 网络流
2.1 最大流算法
01.Dinic算法
a.基本思想
构建分层图，使用DFS多路增广。
b.Java实现
---
class Edge {
int to, cap, flow;
Edge(int to, int cap) {
this.to = to;
this.cap = cap;
}
}
List<Edge>[] graph;
int[] level, iter;
public int maxFlow(int s, int t, int n) {
graph = new ArrayList[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
level = new int[n];
iter = new int[n];
int flow = 0;
while (bfs(s, t, n)) {
Arrays.fill(iter, 0);
int f;
while ((f = dfs(s, t, Integer.MAX_VALUE)) > 0) {
flow += f;
}
}
return flow;
}
private boolean bfs(int s, int t, int n) {
Arrays.fill(level, -1);
Queue<Integer> queue = new LinkedList<>();
level[s] = 0;
queue.offer(s);
while (!queue.isEmpty()) {
int u = queue.poll();
for (Edge e : graph[u]) {
if (level[e.to] < 0 && e.cap > e.flow) {
level[e.to] = level[u] + 1;
queue.offer(e.to);
}
}
}
return level[t] >= 0;
}
private int dfs(int u, int t, int f) {
if (u == t) return f;
for (int i = iter[u]; i < graph[u].size(); i++) {
iter[u] = i;
Edge e = graph[u].get(i);
if (level[u] < level[e.to] && e.cap > e.flow) {
int d = dfs(e.to, t, Math.min(f, e.cap - e.flow));
if (d > 0) {
e.flow += d;
return d;
}
}
}
return 0;
}
---
02.ISAP算法
a.优化
使用gap优化和当前弧优化。
b.时间复杂度
O(V²E)，实际效率很高。
2.2 二分图匹配
01.二分图最大匹配
a.匈牙利算法
使用DFS为每个左侧节点寻找匹配。
b.时间复杂度
O(VE)。
02.最大匹配应用
a.任务分配
将n个任务分配给m个人。
b.婚配问题
稳定婚配问题。
2.3 最小割理论
01.最大流最小割定理
a.定理
网络的最大流等于最小割。
b.应用
将最小割问题转化为最大流问题。
02.最小割应用
a.网络可靠性
最少删除多少条边使网络不连通。
b.图像分割
将图像分为前景和背景。
2.4 费用流
01.最小费用最大流
a.定义
在最大流的基础上，使得总费用最小。
b.应用
带权二分图匹配、运输问题。
02.算法
a.SPFA增广
使用SPFA找最短增广路。
b.时间复杂度
O(nmf)，f是最大流。
03.应用场景
a.任务分配
最小化总成本。
b.物流运输
最小化运输费用。
2.5 上下界网络流
01.无源汇上下界可行流
a.问题
每条边有流量上下界，判断是否存在可行流。
b.解法
转化为普通网络流问题。
02.有源汇上下界最大流
a.问题
在满足上下界的前提下求最大流。
b.解法
先求可行流，再求最大流。
03.有源汇上下界最小流
a.问题
在满足上下界的前提下求最小流。
b.解法
转化为最大流问题。
2.6 网络流建图技巧
01.拆点
a.点容量限制
将点拆成入点和出点。
b.应用
限制经过某点的流量。
02.分层图
a.多阶段问题
按阶段建立分层图。
b.应用
最短路变形问题。
03.常见模型
a.最大独立集
转化为最小割。
b.最小点覆盖
König定理：最小点覆盖=最大匹配。
2.7 网络流综合应用
01.项目选择
a.问题
选择一些项目，最大化收益。
b.建图
最小割模型。
02.方格取数
a.问题
在方格中取数，最大化总和。
b.建图
最小割或最大流。
03.餐巾计划
a.问题
餐巾的购买、清洗、租赁策略。
b.建图
最小费用最大流。
3 高级数据结构
3.1 Splay树
01.Splay树概述
a.定义
自适应的平衡二叉搜索树。
b.特点
最近访问的节点会被旋转到根。
02.Splay操作
a.旋转
zig、zig-zig、zig-zag。
b.时间复杂度
均摊O(log n)。
03.应用
a.动态维护序列
支持插入、删除、查询。
b.区间操作
区间翻转、区间求和。
3.2 树套树
01.线段树套平衡树
a.定义
线段树的每个节点维护一棵平衡树。
b.应用
区间第K大、区间排名。
02.树状数组套线段树
a.定义
树状数组的每个节点维护一棵线段树。
b.应用
二维区间修改和查询。
03.时间复杂度
a.空间
O(n log² n)
b.时间
O(log² n)
3.3 分块算法
01.分块思想
a.基本思想
将序列分成√n块，块内暴力，块间优化。
b.时间复杂度
O(√n)
02.区间修改查询
a.整块
打标记。
b.散块
暴力修改。
03.应用
a.区间众数
分块+莫队。
b.区间第K小
分块+二分。
3.4 莫队算法
01.莫队算法
a.基本思想
离线处理区间查询，按特殊顺序处理询问。
b.时间复杂度
O(n√n)
02.普通莫队
a.排序
按左端点所在块排序，块内按右端点排序。
b.移动指针
add和remove操作。
03.带修改莫队
a.时间维度
增加时间戳维度。
b.复杂度
O(n^(5/3))
04.树上莫队
a.欧拉序
将树转化为序列。
b.应用
树上路径查询。
3.5 树链剖分
01.树链剖分概述
a.定义
将树分解成若干条链，每个节点属于唯一一条链。
b.重链剖分
优先选择子树大小最大的儿子作为重儿子。
c.应用
树上路径查询、树上路径修改。
02.重链剖分实现
a.第一次DFS
计算子树大小、深度、父节点、重儿子。
---
int[] size, depth, parent, son;
void dfs1(int u, int p, int d) {
size[u] = 1;
depth[u] = d;
parent[u] = p;
son[u] = -1;
for (int v : graph[u]) {
if (v == p) continue;
dfs1(v, u, d + 1);
size[u] += size[v];
if (son[u] == -1 || size[v] > size[son[u]]) {
son[u] = v;
}
}
}
---
b.第二次DFS
计算链的顶端、DFS序。
---
int[] top, dfn;
int timestamp;
void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++timestamp;
if (son[u] != -1) {
dfs2(son[u], t);
}
for (int v : graph[u]) {
if (v == parent[u] || v == son[u]) continue;
dfs2(v, v);
}
}
---
03.路径查询
a.LCA查询
---
int lca(int u, int v) {
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) {
int temp = u; u = v; v = temp;
}
u = parent[top[u]];
}
return depth[u] < depth[v] ? u : v;
}
---
b.路径和查询
结合线段树维护DFS序上的区间和。
3.6 动态树LCT
01.Link-Cut Tree
a.定义
维护动态森林的数据结构。
b.操作
link、cut、makeRoot、findRoot。
02.Splay维护
a.实链剖分
将树剖分成若干实链。
b.Splay维护
每条实链用Splay维护。
03.应用
a.动态连通性
动态加边删边。
b.动态树上路径
路径求和、路径最值。
3.7 后缀数组
01.后缀数组
a.定义
所有后缀按字典序排序后的数组。
b.构造
倍增算法O(n log n)。
02.height数组
a.定义
相邻后缀的最长公共前缀。
b.性质
height[i] >= height[i-1] - 1
03.应用
a.最长重复子串
height数组的最大值。
b.不同子串个数
n*(n+1)/2 - Σheight[i]
3.8 后缀自动机
01.后缀自动机SAM
a.定义
识别所有后缀的最小自动机。
b.状态数
O(n)
02.构造
a.在线构造
逐个添加字符。
b.时间复杂度
O(n)
03.应用
a.子串匹配
O(m)时间匹配。
b.本质不同子串
状态数-1
c.最长公共子串
在SAM上匹配。
4 高级DP与分治
4.1 基环树DP
01.基环树
a.定义
n个点n条边的连通图。
b.特点
恰好有一个环。
02.DP策略
a.断环
枚举断开环上的一条边。
b.树形DP
在树上进行DP。
03.应用
a.最大独立集
选择不相邻的点。
b.最小支配集
每个点被选中或与选中点相邻。
4.2 四边形不等式优化
01.四边形不等式
a.定义
w(a,c) + w(b,d) <= w(a,d) + w(b,c)
b.应用
区间DP优化。
02.决策单调性
a.性质
最优决策点单调。
b.优化
O(n³) -> O(n²)
03.应用题
a.石子合并
满足四边形不等式。
b.邮局选址
决策单调性优化。
4.3 插头DP
01.插头DP
a.定义
基于连通性的状态压缩DP。
b.应用
棋盘覆盖、回路计数。
02.轮廓线
a.定义
当前处理位置的边界。
b.状态
用二进制表示插头状态。
03.应用
a.多米诺骨牌
2×n棋盘覆盖。
b.Hamilton回路
经过所有格子恰好一次。
4.4 点分治
01.点分治
a.基本思想
选择树的重心，统计经过重心的路径。
b.时间复杂度
O(n log n)
02.算法步骤
a.找重心
使最大子树最小。
b.统计
统计经过重心的路径。
c.递归
递归处理子树。
03.应用
a.路径统计
统计满足条件的路径数。
b.距离问题
树上距离为K的点对数。
4.5 CDQ分治
01.CDQ分治
a.基本思想
分治处理，统计左边对右边的贡献。
b.应用
三维偏序、动态逆序对。
02.三维偏序
a.问题
统计满足x[i]<x[j], y[i]<y[j], z[i]<z[j]的点对数。
b.解法
第一维排序，第二维分治，第三维树状数组。
03.动态逆序对
a.问题
支持删除元素，查询逆序对数。
b.解法
CDQ分治+树状数组。
4.6 斜率优化DP
01.斜率优化
a.适用条件
DP转移方程可以写成斜率形式。
b.优化
O(n²) -> O(n)
02.凸包优化
a.维护下凸壳
单调队列或单调栈。
b.查询
二分或双指针。
03.应用题
a.任务安排
斜率优化经典题。
b.玩具装箱
斜率优化DP。
4.7 DP综合优化
01.优化技巧总结
a.空间优化
滚动数组、状态压缩。
b.时间优化
单调队列、斜率优化、四边形不等式。
02.常见优化
a.前缀和优化
O(n²) -> O(n)
b.单调栈优化
维护单调性。
c.矩阵快速幂
线性递推优化。
03.综合应用
a.多重背包
二进制优化。
b.最长上升子序列
O(n log n)优化。
5 计算几何
5.1 二维计算几何基础
01.点和向量
a.点的表示
class Point { int x, y; }
b.向量运算
加减、数乘、点积、叉积。
02.叉积应用
a.判断方向
叉积正负表示左右。
b.计算面积
三角形面积 = |叉积| / 2。
03.点积应用
a.判断角度
点积正负表示锐钝角。
b.计算投影
投影长度 = 点积 / 模长。
5.2 凸包算法
01.凸包定义
a.基本概念
包含所有点的最小凸多边形。
b.应用场景
最远点对、旋转卡壳。
02.Graham扫描法
a.基本思想
按极角排序，使用栈维护凸包。
b.Java实现
---
class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public List<Point> convexHull(Point[] points) {
int n = points.length;
if (n < 3) return Arrays.asList(points);
// 找到最下方的点
int minIdx = 0;
for (int i = 1; i < n; i++) {
if (points[i].y < points[minIdx].y ||
(points[i].y == points[minIdx].y && points[i].x < points[minIdx].x)) {
minIdx = i;
}
}
Point p0 = points[minIdx];
// 按极角排序
Arrays.sort(points, (a, b) -> {
int cross = cross(p0, a, b);
if (cross == 0) {
return dist(p0, a) - dist(p0, b);
}
return -cross;
});
Stack<Point> stack = new Stack<>();
stack.push(points[0]);
stack.push(points[1]);
for (int i = 2; i < n; i++) {
while (stack.size() > 1) {
Point top = stack.pop();
Point second = stack.peek();
if (cross(second, top, points[i]) > 0) {
stack.push(top);
break;
}
}
stack.push(points[i]);
}
return new ArrayList<>(stack);
}
private int cross(Point o, Point a, Point b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
private int dist(Point a, Point b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
---
03.Andrew算法
a.基本思想
分别求上凸包和下凸包。
b.时间复杂度
O(n log n)。
5.3 半平面交
01.半平面
a.定义
直线将平面分成两部分，其中一部分称为半平面。
b.表示
用直线和方向表示。
02.半平面交
a.定义
多个半平面的交集。
b.算法
增量法或S&I算法。
03.应用
a.多边形核
所有点可见的区域。
b.线性规划
求可行域。
5.4 最小圆覆盖
01.最小圆覆盖
a.问题
找最小的圆覆盖所有点。
b.算法
随机增量法。
02.随机增量法
a.基本思想
逐个加入点，维护最小圆。
b.时间复杂度
期望O(n)
03.应用
a.设施选址
最小化最远距离。
b.传感器覆盖
最小覆盖半径。
5.5 旋转卡壳
01.旋转卡壳
a.定义
用两条平行线夹住凸包旋转。
b.应用
凸包直径、最小矩形覆盖。
02.凸包直径
a.问题
凸包上最远点对。
b.算法
旋转卡壳O(n)
03.最小矩形覆盖
a.问题
最小面积矩形覆盖凸包。
b.算法
旋转卡壳枚举边。
5.6 扫描线算法
01.扫描线
a.基本思想
用一条线扫描平面，维护相关信息。
b.应用
矩形面积并、周长并。
02.矩形面积并
a.问题
多个矩形的面积并。
b.算法
扫描线+线段树。
03.最近点对
a.问题
平面上最近的两个点。
b.算法
分治+扫描线O(n log n)
5.7 计算几何综合
01.点与多边形
a.点在多边形内
射线法、转角法。
b.点到多边形距离
枚举边计算。
02.多边形面积
a.简单多边形
叉积法。
b.复杂多边形
分解为三角形。
03.综合应用
a.多边形求交
Sutherland-Hodgman算法。
b.Voronoi图
平面分割。
6 高级数学
6.1 莫比乌斯反演
01.莫比乌斯函数
a.定义
μ(1)=1, μ(n)=0(n有平方因子), μ(n)=(-1)^k(n是k个不同质数乘积)
b.性质
Σμ(d) = [n==1]
02.莫比乌斯反演
a.公式
f(n)=Σg(d) ⟺ g(n)=Σμ(d)f(n/d)
b.应用
GCD求和、互质数对。
03.应用题
a.GCD求和
Σgcd(i,j)
b.约数个数和
Σd(ij)
6.2 积性函数
01.积性函数
a.定义
f(ab)=f(a)f(b)，当gcd(a,b)=1
b.完全积性
f(ab)=f(a)f(b)对所有a,b成立
02.常见积性函数
a.欧拉函数φ(n)
积性函数。
b.莫比乌斯函数μ(n)
积性函数。
c.约数个数d(n)
积性函数。
03.线性筛
a.筛积性函数
O(n)时间筛出所有值。
b.应用
预处理欧拉函数、莫比乌斯函数。
6.3 BSGS算法
01.Baby-Step Giant-Step
a.问题
求解a^x ≡ b (mod p)
b.算法
分块+哈希表
02.算法步骤
a.Baby Step
预处理a^0, a^1, ..., a^m
b.Giant Step
枚举a^(im) * b
03.扩展BSGS
a.问题
gcd(a,p)≠1的情况
b.解法
转化为互质情况
6.4 FFT快速傅里叶变换
01.FFT
a.问题
多项式乘法O(n²) -> O(n log n)
b.基本思想
点值表示+快速插值
02.算法步骤
a.DFT
系数表示转点值表示
b.点值相乘
O(n)时间
c.IDFT
点值转系数
03.应用
a.大数乘法
将数字看作多项式
b.卷积
信号处理
6.5 生成函数
01.普通生成函数OGF
a.定义
F(x) = Σa_n * x^n
b.应用
组合计数
02.指数生成函数EGF
a.定义
F(x) = Σa_n * x^n / n!
b.应用
排列计数
03.应用
a.整数拆分
生成函数求解
b.组合问题
卷积求解
6.6 Burnside引理
01.Burnside引理
a.定理
本质不同方案数 = Σ不动点数 / |G|
b.应用
旋转、翻转下的计数
02.Pólya定理
a.定理
Burnside引理的推广
b.应用
染色问题
03.应用题
a.项链染色
旋转对称
b.正方形染色
旋转和翻转
6.7 线性基
01.线性基
a.定义
一组数的极大线性无关组
b.性质
可以表示原集合的所有异或和
02.构造
a.贪心插入
O(n log A)
b.高斯消元
O(n²)
03.应用
a.最大异或和
线性基的最大值
b.第K小异或和
线性基排序
6.8 数学综合应用
01.数论综合
a.中国剩余定理
求解同余方程组
b.扩展欧几里得
求解不定方程
02.组合数学
a.容斥原理
计数问题
b.生成函数
递推求解
03.概率期望
a.期望DP
概率转移
b.随机算法
Monte Carlo方法
7 竞赛技巧与实战
7.1 模拟退火
01.模拟退火
a.基本思想
模拟物理退火过程，概率接受更差解
b.应用
函数优化、TSP
02.算法框架
a.初始温度
T0较大
b.降温
T = T * α (α<1)
c.接受准则
Metropolis准则
03.应用
a.最小圆覆盖
随机化+模拟退火
b.函数极值
连续优化问题
7.2 启发式合并
01.启发式合并
a.基本思想
总是将小集合合并到大集合
b.时间复杂度
O(n log n)
02.应用
a.并查集
按秩合并
b.树上启发式合并
dsu on tree
7.3 Manacher算法
01.Manacher算法
a.问题
O(n)求最长回文子串
b.基本思想
利用回文的对称性
02.算法步骤
a.预处理
插入分隔符
b.维护
维护回文中心和右边界
7.4 构造题技巧
01.构造策略
a.从特殊到一般
先考虑特殊情况
b.归纳法
找规律递推
02.常见技巧
a.贪心构造
局部最优
b.分治构造
递归构造
7.5 打表技巧
01.打表策略
a.小数据打表
n<=20时可以打表
b.找规律
观察前几项找规律
02.应用
a.组合数
预处理组合数
b.质数
筛法预处理
7.6 竞赛心态调整
01.比赛前
a.充分准备
复习模板和常见题型
b.保持状态
充足睡眠
02.比赛中
a.冷静分析
不要慌张
b.合理分配时间
先易后难
03.比赛后
a.总结反思
分析错误
b.补题
做不会的题
7.7 NOI/ICPC经典题
01.NOI经典题
a.玩具装箱
斜率优化DP经典题。
b.郁闷的出纳员
平衡树维护区间。
c.矩阵游戏
二分图匹配。
02.ICPC经典题
a.最小费用最大流
网络流建模。
b.计算几何综合
凸包、半平面交。
c.字符串算法
后缀数组、AC自动机。
03.刷题建议
a.按专题刷
集中练习同一类型题目。
b.做题后总结
整理模板和解题思路。
c.参加模拟赛
提升实战能力。
04.竞赛资源
a.在线平台
Codeforces、AtCoder、洛谷、AcWing。
b.题库
POJ、HDU、BZOJ、UOJ。
c.书籍
算法竞赛进阶指南、挑战程序设计竞赛。