ACM国际大学生程序设计竞赛：知识与入门

　　第一部分入门与进阶
　　第1章入门     3
　　1.1ACM-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.3Bug与Debug     19
　　2.4从做题者到命题者  20
　　第二部分知识点与求解策略
　　第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.5Pólya计数定理       47
　　3.5博弈论       50
　　3.5.1博弈树   50
　　3.5.2SG函数   51
　　3.5.3Nim游戏与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.2Treap    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.1Bellman-ford算法        111
　　5.1.6.2Dijkstra算法        113
　　5.1.6.3Floyd算法    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.2Prim算法     118
　　5.2.2.3Kruskal算法         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.1Ford-Fulkerson
　　算法         131
　　5.4.2.2Dinic算法    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.2LCA与RMQ        157
　　7.3快速傅里叶变换       159
　　7.4字符串       161
　　7.4.1字符串匹配   161
　　7.4.2Trie  164
　　7.4.3AC自动机       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
　　第三部分在线资源
　　第9章在线评测系统     187
　　9.1基本使用方法  187
　　9.2USACO介绍        190
　　9.3CII介绍      191
　　9.4PKU介绍    192
　　9.5SGU介绍    193
　　9.6SPOJ介绍   195
　　第10章网上比赛   197
　　10.1GCJ介绍  197
　　10.2TopCoder介绍 199
　　10.3Codeforces介绍       200
　　参考文献         203

　　俞勇，1961年生于上海，现为上海交通大学教授、博士生导师。1986年毕业于华东师范大学计算机科学系，获硕士学位。毕业后在上海交通大学任教至今。1996至今担任上海交通大学ACM国际大学生程序设计竞赛领队、主教练，3次率队夺得ACM国际大学生程序设计竞赛世界冠军，上海交通大学成为该赛事亚洲第一个获得冠军、全球第三个“三冠王”的大学，2002、2012年相继获得“杰出教练奖”、“功勋教练奖”。俞勇教授曾主编教材或著作4本、译著3本，先后主持教育部教育教学改革项目2项，获得国家ji和上海市教学成果奖7项，上海市优秀教材奖2项，并为国家精品课程“数据结构”、上海市“程序设计类基础课程教学团队”主持人。从事Web搜索与挖掘研究，先后主持国家自然科学基金、863计划等十余项，发表重要国际会议和期刊学术论文百余篇。俞勇教授曾获得国务院特殊津贴、“全国师德标兵”、“宝钢优秀教师特等奖”、“上海市教学名师”、“上海市五一劳动奖章”、“上海市模范教师”、“上海交通大学校长奖”、“上海交通大学zui受学生欢迎教师”、“上海交通大学zui受研究生欢迎导师”等荣誉。曾被中央电视台新闻联播、上海教育台、光明日报、文汇报等十多家媒体报道。

　　acm国际大学生程序设计竞赛（acm-icpc）是国际上公认的水平zui高、规模zui大、影响zui深的计算机专业竞赛，目前全球参与人数达20多万。《ACM国际大学生程序设计竞赛：知识与入门》作者将16年的教练经验与积累撰写成本系列丛书，全面、深入而系统地将acm-icpc展现给读者。本系列丛书包括《acm国际大学生程序设计竞赛：知识与入门》、《acm国际大学生程序设计竞赛：算法与实现》、《acm国际大学生程序设计竞赛：题目与解读》、《acm国际大学生程序设计竞赛：比赛与思考》等4册，其中《acm国际大学生程序设计竞赛：知识与入门》介绍了acm-icpc的知识及其分类、进阶与角色、在线评测系统；《acm国际大学生程序设计竞赛：算法与实现》介绍了acm-icpc算法分类、实现及索引；《acm国际大学生程序设计竞赛：题目与解读》为各类算法配备经典例题及题库，并提供解题思路；《acm国际大学生程序设计竞赛：比赛与思考》介绍了上海交通大学acm-icpc的训练及比赛，包括训练札记、赛场风云、赛季纵横、冠军之路、峥嵘岁月。
　　《ACM国际大学生程序设计竞赛：知识与入门》适用于参加acm国际大学生程序设计竞赛的本科生和研究生，对参加青少年信息学奥林匹克竞赛的中学生也很有指导价值。同时，作为程序设计、数据结构、算法等相关课程的拓展与提升，本丛书也是难得的教学辅助读物。