跳到主要内容

NOI 大纲

全国青少年信息学奥林匹克系列竞赛大纲。

参考资料

说明

各级知识点的 难度系数 范围：

入门级： $1\sim 5$
提高级： $5\sim 8$
NOI 级： $7\sim 10$

以下大纲内容为 2025 年修订版。

1. 入门级

1.1 基础知识与编程环境

【 1 】计算机的基本构成（CPU、内存、I/O 设备等）
【 1 】Windows、Linux 等操作系统的基本概念及其常见操作
【 1 】计算机网络和 Internet 的基本概念
【 1 】计算机的历史和常见用途
【 1 】NOI 以及相关活动的历史
【 1 】NOI 以及相关活动的规则
【 1 】位、字节与字
【 1 】程序设计语言以及程序编译和运行的基本概念
【 1 】使用图形界面新建、复制、删除、移动文件或目录
【 1 】使用 Windows 系统下的集成开发环境（例如 Dev-C++ 等）
【 1 】使用 Linux 系统下的集成开发环境（例如 Code::Blocks 等）
【 1 】常用编译命令 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 】三目运算
【 2 】位运算：与（&）、或（|）、非（~）、异或（^）、左移（<<）、右移（>>）

1.2.5 数学库常用函数

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

1.2.6 结构化程序设计

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

1.2.7 数组

【 1 】数组与数组下标
【 1 】数组的读入与输出
【 3 】二维数组与多维数组

1.2.8 字符串的处理

【 2 】字符数组与相关函数
【 2 】string 类与相关函数

1.2.9 函数与递归

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

1.2.10 结构体与联合体

【 3 】结构体
【 3 】联合体

1.2.11 指针与引用

【 4 】指针
【 4 】基于指针的数组访问
【 4 】字符指针
【 4 】指向结构体的指针
【 5 】引用

1.2.12 文件及基本读写

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

1.2.13 STL 模板

【 3 】算法模板库中的函数：min、max、swap、sort
【 4 】栈（stack）、队列（queue）、链表（list）、向量（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 算法策略

【 3 】前缀和
【 4 】差分

1.4.5 数值处理算法

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

1.4.6 排序算法

【 3 】排序的基本概念
【 3 】冒泡排序
【 3 】选择排序
【 3 】插入排序
【 3 】计数排序

1.4.7 搜索算法

【 5 】深度优先搜索
【 5 】广度优先搜索

1.4.8 图论算法

【 4 】深度优先遍历
【 4 】广度优先遍历
【 5 】泛洪算法（flood fill）

1.4.9 动态规划

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

1.5 数学与其他

1.5.1 数及其运算

【 1 】自然数、整数、有理数、实数及其算术运算（加、减、乘、除）
【 1 】进制与进制转换：二进制、八进制、十进制、十六进制

1.5.2 初等数学

【 1 】代数（初中部分）
【 1 】几何（初中部分）

1.5.3 初等数论

【 3 】整除、因数、倍数、指数、质（素）数、合数
【 3 】取整
【 3 】模运算与取余
【 3 】整数唯一分解定理
【 3 】辗转相除法（欧几里得算法）
【 4 】素数筛法：埃氏筛法与线性筛法

1.5.4 离散与组合数学

【 2 】集合
【 2 】加法原理
【 2 】乘法原理
【 4 】排列
【 4 】组合
【 4 】杨辉三角

1.5.5 其他

【 2 】ASCII 码

2. 提高级

2.1 基础知识与编程环境

【 5 】Linux 系统终端中常用的文件与目录操作命令
【 5 】Linux 系统下常见文本编辑工具的使用
【 5 】常用编译命令 g++ 与相关编译选项
【 5 】在 Linux 系统终端中运行程序，使用 time 命令查看程序用时
【 5 】调试工具 GDB 的使用

2.2 C++ 程序设计

2.2.1 类（`class`）

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

2.2.2 STL 模板

【 5 】容器（container）和迭代器（iterator）
【 5 】对（pair）、元组（tuple）
【 5 】集合（set）、多重集合（multiset）
【 5 】双端队列（deque）、优先队列（priority_queue）
【 5 】映射（map）、多重映射（multimap）
【 5 】位集合（bitset）
【 5 】算法模板库中的常用函数

2.3 数据结构

2.3.1 线性结构

【 5 】双端栈
【 5 】双端队列
【 5 】单调队列
【 6 】优先队列
【 6 】ST 表（Sparse Table）

2.3.2 集合与森林

【 6 】并查集
【 6 】树的孩子兄弟表示法

2.3.3 特殊树

【 6 】二叉堆
【 6 】树状数组
【 6 】线段树
【 6 】字典树（Trie 树）
【 7 】笛卡尔树
【 8 】平衡树：AVL、treap、splay 等

2.3.4 常见图

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

2.3.5 哈希表

【 5 】数值哈希函数构造
【 6 】字符串哈希函数构造
【 6 】哈希冲突的常用处理方法

2.4 算法

2.4.1 复杂度分析

【 6 】时间复杂度分析
【 6 】空间复杂度分析

2.4.2 算法策略

【 6 】离散化
【 7 】扫描线

2.4.3 基础算法

【 6 】分治算法

2.4.4 排序算法

【 5 】归并排序
【 5 】快速排序
【 6 】堆排序
【 5 】桶排序
【 6 】基数排序

2.4.5 字符串相关算法

【 5 】字符串匹配：KMP 算法
【 7 】Manacher 算法

2.4.6 搜索算法

【 6 】搜索的剪枝优化
【 6 】记忆化搜索
【 7 】启发式搜索
【 7 】双向广度优先搜索
【 7 】迭代加深搜索

2.4.7 图论算法

【 6 】最小生成树：Prim 和 Kruskal 等算法
【 6 】单源最短路：Bellman–Ford、Dijkstra、SPFA 等算法
【 7 】单源次短路
【 6 】Floyd–Warshall 算法
【 6 】有向无环图的拓扑排序
【 6 】欧拉道路和欧拉回路
【 6 】二分图的判定
【 7 】强连通分量
【 7 】割点、割边
【 6 】树的重心、直径、DFS 序与欧拉序
【 6 】树上差分、子树和与倍增
【 6 】最近公共祖先

2.4.8 动态规划

【 6 】多维动态规划
【 6 】树型动态规划
【 7 】状态压缩动态规划
【 8 】动态规划的常用优化

2.5 数学与其他

2.5.1 初等数学

【 5 】代数（高中部分）
【 6 】几何（高中部分）

2.5.2 初等数论

【 5 】同余式
【 7 】欧拉定理和欧拉函数
【 7 】费马小定理
【 7 】威尔逊定理
【 7 】裴蜀定理
【 7 】模运算意义下的逆元
【 7 】扩展欧几里得算法
【 7 】中国剩余定理

2.5.3 离散与组合数学

【 6 】多重集合
【 6 】等价关系与等价类
【 6 】多重集上的排列
【 6 】多重集上的组合
【 6 】错排列、圆排列
【 6 】鸽巢原理
【 6 】二项式定理
【 7 】容斥原理
【 7 】卡特兰（Catalan）数

2.5.4 线性代数

【 5 】向量与矩阵的概念
【 6 】向量的运算
【 6 】矩阵的初等变换
【 6 】矩阵的运算：加法、减法、乘法与转置
【 6 】特殊矩阵的概念：单位阵、三角阵、对称阵和稀疏矩阵
【 7 】高斯消元法

3. NOI 级

3.1 C++ 程序设计

【 8 】面向对象的程序设计思想（OOP）

3.2 数据结构

3.2.1 线性结构

【 8 】块状链表

3.2.2 复杂树

【 8 】树链剖分
【 10 】动态树：LCT
【 9 】树套树
【 9 】k-d 树
【 8 】虚树

3.2.3 可合并堆

【 8 】左偏树
【 10 】二项堆

3.2.4 可持久化数据结构

【 8 】可持久化线段树
【 9 】其他可持久化数据结构

3.3 算法

3.3.1 算法策略

【 8 】分块
【 8 】离线处理思想
【 9 】复杂分治思想
【 9 】平衡规划思想
【 9 】构造思想

3.3.2 字符串算法

【 8 】扩展 KMP 算法
【 8 】有穷自动机的概念
【 8 】AC 自动机
【 8 】后缀数组
【 9 】后缀树
【 10 】后缀自动机

3.3.3 图论算法

【 8 】基环树
【 10 】最小树形图
【 8 】2-SAT
【 8 】网络流
【 10 】图的支配集、独立集与覆盖集
【 8 】匈牙利算法
【 10 】KM 算法
【 10 】一般图的匹配

3.3.4 动态规划

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

3.4 数学与其他

3.4.1 初等数论

【 8 】原根和指数
【 8 】大步小步（Baby Step Giant Step，BSGS）算法
【 9 】狄利克雷（Dirichlet）卷积
【 10 】二次剩余
【 10 】二次同余式

3.4.2 离散与组合数学

【 9 】群及其基本性质
【 9 】置换群与循环群
【 9 】母函数
【 9 】莫比乌斯反演
【 9 】Burnside 引理与 Pólya 定理
【 9 】斯特林（Stirling）数
【 9 】无根树的 Prüfer 序列

3.4.3 线性代数

【 9 】逆矩阵
【 9 】行列式
【 9 】向量空间与线性相关
【 9 】基与线性基

3.4.4 高等数学

【 8 】多项式函数的微分
【 8 】多项式函数的积分
【 10 】泰勒（Taylor）级数
【 10 】快速傅里叶变换

3.4.5 概率论

【 8 】概率的基本概念
【 9 】离散随机变量的期望与方差
【 9 】条件概率
【 9 】贝叶斯公式

3.4.6 博弈论

【 9 】尼姆（Nim）博弈
【 9 】SG 函数

3.4.7 最优化

【 10 】单纯形法

3.4.8 计算几何

【 8 】点、线、面之间位置关系的判定
【 8 】一般图形面积的计算
【 8 】二维凸包
【 9 】半平面交

3.4.9 信息论

【 10 】熵、互信息、条件熵、相对熵

3.4.10 其他

【 10 】信息复杂度的概念
【 10 】描述复杂度的概念
【 10 】通讯复杂度的概念

平衡性调整

2025 年修订版

《NOI 大纲》2025 年修订版 相比于 2023 年修订版 的平衡性调整。

入门级

变更 【 1 】g++、gcc 等常见编译器的基本使用 $\to$ 【 1 】常用编译命令 g++ 的基本使用
变更 「指针类型」章节 $\to$ 「指针与引用」章节
新增 【 5 】引用
新增 「算法策略」章节
新增 【 3 】前缀和
新增 【 4 】差分
变更 【 3 】模运算与同余 $\to$ 【 3 】模运算与取余
移除 ~~【 2 】格雷码~~

提高级

变更 【 5 】g++、gcc 等编译器与相关编译选项 $\to$ 【 5 】常用编译命令 g++ 与相关编译选项
新增 【 5 】位集合（bitset）
新增 【 7 】扫描线
变更 【 8 】Manacher 算法 $\to$ 【 7 】Manacher 算法（NOI 级 $\to$ 提高级）
移除 ~~【 7 】次小生成树~~
新增 【 6 】多维动态规划
变更 【 6 】等价类 $\to$ 【 6 】等价关系与等价类

NOI 级

移除 ~~「序列」章节~~
移除 ~~【 9 】跳跃表~~
移除 ~~【 8 】二维线段树~~
变更 【 10 】虚树 $\to$ 【 8 】虚树
变更 【 9 】扩展 KMP 算法 $\to$ 【 8 】扩展 KMP 算法
变更 【 8 】有穷自动机 $\to$ 【 8 】有穷自动机的概念
变更 【 9 】KM 算法 $\to$ 【 10 】KM 算法
新增 【 9 】基与线性基
变更 【 10 】随机变量的期望与方差 $\to$ 【 9 】离散随机变量的期望与方差

参考资料
说明
1. 入门级
2. 提高级
3. NOI 级
平衡性调整
- 2025 年修订版