ACM国际大学生程序设计竞赛 知识与入门PDF电子书下载

第一部分 入门与进阶 3

第1章 入门 3

1.1 ACM-ICPC竞赛介绍 3

1.2新手入门 5

1.3团队的分工与配合 7

1.4训练 9

1.5备战分区赛 12

1.6备战总决赛 13

第2章 进阶 16

2.1如何提高读题能力 16

2.2如何提高代码能力 17

2.3 Bug与Debug 19

2.4从做题者到命题者 20

第二部分 知识点与求解策略 25

第3章 数学基础 25

3.1函数增长与复杂性分类 25

3.1.1渐进符号 25

3.1.2阶的计算 26

3.1.3复杂性分类 27

3.2概率论 28

3.2.1事件与概率 28

3.2.2期望与方差 30

3.3代数学 31

3.3.1矩阵 31

3.3.2行列式 33

3.3.3解线性方程组 34

3.3.4多项式 37

3.3.5复数 38

3.3.6群 39

3.4组合学 42

3.4.1排列与组合 42

3.4.2鸽巢原理 43

3.4.3容斥原理 44

3.4.4特殊计数序列 45

3.4.5 Polya计数定理 47

3.5博弈论 50

3.5.1博弈树 50

3.5.2 SG函数 51

3.5.3.Nim游戏与Nim和 53

3.6数论 54

3.6.1整除 54

3.6.2不定方程 57

3.6.3同余方程与欧拉定理 58

3.6.4原根、离散对数和二项同余方程 60

3.6.5连分数 61

第4章 数据结构 64

4.1线性表 64

4.1.1链表 64

4.1.2栈 65

4.1.3队列 65

4.1.4块状链表 66

4.2集合 67

4.2.1散列表 67

4.2.2并查集 69

4.3排序 71

4.3.1朴素排序算法 71

4.3.1.1插入排序 71

4.3.1.2冒泡排序 72

4.3.2高效排序算法 73

4.3.2.1归并排序算法 73

4.3.2.2快速排序算法 74

4.3.2.3线性排序算法 76

4.4树 78

4.4.1堆 78

4.4.1.1二叉堆 78

4.4.1.2左偏树 80

4.4.2二叉树 82

4.4.2.1二叉搜索树 82

4.4.2.2 Treap 84

4.4.2.3伸展树 85

4.4.3线段树 89

第5章 图论 91

5.1图 91

5.1.1基本概念 91

5.1.1.1图的定义与基本术语 91

5.1.1.2匹配与覆盖 92

5.1.1.3独立集、团与支配集 94

5.1.1.4图的染色 95

5.1.2特殊图的分类 96

5.1.3图的遍历 99

5.1.3.1深度优先遍历 99

5.1.3.2广度优先遍历 100

5.1.4连通性 103

5.1.4.1连通性的基本定义 103

5.1.4.2割点与桥 104

5.1.4.3强连通分量 105

5.1.4.4应用：2-SAT 107

5.1.5哈密顿路与欧拉路 108

5.1.5.1哈密顿路 108

5.1.5.2欧拉路 109

5.1.6最短路 111

5.1.6.1 Bellman-ford算法 111

5.1.6.2 Dijkstra算法 113

5.1.6.3 Floyd算法 114

5.2树 115

5.2.1基本概念与遍历 115

5.2.1.1树的基本定义与术语 115

5.2.1.2树的遍历 117

5.2.2生成树 117

5.2.2.1生成树的基本概念 117

5.2.2.2 Prim算法 118

5.2.2.3 Kruskal算法 120

5.2.2.4最小生成树的变种 121

5.2.2.5生成树计数 123

5.3二分图 124

5.3.1最大匹配 124

5.3.2最大权匹配 126

5.3.3稳定婚姻 128

5.4网络流 129

5.4.1基本概念 129

5.4.1.1流网络 129

5.4.1.2残量网络 130

5.4.1.3增广路径 130

5.4.1.4最大流最小割定理 131

5.4.2最大流算法 131

5.4.2.1 Ford-Fulkerson算法 131

5.4.2.2 Dinic算法 133

5.4.3费用流 135

5.4.4流与割模型 137

5.4.4.1上下界网络流 137

5.4.4.2混合图欧拉回路 139

5.4.4.3最大权闭合子图 140

第6章 计算几何 142

6.1向量 142

6.2点的有序化 143

6.3多边形与圆 144

6.3.1简单多边形 144

6.3.2凸包问题 146

6.3.3圆的面积并 147

6.4半平面交 148

6.5经典问题 151

6.5.1线段求交 151

6.5.2最近点对 152

6.5.3最远点对 154

第7章 论题选编 156

7.1背包问题 156

7.2 LCA与RMQ 157

7.3快速傅里叶变换 159

7.4字符串 161

7.4.1字符串匹配 161

7.4.2 Trie 164

7.4.3 AC自动机 165

7.4.4后缀数组 167

7.4.5扩展KMP 169

第8章 求解策略 171

8.1搜索 171

8.2分治 175

8.3贪心 176

8.4动态规划 179

8.5随机化 183

第三部分 在线资源 187

第9章 在线评测系统 187

9.1基本使用方法 187

9.2 USACO介绍 190

9.3 CII介绍 191

9.4 PKU介绍 192

9.5 SGU介绍 193

9.6 SPOJ介绍 195

第10章 网上比赛 197

10.1 GCJ介绍 197

10.2 TopCoder介绍 199

10.3 Codeforces介绍 200

参考文献 203