NOI级考试大纲

2.3 NOI 级
2.3.1 C++ 程序设计 3
1.[ 8 ] 面向对象的程序设计思想 ( OOP)
2.3.2 数据结构
1. 线性结构
[ 8 ] 块状链表
2.序列
[ 9] 跳跃表
3.复杂树
[ 8 ] 树链剖分
[ 10] 动态树: LCT
[ 8 ] 二维线段树
[ 9 ] 树套树
[ 9] kd树
[ 10] 虚树
4.可合并堆
[ 8]左偏树
[ 10] 二项堆
5.可持久化数据结构
[ 8] 可持久化线段树
[ 9 ] 其他可持久化数据结构
2.3.3 算法
1.算法策略
[ 8] 分块
[ 8 ] 离线处理思想
[ 9 ] 复杂分治思想
[ 9 ] 平衡规划思想
[ 9 ] 构造思想
2.字符串算法
[ 8 ] Manacher 算法
[ 9 ] 扩展 KMP 算法
[ 8 ] 有穷自动机
[ 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 引理与 P6lya 定理
[ 9 ] 斯特林 (Stirling)数
[9 ] 无根树的 Prifer 序列
3.线性代数
[ 9 ] 逆矩阵
[ 9 ] 行列式
[ 9] 向量空间与线性相关
4.高等数学
[ 8] 多项式函数的微分
8多项式函数的积分
[10] 泰勒 (Taylor) 级数
[ 10] 快速傅里叶变换
5.概率论
[ 8 ] 概的基本概念
[ 10] 随机变量的期望与方差
[ 9 ] 条件概率
[ 9 ] 贝叶斯公式
6.博弈论
[9] 尼姆(Nim) 博李
[ 9 ] SG 函数
7.最优化
[ 10] 单纯形法
8.计算几何
[ 8 ] 点、线、面之间位置关系的判定
[ 8] 一般图形面积的计算
[ 8 ] 二维凸包
[ 9 ]半平面交
9.信息论
[10] 熵、互信息、条件、相对熵
10.其他
[10] 信息复杂度的概念
[10] 描述复杂度的概念
[10] 通讯复杂度的概念