挑战程序设计竞赛 第2版PDF电子书下载

第1章 蓄势待发——准备篇 1

1.1何谓程序设计竞赛 2

1.2最负盛名的程序设计竞赛 5

1.2.1世界规模的大赛—— Google Code Jam （GCJ） 5

1.2.2向高排名看齐！—— TopCoder 5

1.2.3历史最悠久的竞赛—— ACM-ICPC 6

1.2.4面向中学生的信息学奥林匹克 竞赛——JOI-1OI 6

1.2.5通过网络自动评测—— Online Judge （OJ） 6

1.3本书的使用方法 7

1.3.1本书所涉及的内容 7

1.3.2所用的编程语言 7

1.3.3题目描述的处理 7

1.3.4程序结构 7

1.3.5练习题 8

1.3.6读透本书后更上一层楼的练习方法 8

1.4如何提交解答 9

1.4.1 POJ的提交方法 9

1.4.2 GCJ的提交方法 11

1.5以高效的算法为目标 15

1.5.1什么是复杂度 15

1.5.2关于运行时间 15

1.6轻松热身 16

1.6.1先从简单题开始 16

1.6.2 POJ的题目Ants 18

1.6.3难度增加的抽签问题 20

第2章 初出茅庐——初级篇 25

2.1最基础的“穷竭搜索” 26

2.1.1递归函数 26

2.1.2栈 27

2.1.3队列 28

2.1.4深度优先搜索 29

2.1.5宽度优先搜索 33

2.1.6特殊状态的枚举 37

2.1.7剪枝 38

2.2一往直前！贪心法 39

2.2.1硬币问题 39

2.2.2区间问题 40

2.2.3字典序最小问题 43

2.2.4其他例题 45

2.3记录结果再利用的“动态规划” 51

2.3.1记忆化搜索与动态规划 51

2.3.2进一步探讨递推关系 57

2.3.3有关计数问题的DP 66

2.4加工并存储数据的数据结构 70

2.4.1树和二叉树 70

2.4.2优先队列和堆 71

2.4.3二叉搜索树 77

2.4.4并查集 84

2.5它们其实都是“图” 91

2.5.1图是什么 91

2.5.2图的表示 94

2.5.3图的搜索 97

2.5.4最短路问题 99

2.5.5最小生成树 105

2.5.6应用问题 107

2.6数学问题的解题窍门 113

2.6.1辗转相除法 113

2.6.2有关素数的基础算法 117

2.6.3模运算 121

2.6.4快速幂运算 122

2.7一起来挑战GCJ的题目（1） 125

2.7.1 Minimum Scalar Product 125

2.7.2 Crazy Rows 127

2.7.3 Bribe the Prisoners 129

2.7.4 Millionaire 132

第3章 出类拔萃——中级篇 137

3.1不光是查找值！“二分搜索” 138

3.1.1从有序数组中查找某个值 138

3.1.2假定一个解并判断是否可行 140

3.1.3最大化最小值 142

3.1.4最大化平均值 143

3.2常用技巧精选（一） 146

3.2.1尺取法 146

3.2.2反转（开关问题） 150

3.2.3弹性碰撞 158

3.2.4折半枚举（双向搜索） 160

3.2.5坐标离散化 164

3.3活用各种数据结构 167

3.3.1线段树 167

3.3.2 Binary Indexed Tree 174

3.3.3分桶法和平方分割 183

3.4熟练掌握动态规划 191

3.4.1状态压缩DP 191

3.4.2 矩阵的幂 199

3.4.3利用数据结构高效求解 206

3.5借助水流解决问题的网络流 209

3.5.1最大流 209

3.5.2最小割 212

3.5.3二分图匹配 217

3.5.4一般图匹配 220

3.5.5匹配、边覆盖、独立集和顶点覆盖 221

3.5.6最小费用流 222

3.5.7应用问题 228

3.6与平面和空间打交道的计算几何 250

3.6.1计算几何基础 250

3.6.2极限情况 255

3.6.3平面扫描 258

3.6.4凸包 260

3.6.5数值积分 263

3.7一起来挑战GCJ的题目（2） 267

3.7.1 Numbers 267

3.7.2 No Cheating 269

3.7.3 Stock Charts 271

3.7.4 Watering Plants 273

3.7.5 Number Sets 278

3.7.6 Wi-fi Towers 280

第4章 登峰造极——高级篇 285

4.1更加复杂的数学问题 286

4.1.1矩阵 286

4.1.2模运算的世界 291

4.1.3计数 295

4.1.4具有对称性的计数 300

4.2找出游戏的必胜策略 305

4.2.1游戏与必胜策略 305

4.2.2 Nim 311

4.2.3 Grundy数 315

4.3成为图论大师之路 320

4.3.1强连通分量分解 320

4.3.2 2-SAT 324

4.3.3 LCA 328

4.4常用技巧精选（二） 335

4.4.1栈的运用 335

4.4.2双端队列的运用 337

4.4.3倍增法 345

4.5开动脑筋智慧搜索 350

4.5.1剪枝 350

4.5.2 A与IDA 356

4.6划分、解决、合并：分治法 359

4.6.1数列上的分治法 359

4.6.2树上的分治法 360

4.6.3平面上的分治法 364

4.7华丽地处理字符串 368

4.7.1字符串上的动态规划算法 368

4.7.2字符串匹配 373

4.7.3后缀数组 378

4.8一起来挑战GCJ的题目（3） 387

4.8.1 Mine Layer 387

4.8.2 Year of More Code Jam 392

4.8.3 Football Team 395

4.8.4 Endless Knight 399

4.8.5 The Year of Code Jam 403

本书中未涉及的拓展主题 408

书中例题列表 411

参考文献 413