ACM国际大学生程序设计竞赛（ACM国际大学生程序设计竞赛（ACM-ICPC）算法与实现系列丛书）

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

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

第一部分 算法第1章 数学1.1 矩阵1.1.1 矩阵类1.1.2 Gauss消元1.1.3 矩阵的逆1.1.4 常系数线性齐次递推1.2 整除与剩余1.2.1 欧几里得算法1.2.2 扩展欧几里得1.2.3 单变元模线性方程1.2.4 中国剩余定理1.2.5 求原根1.2.6 平方剩余1.2.7 离散对数1.2.8 N次剩余1.3 素数与函数1.3.1 素数筛法1.3.2 素数判定1.3.3 质因数分解1.3.4 欧拉函数计算1.3.5 Mobius函数计算1.4 数值计算1.4.1 数值积分1.4.2 高阶代数方程求根1.5 其他1.5.1 快速幂1.5.2 进制转换1.5.3 格雷码1.5.4 高精度整数1.5.5 快速傅立叶变换1.5.6 分数类1.5.7 全排列散列第2章 图论2.1 图的遍历及连通性2.1.1 前向星2.1.2 割点和桥2.1.3 双连通分量2.1.4 极大强连通分量Tarjan算法2.1.5 拓扑排序2.1.6 2SAT2.2 路径2.2.1 Dijkstra2.2.2 SPFA2.2.3 Floyd-Warshall2.2.4 无环图最短路2.2.5 第k短路2.2.6 欧拉回路2.2.7 混合图欧拉回路2.3 匹配2.3.1 匈牙利算法2.3.2 Hopcroft-Karp算法2.3.3 KM算法2.3.4 一般图最大匹配2.4 树2.4.1 LCA2.4.2 最小生成树Prim算法2.4.3 最小生成树Kruskal算法2.4.4 单度限制最小生成树2.4.5 最小树形图2.4.6 最优比例生成树2.4.7 树的直径2.5 网络流2.5.1 最大流Dinic算法2.5.2 最小割2.5.3 无向图最小割2.5.4 有上下界的网络流2.5.5 费用流2.6 其他2.6.1 完美消除序列2.6.2 弦图判定2.6.3 最大团搜索算法2.6.4 极大团的计数2.6.5 图的同构2.6.6 树的同构第3章 计算几何3.1 多边形3.1.1 计算几何误差修正3.1.2 计算几何点类3.1.3 计算几何线段类3.1.4 多边形类3.1.5 多边形的重心3.1.6 多边形内格点数3.1.7 凸多边形类3.1.8 凸多边形的直径3.1.9 半平面切割多边形3.1.10 半平面交3.1.11 凸多边形交3.1.12 多边形的核3.1.13 凸多边形与直线集交3.2 圆3.2.1 圆与线求交3.2.2 圆与多边形交的面积3.2.3 最小圆覆盖3.2.4 圆与圆求交3.2.5 圆的离散化3.2.6 圆的面积并3.3 三维计算几何3.3.1 三维点类3.3.2 三维直线类3.3.3 三维平面类3.3.4 三维向量旋转3.3.5 长方体表面两点最短距离3.3.6 四面体体积3.3.7 最小球覆盖3.3.8 三维凸包3.4 其他3.4.1 三角形的四心3.4.2 最近点对3.4.3 平面最小曼哈顿距离生成树3.4.4 最大空凸包3.4.5 平面划分第4章 数据结构4.1 二叉堆4.2 并查集4.3 树状数组4.4 左偏树4.5 Tne4.6 Treap4.7 伸展树4.8 RMQ线段树4.9 ST表4.10 动态树4.11 块状链表4.12 树链剖分第5章 论题选编5.1 字符串5.1.1 KMP5.1.2 扩展KMP5.1.3 串的最小表示……第二部分 贴士