序

从1970年开始，ACM/ICPC赛事就影响着计算机与信息专业的许多大学生，引导着他们应用计算机技术展示自己分析问题解决问题的才能。哈尔滨工程大学于2005年开始积极投身于ACM/ICPC活动中。时至今日，令我欣慰的是，从仅有的几名程序设计爱好者到如今上百人参与集训的规模，我们的校代表队已形成了一套自己的训练方法。

在多年的磨炼中，我看到我们的队员走了一些弯路，也经历了一些波折。经过不断的尝试、努力，以及与其他高校参赛选手积极的交流，他们渐渐成长起来。今天，他们把自己的经验编辑成为一本系统的教材，既是对自己多年来训练学习的总结，也为了使更多的ACM/ICPC爱好者有“据”可依。

哈尔滨工程大学举办过多种形式的区域ACM/ICPC赛事，包括省级区域赛、东北四省区域赛、亚洲区域赛等。2010年，主办了第34届ACM/ICPC 全球总决赛。这是我们举办的一次最高等级的ACM/ICPC赛事。赛事获得了圆满成功，得到了ACM/ICPC组委会以及世界各国参赛队员的一致好评。作为东北地区组委会，我们每年都会积极地举办省赛、东北地区赛以及其他各种赛事。所谓的不进沙场，一切皆为纸上谈兵。校代表队要在各种赛事中磨炼才能更加坚毅。

ACM/ICPC赛事活动是大学生自己的活动。大学生通过这些活动全面提高了自己的能力。从组织训练、参加比赛、赛队管理到举办比赛，都有学生参与。我们希望看到在一个十分自由的学术氛围里，学生可以放开手脚，自主地学习、创新。在ACM/ICPC竞赛中，我们能够得到的不仅仅是算法上的知识，还有学生的动手能力、创造能力以及团队合作和组织能力等。这种能够全面培养学生各方面能力的赛事实属不多。我们希望借助这样的赛事，来提高学生的综合素质和专业技能。

“教书育人”四个掷地有声的字是我们永远的教学宗旨。我们时常会思索，应该教什么样的书，育什么样的人。从多年的国际教育研讨会上，不难发现，众多世界顶级的高等院校纷纷将创新型人才培养作为教育的重中之重，这和我们的教学理念是不谋而合的。几年来，我校ACM代表队不仅在各种ACM赛事中收获了奖牌，而且在各种科技创新活动中也非常活跃。他们开发的在线考试系统和Online Judge系统，在实际使用中表现出先进的设计思想、良好的人机环境和可靠的软件质量。

希望本书的出版可以引起更多程序设计爱好者的兴趣，可以成为ACM/ICPC参赛队员道路上的一块垫脚石。

第34届ACM/ICPC全球总决赛执行主席

哈尔滨工程大学副校长

前言

本书第1版自2010年8月出版以来，承蒙各个高校计算机程序设计爱好者的厚爱，给予了支持和肯定。根据读者反映，本书对学生参与ACM/ICPC竞赛训练、算法思维培养及程序设计实践，起到了有益的指导作用。

近年来，随着ACM/ICPC赛事在中国的不断发展，国内高校的参与度和竞赛成绩不断攀升。究其原因在于ACM/ICPC竞赛训练能够综合、全面、系统地培养学生的算法思维和设计能力。通过赛事训练，能够将计算机语言类课程以及数据结构、算法设计与分析、离散数学、组合数学、具体数学、数论等众多专业课程进行很好的融合，对学生的专业培养和教育大有益处。

自2005年开始，哈尔滨工程大学ACM/ICPC代表队便开始有针对性的训练，并于2007年秋季将ACM/ICPC实践形式引入本科教学，开设了ACM/ICPC竞赛入门课程。2010年，在哈尔滨工程大学成功举办了第34届ACM/ICPC全球总决赛。2014年秋季，哈尔滨工程大学开始探索创新的教学理念、教学模式以及教学考核评价方法，将ACM/ICPC竞赛形式和在线评测平台引入C语言、数据结构与算法设计和具体数学等课程的教学环节中，使理论与实践高效贯通，众多相关课程深度融合。无论是历年赛事训练，还是日常教学实践，我们都深感有必要对本书进行重新修订和完善，以使低年级学生更容易上手学习，使高年级学生能够站在更高起点进行思维训练。为此，根据历年经验积累，我们精心筛选补充了各章节例题。这些例题设计精巧，对学生能力培养和竞赛训练具有很好的指导作用。本次修订始终本着“实用、管用、够用”的原则，在尽量保持原版特色、组织结构和内容体系不变的前提下，对例题做了大量的筛选工作，同时对解题思路等内容进行了精心的设计和编写，既有利于启发，又留有余地，便于推动学生的思维培养。

在本书第2版的修订编写过程中，我们参阅了国内多位专家、学者的相关著作或译著，也参考了国内各高校ACM网站资源，在此对他们表示崇高的敬意和衷心的感谢！为本书的修订做出重要贡献的有宋旭、袁茂洵、岳盈、罗心语、刘晓冬等同学，他们对文字的整理和程序的调试做了大量辛苦的工作，在此一并表示感谢。

限于编者水平，本书在内容取舍、编写方面难免存在欠妥之处，恳请专家、同行和读者批评指正，我们将不胜感激！

作者2016年7月