ACM国际大学生程序设计竞赛 算法与实现PDF电子书下载

第一部分 算法 3

第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

第二部分 贴士 263

第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