526互联

NOI大纲（2023修订版）（文字稿)

发布时间 2023-03-26 10:41:24作者: IcyRaining

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函数

6.最优化

  • [10] 单纯形法

8.计算几何

  • [8] 点、线、面之间位置关系的判定
  • [8] 一般图形面积的计算
  • [8] 二维凸包
  • [9] 半平面交

9.信息论

  • [10] 熵、互信息、条件熵、相对熵

10.其他

  • [10] 信息复杂度的概念
  • [10] 描述复杂度的概念
  • [10] 通讯复杂度的概念