NOI 竞赛大纲

参考资料

难度系数

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

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++、gcc 等常见编译器的基本使用

1.2 C++ 程序设计

程序基本概念
- 【 $1$ 】标识符、关键字、常量、变量、字符串、表达式的概念
- 【 $1$ 】常量与变量的命名、定义及作用
- 【 $2$ 】头文件与名字空间的概念
- 【 $2$ 】编辑、编译、解释、调试的概念
基本数据类型
- 【 $1$ 】整数型：int、long long
- 【 $1$ 】实数型：float、double
- 【 $1$ 】字符型：char
- 【 $1$ 】布尔型：bool
程序基本语句
- 【 $2$ 】cin 语句、scanf 语句、cout 语句、printf 语句、赋值语句、复合语句
- 【 $2$ 】if 语句、switch 语句、多层条件语句
- 【 $2$ 】for 语句、while 语句、do while 语句
- 【 $3$ 】多层循环语句
基本运算
- 【 $1$ 】算术运算：加、减、乘、除、整除、求余
- 【 $1$ 】关系运算：大于、大于等于、小于、小于等于、等于、不等于
- 【 $1$ 】逻辑运算：与（&&）、或（||）、非（!）
- 【 $1$ 】变量自增与自减运算
- 【 $1$ 】三目运算
- 【 $2$ 】位运算：与（&）、或（|）、非（~）、异或（^）、左移（<<）、右移（>>）
数学库常用函数
- 【 $3$ 】绝对值函数、四舍五入函数、下取整函数、上取整函数、平方根函数、常用三角函数、对数函数、指数函数
结构化程序设计
- 【 $1$ 】顺序结构、分支结构和循环结构
- 【 $2$ 】自顶向下、逐步求精的模块化程序设计
- 【 $2$ 】流程图的概念及流程图描述
数组
- 【 $1$ 】数组与数组下标
- 【 $1$ 】数组的读入与输出
- 【 $3$ 】二维数组与多维数组
字符串的处理
- 【 $2$ 】字符数组与相关函数
- 【 $2$ 】string 类与相关函数
函数与递归
- 【 $2$ 】函数定义与调用、形参与实参
- 【 $3$ 】传值参数与传引用参数
- 【 $2$ 】常量与变量的作用范围
结构体与联合体
- 【 $3$ 】结构体
- 【 $3$ 】联合体
指针类型
- 【 $4$ 】指针
- 【 $4$ 】基于指针的数组访问
- 【 $4$ 】字符指针
- 【 $4$ 】指向结构体的指针
文件及基本读写
- 【 $2$ 】文件的基本概念、文本文件的基本操作
- 【 $2$ 】文本文件类型与二进制文件类型
- 【 $2$ 】文件重定向、文件读写等操作
STL 模板
- 【 $3$ 】算法模板库中的函数：min、max、swap、sort
- 【 $4$ 】栈（stack）、队列（queue）、链表（list）、向量（vector）等容器

1.3 数据结构

线性结构
- 【 $3$ 】链表：单链表、双向链表、循环链表
- 【 $3$ 】栈
- 【 $3$ 】队列
简单树
- 【 $3$ 】树的定义与相关概念
- 【 $4$ 】树的表示与存储
- 【 $3$ 】二叉树的定义与基本性质
- 【 $4$ 】二叉树的表示与存储
- 【 $4$ 】二叉树的遍历：前序、中序、后序
特殊树
- 【 $4$ 】完全二叉树的定义与基本性质
- 【 $4$ 】完全二叉树的数组表示法
- 【 $4$ 】哈夫曼树的定义和构造、哈夫曼编码
- 【 $4$ 】二叉搜索树的定义和构造
简单图
- 【 $3$ 】图的定义与相关概念
- 【 $4$ 】图的表示与存储：邻接矩阵
- 【 $4$ 】图的表示与存储：邻接表

1.4 算法

算法概念与描述
- 【 $1$ 】算法概念
- 【 $2$ 】算法描述：自然语言描述、流程图描述、伪代码描述
入门算法
- 【 $1$ 】枚举法
- 【 $1$ 】模拟法
基础算法
- 【 $3$ 】贪心法
- 【 $3$ 】递推法
- 【 $4$ 】递归法
- 【 $4$ 】二分法
- 【 $4$ 】倍增法
数值处理算法
- 【 $4$ 】高精度的加法
- 【 $4$ 】高精度的减法
- 【 $4$ 】高精度的乘法
- 【 $4$ 】高精度整数除以单精度整数的商和余数
排序算法
- 【 $3$ 】排序的基本概念
- 【 $3$ 】冒泡排序
- 【 $3$ 】选择排序
- 【 $3$ 】插入排序
- 【 $3$ 】计数排序
搜索算法
- 【 $5$ 】深度优先搜索
- 【 $5$ 】广度优先搜索
图论算法
- 【 $4$ 】深度优先遍历
- 【 $4$ 】广度优先遍历
- 【 $5$ 】泛洪算法（flood fill）
动态规划
- 【 $4$ 】动态规划的基本思路
- 【 $4$ 】简单一维动态规划
- 【 $5$ 】简单背包类型动态规划
- 【 $5$ 】简单区间类型动态规划

1.5 数学与其他

数及其运算
- 【 $1$ 】自然数、整数、有理数、实数及其算术运算（加、减、乘、除）
- 【 $1$ 】进制与进制转换：二进制、八进制、十进制、十六进制
初等数学
- 【 $1$ 】代数（初中部分）
- 【 $1$ 】几何（初中部分）
初等数论
- 【 $3$ 】整除、因数、倍数、指数、质（素）数、合数
- 【 $3$ 】取整
- 【 $3$ 】模运算与同余
- 【 $3$ 】整数唯一分解定理
- 【 $3$ 】辗转相除法（欧几里得算法）
- 【 $4$ 】素数筛法：埃氏筛法与线性筛法
离散与组合数学
- 【 $2$ 】集合
- 【 $2$ 】加法原理
- 【 $2$ 】乘法原理
- 【 $4$ 】排列
- 【 $4$ 】组合
- 【 $4$ 】杨辉三角
其他
- 【 $2$ 】ASCII 码
- 【 $2$ 】格雷码

2. 题高级

2.1 基础知识与编程环境

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

2.2 C++ 程序设计

类（class）
- 【 6 】类的概念及简单应用
- 【 6 】成员函数和运算符重载
STL 模板
- 【 5 】容器（container）和迭代器（iterator）
- 【 5 】对（pair）、元组（tuple）
- 【 5 】集合（set）、多重集合（multiset）
- 【 5 】双端队列（deque）、优先队列（priority_queue）
- 【 5 】映射（map）、多重映射（multimap）
- 【 5 】算法模板库中的常用函数

2.3 数据结构

线性结构
- 【 $5$ 】双端栈
- 【 $5$ 】双端队列
- 【 $5$ 】单调队列
- 【 $6$ 】优先队列
- 【 $6$ 】ST 表（Sparse Table）
集合与森林
- 【 $6$ 】并查集
- 【 $6$ 】树的孩子兄弟表示法
特殊树
- 【 $6$ 】二叉堆
- 【 $6$ 】树状数组
- 【 $6$ 】线段树
- 【 $6$ 】字典树（Trie 树）
- 【 $7$ 】笛卡尔树
- 【 $8$ 】平衡树：AVL、treap、splay 等
常见图
- 【 $5$ 】稀疏图
- 【 $6$ 】偶图（二分图）
- 【 $6$ 】欧拉图
- 【 $6$ 】有向无环图
- 【 $7$ 】连通图与强连通图
- 【 $7$ 】双连通图
哈希表
- 【 $5$ 】数值哈希函数构造
- 【 $6$ 】字符串哈希函数构造
- 【 $6$ 】哈希冲突的常用处理方法

2.4 算法

复杂度分析
- 【 $6$ 】时间复杂度分析
- 【 $6$ 】空间复杂度分析
算法策略
- 【 $6$ 】离散化
基础算法
- 【 $6$ 】分治算法
排序算法
- 【 $5$ 】归并排序
- 【 $5$ 】快速排序
- 【 $6$ 】堆排序
- 【 $5$ 】桶排序
- 【 $6$ 】基数排序
字符串相关算法
- 【 $5$ 】字符串匹配：KMP 算法
搜索算法
- 【 $6$ 】搜索的剪枝优化
- 【 $6$ 】记忆化搜索
- 【 $7$ 】启发式搜索
- 【 $7$ 】双向广度优先搜索
- 【 $7$ 】迭代加深搜索
图论算法
- 【 $6$ 】最小生成树：Prim 和 Kruskal 等算法
- 【 $7$ 】次小生成树
- 【 $6$ 】单源最短路：Bellman-Ford、Dijkstra、SPFA 等算法
- 【 $7$ 】单源次短路
- 【 $6$ 】Floyd-Warshall 算法
- 【 $6$ 】有向无环图的拓扑排序
- 【 $6$ 】欧拉道路和欧拉回路
- 【 $6$ 】二分图的判定
- 【 $7$ 】强连通分量
- 【 $7$ 】割点、割边
- 【 $6$ 】树的重心、直径、DFS 序与欧拉序
- 【 $6$ 】树上差分、子树和与倍增
- 【 $6$ 】最近公共祖先
动态规划
- 【 $6$ 】树型动态规划
- 【 $7$ 】状态压缩动态规划
- 【 $8$ 】动态规划的常用优化

2.5 数学与其他

初等数学
- 【 $5$ 】代数（高中部分）
- 【 $6$ 】几何（高中部分）
初等数论
- 【 $5$ 】同余式
- 【 $7$ 】欧拉定理和欧拉函数
- 【 $7$ 】费马小定理
- 【 $7$ 】威尔逊定理
- 【 $7$ 】裴蜀定理
- 【 $7$ 】模运算意义下的逆元
- 【 $7$ 】扩展欧几里得算法
- 【 $7$ 】中国剩余定理
离散与组合数学
- 【 $6$ 】多重集合
- 【 $6$ 】等价类
- 【 $6$ 】多重集上的排列
- 【 $6$ 】多重集上的组合
- 【 $6$ 】错排列、圆排列
- 【 $6$ 】鸽巢原理
- 【 $6$ 】二项式定理
- 【 $7$ 】容斥原理
- 【 $7$ 】卡特兰（Catalan）数
线性代数
- 【 $5$ 】向量与矩阵的概念
- 【 $6$ 】向量的运算
- 【 $6$ 】矩阵的初等变换
- 【 $6$ 】矩阵的运算：加法、减法、乘法与转置
- 【 $6$ 】特殊矩阵的概念：单位阵、三角阵、对称阵和稀疏矩阵
- 【 $7$ 】高斯消元法

3. NOI 级

3.1 C++ 程序设计

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

3.2 数据结构

线性结构
- 【 $8$ 】块状链表
序列
- 【 $9$ 】跳跃表
复杂树
- 【 $8$ 】树链剖分
- 【 $10$ 】动态树：LCT
- 【 $8$ 】二维线段树
- 【 $9$ 】树套树
- 【 $9$ 】k-d 树
- 【 $10$ 】虚树
可合并堆
- 【 $8$ 】左偏树
- 【 $10$ 】二项堆
可持久化数据结构
- 【 $8$ 】可持久化线段树
- 【 $9$ 】其他可持久化数据结构

3.3 算法

算法策略
- 【 $8$ 】分块
- 【 $8$ 】离线处理思想
- 【 $9$ 】复杂分治思想
- 【 $9$ 】平衡规划思想
- 【 $9$ 】构造思想
字符串算法
- 【 $8$ 】Manacher 算法
- 【 $9$ 】扩展 KMP 算法
- 【 $8$ 】有穷自动机
- 【 $8$ 】AC 自动机
- 【 $8$ 】后缀数组
- 【 $9$ 】后缀树
- 【 $10$ 】后缀自动机
图论算法
- 【 $8$ 】基环树
- 【 $10$ 】最小树形图
- 【 $8$ 】2-SAT
- 【 $8$ 】网络流
- 【 $10$ 】图的支配集、独立集与覆盖集
- 【 $8$ 】匈牙利算法
- 【 $9$ 】KM 算法
- 【 $10$ 】一般图的匹配
动态规划
- 【 $9$ 】复杂动态规划模型的构建
- 【 $9$ 】复杂动态规划模型的优化

3.4 数学与其他

初等数论
- 【 $8$ 】原根和指数
- 【 $8$ 】大步小步（Baby Step Giant Step，BSGS）算法
- 【 $9$ 】狄利克雷（Dirichlet）卷积
- 【 $10$ 】二次剩余
- 【 $10$ 】二次同余式
离散与组合数学
- 【 $9$ 】群及其基本性质
- 【 $9$ 】置换群与循环群
- 【 $9$ 】母函数
- 【 $9$ 】莫比乌斯反演
- 【 $9$ 】Burnside 引理与 Pólya 定理
- 【 $9$ 】斯特林（Stirling）数
- 【 $9$ 】无根树的 Prüfer 序列
线性代数
- 【 $9$ 】逆矩阵
- 【 $9$ 】行列式
- 【 $9$ 】向量空间与线性相关
高等数学
- 【 $8$ 】多项式函数的微分
- 【 $8$ 】多项式函数的积分
- 【 $10$ 】泰勒（Taylor）级数
- 【 $10$ 】快速傅里叶变换
概率论
- 【 $8$ 】概率的基本概念
- 【 $10$ 】随机变量的期望与方差
- 【 $9$ 】条件概率
- 【 $9$ 】贝叶斯公式
博弈论
- 【 $9$ 】尼姆（Nim）博弈
- 【 $9$ 】SG 函数
最优化
- 【 $10$ 】单纯形法
计算几何
- 【 $8$ 】点、线、面之间位置关系的判定
- 【 $8$ 】一般图形面积的计算
- 【 $8$ 】二维凸包
- 【 $9$ 】半平面交
信息论
- 【 $10$ 】熵、互信息、条件熵、相对熵
其他
- 【 $10$ 】信息复杂度的概念
- 【 $10$ 】描述复杂度的概念
- 【 $10$ 】通讯复杂度的概念

参考资料​

难度系数​

1. 入门级​

1.1 基础知识与编程环境​

1.2 C++ 程序设计​

1.3 数据结构​

1.4 算法​

1.5 数学与其他​

2. 题高级​

2.1 基础知识与编程环境​

2.2 C++ 程序设计​

2.3 数据结构​

2.4 算法​

2.5 数学与其他​

3. NOI 级​

3.1 C++ 程序设计​

3.2 数据结构​

3.3 算法​

3.4 数学与其他​

参考资料

难度系数

1. 入门级

1.1 基础知识与编程环境

1.2 C++ 程序设计

1.3 数据结构

1.4 算法

1.5 数学与其他

2. 题高级

2.1 基础知识与编程环境

2.2 C++ 程序设计

2.3 数据结构

2.4 算法

2.5 数学与其他

3. NOI 级

3.1 C++ 程序设计

3.2 数据结构

3.3 算法

3.4 数学与其他