信息学奥林匹克辞典 全国青少年信息学奥林匹克系列竞赛大纲详解

本辞典是对全国青少年信息学奥林匹克竞赛（NOI）大纲的详解。辞典立足于 NOI 大纲的知识体系，从准确性、学术性和实用性等原则出发，对有关的知识和概念给出了严谨的解析，并在此基础上对所涉及的思想、方法和技巧做了精要的述评，全面涵盖了全国青少年信息学奥林匹克竞赛所考查的计算机科学基础知识、程序设计语言及其环境、数据结构与算法，以及数学和其他内容。
本辞典的适读人群为参加全国青少年信息学奥林匹克竞赛活动的学生、教师，以及广大信息学、程序设计竞赛爱好者，对从事数据结构和算法的学习或教学等活动的其他读者也有较好的参考价值。

中国计算机学会（CCF）成立于1962年，全国性学会，独立社团法人，中国科学技术协会成员。
CCF是中国计算机及相关领域的学术团体，宗旨是为本领域专业人士的学术和职业发展提供服务；推动学术进步和技术成果的应用；进行学术评价，引领学术方向；促进技术和产业应用一线的交流和互动；对在学术和技术方面有突出成就的个人、企业和单位给予认可和表彰。

全国青少年信息学奥林匹克竞赛（NOI）大纲于2021年4月首次发布。NOI大纲规范了NOI系列赛的知识体系，对信息学竞赛的发展影响深远。NOI主席杜子德老师对大纲给予了高度评价，同时也指出：应当编制一本辞典（《信息学奥林匹克辞典——全国青少年信息学奥林匹克系列竞赛大纲详解》）对各知识点进行详解，进一步明晰和充实竞赛知识体系。辞典编撰团队随即成立，有关工作也全面铺开。

在工作开展初期，编撰团队原计划以资料收集和文字汇编的方式，在数月内完成辞典的编撰。随着工作的深入，辞典编撰的复杂性和挑战性逐渐显现：知识关联错综复杂、内容繁多，各类资料也纷繁芜杂、难以取舍；NOI大纲在此期间做了全面修订，给编撰工作带来了额外挑战。为确保辞典质量，编委会调整了工作方式，对竞赛知识体系进行了梳理、归类和一体化地重新描述。各位成员不遗余力、各展所长，历经近两年夜以继日的撰写和上百次线上线下的研讨，以及反复的内部整合修订，终于完成了这部辞典。以下就辞典的目标原则、体例设计、编撰过程等做简要说明。

一、目标原则

作为信息学竞赛知识方面的首部辞典，《信息学奥林匹克辞典——全国青少年信息学奥林匹克系列竞赛大纲详解》具有十分明确的目标，即立足于NOI大纲的知识体系，厘清当前信息学竞赛中的知识概念，高屋建瓴地评析竞赛中常见的思想、方法和技巧，简明扼要但不失全面地对各知识点做出解析。为此，编撰团队制定了如下编撰原则。

（1）准确性原则：在概念的把握和辨析上务求简练、准确，在结论性文字的表述上务求严谨和必有所本，避免似是而非和无的放矢。

（2）学术性原则：在概念铺陈和思想阐发上，务求与计算机科学学术体系全面接轨，为学生深造架设好知识桥梁，纠正当前小圈子里闭门造车的部分现象。

（3）可用性原则：在内容的设计和侧重上，务求贴近国内信息学竞赛教、学、赛的现状，充分展现面向NOI、服务竞赛师生和信息学爱好者的特点。

二、体例设计

在上述目标原则下，经过反复研讨和实践，编撰团队设计了辞典的如下体例。

（1）按照NOI大纲体系和版块划分组织词条。辞典按照入门级、提高级和NOI级三个等级进行组织，在每个等级下又划分“基础知识与编程环境”“C++程序设计”“数据结构”“算法”和“数学与其他”五个版块。

每个知识点均单独设置词条，在每个词条后均注明全部作者。其中排名最前的作者为词条的主要执笔人，排名最后的作者为词条的学术负责人，其他作者均依工作量大小排序。

（2）每个词条原则上设置“正文（不特别注明）”“代码示例”“参考词条”“延伸阅读”和“典型题目”五部分。五部分内容的定位分别如下。

●正　　文：以图文结合的形式，对词条中的概念、思想或方法予以述评。

●代码示例：紧密配合正文，给出本词条知识点的典型C++代码实现。

●参考词条：指出有关联的其他词条，以建立和加强知识点间的横向联系。

●延伸阅读：给出进一步阅读的文献，引导纵向、深入的学习和思考。

●典型题目：列出NOI系列赛以及国外权威赛事中的相关题目，引导读者做针对性的练习。

考虑到部分版块的特殊性，在“基础知识与编程环境”版块中不设置“代码示例”和“典型题目”，而在“数学与其他”版块中这两部分内容均设置为可选。

三、编撰过程

辞典编写工作启动后，我们首先在全国范围内遴选了多位优秀的一线信息学竞赛指导教师，分别带领所在学校的信息学竞赛教学团队参与编撰工作。他们是：

叶金毅（中国人民大学附属中学）

胡伟栋（北京师范大学附属实验中学）

金　靖（华东师范大学第二附属中学）

李　建（杭州第二中学）

叶国平（安徽师范大学附属中学）

汪星明（北京市十一学校）

谢秋锋（长沙市长郡中学）

李　曙（南京外国语学校）

随后确定了辞典的编撰原则和体例设计，将辞典编写工作分成分头编撰、审读重构、整合统稿三个阶段，并依序开展。由胡伟栋建立了辞典git服务器，以实施书稿的分布式提交与版本管理。在分头编撰阶段，按照辞典的等级与版块设置，我们将词条编撰工作划分成若干部分，分别请以上教师与NOI科学委员会副主席赵启阳一起，牵头撰写了相应词条的初稿。

初稿完成后，我们按照“正文”“代码示例”“参考词条、延伸阅读与典型题目”的纵向划分，将以上牵头教师分成三个小组，分别对初稿进行全面的审读和大幅度重构。其中，叶金毅、胡伟栋、金靖、赵启阳负责“正文”部分，李建、叶国平、李曙负责“代码示例”部分，汪星明、谢秋锋、金靖负责“参考词条、延伸阅读与典型题目”部分（叶国平也参与了部分“正文”的审读重构）。经过纵向的审读与重构，辞典在准确性、学术性、可用性等方面都得到了显著的改进与提升。

在整合统稿阶段，赵启阳、叶金毅、胡伟栋、金靖等对全书内容进行了整合与统稿，从整体性的角度出发，对部分文字、插图等内容进行了调整和修订。金靖对典型题目部分做了全面的梳理和补充。

编写完成这部辞典，没有相当的精力和时间投入是做不到的。全体参编人员都积极投入到辞典的编撰工作中。每个词条都历经数次逐字逐句的推敲，有的词条还经过了前后数十次的修订，其间查阅了大量的学术著作和第一手文献。为了写好、改好每个词条，各位老师纷纷拿出自己经年积累的独家讲义和宝贵的内部材料，充分体现出了无私的奉献精神。在此期间，广泛涉猎算法特别是图算法研究的学界前辈R.Tarjan，凭借其原始论文在辞典编撰过程中极高的“出镜率”和多次意想不到的出场，也逐渐变成了大家非常熟悉的一位“虚拟参编人员”。

在辞典编撰过程中，杜子德老师对各项工作给予了直接指导和全面支持，尹宝林、王宏两位老师在词条的学术性方面也提出了大量宝贵的建议，NOI科学委员会、NOI办公室也在各方面提供了支持和帮助。陈知轩、高麟翔、管晏如、郭羽冲、胡瑞岩、林帮才、柯怿憬、柯绎思、彭思进、齐楚涵、万成章、王又嘉、吴雨洋、肖子尧、郑佳睿、周逸桐、左骏驰（以上按拼音顺序）等也参与了辞典的材料准备和整理工作。在此向他们致以真诚的谢意。

尽管这部辞典是全体参编人员倾力合作完成的，但是由于我们学识有限，而且时间仍显仓促等，其中必然还存在着各种缺陷和不足。在此恳请读者予以指正，以帮助我们更好地改进这部辞典。

《信息学奥林匹克辞典》编委会

序Ⅰ

序Ⅱ

前言

符号表

主要信息学竞赛及相关活动列表

入门级

1.1　基础知识与编程环境3

1.1.1　计算机的基本构成3

1.1.2　Windows、Linux等操作系统的基本概念及其常见操作3

1.1.3　计算机网络和Internet的基本概念4

1.1.4　计算机的历史和常见用途4

1.1.5　NOI以及相关活动的历史6

1.1.6　NOI以及相关活动的规则7

1.1.7　位、字节与字8

1.1.8　程序设计语言以及程序编译和运行的基本概念8

1.1.9　使用图形界面新建、复制、删除、移动文件或目录9

1.1.10　使用Windows系统下的集成开发环境10

1.1.11　使用Linux系统下的集成开发环境10

1.1.12　g++、gcc等常见编译器的基本使用10

1.2　C++程序设计11

1.2.1　程序基本概念11

1.2.2　基本数据类型14

1.2.3　程序基本语句16

1.2.4　基本运算21

1.2.5　数学库常用函数24

1.2.6　结构化程序设计25

1.2.7　数组27

1.2.8　字符串的处理29

1.2.9　函数与递归30

1.2.10　结构体与联合体34

1.2.11　指针类型35

1.2.12　文件及基本读写38

1.2.13　STL模板40

1.3　数据结构44

1.3.1　线性结构44

1.3.2　简单树48

1.3.3　特殊树52

1.3.4　简单图59

1.4　算　法65

1.4.1　算法概念与描述65

1.4.2　入门算法66

1.4.3　基础算法69

1.4.4　数值处理算法74

1.4.5　排序算法82

1.4.6　搜索算法88

1.4.7　图论算法90

1.4.8　动态规划93

1.5　数学与其他100

1.5.1　数及其运算100

1.5.2　初等数论102

1.5.3　离散与组合数学108

1.5.4　其他113

提高级

2.1　基础知识与编程环境117

2.1.1　Linux系统终端中常用的文件与目录操作命令117

2.1.2　Linux系统下常见文本编辑工具的使用118

2.1.3　g++、gcc等编译器与相关编译选项119

2.1.4　在Linux系统终端中运行程序，使用time命令查看程序用时120

2.1.5　调试工具GDB的使用120

2.2　C++程序设计121

2.2.1　类121

2.2.2　STL模板125

2.3　数据结构135

2.3.1　线性结构135

2.3.2　集合与森林144

2.3.3　特殊树146

2.3.4　常见图161

2.3.5　哈希表166

2.4　算　法169

2.4.1　复杂度分析169

2.4.2　算法策略（离散化）173

2.4.3　基础算法（分治算法）173

2.4.4　排序算法174

2.4.5　字符串相关算法（字符串匹配：KMP算法）182

2.4.6　搜索算法184

2.4.7　图论算法188

2.4.8　动态规划218

2.5　数学与其他224

2.5.1　初等数学224

2.5.2　初等数论224

2.5.3　离散与组合数学229

2.5.4　线性代数234

NOI级

3.1　C++程序设计（面向对象的程序设计思想）243

3.2　数据结构244

3.2.1　线性结构（块状链表）244

3.2.2　序列（跳跃表）245

3.2.3　复杂树246

3.2.4　可合并堆267

3.2.5　可持久化数据结构270

3.3　算　法275

3.3.1　算法策略275

3.3.2　字符串算法282

3.3.3　图论算法295

3.3.4　动态规划322

3.4　数学与其他330

3.4.1　初等数论330

3.4.2　离散与组合数学335

3.4.3　线性代数342

3.4.4　高等数学344

3.4.5　概率论349

3.4.6　博弈论352

3.4.7　最优化（单纯形法）353

3.4.8　计算几何357

3.4.9　信息论（熵、互信息、条件熵、相对熵）362

3.4.10　其他363