第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