ACM国际大学生程序设计竞赛 算法与实现PDF|Epub|txt|kindle电子书版本网盘下载

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 2SAT49

2.2路径51

2.2.1 Dijkstra51

2.2.2 SPFA53

2.2.3 Floyd-Warshall54

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 LCA74

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 Trie188

4.6 Treap190

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 KMP213

5.1.2扩展KMP214

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