NOI 级

C++程序设计

C++程序设计

1. STL模板：容器（containers）、迭代器（iterators）、空间配置器（allocators）、配接器（adapters）、算法（algorithms）、仿函数（functors）
2. 面向对象的程序设计思想（OOP）

数据结构

数据结构

1. 线性结构

   • 分块
   • 块状链表

2. 序列

   • 后缀数组
   • 跳跃表
   • 无根树的Prufer序列

3. 复杂树

   • 树链剖分
   • 主席树
   • 二维线段树
   • 后缀树
   • 树套树
   • k-d树
   • 最小树形图
   • 动态树（LCT）

4. 可合并堆

   • 左偏树
   • 二项堆

5. 可持久化数据结构

算法

算法

1. 算法策略

   • 复杂分治思想
   • 平衡规划思想
   • 构造思想

2. 字符串算法

   • 求最长回文串的Manacher算法
   • 多模匹配算法——AC自动机
   • 求字符串前缀和后缀算法——扩展KMP
   • 确定性有穷自动机——DFA算法
   • 非确定性有穷自动机——NFA算法
   • 后缀自动机

3. 图论算法

   • 网络流算法
   • 图的支配集、独立集与覆盖集
   • 二分图的最大匹配——匈牙利算法
   • 二分图的最佳匹配算法——KM算法
   • 一般图的匹配

4. 动态规划

   • 复杂动态规划模型构建
   • 复杂动态规划模型的优化

数学

数学

1. 信息论基础

   • 熵、互信息、条件熵、相对熵的基本概念
   • 信息复杂度的基本概念
   • 描述复杂度的基本概念
   • 通讯复杂度的基本概念

2. 初等数论

   • 原根和指数
   • 大步小步（`Baby Step Giant Step, BSGS）算法
   • 完全数
   • 狄利克雷（Dirichlet）卷积
   • 平方剩余
   • 二次同余式
   • 二次互反律

3. 离散数学

   • 代数系统的基本概念
   • 群的基本概念
   • 置换群与循环群

4. 组合数学

   • 母函数
   • 莫比乌斯变换
   • Burnside引理与Polya原理
   • 斯特林数

5. 高等数学

   • 多项式函数微分
   • 多项式函数积分
   • 泰勒级数
   • 快速傅里叶变换（Fast Fourier Transform, FFT）
   • 卷积

6. 线性代数

   • 矩阵的逆运算
   • 行列式及其运算
   • 线性相关与矩阵的逆

7. 概率论

   • 概率相关概念
   • 求概率的乘法公式、全概率公式、贝叶斯公式

8. 博弈论

   • 零和博弈问题——Nim博弈等
   • Sprague-Garundy(SG)函数概念及应用

9. 运筹学

   • 线性规划之单纯形法

10. 计算几何

    • 矢量及其运算
    • 点、线、面之间的位置判断
    • 常见图形的面积计算
    • 二维凸包的求法及其应用
    • 半平面交

---

最后更新: 2021-09-16