NOI大纲
题单介绍
转载自[NOI官网](https://www.noi.cn/upload/resources/file/2023/03/15/1fa58eac9c412e01ce3c89c761058a43.pdf)
【X】表示难度系数
2.1 入门级
> 2.1.1 计算机基础与编程环境
> 1. 【1】计算机的基本构成（CPU、内存、I/O设 备等）
> 2. 【1】Windows、 Linux等操作系统的基本概念及其常见操作
> 3. 【1】计算机网络和Internet的基本概念
> 4. 【1】计算机的历史及其在现代社会中的常见应用
> 5. 【1】 NOI以及相关活动的历史
> 6. 【1】进制的基本概念与进制转换、字节与字
> 7. 【1】程序设计语言以及程序编译和运行的基本概念
> 8. 【1】使用图形界面新建、复制、删除、移动文件或目录
> 9. 【1】使用Windows系统下的集成开发环境（例如 Dev C++等）
> 10. 【1】使用Linux系统下的集成开发环境（例如 Code::Blocks等）
> 11. 【1】g++、gcc等常见编译器的基本使用
> 2.1.2 C++程序设计1
> 1. 程序基本概念
> > * 【1】标识符、关键字、常量、变量、字符串、 表达式的概念
> > * 【1】常量与变量的命名、定义及作用
> > * 【2】头文件与名字空间的定义与理解
> > * 【2】编辑、编译、解释、调试等概念理解
> 2. 基本数据类型
> > * 【1】整数型：int, long long
> > * 【1】实数型：float, double
> > * 【1】字符型：char
> > * 【1】布尔型：bool
> 3. 程序基本语句
> > * 【2】cin 语句,scanf 语句，cout语句，printf语句，赋值语句，复合语句
> > * 【2】if语句，switch语句，多层条件语句
> > * 【2】for语句，while语句，do while语句
> > * 【3】多层循环语句
> 4. 基本运算
> > * 【1】算数运算：加、减、乘、除、整除、求余
> > * 【1】关系运算：大于，大于等于，小于，小于等于，等于，不等于
> > * 【1】逻辑运算：与（&&）、或（||）、非（！）
> > * 【1】变量自增与自减运算
> > * 【1】三目运算
> > * 【3】位运算：与（&）、或（|）、非（~）、 异或（^）、左移、右移
> 5. 数学库常用函数
> > * 【3】绝对值函数，四舍五入函数，取上整函数， 取下整函数，常用三角函数，对数函数，指数 函数，平方根函数
> 6. 结构化程序设计
> > * 【1】顺序结构、分支结构和循环结构
> > * 【2】自顶向下、逐步求精的模块化程序设计
> > * 【2】流程图的概念及流程图描述
> 7. 数组
> > * 【1】数组定义，数组与数组下标的含义
> > * 【1】数组的读入与输出
> > * 【2】纯一维数组的综合运用
> > * 【3】纯二维数组与多维数组的综合应用
> 8. 字符串的处理
> > * 【2】字符数组与字符串的关系
> > * 【2】字符数组的综合应用
> > * 【2】string类定义、相关函数引用
> > * 【3】string类的综合应用
> 9. 函数与递归
> > * 【2】函数定义与调用，形参与实参
> > * 【3】传值参数与传引用参数
> > * 【2】常量与变量的作用范围
> > * 【2】递归函数的概念、定义与调用
> 10. 结构体类型
> > * 【3】结构体的定义及应用
> 11. 指针类型
> > * 【4】指针的概念及调用
> > * 【4】指针与数组
> > * 【4】字符指针与string类
> > * 【4】指向结构体的指针
> 12. 文件及基本读写
> > * 【2】文件的基本概念，文本文件的基本操作
> > * 【2】文本文件类型与二进制文件类型
> > * 【2】文件重定向、文件读写等操作
> 13. STL模板应用
> > * 【3】<algorithm> 中 sort 函数
> > * 【4】 栈（stack）、 队列（queue）、链表（list）、向量（vector）等容器
> 2.1.3 数据结构
> 1. 线性表
> > * 【3】链表：单链表、双向链表、循环链表
> > * 【3】栈
> > * 【3】队列
> 2. 简单树
> > * 【3】树的定义及其相关概念
> > * 【4】树的父亲表示法
> > * 【3】二叉树的定义及其基本性质
> > * 【4】二叉树的孩子表示法
> > * 【4】二叉树的遍历：前序、中序、后序遍历
> 3. 特殊树
> > * 【4】完全二叉树的定义与基本性质
> > * 【4】完全二叉树的数组表示法
> > * 【4】哈夫曼树的定义、构造及其遍历
> > * 【4】二叉树的定义、构造及其遍历
> 4. 简单图
> > * 【3】图的定义及其相关概念
> > * 【4】图的邻接矩阵存储
> > * 【4】图的邻接表存储
> 2.1.4 算法
> 1. 算法概念与描述
> > * 【1】算法概念
> > * 【2】算法描述：自然语言描述、流程图描述、伪代码描述
> 2. 入门算法
> > * 【1】枚举法
> > * 【1】模拟法
> 3. 基础算法
> > * 【3】贪心法
> > * 【3】递推法
> > * 【4】递归法
> > * 【4】二分法
> > * 【4】倍增法
> 4. 数值处理算法
> > * 【4】高精度的加法
> > * 【4】高精度的减法
> > * 【4】高精度的乘法
> > * 【4】求高精度整数除以单精度整数的商和余数
> 5. 排序算法
> > * 【3】排序的基本概念（稳定性等）
> > * 【3】冒泡排序
> > * 【3】简单选择排序
> > * 【3】简单插入排序
> 6. 图论算法
> > * 【4】图的深度优先遍历算法
> > * 【4】图的宽度优先遍历算法
> > * 【5】洪水填充算法（floodfill）
> 7. 动态规则
> > * 【4】动态规划的基本思路
> > * 【4】简单一维动态规划
> > * 【5】简单背包类型动态规划
> > * 【5】简单区间类型动态规划
> 2.1.5 数学
> 1. 数及其运算
> > * 【1】数的概念，算术运算（加、减、乘、除、求余）
> > * 【1】数的进制：二进制、八进制、十六进制和十进制及其转换
> > * 【2】编码：ASCII码，哈夫曼编码，格雷码
> 2. 初中数学
> > * 【1】初中代数
> > * 【1】初中平面几何
> 3. 初等数论
> > * 【3】整除、因数、倍数、指数、质数、合数、同余等概念
> > * 【3】唯一分解定理
> > * 【3】欧几里得算法（辗转相除法）
> > * 【4】埃氏筛法和线性筛法求素数
> 4. 组合数学
> > * 【2】加法原理
> > * 【2】乘法原理
> > * 【4】排列及计算公式
> > * 【4】组合及计算公式
> > * 【4】杨辉三角公式
2.2 提高级
> 2.2.1 计算机基础与编程环境
> 1. 【5】在Linux系统终端中使用mkdir、cp、rm、mv等命令新建、复制、删除、移动文件或目录
> 2. 【5】在Linux系统终端中使用cd、pwd、ls等命令更改、显示目录路径和查看目录中的文件
> 3. 【5】在Linux系统下使用Gedit、Vim或Emacs等文本编辑工具编写代码
> 4. 【5】熟悉g++、gcc等编译器以及优化、数学库等常见编译选项
> 5. 【5】在Linux系统终端中运行程序，并使用time命令查看程序用时（区分real time、sys time和user time）
> 6. 【5】了解调式工具gdb及其break、display、continue、step等命令
> 2.2.1 C++程序设计
> 1. 类（class）
> > * 【6】类的概念及简单应用
> > * 【6】成员函数和运算符重载
> 2. STL模板
> > * 【5】集合（set）
> > * 【5】列表（list），双端队列（deque），优先队列（priority_queue）
> > * 【5】多重集合（multiset）
> > * 【5】映射（map），多重映射（multimap）
> > * 【5】对（pair），元组（tuple）
> 2.2.2 数据结构
> 1. 线性结构
> > * 【5】双端栈
> > * 【5】双端队列
> > * 【5】有序队列
> > * 【6】优先队列
> > * 【6】倍增表（ST表）
> 2. 集合与森林
> > * 【6】等价类
> > * 【6】并查集
> > * 【6】树与二叉树的转化——孩子兄弟表示法
> 3. 特殊树
> > * 【6】线段树与树状数组
> > * 【6】字典树（trie树）
> > * 【7】笛卡尔树
> > * 【8】二叉平衡树AVL、treap、splay等
> > * 【8】基环树
> 4. 常见图
> > * 【5】稀疏图
> > * 【6】偶图（二分图）
> > * 【6】欧拉图
> > * 【6】有向无环图
> > * 【7】连通图与强连通图
> > * 【7】重连通图
> 5. 哈希表
> > * 【5】数值哈希函数构造
> > * 【6】排列哈希函数构造
> > * 【6】字符串哈希函数构造
> > * 【6】哈希函数冲突的常见解决方法
> 2.2.3 算法
> 1. 复杂度分析
> > * 【6】空间复杂度分析
> > * 【6】时间复杂度分析
> 2. 基础算法
> > * 【6】分治算法
> 3. 排序算法
> > * 【5】归并排序
> > * 【5】快速排序
> > * 【6】堆排序
> > * 【6】树形选择排序（锦标赛排序）
> > * 【5】桶排序
> > * 【6】基数排序
> 4. 字符串相关算法
> > * 【5】字符串匹配算法——KMP
> 5. 搜索算法
> > * 【6】搜索的剪枝优化
> > * 【6】记忆化搜索
> > * 【7】启发式搜索
> > * 【7】双向宽度优先搜索
> > * 【7】迭代加深搜索
> > * 【8】搜索对象的压缩存储
> 6. 图论算法
> > * 【6】Prim和kruskal等求最小生成树算法
> > * 【7】求次小生成树算法
> > * 【6】Dijkstra、bellman_ford、SPFA等求单源最短路算法
> > * 【7】求单源次短路径算法
> > * 【6】Floyd-Warshall算法求任意两点间的最短路和传递闭包
> > * 【6】有向无环图的拓扑排序算法
> > * 【6】求欧拉道路和欧拉回路算法
> > * 【6】二分图的构造及其判定算法
> > * 【6】最近公共祖先
> > * 【7】求强联通分量算法
> > * 【7】强连通分量的缩点算法
> > * 【7】求割点、割边算法
> 7. 动态规则
> > * 【6】树型动态规划
> > * 【7】状态压缩动态规划
> > * 【8】动态规划的常用优化
> 2.2.4 数学
> 1. 高中数学
> > * 【5】代数
> > * 【6】解析几何
> > * 【6】立体几何
> 2. 初等数论
> > * 【5】同余式
> > * 【7】欧拉定理和欧拉函数
> > * 【7】费马小定理
> > * 【7】威尔逊定理
> > * 【7】裴蜀定理
> > * 【7】逆元
> > * 【7】扩展欧几里得算法
> > * 【7】孙子定理（即中国剩余定理）
> 3. 组合数学
> > * 【6】可重集排列
> > * 【6】可重集组合
> > * 【6】错排列、圆排列
> > * 【6】鸽巢原理
> > * 【6】二项式定理
> > * 【7】容斥原理
> > * 【7】卡特兰数
> 4. 线性代数
> > * 【5】矩阵概念
> > * 【6】特殊矩阵：稀疏矩阵，三角矩阵，对称矩阵
> > * 【6】矩阵的初等变换
> > * 【6】矩阵的加减乘和转置运算
> > * 【7】线性方程组的高斯消元法
2.3 NOI级
> 2.3.1 C++程序设计3
> 1. 【8】STL模板：容器（containers）、迭代器（iterators）、空间配置器（allocators）、配接器（adapters）、算法（algorithms）、仿函数（functors）
> 2. 【8】面向对象的程序设计思想（OOP）
> 2.3.2 数据结构
> 1. 线性结构
> > * 【8】分块
> > * 【8】块状链表
> 2. 序列
> > * 【8】后缀数组
> > * 【9】跳跃表
> > * 【9】无根树的Prüfer序列
> 3. 复杂树
> > * 【8】树链剖分
> > * 【8】主席树
> > * 【8】二位线段树
> > * 【9】后缀树
> > * 【9】树套树
> > * 【9】k-d 树
> > * 【10】最小树形图
> > * 【10】动态树（LCT）
> 4. 可合并堆
> > * 【8】左偏树
> > * 【10】二项堆
> 5. 【9】可持久化数据结构
> 2.3.3 算法
> 1. 算法策略
> > * 【9】复杂分治思想
> > * 【9】平衡规划思想
> > * 【9】构造思想
> 2. 字符串算法
> > * 【8】求最长回文串的Manacher算法
> > * 【8】多模匹配算法——AC自动机
> > * 【9】求字符串前缀和后缀算法——扩展KMP
> > * 【9】确定性有穷自动机——DFA算法
> > * 【10】非确定性有穷自动机——NFA算法
> > * 【10】后缀自动机
> 3. 图论算法
> > * 【8】网络流算法
> > * 【10】图的支配集、独立集与覆盖集
> > * 【8】二分图的最大匹配——匈牙利算法
> > * 【9】二分图的最佳匹配算法——KM算法
> > * 【10】一般图的匹配
> 4. 动态规划
> > * 【9】复杂动态规划模型构建
> > * 【9】复杂动态规划模型的优化
> 2.2.4 数学
> 1. 信息论基础
> > * 【10】熵、互信息、条件熵、相对熵的基本概念
> > * 【10】信息复杂度的基本概念
> > * 【10】描述复杂度的基本概念
> > * 【10】通讯复杂度的基本概念
> 2. 初等数论
> > * 【8】原根和指数
> > * 【8】大步小步（Baby Step Giant Step，BSGS）算法
> > * 【9】完全数
> > * 【9】狄利克雷（Dirichlet）卷积
> > * 【10】平方剩余
> > * 【10】二次同余式
> > * 【10】二次互反律
> 3. 离散数学
> > * 【9】代数系统的基本概念
> > * 【9】群的基本概念
> > * 【9】置换群与循环群
> 4. 组合数学
> > * 【9】母函数
> > * 【9】莫比乌斯变换
> > * 【9】Burnside引理与Pólya原理
> > * 【9】斯特林数
> 5. 高等数学
> > * 【9】多项式函数微分
> > * 【9】多项式函数积分
> > * 【10】泰勒级数
> > * 【10】快速傅里叶变换（Fast Fourier Transform，FFT）
> > * 【10】卷积
> 6. 线性代数
> > * 【9】矩阵的逆运算
> > * 【9】行列式及其运算
> > * 【9】线性相关与矩阵的逆
> 7. 概率论
> > * 【8】概率相关概念
> > * 【9】求概率的乘法公式、全概率公式、贝叶斯公式
> 8. 博弈论
> > * 【9】零和博弈问题——Nim博弈等
> > * 【9】Sprague-Garundy（SG）函数概念及应用
> 9. 运筹学
> > * 【10】线性规划之单纯形法
> 10. 计算几何
> > * 【7】矢量及其运算
> > * 【8】点、线、面之间的位置判断
> > * 【8】常见图形的面积计算
> > * 【8】二维凸包的求及其应用
> > * 【9】半平面交