2023年7月30日发(作者：)

「NOI⼤纲」「NOI⼤纲」【X】表⽰难度系数2.1 ⼊门级2.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】g++、gcc等常见编译器的基本使⽤2.1.2 C++程序设计11. 程序基本概念【1】标识符、关键字、常量、变量、字符串、 表达式的概念【1】常量与变量的命名、定义及作⽤【2】头⽂件与名字空间的定义与理解【2】编辑、编译、解释、调试等概念理解2. 基本数据类型【1】整数型：int, long long【1】实数型：float, double【1】字符型：char【1】布尔型：bool3. 程序基本语句【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】 中

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 计算机基础与编程环境【5】在Linux系统终端中使⽤mkdir、cp、rm、mv等命令新建、复制、删除、移动⽂件或⽬录【5】在Linux系统终端中使⽤cd、pwd、ls等命令更改、显⽰⽬录路径和查看⽬录中的⽂件【5】在Linux系统下使⽤Gedit、Vim或Emacs等⽂本编辑⼯具编写代码【5】熟悉g++、gcc等编译器以及优化、数学库等常见编译选项【5】在Linux系统终端中运⾏程序，并使⽤time命令查看程序⽤时（区分real time、sys time和user time）【5】了解调式⼯具gdb及其break、display、continue、step等命令2.2.1 C++程序设计21. 类（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】字符串匹配算法——KMP5. 搜索算法【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【8】STL模板：容器（containers）、迭代器（iterators）、空间配置器（allocators）、配接器（adapters）、算法（algorithms）、仿函数（functors）【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.3.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】半平⾯交