ACM国际大学生程序设计竞赛

出版时间：2013-1  出版社：清华大学出版社  作者：俞勇 编  页数：274  字数：445000  
Tag标签：无  

前言

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

内容概要

　　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 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 串的最小表示
……
第二部分 贴士

章节摘录

版权页：   插图：   【注释】 常数中，maxn为圆的个数，maxN为所有事件点的个数。 另外，新增了圆类Tcir和中间过程所需的区问类Tinterval。 【使用范例】 参见程序SPOJ VCIRCLE.CPP。 3.2.6圆的面积并 【任务】 给定n个圆，求它们的面积并。 【说明】 如图所示，将圆的面积剖分成若干个多边形的面积与若干个弓形的面积。多边形的边就是圆的交点构成的不被其他圆覆盖的弦。计算有向面积的话，可以看到中间“洞”的面积恰好被顺时针的多边形包围，因此会被减去。请注意，必须去除重复的圆，否则答案会有重复计算的面积。

编辑推荐

《ACM国际大学生程序设计竞赛(ACM-ICPC)系列丛书:ACM国际大学生程序设计竞赛:算法与实现》适用于参加ACM国际大学生程序设计竞赛的本科生和研究生，对参加青少年信息学奥林匹克竞赛的中学生也很有指导价值。

用户评论 (总计36条)

•   ACM国际大学生程序设计竞赛：算法与实现（ACM国际大学生程序设计竞赛（ACM-ICPC）系列丛书）
•   适合准备ACM竞赛，对学习算法也很有帮助
•   ACM-ICPC训练的引导书籍，这书内容很简单，我认为作用就是告诉ACMers应该学习哪些内容
•   给学生辅导大学生软件竞赛参考一下，还可以
•   提供了各种算法的程序，配套系列的其他书籍更好
•   其实不参加竞猜也可可以把它当做算法的学习参考书来看的
•   对于学算法的人很有帮助，用了感觉挺不错的
•   孩子学习需要，一本不错的教材
•   当当的包装实在太差了！
•   书的内容不错，但是书有破损，有折痕，印刷不错。应该是没保存，快递速度一般。
•   很多超详细的代码呀，不过没有关于代码的注释，理解起来有难度。
•   实用有效很好非常的不错哦
•   给孩子买的，是本不错的的书。
•   一整套的scl，很实用。一本书可以带着区面试了。
•   好好，还可以，挺不错的，用起来还乐意
•   适合想要搞ACM的同学。
•   RT，很多方面的算法都有可执行的代码实现，但是几何部分的代码整合得有点乱，而且没有DP的例题。。
•   这本书的算法那些 都还是比较详细
•   书还行，快递就算了，这辈子没见过这么**的快递，18号下单，26号才到，派件派了5天
•   内容还是不错的，只是封面有点儿旧
•   希望能吃透这本书
•   没看呢，等看完了给追评！
•   这本书很适合初学算法的同学，可以当作模版来使用，也可以用来比较各种算法的效率问题
•   学了很久的ACM，这是买个学弟们使用的。
•   不错，用的c++语言写的。
•   好好读一读，觉得这书写的挺好的
•   算法与实现比起第一本书而言专业的多，都是详尽的代码和算法。可作为SCL使用
•   涉及的面还可以，模版的代码风格也还不错。
•   非常好，全面。要同时看另外2本书
•   题目难度有点大 不过毕竟是竞赛 我要加油啦
•   书的知识面覆盖还可以，基本各种算法都涉及到了，但是代码没有任何注释，很多算法直接是代码，如果想搞清来龙去脉还不太够。
•   这本书只有题目。而且解答都不咋的，，，，，，不全，，，
•   对于学算法是本好书，讲的很不错
•   书就那样吧，旧了点就是了
•   全是代码，都没有文字说明算法。
•   书的质量还不错，可以拿来当模板库。