本书对程序设计竞赛中的基础算法和经典问题进行了汇总,分为准备篇、初级篇、中级篇与**篇4章。作者结合自己丰富的参赛经验,对严格筛选的110 多道各类试题进行了由浅入深、由易及难的细致讲解,并介绍了许多实用技巧。每章后附有习题,供读者练习,巩固所学。

如今,形形色色的程序设计竞赛层出不穷,听说过Google Code Jam、TopCoder、ACM-ICPC的读者恐怕不在少数。本书要介绍的正是这类以在规定时间内、又快又准地解决尽可能多的题目为目标的程序设计竞赛。
程序设计竞赛内涵丰富,即便是经验老道的程序员,要想在比赛中取得好成绩也绝非易事。要在程序设计竞赛中取胜,不仅需要运用灵活的想象和丰富的知识得出正确的算法,还需要一气呵成地实现并调试通过。
另一方面,程序设计竞赛对新手而言亦非遥不可及。为了让更多的参赛选手体会到比赛的乐趣,大多数比赛都会准备若干面向初学者的题目。另外,即便未能在比赛中取得好成绩,通过比赛,也能够使自己的能力得到有效的锻炼。*重要的是,大家能够享受到激烈的比赛带来的乐趣。
本书的作者们参加过众多程序设计竞赛,在平时的练习和学习中,也获得了各种各样的知识与技巧,本书将这���知识技巧总结成册,主要介绍算法及其在相关问题中的应用。本书依照由易及难的顺序对问题进行讲解,章节的编排也参考了主题的难易程度及其相互的联系,内容较多的主题则按难易程度划分为多个子主题分别介绍。各个主题由算法介绍和例题讲解穿插而成。
只要是具有编程基础知识的读者,均适合阅读本书。书中的源代码均用C++实现,不过只用到了其基本功能,所以即便读者不熟悉C++也不影响阅读。
【关于再版】
令人惊喜的是,本书的第1版受到了广大读者的高度评价,在此表示感谢。特别是一些并不热衷于程序设计竞赛的读者也购买了本书。这是因为通过本书不仅可以学到算法,更能学到其设计和运用的思想。这正是本书划时代的亮点。
本书第2版追加了计算几何、搜索减枝、分治法和字符串相关算法4个主题。此外还追加了方便读者加深理解的练习题,并为学有余力的读者列出了书中未涉及的拓展主题,进一步丰富了本书内容。
……

第1章 蓄势待发--准备篇
1.1 何谓程序设计竞赛
1.2 *负盛名的程序设计竞赛
1.2.1 世界规模的大赛--Google Code Jam(GCJ)
1.2.2 向高排名看齐!--TopCoder
1.2.3 历史*悠久的竞赛-- ACM-ICPC
1.2.4 面向中学生的信息学奥林匹克竞赛--JOI-IOI
1.2.5 通过网络自动评测--Online Judge(OJ)
1.3 本书的使用方法
1.3.1 本书所涉及的内容
1.3.2 所用的编程语言
1.3.3 题目描述的处理
1.3.4 程序结构
1.3.5 练习题
1.3.6 读透本书后更上一层楼的练习方法
1.4 如何提交解答
1.4.1 POJ的提交方法
1.4.2 GCJ的提交方法
1.5 以**的算法为目标
1.5.1 什么是复杂度
1.5.2 关于运行时间
1.6 轻松热身
1.6.1 先从简单题开始
1.6.2 POJ的题目Ants
1.6.3 难度增加的抽签问题

第2章 初出茅庐--初级篇
2.1 *基础的“穷竭搜索”
2.1.1 递归函数
2.1.2 栈
2.1.3 队列
2.1.4 深度优先搜索
2.1.5 宽度优先搜索
2.1.6 特殊状态的枚举
2.1.7 剪枝
2.2 一往直前!贪心法
2.2.1 硬币问题
2.2.2 区间问题
2.2.3 字典序*小问题
2.2.4 其他例题
2.3 记录结果再利用的“动态规划”
2.3.1 记忆化搜索与动态规划
2.3.2 进一步探讨递推关系
2.3.3 有关计数问题的DP
2.4 加工并存储数据的数据结构
2.4.1 树和二叉树
2.4.2 优先队列和堆
2.4.3 二叉搜索树
2.4.4 并查集
2.5 它们其实都是“图”
2.5.1 图是什么
2.5.2 图的表示
2.5.3 图的搜索
2.5.4 *短路问题
2.5.5 *小生成树
2.5.6 应用问题
2.6 数学问题的解题窍门
2.6.1 辗转相除法
2.6.2 有关素数的基础算法
2.6.3 模运算
2.6.4 快速幂运算
2.7 一起来挑战GCJ的题目(1)
2.7.1 Minimum Scalar Product
2.7.2 Crazy Rows
2.7.3 Bribe the Prisoners
2.7.4 Millionaire

第3章 出类拔萃--中级篇
3.1 不光是查找值!“二分搜索”
3.1.1 从有序数组中查找某个值
3.1.2 假定一个解并判断是否可行
3.1.3 *大化*小值
3.1.4 *大化平均值
3.2 常用技巧精选(一)
3.2.1 尺取法
3.2.2 反转(开关问题)
3.2.3 弹性碰撞
3.2.4 折半枚举(双向搜索)
3.2.5 坐标离散化
3.3 活用各种数据结构
3.3.1 线段树
3.3.2 Binary Indexed Tree
3.3.3 分桶法和平方分割
3.4 熟练掌握动态规划
3.4.1 状态压缩DP
3.4.2 矩阵的幂
3.4.3 利用数据结构**求解
3.5 借助水流解决问题的网络流
3.5.1 *大流
3.5.2 *小割
3.5.3 二分图匹配
3.5.4 一般图匹配
3.5.5 匹配、边覆盖、独立集和顶点覆盖
3.5.6 *小费用流
3.5.7 应用问题
3.6 与平面和空间打交道的计算几何
3.6.1 计算几何基础
3.6.2 极限情况
3.6.3 平面扫描
3.6.4 凸包
3.6.5 数值积分
3.7 一起来挑战GCJ的题目(2)
3.7.1 Numbers
3.7.2 No Cheating
3.7.3 Stock Charts
3.7.4 Watering Plants
3.7.5 Number Sets
3.7.6 Wi-fi Towers

第4章 登峰造极--**篇
4.1 更加复杂的数学问题
4.1.1 矩阵
4.1.2 模运算的世界
4.1.3 计数
4.1.4 具有对称性的计数
4.2 找出游戏的必胜策略
4.2.1 游戏与必胜策略
4.2.2 Nim
4.2.3 Grundy数
4.3 成为图论大师之路
4.3.1 强连通分量分解
4.3.2 2-SAT
4.3.3 LCA
4.4 常用技巧精选(二)
4.4.1 栈的运用
4.4.2 双端队列的运用
4.4.3 倍增法
4.5 开动脑筋智慧搜索
4.5.1 剪枝
4.5.2 A*与IDA*
4.6 划分、解决、合并:分治法
4.6.1 数列上的分治法
4.6.2 树上的分治法
4.6.3 平面上的分治法
4.7 华丽地处理字符串
4.7.1 字符串上的动态规划算法
4.7.2 字符串匹配
4.7.3 后缀数组
4.8 一起来挑战GCJ的题目(3)
4.8.1 Mine Layer
4.8.2 Year of More Code Jam
4.8.3 Football Team
4.8.4 Endless Knight
4.8.5 The Year of Code Jam
本书中未涉及的拓展主题
书中例题列表
参考文献

世界**程序设计高手的经验总结
【ACM-ICPC全球总**】巫泽俊主译
日本ACM-ICPC参赛者人手一册
《挑战程序设计竞赛(第2版)》对程序设计竞赛中的基础算法和经典问题进行了汇总,分为准备篇、初级篇、中级篇与**篇4章。作者结合自己丰富的参赛经验,对严格筛选的110 多道各类试题进行了由浅入深、由易及难的细致讲解,并介绍了许多实用技巧。每章后附有习题,供读者练习,巩固所学。