第一部分  算    法

第1章  数学 3

　　1.1  矩阵 3

1.1.1  矩阵类 3

1.1.2  Gauss消元 4

1.1.3  矩阵的逆 6

1.1.4  常系数线性齐次递推 7

　　1.2  整除与剩余 9

1.2.1  欧几里得算法 9

1.2.2  扩展欧几里得 9

1.2.3  单变元模线性方程 10

1.2.4  中国剩余定理 11

1.2.5  求原根 13

1.2.6  平方剩余 14

1.2.7  离散对数 15

1.2.8  N次剩余 16

　　1.3  素数与函数 18

1.3.1  素数筛法 18

1.3.2  素数判定 19

1.3.3  质因数分解 20

1.3.4  欧拉函数计算 21

1.3.5  Mobius函数计算 23

　　1.4  数值计算 24

1.4.1  数值积分 24

1.4.2  高阶代数方程求根 26

　　1.5  其他 27

1.5.1  快速幂 27

1.5.2  进制转换 28

1.5.3  格雷码 29

1.5.4  高精度整数 30

1.5.5  快速傅立叶变换 35

1.5.6  分数类 37

1.5.7  全排列散列 38

第2章  图论 40

　　2.1  图的遍历及连通性 40

2.1.1  前向星 40

2.1.2  割点和桥 42

2.1.3  双连通分量 43

2.1.4  极大强连通分量Tarjan

算法 45

2.1.5  拓扑排序 47

2.1.6  2SAT 49

　　2.2  路径 51

2.2.1  Dijkstra 51

2.2.2  SPFA 53

2.2.3  Floyd-Warshall 54

2.2.4  无环图最短路 55

2.2.5  第k短路 56

2.2.6  欧拉回路 59

2.2.7  混合图欧拉回路 61

　　2.3  匹配 64

2.3.1  匈牙利算法 64

2.3.2  Hopcroft-Karp算法 66

2.3.3  KM算法 68

2.3.4  一般图最大匹配 71

　　2.4  树 74

2.4.1  LCA 74

2.4.2  最小生成树Prim算法 77

2.4.3  最小生成树Kruskal算法 78

2.4.4  单度限制最小生成树 79

2.4.5  最小树形图 83

2.4.6  最优比例生成树 85

2.4.7  树的直径 87

　　2.5  网络流 89

2.5.1  最大流Dinic算法 89

2.5.2  最小割 92

2.5.3  无向图最小割 93

2.5.4  有上下界的网络流 95

2.5.5  费用流 97

　　2.6  其他 100

2.6.1  完美消除序列 100

2.6.2  弦图判定 101

2.6.3  最大团搜索算法 103

2.6.4  极大团的计数 105

2.6.5  图的同构 107

2.6.6  树的同构 108

第3章  计算几何 112

　　3.1  多边形 112

3.1.1  计算几何误差修正 112

3.1.2  计算几何点类 113

3.1.3  计算几何线段类 115

3.1.4  多边形类 117

3.1.5  多边形的重心 118

3.1.6  多边形内格点数 119

3.1.7  凸多边形类 120

3.1.8  凸多边形的直径 123

3.1.9  半平面切割多边形 124

3.1.10  半平面交 126

3.1.11  凸多边形交 128

3.1.12  多边形的核 129

3.1.13  凸多边形与直线集交 130

　　3.2  圆 133

3.2.1  圆与线求交 133

3.2.2  圆与多边形交的面积 134

3.2.3  最小圆覆盖 137

3.2.4  圆与圆求交 138

3.2.5  圆的离散化 140

3.2.6  圆的面积并 144

　　3.3  三维计算几何 147

3.3.1  三维点类 147

3.3.2  三维直线类 150

3.3.3  三维平面类 152

3.3.4  三维向量旋转 154

3.3.5  长方体表面两点

最短距离 155

3.3.6  四面体体积 156

3.3.7  最小球覆盖 158

3.3.8  三维凸包 161

　　3.4  其他 164

3.4.1  三角形的四心 164

3.4.2  最近点对 166

3.4.3  平面最小曼哈顿距离

生成树 167

3.4.4  最大空凸包 171

3.4.5  平面划分 174

第4章  数据结构 179

　　4.1  二叉堆 179

　　4.2  并查集 183

　　4.3  树状数组 184

　　4.4  左偏树 186

　　4.5  Trie 188

　　4.6  Treap 190

　　4.7  伸展树 193

　　4.8  RMQ线段树 199

　　4.9  ST表 201

　　4.10  动态树 202

　　4.11  块状链表 207

　　4.12  树链剖分 210

第5章  论题选编 213

　　5.1  字符串 213

5.1.1  KMP 213

5.1.2  扩展KMP 214

5.1.3  串的最小表示 216

5.1.4  有限状态自动机 217

5.1.5  后缀数组 221

5.1.6  最长重复子串 223

5.1.7  最长公共子串 225

5.1.8  最长回文子串manacher

算法 227

5.1.9  字符串散列 228

　　5.2  转换 229

5.2.1  星期计算 229

5.2.2  日期相隔天数计算 230

5.2.3  斐波那契进制转换 232

5.2.4  罗马进制转换 233

　　5.3  构造 235

5.3.1  幻方构造 235

5.3.2  N皇后问题 237

5.3.3  旋转魔方 239

5.3.4  骑士周游问题 242

　　5.4  计算 245

5.4.1  表达式计算 245

5.4.2  最大权子矩形 247

5.4.3  矩形面积并 249

5.4.4  矩形并的周长 252

　　5.5  序列 255

5.5.1  第k小数 255

5.5.2  逆序对 256

5.5.3  最长公共子序列 257

5.5.4  最长公共上升子序列 259

第二部分  贴    士

第6章  代数 263

　　6.1  Bertrand猜想 263

　　6.2  差分序列 263

　　6.3  威尔逊定理 263

　　6.4  约数个数 263

　　6.5  行列式的值 264

　　6.6  最小二乘法 264

第7章  解析几何 265

　　7.1  四边形 265

　　7.2  抛物线 265

　　7.3  双曲线 265

　　7.4  椭圆 266

第8章  平面立体几何 267

　　8.1  费马点 267

　　8.2  皮克定理 267

　　8.3  三角公式 267

　　8.4  三维几何体 268

　　8.5  托勒密定理 268

第9章  组合数学 269

　　9.1  Catalan数 269

　　9.2  组合公式 269

第10章  图论 271

　　10.1  树的计数 271

　　10.2  有特殊条件的汉米尔顿回路 271

　　10.3  普吕弗序列 272

　　10.4  模2意义下的二分图匹配数 272

第11章  积分表 273