ACM/ICPC算法训练教程PDF|Epub|txt|kindle电子书版本网盘下载

ACM/ICPC算法训练教程PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章 基础算法1

1.1 枚举法2

1.2 递归法4

1.3 分治法8

1.4 贪心法12

1.4.1 拟阵16

1.4.2 关于带权拟阵的贪心算法16

1.4.3 任务时间表问题17

1.5 模拟法19

第2章 数据结构22

2.1 基本数据结构22

2.1.1 堆栈22

2.1.2 队列23

2.1.3 堆25

2.1.4 并查集29

2.2 线段树33

2.3 树状数组39

2.4 搜索树43

2.4.1 二叉搜索树44

2.4.2 AVL搜索树47

2.4.3 红黑树54

2.4.4 伸展树55

2.4.5 Treap树堆64

2.4.6 SBT70

2.4.7 跳跃表77

2.5 Hash表83

2.6 左偏树88

第3章 动态规划96

3.1 动态规划简介96

3.1.1 动态规划的基本思想96

3.1.2 动态规划法的步骤96

3.1.3 动态规划问题的特征96

3.1.4 适用动态规划解题的条件97

3.2 线性动态规划97

3.3 树形动态规划102

3.4 概率动态规划103

3.5 动态规划中的状态压缩105

第4章 数学问题108

4.1 乘方取模和矩阵快速幂108

4.1.1 乘方取模问题108

4.1.2 矩阵快速幂111

4.2 欧几里得算法114

4.2.1 最大公约数与欧几里得算法114

4.2.2 二元一次不定方程和扩展欧几里得算法114

4.3 进位制转换117

4.3.1 整数的进位制转换117

4.3.2 小数的进位制转换119

4.3.3 负进位制119

4.4 欧拉函数121

4.4.1 剩余类、完全乘余系、简化剩余系的概念121

4.4.2 欧拉函数121

4.5 素数判定和大数分解123

4.5.1 素数判定123

4.5.2 大整数分解127

4.6 中国剩余定理131

4.7 Pólya原理134

第5章 计算几何142

5.1 矢量142

5.2 确定任意一对线段是否相交151

5.3 线段合并153

5.4 凸包157

5.5 寻找最近点对163

5.6 半平面交167

5.7 旋转卡壳173

5.8 扫描线177

5.9 计算几何基本算法代码集锦181

第6章 搜索算法192

6.1 深度优先搜索192

6.2 广度优先搜索195

6.3 启发式搜索197

第7章 图算法204

7.1 图的表示方式204

7.2 最短路算法205

7.2.1 Dijkstra算法求最短路205

7.2.2 SPFA（Bellman-Ford算法优化）求最短路及判定负环211

7.2.3 Floyd求最短路215

7.2.4 第k短路（A＊算法）217

7.2.5 差分约束系统219

7.3 生成树算法220

7.3.1 Prim算法求最小生成树220

7.3.2 Kruskal求最小生成树222

7.3.3 次小生成树225

7.3.4 最优比率生成树229

7.3.5 最小度限制生成树233

7.4 图的连通性问题238

7.4.1 无向图238

7.4.2 有向图242

7.4.3 连通性问题示例246

7.5 网络流问题254

7.5.1 网络流概述254

7.5.2 最大流256

7.5.3 模型的建立264

7.5.4 最大流应用268

7.5.5 费用流270

7.6 二分图匹配274

7.6.1 定义274

7.6.2 二分图的匹配274

7.6.3 二分图的最大匹配274

7.6.4 与最大匹配相关的几个问题275

7.6.5 用最大流解决二分匹配276

7.6.6 二分图最优匹配278

7.6.7 用费用流解决最优匹配282

第8章 字符串算法286

8.1 KMP算法286

8.2 字典树289

8.3 AC自动机292

8.4 后缀数组301

参考文献310