前言

编程竞赛介绍

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

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

为什么要学习算法？

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

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

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

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

本书的特色及用法

为了提高读者的学习效率，本书直接以各类竞赛真题入手，以精练而准确的语言，全面细致地介绍了编程竞赛中经常用到的各类基础算法；为了帮助读者更深刻地理解和掌握算法的思想内涵，本书还通过精挑细选，由浅入深地安排了相关习题。考虑到读者的接受水平，一般引入新知识点的题目时，书中会提供该题目的完整参考代码以供读者参考，但随着读者对知识点的理解逐步加深，后续的同类型题目将逐步向仅提供算法思路、提供伪代码或无任何提示的方式转变。此外，对于一些思维跨度较大的题目，本书会酌情给予读者一定的提示。

本书每章分为普及组和提高组两部分。通常，普及组所涉及的内容对应NOIP普及组难度，提高组所涉及的内容对应NOIP提高组难度。一个合理的学习安排是将本书的内容分为两个阶段学习，即第一个阶段学习各章的普及组内容，初步掌握每种算法的思想和用法，第二个阶段学习各章的提高组内容，作为之前学习的算法内容的复习和提高。

配套资源

为了帮助读者通过本书更好地掌握算法知识，本书提供了丰富的配套资源，包括源码、题目讲解视频、PPT。读者可通过以下方式获取配套资源。

● 源码和PPT的下载地址为https://box.ptpress.com.cn/y/59659

● 题目讲解视频可在线观看。

方法一：在异步社区网站搜索本书书名，进入本书页面，单击【在线课程】，可在线观看讲解视频。

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

适合阅读本书的读者

本书可作为NOIP复赛的教材和ICPC的参考与学习用书，也可作为计算机专业学生、IT工程师、科研人员、算法爱好者的参考和学习用书。

本书既可以作为学习完《编程竞赛宝典：C++语言和算法入门》的读者继续学习的教材，也可以作为有一定编程基础的读者学习算法的独立用书。

致谢

感谢全国各省市中学、大学的信息学奥赛指导老师，他们给本书提了许多真诚而有益的建议，并对编者在写书过程中遇到的一些困惑和问题给予了热心的解答。

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

感谢卷积文化传媒（北京）有限公司CEO高博先生和他的同事。

最后要说的话

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

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

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

广州市第六中学强基计划基地教材编委会

2023年1月