分类 题数 备注
0/1分数规划 12 求解一个分数形式的函数的最值,常用的方法有二分答案等
01BFS 3 用于能转化为边权 0 or 1的最短路问题,双端队列实现
01背包 12 背包的基本类型
2-SAT 8 利用对称性求解2-SAT问题
A* 4
ACM/ICPC 5 美国大学生程序设计竞赛
AC自动机 1 多字符串匹配算法
APIO 8 亚洲-太平洋 OI
BFS 24 广度优先搜索 宽度优先搜索 广搜 宽搜
BFS序 2
bitset 优化 3
BSGS 2 大步小步算法(baby step giant step)
BYVoid 7 BYVoid原创题。
CDQ分治 32 按时间分治的算法,又称CDQ分治
COCI 5 克罗地亚地区信息学奥林匹克竞赛
CodeChef 4 某在线竞赛网站
Codeforces 20 俄罗斯在线比赛网站。
CTS论文相关 38 CTSC国家集训队选手答辩论文相关题目
DAG 6 有向无环图
DFS 24 深度优先搜索 深搜
DFS序 9
DP套dp 3 将内层 dp 的结果作为外层 dp 的状态进行 dp
EZOI 7 石家庄二中实验学校OI
Fail树 2
FFT 27 快速傅立叶变换
FWT 5 快速沃尔什变换
Gomory-Hu树 1
HAOI 71 河南省选
HDU 3 杭州电子科技大学在线评测系统
HEOI 8 河北省选
Hopcroft-karps算法 1
hs的简单题 22
HtBest 4 HtBest原创题目,后期将会整理为一些集合(希望我那时候没有退役)。
HZOI 67 河北省衡水中学信息学奥林匹克竞赛
IDA* 3
IOI 30 国际信息学奥林匹克竞赛
ISAP 1
K-D Tree 12 一种分割k维数据空间的数据结构
Keller系列 13
KMP 12
Kruskal 重构树 3
K短路 6 用a*算法,求解第k短的路径
LCA 33 最近公共祖先
LCP 1 最长公共前缀
LCS 4 最长公共子序列问题
LCT 6 Link-Cut Tree
LIS 12 最长不下降子序列
Lucas定理 5
Meet in the Middle算法 1 Meet in the Middle算法可以看成是搜索算法的一个改进,一般来说用于广搜(BFS),不过如果搜索深度有上限的情况下也可以用深搜。
NOI 109 全国信息学奥林匹克竞赛
NOIP/CSP 194 全国青少年信息学奥林匹克联赛/全国非专业级软件能力认证
NP问题 5 非确定性多项式时间复杂度问题 多项式基本技术
NTT 12 快速数论变换
POJ 44 Pku Online Judge (ACM)
Polya 定理 1 Polya定理给出了以置换作为等价关系的条件下,等价类的计数方法,形象的说,这个就是求出了本质不同的染色方案数。
polya罐子模型 1 概率论,Polya's urn scheme
RMQ 16 区间最值问题,Range Minimum/Maximum Query,可以用线段树或者ST算法解决。
SDOI 3 山东省选
SG函数 5 博弈论的工具
Splay 3 伸展树,一种平衡树。
SPOJ 18 某在线评测网站
ST表 6
SYOI 33 河南省实验中学信息学奥林匹克竞赛
TopCoder 2 某在线比赛网站
Ural 15 俄罗斯的在线评测系统,又叫 Timus OJ
USACO 244 USA Computing Olympiad 美国计算机竞赛
UVa 57 UVaOJ,来自西班牙的在线评测系统。
ZJOI 14 全国信息学奥林匹克竞赛浙江省队选拔赛,简称ZJOI。
三分法 3
三维偏序 3
三维莫队 2
中国剩余定理 10 Chinese Remainder Theorem,简称 CRT。
主元素问题 1
乘法原理 6
乘法逆元 7 通常用来将除法取余运算转化为乘法取余运算
二分优化 6
二分图 70
二分法 94 二分参数 二分答案 二分求解
二分答案 20
二叉树 5 二叉树
二维偏序 6 二维偏序问题一般用树状数组解决。
二维树状数组 7 这题是二维的 水 树状数组的应用,从一维转到二维,加一层循环即可搞定。
二维线段树 2
二项式定理 2
交互式 1 交互式题目
人工智能 2
仙人掌图 4 任意一条边都属于且仅属于一个环的有向强连通图,和任意一条边都至多属于一个环的无向连通图被称为仙人掌图
优先队列 9 基于堆实现的特殊队列 STL中有priority_queue
估价函数 1 估计打1-4张同色牌的代价,以减少分支数目
位运算 51 ~ 非运算 >> 右移位运算 << 左移位运算 & 与运算 ^ 异或运算 | 或运算 卡常大法好w~
保序回归问题 1
倍增法 38 倍增算法 倍增 恩 很经典的倍增思想 倍增
倒序处理 1 离线所有操作后倒序处理操作
决策单调性优化 15 动态规划的一种优化方法。 动态规划之优化
凸包 3
凸轮 1
分块 56 分块之后,随便搞。
分层图 7 把原图复制分层来解决一些不同寻常的最短路问题。详见集训队2004《肖天——分层图思想及其在信息学竞赛中的应用》
分形 1
分治 76 二分查找 二分 分治 二分答案 二分合理答案 二分答案之后贪心
分组背包 4 分组背包 动态规划-背包问题-分组背包
划分树 9 可在O(logn)的时间复杂度内求出区间第k大值的一种数据结构 采用定义数据结构的方法来完成题目。 利用自己定义的数据结构来储存数据
前缀和 33
剪枝 14 不剪你就wa到黑吧
割点与桥 6 tarjan
动态图 1
动态开点 3
动态树 18 包含对树的分割与合并,对每个点到根路径和子树操作/查询的一类问题
动态规划 593 通过把原问题分解为形式相同、规模较小的子问题求解,适用于据有最优子结构性质的问题,同时需要满足无后效性原则。
勒让德定理 2
匈牙利算法 13
区间DP 20
半平面交 5 求若干个半平面的交集。常用分治法或朱泽园提出的排序增量法(二者复杂度均为O(NlogN))解决。 复杂度
单纯形 2
单调栈 15
单调队列 41 通过维护一个内部元素保持单调性的队列用均摊O(1)的时间复杂度求出满足一定条件的区间最值 需要单调队列维护优化
博弈论 36 研究公式化了的激励结构(游戏或者博弈)间的相互作用 玄学
卡特兰数 1 卡特兰数,组合数学中一个常出现在各种计数问题中的数列。常见问题有出入栈方案、二叉树方案、买票找零等。
压位 1
双向BFS 3
双向DFS 1
双向DP 3
双指针扫描法 7 尺取法
双端队列 4 队头和队尾都能出队入队的结构 STL deque
双连通分量 10 利用dfs求双连通分量
反图 1 反向建图
可持久化 18 可持久化数据结构
可持久化平衡树 1 可持久化和平衡树
可持久化线段树 37 函数式线段树 系统函数及数学库函数的熟练使用 可持久化线段树
合并类动态规划 13
同余 8 同余 同余方程
后效性 1 环形与后效性处理
后缀数组 28
后缀树 6
后缀自动机 24 后缀自动机
启发式合并 4
哈夫曼树 3
四分树 3
四叉树 1 Quadtree
回文 4 回文子串问题,大多可用Manacher算法,后缀数组等字符串算法解决
回文自动机 6 自动机,处理各种回文串问题。
回溯法 17 回溯法
图的匹配 2 最大匹配、完美匹配
图论 249 图论 构图 建图 图 最小生成树 基本数据结构之一 割边
圆方树 3 解决一类静态仙人掌问题的树
埃氏筛 4 Eratosthenes筛法
基本 164 语言的基本知识及练习
基环树 11
基环树DP 7
39 二叉堆 可并堆 大根堆  小根堆 堆结构 heap 优先队列  Fibonacci堆 可用优先队列ac
复杂度分析 1
多重背包 7
多项式求逆 2 求取多项式乘法(往往带有取模)群中某个元素(多项式)的逆元的过程,常用一种巧妙的递归NTT解决,许多题目也有CDQ分治+NTT的做法
子集和变换 1
字典树/Trie 32 又称单词查找树; 是一种树形结构; 用于保存大量的字符串。它的优点是:利用字符串的公共前缀来节约存储空间。
字符串 143 字符串 string 字符串匹配 KMP算法 格式输入 通过o n+m的效率来查找模式串在目标串中出现的位置和次数 kmp算法
字符串哈希 21
字符串排序 3 都要用得上。
完全背包 7
容斥原理 24
密码 4
对偶图 2
局部搜索 2 启发式算法,解决NPC问题
左偏树 9
差分 20 差分
差分约束 16 最短路径解决差分约束系统问题
带修莫队 2
带权并查集 4
带花树 3 一般图的最大匹配
平衡树 75 平衡树,即排序二叉树,又名二叉搜索树(Binary Search Tree)。常见实现有SBT,Treap,AVL树,Splay伸展树,红黑树,Van Emde Boas,B树,STL中用红黑树实现了set,multiset,map,multimap。
平面图 2
并查集 71 对不相交集合的合并和查找 UFS
弦图 2 在一个图中,每一个长度大于三的环都至少有一条弦,弦是连接环上两个不相邻顶点的一条边。
弦图和区间图 2
强连通分量 17
快速幂 33
思维 16
悬线法 3 求解各类最大子矩形问题
扩展欧几里得算法 13
扫描线法 15
找规律 20
折半递归 2
拉格朗日插值 1
拓扑排序 12 拓扑排序  判环
拟阵 0 拟阵是一个满足交换性的子集系统
括号匹配 7
换根 6 按照深搜序对各条边上两点的父子关系反向,同时更新贡献,反向操作不超过2n次(n为点数)
排列组合 26 ANS=C(快速幂结果-1,k-1)
排序 54 快速排序 冒泡排序 选择排序 桶排序 归并排序 基数排序 系统快排 用的排序算法越优,时间会越短。 程序好编,完美去重!
插头DP 13 基于连通性状态压缩的动态规划
搜索法 307 BFS 广度优先搜索 宽度优先搜索 广搜 宽搜 DFS 深度优先搜索 深搜 记忆化搜索 剪枝 
支配树 2
散列 35 Hash 散列 哈希
数位DP 17
数值方法 4 数值方法解函数,数值方法求极值,数值积分,Simpson公式求积分
数学 279 数学知识  数论 线性代数 组合数学 概率论 博弈论等
数据结构优化建图 0 用线段树,前缀和,主席树,CDQ分治,KD树等数据结构优化建图。
数论 117 整数性质 素数 同余 RSA加密算法 莫比乌斯反演 学好数学......
整体二分 1 详见——许昊然论文《浅谈数据结构题的几个非经典解法》
整体分治 9 对所有询问二分最后得到答案,基于值域的整体分治
文法分析 3 文法分析 编译原理 BNF
斐波那契数列 3 “斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”。
斜率优化 30 用平面上的点表示决策,并维护决策的凸包以降低DP的时间复杂度
斯特林数 5
映射 2
替罪羊树 1
最值子图 6 最大独立集 最小支配集 最小路径覆盖 最大闭合子图
最大公约数 8
最小公倍数 3
最小割 6
最小割树 2
最小生成树 44 最小生成树 MST Kruskal 克鲁斯卡尔 Prim 普利姆
最小表示法 4
最短路 144 图论中的最短路径问题。
最短路径树 2
有限状态自动机 1
李超线段树 4 永久化标记
杜教筛 3
构造 10 根据输入构造最优/最差情况下的值
枚举 19 一个一个来
28 FILO stack
28
树上差分 8
树分块 1
树分治 17 树的边分治和点分治
树套树 17
树形DP 50
树状数组 100 在一个区间内实现快速查询,修改,删除的高效结构。 树状数组的离线应用
树的直径 7
树链剖分 47 将一棵树划分成若干条链使得每个点属于唯一一条链
根号分治 0
概率与期望 37 概率与期望,数学中的一类问题,广泛存在于 OI 之中
概率分析 5
模型转换 2
模式匹配 30 在串中寻找子串出现的位置 KMP算法 AC自动机 一种多串匹配的东西,俗称"自动AC机"
模拟 174 模拟 就是模拟 耐心吧 扫一遍即可 模拟 贪心 入门题 模拟算法 耐心就一定能过 找规律 模拟中 找规律 youdianshui
模拟退火 4
模线性方程组 1
次小生成树 0
次短路 3
欧几里得算法 2 辗转相除
欧拉函数 14 筛法求OL函数 筛素数。。
欧拉反演 1
欧拉定理及扩展 3 欧拉定理,扩展欧拉定理,欧拉函数 https://zhuanlan.zhihu.com/p/131536831
欧拉筛法 1 线性筛法
欧拉路径 9 欧拉路径 欧拉回路
母函数/生成函数 14 生成函数(Generating Function,也叫母函数)是组合数学中一种重要的方法,它把离散数列与形式幂级数对应了起来。
洛谷 6
浮水法 4 一种解决区间染色问题的奇怪方法 其实就是线段切割
浮点运算 3 测试计算机浮点运算能力 Super PI
清北学堂 16 人生需要规划,高中更应如此
滚动数组 3 要用到滚动数组优化空间 防止爆内存的利器
点分治 1
点双连通分量 3
物理 4 这是一道运用了热胀冷缩知识的题A
特判 5
特殊判断 2
状压DP 20 233 就是状压啊
状态压缩 56 将状态用一个正整数表示
狄利克雷前缀和 1
瓶颈生成树 1
生物 7 需要一点点生物知识,不然理解题意有困难
矩阵乘法 15
矩阵快速幂 25
矩阵树定理 4 求图的生成树数量
矩阵运算 32
离散化 35 离散化
种子填充 9 Flood Fill是一种图论算法,对于一个图来说,可以很方便的求子图的个数。
稀疏表 5 Sparse Table 稀疏表 ST ST算法
类背包 3
素数筛法 17 筛素数
线性DP 14
线性基 9
线性空间 1
线性结构 14 线性表 链表 线形结构
线性规划 5 单纯形算法
线段树 177 在一个区间内实现快速查询,修改,删除的高效结构。 不解释 括号序列 线段树 链式线段树
线段树分治 2 通过线段树 (一般不动态开点)的结构,对时间进行分治,从而在 O ( nlogn )的时间中维护出每一次询问的状态。是一种离线算法,如果不带修改,一般也可以用CDQ分治替换。
线段树合并 3 全称:动态开点权值线段树合并(建立一棵新的线段树保存原有的两颗线段树的信息)
组合数学 27
结构体 3 使用struct定义更方便
结论 3
缩点 7
网络流 120 一类图论问题
群论 16 置换群 E8李群
背包类树形DP 11 有树形依赖的背包问题(结点编号作为DP阶段,背包体积作为第二维状态,状态转移时要处理的实际就是一个分组背包问题)
背包问题 37 01背包 完全背包 有物品数量限制的背包问题
自然数拆分问题 6
莫比乌斯反演 11 数论内容
莫队 11
虚树 1 多个相关点的树上修改,将整个树按照这些点的lca关系造出一个缩边的虚树,之后原树上链修改 根据输入造最优/最差情况下的值
表达式树 4 表达式计算与表达式树 波兰算法 波兰表达式 逆波兰表达式
表达式求值 1
解异或方程组 3
计数 15 统计选择的方案数
计数类DP 8
计算几何 63 计算几何 凸包 旋转卡壳 典型凸包题
记忆化搜索 12
贪心 256 从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解 满足局部最优解是全局最优解的DP 可以用数学证明
轮廓线DP 2
连通分量 2
连通性 49 连通块 连通度 割顶 桥 块 连通图 无向图连通分量 有向图强连通分量 弱连通分量 Tarjan 利用dfs求出强连通分量来解决问题 深搜 用途广泛的Tarjan具有缩点、求SCC/DCC/LCA等诸多用途 经典的使用tarjan求强连通分量题目 看榜 可以缩点
迭代加深搜索 12 IDDFS
逆序对 11
递归 14 将矩阵一层一层分解
递推 100 递推 总结归纳出递推公式进行求值 数值递推
重链剖分 1 树链剖分分为两种:重链剖分和长链剖分。
链分治 1
长链剖分 2 一种基于子树深度而非节点数的树链剖分
队列 12 FIFO
随机化 17 利用随机数的稳定概率
集合幂级数 2 FMT, FWT。集合上的 poly。
高斯消元法 17 高斯消元 高斯消元法解线性方程组
高等数学 3 大学数学
高精度 63 高精度加法 高精度减法 高精度乘法 高精度除法 需要用到高精度计算
高精快速幂 2
黑白染色 2