清华科技大讲堂 算法竞赛入门到进阶PDF电子书下载

第1章 算法竞赛概述 1

1.1 培养杰出程序员的捷径 2

1.1.1 编写大量代码 3

1.1.2 丰富的算法知识 3

1.1.3 计算思维和逻辑思维 3

1.1.4 团队合作精神 3

1.2 算法竞赛与创新能力的培养 4

1.3 算法竞赛入门 5

1.3.1 竞赛语言和训练平台 5

1.3.2 判题和基本的输入与输出 5

1.3.3 测试 8

1.3.4 编码速度 9

1.3.5 模板 10

1.3.6 题目分类 11

1.3.7 代码规范 12

1.4 天赋与勤奋 13

1.5 学习建议 14

1.6 本书的特点 15

第2章 算法复杂度 17

2.1 计算的资源 17

2.2 算法的定义 21

2.3 算法的评估 22

第3章 STL和基本数据结构 24

3.1 容器 24

3.1.1 vector 25

3.1.2 栈和stack 27

3.1.3 队列和queue 28

3.1.4 优先队列和priority＿queue 30

3.1.5 链表和list 30

3.1.6 set 31

3.1.7 map 33

3.2 sort（） 34

3.3 next＿permutation（） 35

第4章 搜索技术 37

4.1 递归和排列 38

4.2 子集生成和组合问题 41

4.3 BFS 43

4.3.1 BFS和队列 43

4.3.2 八数码问题和状态图搜索 46

4.3.3 BFS与A＊算法 50

4.3.4 双向广搜 52

4.4 DFS 53

4.4.1 DFS和递归 53

4.4.2 回溯与剪枝 54

4.4.3 迭代加深搜索 57

4.4.4 IDA＊ 58

4.5 小结 60

第5章 高级数据结构 61

5.1 并查集 62

5.2 二叉树 66

5.2.1 二叉树的存储 66

5.2.2 二叉树的遍历 67

5.2.3 二叉搜索树 70

5.2.4 Treap树 72

5.2.5 Splay树 78

5.3 线段树 84

5.3.1 线段树的概念 84

5.3.2 点修改 85

5.3.3 离散化 89

5.3.4 区间修改 90

5.3.5 线段树习题 93

5.4 树状数组 93

5.5 小结 97

第6章 基础算法思想 98

6.1 贪心法 98

6.1.1 基本概念 98

6.1.2 常见问题 100

6.1.3 Huffman编码 102

6.1.4 模拟退火 105

6.1.5 习题 107

6.2 分治法 107

6.2.1 归并排序 108

6.2.2 快速排序 111

6.3 减治法 113

6.4 小结 114

第7章 动态规划 115

7.1 基础DP 116

7.1.1 硬币问题 116

7.1.2 0/1背包 123

7.1.3 最长公共子序列 127

7.1.4 最长递增子序列 129

7.1.5 基础DP习题 132

7.2 递推与记忆化搜索 133

7.3 区间DP 134

7.4 树形DP 139

7.5 数位DP 144

7.6 状态压缩DP 148

7.7 小结 153

第8章 数学 154

8.1 高精度计算 154

8.2 数论 155

8.2.1 模运算 156

8.2.2 快速幂 156

8.2.3 GCD、LCM 159

8.2.4 扩展欧几里得算法与二元一次方程的整数解 159

8.2.5 同余与逆元 161

8.2.6 素数 163

8.3 组合数学 166

8.3.1 鸽巢原理 166

8.3.2 杨辉三角和二项式系数 167

8.3.3 容斥原理 168

8.3.4 Fibonacci数列 168

8.3.5 母函数 169

8.3.6 特殊计数 174

8.4 概率和数学期望 180

8.5 公平组合游戏 183

8.5.1 巴什游戏与P－position、N－position 184

8.5.2 尼姆游戏 185

8.5.3 图游戏与Sprague－Grundy函数 187

8.5.4 威佐夫游戏 190

8.6 小结 191

第9章 字符串 192

9.1 字符串的基本操作 192

9.2 字符串哈希 194

9.3 字典树 196

9.4 KMP 198

9.5 AC自动机 202

9.6 后缀树和后缀数组 204

9.6.1 概念 205

9.6.2 用倍增法求后缀数组 206

9.6.3 用后缀数组解决经典问题 212

9.7 小结 213

第10章 图论 214

10.1 图的基本概念 214

10.2 图的存储 215

10.3 图的遍历和连通性 217

10.4 拓扑排序 219

10.5 欧拉路 223

10.6 无向图的连通性 225

10.6.1 割点和割边 225

10.6.2 双连通分量 228

10.7 有向图的连通性 230

10.7.1 Kosaraju算法 231

10.7.2 Tarjan算法 234

10.8 2－SAT问题 236

10.9 最短路 239

10.9.1 Floyd－Warshall 240

10.9.2 Bellman－Ford 242

10.9.3 SPFA 246

10.9.4 Dijkstra 250

10.10 最小生成树 253

10.10.1 prim算法 254

10.10.2 kruskal算法 255

10.11 最大流 257

10.11.1 Ford－Fulkerson方法 258

10.11.2 Edmonds－Karp算法 260

10.11.3 Dinic算法和ISAP算法 262

10.12 最小割 263

10.13 最小费用最大流 264

10.14 二分图匹配 268

10.15 小结 271

第11章 计算几何 272

11.1 二维几何基础 272

11.1.1 点和向量 273

11.1.2 点积和叉积 274

11.1.3 点和线 276

11.1.4 多边形 280

11.1.5 凸包 283

11.1.6 最近点对 285

11.1.7 旋转卡壳 287

11.1.8 半平面交 288

11.2 圆 293

11.2.1 基本计算 293

11.2.2 最小圆覆盖 297

11.3 三维几何 300

11.3.1 三维点和向量 300

11.3.2 三维点积 301

11.3.3 三维叉积 302

11.3.4 最小球覆盖 304

11.3.5 三维凸包 304

11.4 几何模板 308

11.5 小结 315

第12章 ICPC区域赛真题 316

12.1 ICPC亚洲区域赛（中国大陆）情况 316

12.2 ICPC区域赛题目解析 317

12.2.1 F题Friendship of Frog（hdu 5578） 318

12.2.2 K题Kingdom of Black and White（hdu 5583） 320

12.2.3 L题LCM Walk（hdu 5584） 323

12.2.4 A题An Easy Physics Problem（hdu 5572） 325

12.2.5 B题Binary Tree（hdu 5573） 326

12.2.6 D题Discover Water Tank（hdu 5575） 328

12.2.7 E题Expection of String（hdu 5576） 333

12.2.8 G题Game of Arrays（hdu 5579） 336

12.2.9 I题Infinity Point Sets（hdu 5581） 339

参考文献 344