lym 版 NOI 大纲文字版

---
# 写在前面

1. 为了大家方便更改、使用到任务计划中、魔改、保存等，准备了[\<云剪贴板版本\>](https://www.luogu.com.cn/paste/zh8hedle)。
2. 可以搬运，但需著名原作者 @[lym12](https://www.luogu.com.cn/user/782768)。
3. 本文目前为**第一版**。
4. 更新日志：
   - $\texttt{DATE: \textcolor{red}{2024/07/26}}$ 第一版发布，最基础。
5. **TODO：**
   - 添加学习链接（OI Wiki）
   - 添加例题
   - 规范化英文、中文、字符连写格式
   - 增加 $\KaTeX$
   - pdf 版本
6. 有错误请指出，私信、微信、QQ、留言皆可。
7. 感谢贡献者：@[lym12](https://www.luogu.com.cn/user/782768)。

---

# NOI大纲
## 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】常量与变量的命名、定义及作用
- 【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】逻辑运算:与(&&) 、或 (I) 、非 (! )
- 【1】变量自增与自减运算
- 【1】三目运算
- 【2】位运算:与(&)、或() 、非 (~)、异或 (^) 、左移(<<)、右移(>>)
#### 5.数学库常用函数
- 【3】绝对值函数，四舍五入函数，取上整函数取下整函数，常用三角函数，对数函数，指数函数，平方根函数
#### 6.结构化程序设计
- 【1】顺序结构、分支结构和循环结构
- 【2】自顶向下、逐步求精的模块化程序设计
- 【2】流程图的概念及流程图描述
#### 7.数组
- 【1】数组定义，数组与数组下标的含义
- 【1】数组的读入与输出
- 【3】二维数组与多维数组
#### 8.字符串的处理
- 【2】字符数组与相关函数
- 【2】string 类与相关函数
#### 9.函数与递归
- 【2】函数定义与调用，形参与实参
- 【3】传值参数与传引用参数
- 【2】常量与变量的作用范围
- 【2】递归函数的概念、定义与调用
#### 10.结构体类型
- 【3】结构体
- 【4】联合体
#### 11.指针类型
- 【4】指针
- 【4】基于指针的数组访问
- 【4】字符指针
- 【4】指向结构体的指针
#### 12.文件及基本读写
- 【2】文件的基本概念，文本文件的基本操作
- 【2】文本文件类型与二进制文件类型
- 【2】文件重定向、文件读写等操作
#### 13.STL 模板应用
- 【3】算法模板库中的函数：min、max、swap、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】插入排序
- 【3】计数排序
#### 6.搜索算法
- 【5】深度优先搜索
- 【5】广度优先搜索
#### 7.图论算法
- 【4】深度优先遍历
- 【4】广度优先遍历
- 【5】泛洪算法 (flood fill)
#### 8.动态规划
- 【4】动态规划的基本思路
- 【4】简单一维动态规划
- 【5】简单背包类型动态规划
- 【5】简单区间类型动态规划
### 2.1.5 数学
#### 1. 数及其运算
- 【1】自然数、整数、有理数、实数及其算术运算 (加、减、乘、除)
- 【1】进制与进制转换:二进制、八进制、十进制、十六进制
#### 2.初等数学
- 【1】代数（初中部分）
- 【1】几何（初中部分）
#### 3.数论
- 【3】整除、因数、倍数、指数、质（素）数、合数
- 【3】取整
- 【3】模运算与同余
- 【3】整数唯一分解定理
- 【3】辗转相除法(欧几里德算法)
- 【4】素数筛法：埃氏筛法与线性筛法
#### 4.离散与组合数学
- 【2】集合
- 【2】加法原理
- 【2】乘法原理
- 【4】排列
- 【4】组合
- 【4】杨辉三角公式
#### 5.其他
- 【2】ASCII码
- 【2】格雷码
## 2.2 提高级
### 2.2.1 计算机基础知识与编程环境
1. 【5】Linux系统终端中常用的文件与目录操作命令
2. 【5】Linux系统下常见文本编辑工具的使用
4. 【5】g++、gcc 等编译器与相关见编译选项
5. 【5】在 Linux 系统终端中运行程序，使用time命令查看程序用时
6. 【5】调试工具GDB的使用
### 2.2.1 C++ 程序设计
#### 1.类(class)
- 【6】类的概念及简单应用
- 【6】成员函数和运算符重载
#### 2.STL 模板
- 【5】容器(container)和迭代器(iterator)
- 【5】对 (pair) 、元组 (tuple)
- 【5】集合 (set)、多重集合(multiset)
- 【5】双端队列(deque)、优先队列(priority_queue)
- 【5】映射(map)，多重映射(multimap)
- 【5】算法模板库中的常用函数
### 2.2.2 数据结构
#### 1.线性结构
- 【5】双端栈
- 【5】双端队列
- 【5】单调队列
- 【6】优先队列
- 【6】ST表(Sparse Table)
#### 2.集合与森林
- 【6】并查集
- 【6】树的孩子兄弟表示法
#### 3.特殊树
- 【6】二叉堆
- 【6】树状数组
- 【6】线段树
- 【6】字典树 (Trie 树)
- 【7】笛卡尔树
- 【8】平衡树AVL、treap、splay 等
#### 4.常见图
- 【5】稀疏图
- 【6】偶图 (二分图)
- 【6】欧拉图
- 【6】有向无环图
- 【7】连通图与强连通图
- 【7】双连通图
#### 5.哈希表
- 【5】数值哈希函数构造
- 【6】字符串哈希函数构造
- 【6】哈希冲突的常用处理方法
### 2.2.3 算法
#### 1.复杂度分析
- 【6】时间复杂度分析
- 【6】空间复杂度分析
#### 2.算法策略
- 【6】离散化
#### 3.基础算法
- 【6】分治算法
#### 4.排序算法
- 【5】归并排序
- 【5】快速排序
- 【6】堆排序
- 【5】桶排序
- 【6】基数排序
#### 5.字符串相关算法
- 【5】字符串匹配算法：KMP
#### 6.搜索算法
- 【6】搜索的剪枝优化
- 【6】记忆化搜索
- 【7】启发式搜索
- 【7】双向广度优先搜索
- 【7】迭代加深搜索
#### 7.图论算法
- 【6】Prim和Kruskal 等求最小生成树算法
- 【7】求次小生成树算法
- 【6】单源最短路：Dijkstra、bellman_ford、SPFA 等算法
- 【7】单源次短路
- 【6】Floyd-Warshall 算法
- 【6】有向无环图的拓扑排序算
- 【6】欧拉道路和欧拉回路
- 【6】二分图的判定
- 【7】强连通分量
- 【7】割点、割边
- 【6】树的重心、直径、DFS序与欧拉序
- 【6】树上差分、子树和与倍增
- 【6】最近公共祖先
#### 8.动态规划
- 【6】树型动态规划
- 【7】状态压缩动态规划
- 【8】动态规划的常用优化
### 2.2.4数学
#### 1.初等数学
- 【5】代数(高中部分)
- 【6】几何(高中部分)
#### 2.初等数论
- 【5】同余式
- 【7】欧拉定理和欧拉函数
- 【7】费马小定理
- 【7】威尔逊定理
- 【7】裴蜀定理
- 【7】模运算意义下的逆元
- 【7】扩展欧几里得算法
- 【7】中国剩余定理
#### 3.离散与组合数学
- 【6】多重集合
- 【6】等价类
- 【6】多重集上的排列
- 【7】多重集上的组合
- 【6】错排列、圆排列
- 【6】鸽巢原理
- 【6】二项式定理
- 【7】容斥原理
- 【7】卡特兰(Catalan)数
#### 4.线性代数
- 【5】向量与矩阵概念
- 【6】向量的运算
- 【6】矩阵的初等变换
- 【6】矩阵的运算:加法、减法、乘法与转置
- 【6】特殊矩阵的概念:单位阵、三角阵、对称阵和稀疏矩阵
- 【7】高斯消元法
## 2.3 NOI 级
### 2.3.1 C++ 程序设计
1. 【8】面向对象的程序设计思想(OOP)
### 2.3.2 数据结构
#### 1.线性结构
- 【8】块状链表
#### 2. 序列
- 【9】跳跃表
#### 3.复杂树
- 【8】树链部分
- 【10】动态树：LCT
- 【8】二维线段树
- 【9】树套树
- 【9】k-d 树
- 【10】虚树
#### 4.可合并堆
- 【8】左偏树
- 【10】二项堆
#### 4.可持化数据结构
- 【8】可持久化线段树
- 【9】其他可持久化数据结构
### 2.3.3 算法
#### 1.算法策略
- 【8】分块
- 【8】离线处理思想
- 【9】复杂分治思想
- 【9】平衡规划思想
- 【9】构造思想
#### 2.字符串算法
- 【8】Manacher 算法
- 【9】扩展 KMP算法
- 【9】有穷自动机
- 【8】AC自动机
- 【8】后缀数组
- 【9】后缀树
- 【10】后缀自动机
#### 3.图论算法
- 【8】基环树
- 【10】最小树形图
- 【8】2-SAT
- 【8】网络流
- 【10】图的支配集、独立集和覆盖集
- 【8】匈牙利算法
- 【9】KM算法
- 【10】一般图的匹配
#### 4.动态规划
- 【9】复杂动态规划模型的构建
- 【9】复杂动态规划模型的优化
### 2.3.4数学
#### 1.初等数论
- 【8】原根和指数
- 【8】大步小步(Baby Step Giant Step，BSGS)算法
- 【9】狄利克雷(Dirichlet) 卷积
- 【10】二次剩余
- 【10】二次同余式
#### 2.离散与组合数学
- 【9】群及其基本性质
- 【9】置换群与循环群
- 【9】母函数
- 【9】莫比乌斯反演
- 【9】Burnside引理与Pólya原理
- 【9】斯特林(Stirling)数
- 【9】无根树的Prüfer序列
#### 3.线性代数
- 【9】逆矩阵
- 【9】行列式
- 【9】向量空间与线性相关
#### 4.高等数学
- 【9】多项式函数的微分
- 【9】多项式函数的积分
- 【10】泰勒(Taylor)级数
- 【10】快速傅里叶变换
#### 5.概率论
- 【8】概率的基本概念
- 【9】概率变量的期望与方差
- 【9】条件概率
- 【9】贝叶斯公式
#### 6.博弈论
- 【9】尼姆(Nim)博弈
- 【9】SG函数
#### 7.最优化
- 【10】单纯形法
#### 8.计算几何
- 【8】点、线、面之间位置关系的判定
- 【8】一般图形面积的计算
- 【8】二维凸包
- 【9】半平面交
#### 9.信息论
- 【10】熵、互信息、条件熵、相对熵
#### 10.其他
- 【10】信息复杂度的概念
- 【10】描述复杂度的概念
- 【10】通讯复杂度的概念

正在渲染内容...

lym 版 NOI 大纲 文字版

lym 版 NOI 大纲文字版