Skip to content

NOI 大纲

本文在 CCF 公布的《全国青少年信息学奥林匹克系列竞赛大纲》的基础上，修正了一些笔误，重新进行了排版，并添加了一些外部链接。

#一、入门级

#1.1 计算机基础与编程环境

【1 级】计算机的基本构成（CPU、内存、I/O 设备等）；
【1 级】Windows、 Linux 等操作系统的基本概念及其常见操作；
【1 级】计算机网络和 Internet 的基本概念；
【1 级】计算机的历史及其在现代社会中的常见应用；
【1 级】NOI 以及相关活动的历史；
【1 级】进制的基本概念与进制转换、字节与字；
【1 级】程序设计语言以及程序编译和运行的基本概念；
【1 级】使用图形界面新建、复制、删除、移动文件或目录；
【1 级】使用 Windows 系统下的集成开发环境（例如 Dev-C++ 等）；
【1 级】使用 Linux 系统下的集成开发环境（例如 Code::Blocks 等）；
【1 级】gcc、g++ 等常见编译器的基本使用。

#1.2 C++ 程序设计

#1.2.1 程序基本概念

【1 级】标识符、关键字、常量、变量、字符串、表达式的概念；
【1 级】常量与变量的命名、定义及作用；
【2 级】头文件与名字空间的定义与理解；
【2 级】编辑、编译、解释、调试等概念理解。

#1.2.2 基本数据类型

【1 级】整数型：int、long long；
【1 级】实数型：float、double；
【1 级】字符型：char；
【1 级】布尔型：bool。

#1.2.3 程序基本语句

【2 级】cin 语句、scanf 语句、cout 语句、printf 语句、赋值语句、复合语句；
【2 级】if 语句、switch 语句、多层条件语句；
【2 级】for 语句、while 语句、do while 语句；
【3 级】多层循环语句。

#1.2.4 基本运算

【1 级】算数运算：加、减、乘、除、整除、求余；
【1 级】关系运算：大于、大于等于、小于、小于等于、等于、不等于；
【1 级】逻辑运算：与（&&）、或（||）、非（!）；
【1 级】变量自增与自减运算；
【1 级】三目运算；
【3 级】位运算：与（&）、或（|）、非（~）、异或（^）、左移（<<）、右移（>>）。

#1.2.5 数学库常用函数

【3 级】绝对值函数、四舍五入函数、取上整函数、取下整函数、常用三角函数、对数函数、指数函数、平方根函数。

#1.2.6 结构化程序设计

【1 级】顺序结构、分支结构和循环结构；
【2 级】自顶向下、逐步求精的模块化程序设计；
【2 级】流程图的概念及流程图描述。

#1.2.7 数组

【1 级】数组定义，数组与数组下标的含义；
【1 级】数组的读入与输出；
【2 级】纯一维数组的综合运用；
【3 级】纯二维数组与多维数组的综合应用。

#1.2.8 字符串的处理

【2 级】字符数组与字符串的关系；
【2 级】字符数组的综合应用；
【2 级】std::string 类定义、相关函数引用；
【3 级】std::string 类的综合应用。

#1.2.9 函数与递归

【2 级】函数定义与调用，形参与实参；
【3 级】传值参数与传引用参数；
【2 级】常量与变量的作用范围；
【2 级】递归函数的概念、定义与调用。

#1.2.10 结构体类型

【3 级】结构体的定义及应用。

#1.2.11 指针类型

【4 级】指针的概念及调用；
【4 级】指针与数组；
【4 级】字符指针与 std::string 类；
【4 级】指向结构体的指针。

#1.2.12 文件及基本读写

【2 级】文件的基本概念，文本文件的基本操作；
【2 级】文本文件类型与二进制文件类型；
【2 级】文件重定向、文件读写等操作。

#1.2.13 STL 模板应用

【3 级】<algorithm> 中 std::sort 函数；
【4 级】栈（std::stack）、队列（std::queue）、链表（std::list）、向量（std::vector）等容器。

#1.3 数据结构

#1.3.1 线性表

【3 级】链表：单链表、双向链表、循环链表；
【3 级】栈；
【3 级】队列。

#1.3.2 简单树

【3 级】树的定义及其相关概念；
【4 级】树的父亲表示法；
【3 级】二叉树的定义及其基本性质；
【4 级】二叉树的孩子表示法；
【4 级】二叉树的遍历：前序、中序、后序遍历。

#1.3.3 特殊树

【4 级】完全二叉树的定义与基本性质；
【4 级】完全二叉树的数组表示法；
【4 级】哈夫曼树的定义、构造及其遍历；
【4 级】二叉树的定义、构造及其遍历。

#1.3.4 简单图

【3 级】图的定义及其相关概念；
【4 级】图的邻接矩阵存储；
【4 级】图的邻接表存储。

#1.4 算法

#1.4.1 算法概念与描述

【1 级】算法概念；
【2 级】算法描述：自然语言描述、流程图描述、伪代码描述。

#1.4.2 入门算法

【1 级】枚举法；
【1 级】模拟法。

#1.4.3 基础算法

【3 级】贪心法；
【3 级】递推法；
【4 级】递归法；
【4 级】二分法；
【4 级】倍增法。

#1.4.4 数值处理算法

【4 级】高精度的加法；
【4 级】高精度的减法；
【4 级】高精度的乘法；
【4 级】求高精度整数除以单精度整数的商和余数。

#1.4.5 排序算法

【3 级】排序的基本概念（稳定性等）；
【3 级】冒泡排序；
【3 级】简单选择排序；
【3 级】简单插入排序。

#1.4.6 图论算法

【4 级】图的深度优先遍历算法；
【4 级】图的宽度优先遍历算法；
【5 级】洪水填充算法（Flood Fill）。

#1.4.7 动态规则

【4 级】动态规划的基本思路；
【4 级】简单一维动态规划；
【5 级】简单背包类型动态规划；
【5 级】简单区间类型动态规划。

#1.5 数学

#1.5.1 数及其运算

【1 级】数的概念，算术运算（加、减、乘、除、求余）；
【1 级】数的进制：二进制、八进制、十六进制和十进制及其转换；
【2 级】编码：ASCII 码，哈夫曼编码，格雷码。

#1.5.2 初中数学

【1 级】初中代数；
【1 级】初中平面几何。

#1.5.3 初等数论

【3 级】整除、因数、倍数、指数、质数、合数、同余等概念；
【3 级】唯一分解定理；
【3 级】欧几里得算法（辗转相除法）；
【4 级】埃氏筛法和线性筛法求素数。

#1.5.4 组合数学

【2 级】加法原理；
【2 级】乘法原理；
【4 级】排列及计算公式；
【4 级】组合及计算公式；
【4 级】杨辉三角公式。

#二、提高级

#2.1 计算机基础与编程环境

【5 级】在 Linux 系统终端中使用 mkdir、cp、rm、mv 等命令新建、复制、删除、移动文件或目录；
【5 级】在 Linux 系统终端中使用 cd、pwd、ls 等命令更改、显示目录路径和查看目录中的文件；
【5 级】在 Linux 系统下使用 Gedit、Vim 或 Emacs 等文本编辑工具编写代码；
【5 级】熟悉 gcc、g++ 等编译器以及优化、数学库等常见编译选项；
【5 级】在 Linux 系统终端中运行程序，并使用 time 命令查看程序用时（区分 real time、sys time 和 user time）；
【5 级】了解调试工具 gdb 及其 break、display、continue、step 等命令。

#2.2 C++ 程序设计

#2.2.1 类（class）

【6 级】类的概念及简单应用；
【6 级】成员函数和运算符重载。

#2.2.2 STL 模板

【5 级】集合（std::set）；
【5 级】列表（std::list），双端队列（std::deque），优先队列（std::priority_queue）；
【5 级】多重集合（std::multiset）；
【5 级】映射（std::map），多重映射（std::multimap）；
【5 级】对（std::pair），元组（std::tuple）。

#2.3 数据结构

#2.3.1 线性结构

【5 级】双端栈；
【5 级】双端队列；
【5 级】有序队列；
【6 级】优先队列；
【6 级】倍增表（ST 表）。

#2.3.2 集合与森林

【6 级】等价类；
【6 级】并查集；
【6 级】树与二叉树的转化 —— 孩子兄弟表示法。

#2.3.3 特殊树

【6 级】线段树与树状数组；
【6 级】字典树（Trie 树）；
【7 级】笛卡尔树；
【8 级】二叉平衡树：AVL、Treap、Splay 等；
【8 级】基环树。

#2.3.4 常见图

【5 级】稀疏图；
【6 级】偶图（二分图）；
【6 级】欧拉图；
【6 级】有向无环图；
【7 级】连通图与强连通图；
【7 级】重连通图。

#2.3.5 哈希表

【5 级】数值哈希函数构造；
【6 级】排列哈希函数构造；
【6 级】字符串哈希函数构造；
【6 级】哈希函数冲突的常见解决方法。

#2.4 算法

#2.4.1 复杂度分析

【6 级】空间复杂度分析；
【6 级】时间复杂度分析。

#2.4.2 基础算法

【6 级】分治算法。

#2.4.3 排序算法

【5 级】归并排序；
【5 级】快速排序；
【6 级】堆排序；
【6 级】树形选择排序（锦标赛排序）；
【5 级】桶排序；
【6 级】基数排序。

#2.4.4 字符串相关算法

【5 级】字符串匹配算法 —— KMP。

#2.4.5 搜索算法

【6 级】搜索的剪枝优化；
【6 级】记忆化搜索；
【7 级】启发式搜索；
【7 级】双向宽度优先搜索；
【7 级】迭代加深搜索；
【8 级】搜索对象的压缩存储。

#2.4.6 图论算法

【6 级】Prim 和 Kruskal 等求最小生成树算法；
【7 级】求次小生成树算法；
【6 级】Dijkstra、Bellman-Ford、SPFA 等求单源最短路算法；
【7 级】求单源次短路径算法；
【6 级】Floyd-Warshall 算法求任意两点间的最短路和传递闭包；
【6 级】有向无环图的拓扑排序算法；
【6 级】求欧拉道路和欧拉回路算法；
【6 级】二分图的构造及其判定算法；
【6 级】最近公共祖先；
【7 级】求强联通分量算法；
【7 级】强连通分量的缩点算法；
【7 级】求割点、割边算法。

#2.4.7 动态规则

【6 级】树型动态规划；
【7 级】状态压缩动态规划；
【8 级】动态规划的常用优化。

#2.5 数学

#2.5.1 高中数学

【5 级】代数；
【6 级】解析几何；
【6 级】立体几何。

#2.5.2 初等数论

【5 级】同余式；
【7 级】欧拉定理和欧拉函数；
【7 级】费马小定理；
【7 级】威尔逊定理；
【7 级】裴蜀定理；
【7 级】逆元；
【7 级】扩展欧几里得算法；
【7 级】孙子定理（即中国剩余定理）。

#2.5.3 组合数学

【6 级】可重集排列；
【6 级】可重集组合；
【6 级】错排列、圆排列；
【6 级】鸽巢原理；
【6 级】二项式定理；
【7 级】容斥原理；
【7 级】卡特兰数。

#2.5.4 线性代数

【5 级】矩阵概念；
【6 级】特殊矩阵：稀疏矩阵，三角矩阵，对称矩阵；
【6 级】矩阵的初等变换；
【6 级】矩阵的加减乘和转置运算；
【7 级】线性方程组的高斯消元法。

#三、NOI 级

#3.1 C++ 程序设计

【8 级】STL 模板：容器（containers）、迭代器（iterators）、空间配置器（allocators）、配接器（adapters）、算法（algorithms）、仿函数（functors）；
【8 级】面向对象的程序设计思想（OOP）。

#3.2 数据结构

#3.2.1 线性结构

【8 级】分块；
【8 级】块状链表。

#3.2.2 序列

【8 级】后缀数组；
【9 级】跳跃表；
【9 级】无根树的 Prüfer 序列。

#3.2.3 复杂树

【8 级】树链剖分；
【8 级】主席树；
【8 级】二维线段树；
【9 级】后缀树；
【9 级】树套树；
【9 级】K-D 树；
【10 级】最小树形图；
【10 级】动态树（LCT）。

#3.2.4 可合并堆

【8 级】左偏树；
【10 级】二项堆。

#3.2.5 可持久化数据结构

【9 级】可持久化数据结构。

#3.3 算法

#3.3.1 算法策略

【9 级】复杂分治思想；
【9 级】平衡规划思想；
【9 级】构造思想。

#3.3.2 字符串算法

【8 级】求最长回文串的 Manacher 算法；
【8 级】多模匹配算法 —— AC 自动机；
【9 级】求字符串前缀和后缀算法 —— 扩展 KMP；
【9 级】确定性有穷自动机 —— DFA 算法；
【10 级】非确定性有穷自动机 —— NFA 算法；
【10 级】后缀自动机。

#3.3.3 图论算法

【8 级】网络流算法；
【10 级】图的支配集、独立集与覆盖集；
【8 级】二分图的最大匹配——匈牙利算法；
【9 级】二分图的最佳匹配算法 —— KM 算法；
【10 级】一般图的匹配。

#3.3.4 动态规划

【9 级】复杂动态规划模型构建；
【9 级】复杂动态规划模型的优化。

#3.4 数学

#3.4.1 信息论基础

【10 级】熵、互信息、条件熵、相对熵的基本概念；
【10 级】信息复杂度的基本概念；
【10 级】描述复杂度的基本概念；
【10 级】通讯复杂度的基本概念。

#3.4.2 初等数论

【8 级】原根和指数；
【8 级】大步小步（Baby Step Giant Step，BSGS）算法；
【9 级】完全数；
【9 级】狄利克雷（Dirichlet）卷积；
【10 级】平方剩余；
【10 级】二次同余式；
【10 级】二次互反律。

#3.4.3 离散数学

【9 级】代数系统的基本概念；
【9 级】群的基本概念；
【9 级】置换群与循环群。

#3.4.4 组合数学

【9 级】母函数；
【9 级】莫比乌斯变换；
【9 级】Burnside 引理与 Pólya 原理；
【9 级】斯特林数。

#3.4.5 高等数学

【9 级】多项式函数微分；
【9 级】多项式函数积分；
【10 级】泰勒级数；
【10 级】快速傅里叶变换（Fast Fourier Transform，FFT）；
【10 级】卷积。

#3.4.6 线性代数

【9 级】矩阵的逆运算；
【9 级】行列式及其运算；
【9 级】线性相关与矩阵的逆。

#3.4.7 概率论

【8 级】概率相关概念；
【9 级】求概率的乘法公式、全概率公式、贝叶斯公式。

#3.4.8 博弈论

【9 级】零和博弈问题 —— Nim 博弈等；
【9 级】Sprague-Garundy（SG）函数概念及应用。

#3.4.9 运筹学

【10 级】线性规划之单纯形法。

#3.4.10 计算几何

【7 级】矢量及其运算；
【8 级】点、线、面之间的位置判断；
【8 级】常见图形的面积计算；
【8 级】二维凸包的求及其应用；
【9 级】半平面交。