写在最前面的话

　　　自从上海交通大学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月于上海