前      言

编程竞赛介绍

随着计算机逐步深入人类生活的各个方面，利用计算机及其程序设计来分析、解决问题的算法在计算机科学领域乃至整个科学界的作用日益明显。相应地，各类以算法为主的编程竞赛也层出不穷：在国内，有全国青少年信息学奥林匹克联赛（National Olympiad in Informatics in Provinces，NOIP），该联赛与全国中学生生物学联赛、全国中学生物理竞赛、全国高中数学联赛、全国高中学生化学竞赛并称为国内影响力最大的“五大奥赛”；在国际上，有面向中学生的国际信息学奥林匹克竞赛（International Olympiad in Informatics， IOI）、面向亚太地区在校中学生的信息学科竞赛即亚洲与太平洋地区信息学奥林匹克（Asia-Pacific Informatics Olympiad，APIO）以及由国际计算机 学会主办的面向大学生的国际大学生程序设计竞赛（International Collegiate Programming Contest，ICPC）等。

各类编程竞赛要求参赛选手不仅具有深厚的计算机算法功底、快速并准确编程的能力以及创造性的思维，而且有团队合作精神和抗压能力，因此编程竞赛在高校、IT公司和其他社会各界中获得越来越多的认同和重视。编程竞赛的优胜者更是微软、谷歌、百度、Facebook等全球知名IT公司争相高薪招募的对象。因此，除了各类参加编程竞赛的选手外，很多不参加此类竞赛的研究工作者和从事IT行业的人士，也都希望能获得这方面的专业训练并从中得到一定的收获。

为什么要学习算法

经常有人说：“我不学算法也照样可以编程开发软件。”那么，为什么还要学习算法呢？

首先，算法（Algorithm）一词源于算术（Algorism），具体地说，算法是一个由已知推求未知的运算过程。后来，人们把它推广到一般过程，即把进行某一工作的方法和步骤称为算法。一个程序要完成一个任务，其背后大多会涉及算法的实现，算法的优劣直接决定了程序的优劣。因此，算法是程序的“灵魂”。学好了算法，就能够设计出更加优异的软件，以非常有效的方式实现复杂的功能。例如，设计完成一个具有较强人工智能的人机对弈棋类游戏，程序员没有深厚的算法功底是根本不可能实现的。

其次，算法是对事物本质的数学抽象，是初等数学、高等数学、线性代数、计算几何、离散数学、概率论、数理统计和计算方法等知识的具体运用。真正懂计算机的人（不是“编程匠”）都在数学上有相当高的造诣，既能用科学家的严谨思维来求证，也能用工程师的务实手段来解决问题——这种思维和手段的最佳演绎之一就是“算法”。学习算法，能锻炼我们的思维，使思维变得更清晰、更有逻辑、更有深度和广度。学习算法更是培养逻辑推理能力的非常好的方法之一。因此，学会算法思想，其意义不仅在于算法本身，更重要的是，对以后的学习生活和思维方式也会产生深远的影响。

最后，学习算法本身很有意思、很有趣味。所谓“技术做到极致就是艺术”，当一个人真正沉浸到算法研究中时，他会感受到精妙绝伦的算法的艺术之美，也会为它的惊人的运行速度和构思而深深震撼，并从中体会到一种不可言喻的美感和愉悦。当然，算法的那份“优雅”与“精巧”虽然吸引人，却也令很多人望而生畏。事实证明，对很多人来说，学习算法是一件非常有难度的事情。

本书的特色

本书尽可能详尽而全面地介绍编程竞赛中用到的大多数知识，读者如果能按照书中的安排，认真做好每一道题，必然能在各类编程竞赛中一展身手。

本书中部分题目采用了“多向思考”“一题多解” “一题多变”的解决方法，其目的主要有3点：一是充分调动读者思维的积极性，提高读者综合运用已学知识解答问题的技能；二是锻炼读者思维的灵活性，促进读者知识和智慧的增长；三是增加读者思维的深度和广度，引导读者灵活地掌握知识的纵横联系，培养和发挥读者的创造性。因此，绝不能简单地将这种训练看作编程技巧的花哨卖弄，相反，它能培养读者思维的敏捷性，促进读者智力和思维的发展，提高读者的变通能力与综合运用所学知识的能力。读者若能坚持这种思维训练方法，必能获得意想不到的良好学习效果。

如何使用本书

本书采用的是循序渐进、由浅入深的教学方法。一开始讲解引入新知识点的题目时，书中会提供该题目的完整参考代码以供读者参考，但随着读者对此知识点的理解逐步加深，后续的同类型题目将逐步向仅提供算法思路、提供伪代码和无任何提示的方式转变。此外，对于一些思维跨度较大的题目，本书会酌情给予读者一定的提示。

本书在“第02章 基本结构”后直接安排了“第03章 竞赛模拟”，是为了使读者尽快熟悉竞赛环境，做到在平时的训练中以竞赛的标准要求自己，例如，制作全面而完善的测试数据验证程序的正确性、确保提交的程序一次通过而不是反复提交才通过等。但这种思维习惯的养成，非一朝一夕之功，所以读者无须循规蹈矩，只需大致了解第03章的内容后就可以继续后面章节的学习，因为第03章的内容是贯穿于整本书的学习过程，并在不断做题实践中加深理解的。

第08章是关于指针的内容，通常初学者在竞赛中应用极少，读者可以根据自身情况确定是否学习。

题目后括号内的英文为提交的源代码名。

资源与支持

为了让读者有更好的使用体验，本书提供了多种资源与支持的方式。

（1）增值讲解视频

• 扫描书上二维码即可在线观看视频。

• “内容市场”微信小程序或App中搜索本书书名，即可在线观看视频。

• 异步社区网站搜索本书书名，单击在线课程，即可在线观看视频。

（2）测试数据

登录本书作者开发维护的在线评测网站www.magicoj.com，单击【课程分类】-【语言和算法入门】，选择对应题目即可查看，还可解锁海量题库并在线提交代码获得反馈。

（3）例题完整参考代码

在异步社区网站搜索本书书名，单击下载资源，即可下载例题完整参考代码。

适合阅读本书的读者

本书可作为NOIP的复赛教程和ICPC的参考和学习用书，还可作为计算机专业学生、算法爱好者的参考和学习用书。

致谢

感谢安徽省安庆市石化第一中学胡向荣老师，感谢浙江省宁波市北仑区霞浦学校张义丰老师，感谢浙江省慈溪市周巷镇潭北小学陈科老师，感谢贵州省贵阳市第一中学李守志老师，感谢全国各省市中学、大学的信息学奥赛指导老师，他们给本书提了许多真诚而有益的建议，并对笔者在写书过程中遇到的一些困惑和问题给予了热心的解答。

本书在完成过程中，使用了NOIP的部分原题、在线评测网站的部分题目，并参考和收集了其他创作者发表在互联网、杂志等媒体上的相关资料，无法一一列举，在此一并表示衷心感谢。

感谢卷积文化传媒（北京）有限公司CEO高博先生和他的同事，他们成功地将现代AI技术与传统的图书完美地结合起来，降低了读者学习编程的门槛。

最后要说的话

由于笔者水平所限，书中难免存在不妥之处，欢迎同仁或读者赐正。读者如果在阅读中发现任何问题，请发送电子邮件到hiapollo@sohu.com，更希望读者对本书提出建设性意见，以便修订再版时改进。

本书对应的题库网站正在不断完善中，网址为www.magicoj.com。

希望本书的出版，能够给学有余力的中学生、计算机专业的大学生、程序算法爱好者以及IT行业从业者提供学习计算机科学的帮助。

张新华

2021年5月