ACM国际大学生程序设计竞赛（ACM-ICPC）是国际上公认的水平zui高、规模zui大、影响zui深的计算机专业竞赛，目前全球参与人数达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国际大学生程序设计竞赛的本科生和研究生，对参加青少年信息学奥林匹克竞赛的中学生也很有指导价值。同时，作为程序设计、数据结构、算法等相关课程的拓展与提升，本丛书也是难得的教学辅助读物。

第一部分 算法
第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 2SAT
2.2 路径
2.2.1 Dijkstra
2.2.2 SPFA
2.2.3 Floyd-Warshall
2.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 LCA
2.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 Tne
4.6 Treap
4.7 伸展树
4.8 RMQ线段树
4.9 ST表
4.10 动态树
4.11 块状链表
4.12 树链剖分
第5章 论题选编
5.1 字符串
5.1.1 KMP
5.1.2 扩展KMP
5.1.3 串的最小表示
……
第二部分 贴士

　　在ACM国际大学生程序设计竞赛（ACM International Collegiate Programming Contest，ACM-ICPC或ICPC）中，实现算法的能力是非常重要的。尤其是对新手来说，在了解到一个新的算法后，有时会对如何实现该算法产生困惑，也许并不能一下想到很好的实现，这时就需要参考一些已有的实现。
　　另外，ACM-ICPC比赛中允许选手将一定量的（一般为25页）纸质资料带入比赛现场进行参考。队伍往往会将一些相对较难实现的常用算法的代码整理为SCL（Standard Code Library，标准代码库）带入赛场，在需要的时候可以直接抄写已有代码，既节省时间，也保证了正确性。
　　因此我们出版这本收集了大量经典常用算法的用C++语言实现的代码库，希望可以帮助读者学习算法以及准备比赛用的SCL。
　　本书分为两个部分。第一部分为代码库，涵盖了大部分比赛常用的经典算法，包括数学、图论、数据结构、计算几何、论题选编五个大类，对每个算法的代码实现，都配有接口说明以及简略的算法阐述，便于读者理解。第二部分为贴士，收集了一些实用的知识点以及积分表，适合于带入赛场进行参考。
　　本书编写工作历时两年左右，参与编写工作的人员全部为上海交通大学ACM-ICPC队的现役队员。代码大多来自于往年上海交通大学ACM-ICPC队使用的SCL以及队员的日常训练。同时，本书的编写也得到上海交通大学ACM-ICPC队的退役队员大力帮助，他们参与了代码库的收集、整理、校验等工作。
　　参与本书写稿、审稿的人员主要有（按姓氏笔画为序）：?尹天蛟，乌辰洋，任春旭，刘奇，刘彦，寿鹤鸣，李说，杨思逸，吴卓杰，张捷钧，陈明骋，陈泽佳，陈彬毅，陈爽，林承宇，金斌，郑，胡张广达，郭晓旭，曹雪智，康南茜，章雍哲，商静波，彭上夫，谭天，缪沛晗，瞿钧等。
　　在此，衷心感谢所有为此书出版做出直接或间接贡献的人！也真心祝愿此书能够在算法实现和SCL的准备上给读者带来帮助。
　　由于时间仓促，作者水平有限，疏漏、不当和不足之处在所难免，真诚地希望专家和读者朋友们不吝赐教。如果您能在阅读和使用此书过程中发现任何问题或有任何建议，恳请发邮件，我们将不胜感激。
　　编  者
　　2012年10月于上海