自从上海交通大学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）的试题覆盖了计算机科学以及相关数学领域众多知识点。这些知识通常会散落在各种书籍和论文之中，学习和查找起来相对麻烦。此外，竞赛中所考察的内容具有一定的特殊性，即使是像由Thomas H. Cormen等编著的Introduction to Algorithms这样的经典书籍，其中介绍的东西也并非都是竞赛中的考察点。因此能够有一本书针对ACM-ICPC竞赛所经常考察的知识点进行统一的介绍是有必要的。

　　本书分为三个部分，第一部分为入门与进阶，第二部分为知识点与求解策略，第三部分为在线资源。第一部分介绍的内容包括如何快速入门、如何提高自身以及团队水平等，主要是编者根据多年的参赛经验总结而来。第二部分基本涵盖了竞赛中所涉及的主要知识点，包括数学基础、数据结构、图论、计算几何、论题选编、求解策略等6个大类。第三部分对一些常用的在线评测系统和网上比赛进行了介绍。其中，第一部分和第三部分主要针对初学者。

　　由于ACM-ICPC竞赛涉及到的知识点较多，很难在有限的篇幅里做到完全的覆盖，编者主要根据重要性和实用性对内容进行了筛选。例如，在介绍平衡二叉树时，一般的数据结构书籍往往会介绍AVL树或是红黑树，但本书只介绍了理解和实现起来更为简单的伸展树和Treap。

　　本书知识点部分的内容采用的是一种类似百科全书的组织方式，所以并不需要一章一章地从前往后阅读。读者完全可以选择一个自己感兴趣的知识点进行阅读，并扩展延伸到与之相关的其他知识点中。

　　本书编写工作历时两年多，参与编写工作的人员全部为上海交通大学ACM-ICPC队的现役与退役队员。他们参考了大量的书籍，并结合了多年的竞赛经验，对本书的内容进行选择、撰写和修改。

　　参与本书写稿、审稿的人员主要有（按姓氏笔画为序）：乌辰洋、吴卓杰、张培超、陈彬毅、林承宇、易茜、郑曌、姜啸、曹正、曹雪智、商静波、彭上夫、程宇、谭天。

　　在此，衷心感谢所有为此书出版做出直接或间接贡献的人！也真心祝愿此书能够给更多读者带来学习知识的快乐！

　　由于时间仓促，作者水平有限，疏漏、不当和不足之处在所难免，真诚地希望专家和读者朋友们不吝赐教。如果您在阅读和使用此书过程中发现任何问题或有任何建议，恳请发邮件，我们将不胜感激。

　　编  者     

2012年10月于上海