图灵社区的电子书没有采用专有客 户端，您可以在任意设备上，用自 己喜欢的浏览器和PDF阅读器进行 阅读。 但您购买的电子书仅供您个人使用， 未经授权，不得进行传播。 我们愿意相信读者具有这样的良知 和觉悟，与我们共同保护知识产权。 如果购买者有侵权行为，我们可能 对该用户实施包括但不限于关闭该 帐号等维权措施，并可能追究法律 责任。 图书在版编目（CIP）数据 高效算法：竞赛、应试与提高必修 128 例 /（法）克 里斯托弗·杜尔（Christoph Dürr） ， （法）吉尔 - 让· 维（Jill-Jênn Vie）著 ；史世强译 . -- 北京 ：人民 邮电出版社，2018.5 （图灵程序设计丛书） ISBN 978-7-115-48085-9 Ⅰ. ①高… Ⅱ. ①克… ②吉… ③史… Ⅲ . ①计算机 算法－研究 Ⅳ . ① TP301.6 中国版本图书馆 CIP 数据核字（2018）第 050544 号 内 容 提 要 本书旨在探讨如何优化算法效率，详细阐述了经典算法和特殊算法的实现、应用技巧和复杂度验证 过程，内容由浅入深，能帮助读者快速掌握复杂度适当、正确率高的高效编程方法以及自检、自测技巧， 是参加 ACM/ICPC、Google Code Jam 等国际编程竞赛、备战编程考试、提高编程效率、优化编程方法的 参考书目。 [ 法 ] Christoph Dürr Jill-Jênn Vie ◆著 译 史世强 责任编辑 戴 童 责任印制 周昇亮 ◆ 人民邮电出版社出版发行 邮编 100164 北京市丰台区成寿寺路 11 号 电子邮件 [email protected] 网址 http://www.ptpress.com.cn 北京 印刷 ◆ 开本：800×1000 1/16 印张：12.75 字数：301 千字 2018 年 5 月第 1 版 印数：1 -3 500 册 2018 年 5 月北京第 1 次印刷 著作权合同登记号 图字：01-2017-3131号 定价：55.00 元 读者服务热线：(010)51095186 转 600 印装质量热线：(010)81055316 反盗版热线：(010)81055315 广告经营许可证：京东工商广登字 20170147 号 译者序 22 年前的秋天，我刚刚进入初中时，得到了一台中华学习机。它的 1 MHz 主频甚至赶不上现 在一台 10 元钱的计算器。我从第一行用 BASIC 语言写的 IF/ELSE 开始，开启了自己的编程人生。 1996 年，还是初中生的我凭着不多的算法和逻辑知识参加了国家信息学奥林匹克竞赛，当然，最后 只得到了安慰奖。二十多年后，我得知当年斩获金牌的是王小川，如今搜狗的 CEO。 现在，我在一家互联网公司负责技术并管理研发团队。从自身的职业发展经历，以及在中国和 法国的招聘和用人经历中，我深刻体会到了软件工程师的成就在很大程度上取决于他的专业知识视 野。这是个很现实的问题。因此，我在得到翻译这本法语技术书的机会时，欣然接受了这个颇有难 度的任务。 法国是一个盛产数学家的国度。不同于大家的传统印象，法国人在“浪漫”的同时，在工作和 科研中非常讲究逻辑与验证——产品原型要验证，技术探索要验证。证明和实验有着同样不可或缺 的地位。理论和实践的结合，让法国学界和企业界在相当长时间内保持着旺盛的生命力与创造力。 这是我在法国 8 年学习和工作中的真实体验。 本书由法国国际信息学奥林匹克竞赛“国家队”辅导老师编写，凝聚了作者辅导高中生、大学 生参加国际信息学奥林匹克竞赛的大量经验和技巧。书中提及的部分算法十分常见，在实际工作中 也十分常用。但也有另一部分算法，例如舞蹈链算法以及一些涉及图论与匹配的算法，在中国的大 学教育都不太提及。 在人工智能和深度学习大发展的今天，Python 语言、算法，特别是证明算法可靠性和高效性的 能力，是进入大数据和人工智能人才市场的入场券。希望读者善用 Github 和作者准备的源代码网 站，以及网上能够找到的技术资源，在尝试代码实现的同时，去理解算法复杂度的证明过程，从而 彻底掌握并熟练运用这些凝聚了很多代人智慧的无形资产。 我要感谢教我写下第一行代码的哥哥史轶，支持并指导我参加国家信息学奥林匹克竞赛的湖北省 十堰市东风汽车公司第四中学的陈长国老师，用大量课外知识开拓了我的见识的东风汽车公司第一中 学的吴华山老师，支持我前往法国留学的父母，以及一直以来给我带来太多快乐的妻子和孩子。 由于个人水平有限，译文不能做到尽善尽美，欢迎读者通过我的个人网站 www.jetwaves.cn 与 我交流。 史世强 2017 年 10 月于巴黎 序 我们编写本书的主要动力是对 Python 语言编程的热爱和对解决算法问题的激情。Python 语言 能够如此打动人，是因为这种语言能让我们编写清晰而优雅的代码，把注意力集中于算法的本质步 骤，而不需要过多关注复杂的语法和数据结构。同时，我们用 Python 完成编写程序后数个月再回 头来读的时候，仍然可以理解自己写的代码，这一点十分有教益。作为本书的作者，我们最希望的 是能接受新的挑战，其次是能经得住各种测试，因为一段程序代码只有在毫无 bug 地实现后，我们 才算真正地掌握了编程技巧。我们希望用自己的热情感染读者，营造出一种氛围，鼓励大家学习和 掌握扎实的算法和编程基础知识。这种学习经历往往会受到大型软件企业招聘人员的赏识，而对于 软件工程师或计算机科学教育工作者来说，这对其整个职业生涯也会有所帮助。 本书按照主题而不是技术分类收录了 128 种算法。其中某些算法是常见的经典算法，另一些则 不太常见。尤其在读者备战 ACM-ICPC、Google Code Jam、Facebook Hacker Cup、Prologin 和 France-ioi 等编程竞赛时，本书编写的大量问题将起到积极的辅导作用。我们希望本书能够成为算 法的基础教程和高级程序设计教程的参考，或者能让学习数学和计算机专业的读者看到与众不同的 进修内容。读者可以在网站 tryalgo.org（http://tryalgo.org/code/）上找到本书使用的源代码库 A，以及 用来测试代码调试结果和实现性能的链接。 感谢 Huong 和智子，如果没有这两位朋友的支持，本书是无法完成的。感谢法国综合理工学院 和法国高等师范学院 Cachan 分校的学生们，他们多次通宵达旦的训练，为本书提供了很多素材。 最后，感谢所有审阅手稿的朋友们，他们是 René Adad、Evripidis Bampis、Binh-Minh Bui-Xuan、 Stéphane Henriot、Lê Thành Dững Nguyễn、Alexandre Nolin 和 Antoine Pietri。本书的作者之一要特 别感谢在 Tiers 高中时的老师 Yves Lemaire 先生：当年就是在这位老师的启迪下，作者才初次发现 了本书 2.5 节中描述的“宝藏”。 最后，我们希望读者在碰到算法难题时，能够耐心地花时间去思考。祝愿大家能在豁然间找到 解答，甚至是一个优雅的解答，享受到胜利的喜悦之情。 好，我们要开始了！ A 也可以用 PyPI 直接安装后下载查看并执行。——译者注 目录 第 1 章 引言............................................................................................................................................... 1 1.1 编程竞赛............................................................................................................................ 1 1.2 线上学习网站......................................................................................................... 3 1.1.2 线上裁判的返回值.................................................................................................. 4 我们的选择：Python........................................................................................................ 5 1.3 输入输出............................................................................................................................ 6 1.4 读取标准输入......................................................................................................... 6 1.3.2 显示格式. ............................................................................................................... 9 复杂度................................................................................................................................ 9 1.5 抽象类型和基本数据结构.............................................................................................. 11 1.1.1 1.3.1 1.5.1 1.5.2 1.5.3 1.5.4 1.6 栈. .............................................................................................................