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

写在最前面的话 自从上海交通大学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所高校承办过亚洲区预赛；参赛学校从不满30所，到如今已达150多所；人数从不到200人，到如今已近15万；总决赛名额从起初的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题集，希望可以为读者指引一条割题之路。 　　本书的选题基本涵盖了《ACM国际大学生程序设计竞赛：知识与入门》和《ACM国际大学生程序设计竞赛：算法与代码》两书中所涉及的算法，包括数学、图论、计算几何、数据结构、求解策略、问题选编6个大类。题目来源也可谓包罗万象，包括历年ACM-ICPC的分区赛、总决赛，各个在线评测系统：POJ、ZOJ、UVa、Ural、SGU、SPOJ、TC，以及各国的奥林匹克信息学（Olympiad in lnformatics，简称OI）竞赛。全书分为两个部分，第一部分“例题精讲”针对各个算法配备经典例题，并提供细致的解题思路，读者可以通过这一部分学习和掌握算法；第二部分“海量题库”按照算法分类罗列出大量习题，并提供相应的题解思路，读者可以利用这一部分的题目进行练习和训练，更加熟练地运用各类算法。 　　我们在收集题目时，按照题目难易程度由易到难的顺序分为5档：★☆☆☆☆（1颗星）、★★☆☆☆（2颗星）、★★★☆☆（3颗星）、★★★★☆（4颗星）、★★★★★（5颗星），其中1颗星属于分区赛的“前期题”，而5颗星则属于“后期题”、“防退场题”。考虑到1颗星几乎没有思考难度，以及限于本书的篇幅，我们没有将其收录到书中，而其余4档难度的题目则适合各种程度的选手。 　　本书编写工作历时两年多，参与编写工作的人员全部为上海交通大学ACM-ICPC队的现役队员，他们在亲力亲为割题的基础上，将解题思路书写成册。书中随处可见他们的思维过程以及做题时所遇到的困难，相信读者或多或少会产生些共鸣，从而获得启发。同时，本书的编写也得到上海交通大学ACM-ICPC队的退役队员的大力帮助，他们参与选题、写稿、审 稿等工作。 　　参与本书写稿、审稿的人员主要有（按姓氏笔画为序）：尹天蛟、王凯南、戎术、刘奇、刘彦、刘爽、任春旭、李说、陈爽、陈彬毅、陈楠昕、佘召臣、张弘毅、张健夫、张捷均、杨思逸、寿鹤鸣、易茜、金斌、金天行、周玉姣、林承宇、胡张广达、饶国腾、郭晓旭、黄偲、黄文瀚、曹雪智、章雍哲、商静波、彭上夫、谭天、缪沛晗、瞿钧等。 　　参与本书选题工作的人员主要有（按姓氏笔画为序）：陈明骋、陈泽佳、吴卓杰、张培超、郑曌、姜啸、曹正等。 　　在此，衷心感谢所有为此书出版做出直接或间接贡献的人！也真心祝愿此书能够给更多读者带来“割题”的快乐！ 　　由于时间仓促，作者水平有限，疏漏、不当和不足之处在所难免，真诚地希望专家和读者朋友们不吝赐教。如果您在阅读和使用此书过程中发现任何问题或有任何建议，恳请发邮件，我们将不胜感激。 　　 　　编 者 　　2012年10月于上海

版权图片链接