Skip to content

NOI 大纲

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

本文在 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 级】整数型:intlong long
  • 【1 级】实数型:floatdouble
  • 【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 系统终端中使用 mkdircprmmv 等命令新建、复制、删除、移动文件或目录;
  • 【5 级】在 Linux 系统终端中使用 cdpwdls 等命令更改、显示目录路径和查看目录中的文件;
  • 【5 级】在 Linux 系统下使用 GeditVimEmacs 等文本编辑工具编写代码;
  • 【5 级】熟悉 gcc、g++ 等编译器以及优化、数学库等常见编译选项;
  • 【5 级】在 Linux 系统终端中运行程序,并使用 time 命令查看程序用时(区分 real timesys timeuser time);
  • 【5 级】了解调试工具 gdb 及其 breakdisplaycontinuestep 等命令。

#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 级】半平面交。