注：带有‘*’为NOI级，过于简单的不再收录

计算机基础与编程环境

C++程序设计

基本运算

逻辑运算：与或非

变量自增与自减运算

三目运算

位运算

指针类型

STL模板应用

栈（stack）、队列（queue）、链表（list）、向量（vector）等容器

set集合、多重集合（multiset）

双端队列（deque）、优先队列（priority_queue）

映射（map）多重映射（multimap）

对（pair）、元组（tuple）

*容器（containers）、迭代器（iterators）、配接器（adapters）、空间配置器（allocators）、仿函数（functors）

*面向对象的程序设计思想

数据结构

线性表

链表：单链表、双向链表、循环链表

栈

队列

线性结构

双端栈

双端队列

有序队列

优先队列

倍增表（ST表）

*分块

*块状链表

树：简单树、特殊树

树与二叉树定义、表示、遍历

哈夫曼树定义、构造及其遍历

二叉排序树定义、构造及其遍历

线段树

树状数组

字典树

笛卡尔树

二叉平衡树AVL、treap、splay

基环树

*树链剖分

*可持久化线段树(主席树)

*二维线段树

*后缀树

*树套树

*KD树

*最小树形图

*动态树（LCT）

集合与森林

等价类

并查集

树与二叉树的转化——孩子兄弟表示法

简单图、常见图

图定义及其相关概念、邻接矩阵、邻接表存储

稀疏图

偶图（二分图）

欧拉图

有向无环图

连通图与强连通图

重连通图

哈希表

数值哈希函数构造

排列哈希函数构造

字符哈希函数构造

哈希函数冲突的常用解决办法

*序列

*后缀数组

*跳跃表

*无线树的Prufer序列

*可合并堆

*左偏树

*二项堆

算法

概念与描述

复杂度分析：时间与空间

*算法策略

*复杂分治思想

*平衡规划思想

*构造思想

枚举与模拟

基础算法

贪心

递推

二分

倍增

分治

高精：加减乘以及整数除以单精度整数的商和余数

排序

基本概念：...稳定性等

冒泡排序、选择排序、插入排序

归并排序、快速排序、桶排序

堆排序、树形选择排序、基数排序

图论算法

图的深度优先遍历、宽度优先遍历

洪水填充算法（floodfill）

最小生成树（Prim和kruskal等）

求次小生成树

Dijkstra、bellman_ford、SPFA单源最短路

单源次短路

Floyed-Warshall算法求任意两点间的最短路和传递闭包

有向无环图的拓扑排序算法

求欧拉道路和欧拉回路算法

二分图的构造及其判定算法

最近公共祖先（LCA）

求强联通分量算法（Tatjan）

强连通分量的缩点算法

求割点、割边算法

*网络流算法

*图的支配集、独立集与覆盖集

*二分图的最大匹配——匈牙利算法

*二分图的最佳匹配算法——KM算法

*一般图的匹配

动态规划

求解原理

背包类型

线性DP

区间DP

树形DP

数位DP

状态压缩DP

插头DP

动态规划的常用优化

*复杂动态规划模型构建与优化

字符串相关

KMP

*求最长回文串的Manacher算法

*AC自动机

*扩展KMP——求字符串前缀和后缀

*确定性又穷自动机——DFA算法

*非确定性有穷自动机——NFA算法

*后缀自动机

搜索算法

搜索的剪枝优化

记忆化搜索

启发式搜索

双向宽度优先搜索

迭代加深搜索

搜索对象的压缩存储

数学

进制及其转换

编码

ASCII码

哈夫曼编码

格雷码

初等数论

整数、因数、倍数、指数、素数、合数、同余概念

唯一分解定理

欧几里得算法（辗转相除法）

埃式筛法和线性筛法求素数

同余式

欧拉定理和欧拉函数

费马小定理

威尔逊定理

裴蜀定理

逆元

扩展欧几里得算法

孙子定理（中国剩余定理）

*原根和指数

*大步小步算法BSGS

*完全数

*狄利克雷卷积

*平方剩余

*二次同余式

*二次互反律

组合数学

加法原理乘法原理

排列组合及计算公式

杨辉三角公式

可重集排列组合

错排列、圆排列

鸽巢原理

二次项定理

容斥原理

卡特兰数

*母函数

*莫比乌斯变换

*Bumside引理与Polya原理

*斯特林数

高中数学

代数

解析几何

立体几何

线性代数

矩阵概念

特殊矩阵：稀疏，三角，对称

矩阵的初等变换

矩阵的加减乘和转置算法

线性方程组的高斯消元法

*矩阵的逆运算

*行列式及其运算

*线性相关与矩阵的逆

*信息论基础

*熵、互信息、条件熵、相对熵的基本概念

*信息复杂度的基本概念

*描述复杂度的基本概念

*通讯复杂度的基本概念

*离散数学

*代数系统的基本概念

*群的基本概念

*置换群与循环群

*高等数学

*多项式函数微分

*多项式函数积分

*泰勒级数

*快速傅里叶变换

*卷积

*概率论

*概率相关概念

*求概率的乘法公式、全概率公式、贝叶斯公式

*博弈论

*零和博弈问题——Nim博弈等

*Sprague-Garundy（SG）函数概念及应用

*运筹学

*线性规划之单纯形法

*计算几何

*矢量及其运算

*点线面之间的位置判断

*常见的图形面积计算

*二维凸包的求法及其应用

*半平面交