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

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

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

第1章 基础算法1

1.1 模拟题1

1.1.1 基本概念1

1.1.2 例题讲解1

1.1.3 习题推荐9

1.2 枚举算法10

1.2.1 基本概念10

1.2.2 例题讲解10

1.2.3 习题推荐13

1.3 递归算法13

1.3.1 基本概念13

1.3.2 例题讲解14

1.3.3 习题推荐16

1.4 贪心算法16

1.4.1 基本概念16

1.4.2 例题讲解17

1.4.3 习题推荐23

1.5 分治算法24

1.5.1 基本概念24

1.5.2 例题讲解24

1.5.3 习题推荐29

1.6 二分/三分算法30

1.6.1 基本概念30

1.6.2 例题讲解30

1.6.3 习题推荐33

第2章 数据结构34

2.1 线性表34

2.1.1 基本概念34

2.1.2 基本特征34

2.2 队列35

2.2.1 基本概念35

2.2.2 顺序队列的基本操作35

2.2.3 循环队列36

2.2.4 例题讲解37

2.2.5 习题推荐40

2.3 栈40

2.3.1 基本概念40

2.3.2 基本操作40

2.3.3 栈的实现41

2.3.4 栈的应用42

2.3.5 例题讲解43

2.3.6 习题推荐44

2.4 堆45

2.4.1 基本概念45

2.4.2 基本操作45

2.4.3 时间及空间复杂度47

2.4.4 例题讲解47

2.4.5 习题推荐50

2.5 Hash51

2.5.1 基本概念51

2.5.2 哈希函数的构造方法51

2.5.3 处理碰撞的方法52

2.5.4 例题讲解52

2.5.5 习题推荐54

2.6 并查集54

2.6.1 基本概念54

2.6.2 基本操作54

2.6.3 时间及空间复杂度55

2.6.4 例题讲解55

2.6.5 习题推荐57

2.7 树状数组57

2.7.1 基本概念57

2.7.2 基本操作58

2.7.3 时间及空间复杂度59

2.7.4 例题讲解59

2.7.5 习题推荐63

2.8 线段树63

2.8.1 基本概念63

2.8.2 线段树中的“懒操作”64

2.8.3 线段树的基本操作64

2.8.4 例题讲解66

2.8.5 习题推荐69

2.9 最近公共祖先/区间最小值70

2.9.1 基本概念70

2.9.2 离线算法Tarjan70

2.9.3 在线算法71

2.9.4 RMQ72

2.9.5 LAC＋RMQ在线算法的具体实现73

2.9.6 例题讲解74

2.9.7 习题推荐77

2.10 伸展树77

2.10.1 基本概念77

2.10.2 伸展树的基本操作77

2.10.3 伸展树对区间的操作81

2.10.4 例题讲解83

2.10.5 习题推荐92

2.11 K-Dimensional树92

2.11.1 基本概念92

2.11.2 基本思想92

2.11.3 KD-Tree构建算法93

2.11.4 例题讲解95

2.11.5 习题推荐98

第3章 搜索算法99

3.1 宽度优先搜索99

3.1.1 基本概念99

3.1.2 算法实现100

3.1.3 例题讲解101

3.1.4 习题推荐106

3.2 深度优先搜索107

3.2.1 基本概念107

3.2.2 算法实现107

3.2.3 例题讲解108

3.2.4 习题推荐114

3.3 搜索与剪枝114

3.3.1 基本概念114

3.3.2 算法实现114

3.3.3 例题讲解115

3.3.4 习题推荐117

3.4 A＊算法117

3.4.1 基本概念117

3.4.2 算法实现117

3.4.3 例题讲解118

3.4.4 习题推荐125

3.5 迭代加深搜索125

3.5.1 基本概念125

3.5.2 算法实现125

3.5.3 例题讲解126

3.5.4 习题推荐132

3.6 双向宽度优先搜索132

3.6.1 基本概念132

3.6.2 算法实现132

3.6.3 例题讲解133

3.6.4 习题推荐140

3.7 舞蹈链140

3.7.1 基本概念140

3.7.2 算法实现140

3.7.3 例题讲解141

3.7.4 习题推荐146

第4章 图论基础147

4.1 最小生成树147

4.1.1 Prim算法147

4.1.2 Kruskal算法150

4.2 最短路152

4.2.1 Dijkstra算法152

4.2.2 Floyd算法155

4.2.3 Bellman-Ford算法及SPFA算法157

4.3 割点/割边162

4.3.1 基本概念162

4.3.2 算法实现162

4.3.3 例题讲解163

4.3.4 习题推荐165

4.4 二分图匹配166

4.4.1 基本概念166

4.4.2 最大匹配166

4.4.3 最大权匹配167

4.4.4 习题推荐167

4.5 拓扑排序168

4.5.1 基本概念168

4.5.2 算法实现168

4.5.3 习题推荐168

4.6 欧拉路和欧拉回路168

4.6.1 基本概念168

4.6.2 算法实现169

4.6.3 例题讲解169

4.6.4 习题推荐172

4.7 强连通分量和2-SAT问题172

4.7.1 基本概念172

4.7.2 算法实现173

4.7.3 2-SAT问题174

4.7.4 例题讲解174

4.7.5 习题推荐181

第5章 网络流182

5.1 最大流182

5.1.1 网络流182

5.1.2 残余网络与增广路183

5.1.3 Ford-Fulkerson算法184

5.1.4 最小割最大流定理185

5.1.5 Dinic算法186

5.1.6 例题讲解191

5.1.7 习题推荐200

5.2 费用流200

5.2.1 最小费用流问题200

5.2.2 最小费用流算法201

5.2.3 实现代码201

5.2.4 例题讲解204

5.2.5 习题推荐209

5.3 上下界网络流209

第6章 动态规划算法211

6.1 背包问题211

6.1.1 基本概念211

6.1.2 01背包问题211

6.1.3 完全背包问题213

6.1.4 多重背包问题216

6.1.5 习题推荐218

6.2 状态压缩218

6.2.1 基本概念218

6.2.2 经典旅行商问题218

6.2.3 插头dp221

6.2.4 习题推荐228

6.3 动态规划优化228

6.3.1 基本概念228

6.3.2 数据结构优化228

6.3.3 斜率优化235

6.3.4 四边形不等式优化238

6.3.5 习题推荐240

6.4 常见动态规划题目类型241

6.4.1 基本概念241

6.4.2 树形dp241

6.4.3 RMQ问题243

6.4.4 有向图最短路246

6.4.5 最长上升子序列250

6.4.6 习题推荐253

第7章 数学基础254

7.1 组合游戏254

7.1.1 基本概念254

7.1.2 Nim游戏与Nim和255

7.1.3 SG函数与SG定理257

7.1.4 例题讲解258

7.1.5 习题推荐260

7.2 数论261

7.2.1 基本概念261

7.2.2 线性同余方程组268

7.2.3 原根与离散对数270

7.2.4 习题推荐275

7.3 组合数学276

7.3.1 基本计数问题276

7.3.2 鸽巢原理276

7.3.3 容斥原理277

7.3.4 特殊计数数列277

7.3.5 Pólya计数279

7.3.6 习题推荐281

7.4 快速傅里叶变换281

7.4.1 多项式的表示281

7.4.2 DFT与FFT算法282

7.4.3 例题讲解285

7.5 进一步学习的建议286

第8章 字符串算法288

8.1 Hash算法288

8.1.1 基本概念288

8.1.2 算法实现289

8.1.3 例题讲解290

8.1.4 习题推荐292

8.2 最小循环表示292

8.2.1 基本概念292

8.2.2 算法实现292

8.2.3 例题讲解293

8.2.4 习题推荐295

8.3 Manacher算法295

8.3.1 基本概念295

8.3.2 算法实现295

8.3.3 例题讲解296

8.3.4 习题推荐297

8.4 KMP算法297

8.4.1 基本概念297

8.4.2 算法实现298

8.4.3 next数组的性质299

8.4.4 例题讲解299

8.4.5 习题推荐307

8.5 扩展KMP算法308

8.5.1 基本概念308

8.5.2 算法实现308

8.5.3 例题讲解309

8.5.4 习题推荐315

8.6 字典树316

8.6.1 基本概念316

8.6.2 算法实现316

8.6.3 例题讲解317

8.6.4 习题推荐322

8.7 AC自动机322

8.7.1 基本概念322

8.7.2 算法实现322

8.7.3 AC自动机与动态规划算法的结合324

8.7.4 例题讲解324

8.7.5 习题推荐335

8.8 后缀数组335

8.8.1 基本概念335

8.8.2 算法实现335

8.8.3 后缀数组的使用技巧339

8.8.4 例题讲解339

8.8.5 习题推荐343

8.9 后缀自动机343

8.9.1 基本概念343

8.9.2 算法实现344

8.9.3 后缀自动机与动态规划的结合346

8.9.4 例题讲解346

8.9.5 习题推荐359

第9章 计算几何基础360

9.1 数学基础知识360

9.2 向量的基本运算361

9.2.1 基本概念361

9.2.2 例题讲解363

9.2.3 习题推荐367

9.3 几何元素间的位置关系368

9.3.1 基本概念368

9.3.2 例题讲解372

9.3.3 习题推荐375

9.4 凸包376

9.4.1 基本概念376

9.4.2 例题讲解377

9.4.3 习题推荐379

9.5 半平面交379

9.5.1 基本概念379

9.5.2 算法实现380

9.5.3 例题讲解382

9.5.4 习题推荐388

9.6 旋转卡壳算法388

9.6.1 基本概念388

9.6.2 例题讲解389

9.7 三维几何397

9.7.1 基本概念397

9.7.2 习题推荐399

9.8 三维凸包399

9.8.1 基本概念399

9.8.2 例题讲解400

9.8.3 习题推荐403

参考文献404