本章主要介绍一些基础算法,为之后的进阶内容做铺垫。
一方面,这些内容可以让初学者对 ACM 的一些思想有初步的认识;另一方面,本章介绍的大部分算法还会在以后的进阶内容中得到运用。
算法基础简介
复杂度
枚举
模拟
递归 & 分治
贪心
排序
前缀和 & 差分
二分
倍增
构造
搜索
搜索部分简介
DFS(搜索)
BFS(搜索)
双向搜索
启发式搜索
以下是扩展
A*
迭代加深搜索
IDA*
回溯法
Dancing Links
Alpha-Beta 剪枝
优化
动态规划
动态规划部分简介
动态规划基础
记忆化搜索
背包 DP
区间 DP
DAG 上的 DP
树形 DP
状压 DP
数位 DP
以下为扩展:
插头 DP
计数 DP
动态 DP
概率 DP
DP 优化
其它 DP 方法
字符串
字符串部分简介
字符串基础
标准库
字符串匹配
字符串哈希
字典树 (Trie)
前缀函数与 KMP 算法
AC 自动机
后缀数组 (SA)
Boyer-Moore 算法
Z 函数(扩展 KMP)
后缀自动机 (SAM)
后缀平衡树
广义后缀自动机
后缀树
Manacher
回文树
序列自动机
最小表示法
Lyndon 分解
Main-Lorentz 算法
数学 (这一部分较难,需要系统学习)
数学部分简介
符号
进位制
位运算
二进制集合操作
平衡三进制
高精度计算
快速幂
置换和排列
弧度制与坐标系
复数
数论
多项式与生成函数
组合数学
线性代数
线性规划
群论
概率论
博弈论
牛顿迭代法
数值积分
傅里叶-莫茨金消元法
序理论
杨氏矩阵
Schreier–Sims 算法
Berlekamp-Massey 算法
数据结构
数据结构部分简介
栈
队列
链表
哈希表
并查集
堆
块状数据结构
单调栈
单调队列
ST 表
树状数组
线段树
以下为扩展
李超线段树
区间最值操作 & 区间历史最值
划分树
二叉搜索树 & 平衡树
跳表
可持久化数据结构
树套树
K-D Tree
动态树
析合树
PQ 树
手指树
霍夫曼树
图论
图论部分简介
图论相关概念
图的存储
DFS(图论)
BFS(图论)
树上问题
矩阵树定理
有向无环图
拓扑排序
最小生成树
斯坦纳树
最小树形图
最小直径生成树
最短路
拆点
差分约束
以下是扩展:
k 短路
同余最短路
连通性相关
2-SAT
欧拉图
哈密顿图
二分图
最小环
平面图
图的着色
网络流
Stoer-Wagner 算法
图的匹配
Prufer 序列
LGV 引理
弦图
最大团搜索算法
点/边连通度
计算几何
计算几何部分简介
二维计算几何基础
三维计算几何基础
距离
Pick 定理
三角剖分
凸包
扫描线
旋转卡壳
半平面交
平面最近点对
随机增量法
反演变换
计算几何杂项