acm国际大学生程序设计竞赛（acm-icpc）是国际上公认的水平最高、规模最大、影响最深的计算机专业竞赛，目前全球参与人数达20多万。《ACM国际大学生程序设计竞赛：知识与入门》作者将16年的教练经验与积累撰写成本系列丛书，全面、深入而系统地将acm-icpc展现给读者。本系列丛书包括《acm国际大学生程序设计竞赛：知识与入门》、《acm国际大学生程序设计竞赛：算法与实现》、《acm国际大学生程序设计竞赛：题目与解读》、《acm国际大学生程序设计竞赛：比赛与思考》等4册，其中《acm国际大学生程序设计竞赛：知识与入门》介绍了acm-icpc的知识及其分类、进阶与角色、在线评测系统；《acm国际大学生程序设计竞赛：算法与实现》介绍了acm-icpc算法分类、实现及索引；《acm国际大学生程序设计竞赛：题目与解读》为各类算法配备经典例题及题库，并提供解题思路；《acm国际大学生程序设计竞赛：比赛与思考》介绍了上海交通大学acm-icpc的训练及比赛，包括训练札记、赛场风云、赛季纵横、冠军之路、峥嵘岁月。
《ACM国际大学生程序设计竞赛：知识与入门》适用于参加acm国际大学生程序设计竞赛的本科生和研究生，对参加青少年信息学奥林匹克竞赛的中学生也很有指导价值。同时，作为程序设计、数据结构、算法等相关课程的拓展与提升，本丛书也是难得的教学辅助读物。
写在最前面的话
自从上海交通大学2002年第一次、2005年第二次获得ACM国际大学生程序设计竞赛（ACM International Collegiate Programming Contest，简称ACM-ICPC或ICPC）世界冠军以来，总有记者邀请编者撰写冠军之路类的文章，也总有出版社希望编者出版ACM-ICPC竞赛类的书籍，因为没有想清楚怎么写，所以一直没动笔。直到2010年上海交通大学第三次获得ACM-ICPC世界冠军后，编者决定出版一套系列丛书，包括《ACM国际大学生程序设计竞赛：知识与入门》、《ACM国际大学生程序设计竞赛：算法与实现》、《ACM国际大学生程序设计竞赛：题目与解读》及《ACM国际大学生程序设计竞赛：比赛与思考》4册书籍，全面、深入而系统地将ACM-ICPC展现给读者，把上海交通大学十多年来对ACM-ICPC竞赛的感悟分享给读者。
编写此系列丛书的另一个重要原因是ACM-ICPC竞赛在中国大陆的迅猛发展。自从1996年ACM-ICPC引入中国大陆，前六届仅设立1个赛区，目前每年一般设立5个赛区，并已有30所高校承办过亚洲区预赛；参赛学校从不满20所，到如今已达200多所；参赛人数从不到100人，到如今已超过12万人次；总决赛名额从起初的3个，到如今已超过15个。同时，中国大陆在ACM-ICPC竞赛上所取得的成绩也举世瞩目。清华大学9次获得总决赛奖牌（3金5银1铜），位居奖牌榜之首，是实力最强、表现最稳定的高校；上海交通大学8次获得总决赛奖牌（4金3银1铜），3次夺得世界冠军，算是目前国内成绩最好的高校；中山大学4次获得总决赛奖牌（2银2铜），在生源不占优势的情况下，这一成绩令人敬佩；复旦大学3次获得总决赛奖牌（1银2铜），是公认的强校；浙江大学2次获得总决赛奖牌（1金1银），1次夺得世界冠军，再次让国人欢欣鼓舞；北京大学1次获得总决赛奖牌（1铜），队员的综合实力堪称一流；最难能可贵的是，华南理工大学也获得过总决赛的奖牌（1铜），它告诉我们，ACM-ICPC不仅仅是“强校”之间的“对话”，只要坚持参与就会斩获成果。另外，至今已有37所大陆高校参加过全球总决赛，且不论成绩如何，他们在赛场上的奋斗亦值得称道。
本系列丛书的第一册《ACM国际大学生程序设计竞赛：知识与入门》分为三个部分。知识点部分基本涵盖了竞赛中所涉及的主要知识点，包括数学基础、数据结构、图论、计算几何、论题选编、求解策略等六个大类内容。入门与进阶部分介绍了包括如何快速入门、如何提高自身以及团队水平等，主要根据上海交通大学ACM-ICPC队多年参赛经验总结而来。在线资源部分对一些常用的在线评测系统和网上比赛进行了介绍。
本系列丛书的第二册《ACM国际大学生程序设计竞赛：算法与实现》涵盖了大部分ACM-ICPC竞赛常用的经典算法，包括数学、图论、数据结构、计算几何、论题选编五个大类，对每个算法的代码实现，都配有接口说明以及简略的算法阐述，并提供算法的完整程序。并收集了一些实用的知识点及积分表，方便读者查找使用。
本系列丛书的第三册《ACM国际大学生程序设计竞赛：题目与解读》分为两个部分。例题精讲部分针对第二册《ACM国际大学生程序设计竞赛：算法与实现》中的算法配备经典例题，并提供细致的解题思路，读者可以通过这一部分学习和掌握算法；海量题库部分按照算法分类罗列出大量习题，并提供相应的题解，读者可以利用这一部分的题目进行训练，更加熟练地运用各类算法。
本系列丛书的第四册《ACM国际大学生程序设计竞赛：比赛与思考》从120多名队员、2400余篇文档中精心挑选、编纂而成的文集，包括训练札记、赛场风云、赛季纵横、冠军之路、峥嵘岁月，集中展现了上海交通大学ACM-ICPC队16年的奋斗历程，记载了这些队员为了实现自己的梦想而不懈努力、勇于拼搏的故事。
这是一套全面、系统地学习ACM-ICPC竞赛的知识类书籍；
这是一套详尽、深入地熟悉ACM-ICPC竞赛的算法及题目的手册类书籍；
这是一套程序设计、数据结构、算法等相关课程的拓展与提升类书籍；
这是一部上海交通大学ACM-ICPC队的成长史；
这是一部激励更多学子勇敢追寻并实现自己最初梦想的励志书。
历时2年零5个月，终于完成了本系列丛书，编者与队员有一种如释重负的感觉，因为我们把出版这套丛书看得很重，这是我们16年的经验与积累，希望对广大读者有用。
值此ACM-ICPC进入中国大陆16周年、上海交通大学获得ACM-ICPC世界冠军10周年之际，谨以此系列丛书——
纪念我们曾经走过的路、度过的岁月；
献给所有支持、帮助过我们的人……
俞 勇
2012年10月于上海
前 言
ACM国际大学生程序设计竞赛（ACM International Collegiate Programming Contest，简称ACM-ICPC或ICPC）的试题覆盖了计算机科学以及相关数学领域众多知识点。这些知识通常会散落在各种书籍和论文之中，学习和查找起来相对麻烦。此外，竞赛中所考察的内容具有一定的特殊性，即使是像由Thomas H. Cormen等编著的Introduction to Algorithms这样的经典书籍，其中介绍的东西也并非都是竞赛中的考察点。因此能够有一本书针对ACM-ICPC竞赛所经常考察的知识点进行统一的介绍是有必要的。
本书分为三个部分，第一部分为入门与进阶，第二部分为知识点与求解策略，第三部分为在线资源。第一部分介绍的内容包括如何快速入门、如何提高自身以及团队水平等，主要是编者根据多年的参赛经验总结而来。第二部分基本涵盖了竞赛中所涉及的主要知识点，包括数学基础、数据结构、图论、计算几何、论题选编、求解策略等6个大类。第三部分对一些常用的在线评测系统和网上比赛进行了介绍。其中，第一部分和第三部分主要针对初学者。
由于ACM-ICPC竞赛涉及到的知识点较多，很难在有限的篇幅里做到完全的覆盖，编者主要根据重要性和实用性对内容进行了筛选。例如，在介绍平衡二叉树时，一般的数据结构书籍往往会介绍AVL树或是红黑树，但本书只介绍了理解和实现起来更为简单的伸展树和Treap。
本书知识点部分的内容采用的是一种类似百科全书的组织方式，所以并不需要一章一章地从前往后阅读。读者完全可以选择一个自己感兴趣的知识点进行阅读，并扩展延伸到与之相关的其他知识点中。
本书编写工作历时两年多，参与编写工作的人员全部为上海交通大学ACM-ICPC队的现役与退役队员。他们参考了大量的书籍，并结合了多年的竞赛经验，对本书的内容进行选择、撰写和修改。
参与本书写稿、审稿的人员主要有（按姓氏笔画为序）：乌辰洋、吴卓杰、张培超、陈彬毅、林承宇、易茜、郑曌、姜啸、曹正、曹雪智、商静波、彭上夫、程宇、谭天。
在此，衷心感谢所有为此书出版做出直接或间接贡献的人！也真心祝愿此书能够给更多读者带来学习知识的快乐！
由于时间仓促，作者水平有限，疏漏、不当和不足之处在所难免，真诚地希望专家和读者朋友们不吝赐教。如果您在阅读和使用此书过程中发现任何问题或有任何建议，恳请发邮件，我们将不胜感激。
编 者
2012年10月于上海
第一部分 入门与进阶
第1章 入门
1.1 acm-icpc竞赛介绍
1.2 新手入门
1.3 团队的分工与配合
1.4 训练
1.5 备战分区赛
1.6 备战总决赛
第2章 进阶
2.1 如何提高读题能力
2.2 如何提高代码能力
2.3 bug与debug
2.4 从做题者到命题者
第二部分 知识点与求解策略
第3章 数学基础
3.1 函数增长与复杂性分类
3.1.1 渐进符号
3.1.2 阶的计算
3.1.3 复杂性分类
.3.2 概率论
3.2.1 事件与概率
3.2.2 期望与方差
3.3 代数学
3.3.1 矩阵
3.3.2 行列式
3.3.3 解线性方程组
3.3.4 多项式
3.3.5 复数
3.3.6 群
3.4 组合学
3.4.1 排列与组合
3.4.2 鸽巢原理
3.4.3 容斥原理
3.4.4 特殊计数序列
3.4.5 pólya计数定理
3.5 博弈论
3.5.1 博弈树
3.5.2 sg函数
3.5.3 nim游戏与nim和
3.6 数论
3.6.1 整除
3.6.2 不定方程
3.6.3 同余方程与欧拉定理
3.6.4 原根、离散对数和二项同余方程
3.6.5 连分数
第4章 数据结构
4.1 线性表
4.1.1 链表
4.1.2 栈
4.1.3 队列
4.1.4 块状链表
4.2 集合
4.2.1 散列表
4.2.2 并查集
4.3 排序
4.3.1 朴素排序算法
4.3.1.1 插入排序
4.3.1.2 冒泡排序
4.3.2 高效排序算法
4.3.2.1 归并排序算法
4.3.2.2 快速排序算法
4.3.2.3 线性排序算法
4.4 树
4.4.1 堆
4.4.1.1 二叉堆
4.4.1.2 左偏树
4.4.2 二叉树
4.4.2.1 二叉搜索树
4.4.2.2 treap
4.4.2.3 伸展树
4.4.3 线段树
第5章 图论
5.1 图
5.1.1 基本概念
5.1.1.1 图的定义与基本术语
5.1.1.2 匹配与覆盖
5.1.1.3 独立集、团与支配集
5.1.1.4 图的染色
5.1.2 特殊图的分类
5.1.3 图的遍历
5.1.3.1 深度优先遍历
5.1.3.2 广度优先遍历
5.1.4 连通性
5.1.4.1 连通性的基本定义
5.1.4.2 割点与桥
5.1.4.3 强连通分量
5.1.4.4 应用：2-sat
5.1.5 哈密顿路与欧拉路
5.1.5.1 哈密顿路
5.1.5.2 欧拉路
5.1.6 最短路
5.1.6.1 bellman-ford算法
5.1.6.2 dijkstra算法
5.1.6.3 floyd算法
5.2 树
5.2.1 基本概念与遍历
5.2.1.1 树的基本定义与术语
5.2.1.2 树的遍历
5.2.2 生成树
5.2.2.1 生成树的基本概念
5.2.2.2 prim算法
5.2.2.3 kruskal算法
5.2.2.4 最小生成树的变种
5.2.2.5 生成树计数
5.3 二分图
5.3.1 最大匹配
5.3.2 最大权匹配
5.3.3 稳定婚姻
5.4 网络流
5.4.1 基本概念
5.4.1.1 流网络
5.4.1.2 残量网络
5.4.1.3 增广路径
5.4.1.4 最大流最小割定理
5.4.2 最大流算法
5.4.2.1 ford-fulkerson算法
5.4.2.2 dinic算法
5.4.3 费用流
5.4.4 流与割模型
5.4.4.1 上下界网络流
5.4.4.2 混合图欧拉回路
5.4.4.3 最大权闭合子图
第6章 计算几何
6.1 向量
6.2 点的有序化
6.3 多边形与圆
6.3.1 简单多边形
6.3.2 凸包问题
6.3.3 圆的面积并
6.4 半平面交
6.5 经典问题
6.5.1 线段求交
6.5.2 最近点对
6.5.3 最远点对
第7章 论题选编
7.1 背包问题
7.2 lca与rmq
7.3 快速傅里叶变换
7.4 字符串
7.4.1 字符串匹配
7.4.2 trie
7.4.3 ac自动机
7.4.4 后缀数组
7.4.5 扩展kmp
第8章 求解策略
8.1 搜索
8.2 分治
8.3 贪心
8.4 动态规划
8.5 随机化
第三部分 在 线 资 源
第9章 在线评测系统
9.1 基本使用方法
9.2 usaco介绍
9.3 cii介绍
9.4 pku介绍
9.5 sgu介绍
9.6 spoj介绍
第10章 网上比赛
10.1 gcj介绍
10.2 topcoder介绍
10.3 codeforces介绍
参考文献
书单推荐
