分类 题数 备注
空题「人工置顶分类」 3 新建题目时请优先修改该分类中的题目。
0/1分数规划 4 求解一个分数形式的函数的最值,常用的方法有二分答案等
0/1背包 11 背包最基本的一类,练手用~~
2-SAT 3 利用对称性求解2-SAT问题
ACM/ICPC 6 美国大学生程序设计竞赛
AC自动机 1 多字符串匹配算法
APIO 8 亚洲-太平洋 OI
BFS 1
BFS序 1
bitset 7
BSGS 0 大步小步算法,用于求解高次同余方程。
BYVoid 7 BYVoid原创题。
COCI 5 克罗地亚地区信息学奥林匹克竞赛
CodeChef 4 某在线竞赛网站
Codeforces 14 俄罗斯在线比赛网站。
DAG 7 有向无环图
DFS 4 深度优先搜索
DFS序 5
Dijkstra 5
Dinic 7
EZOI 7 石家庄二中实验学校OI
Fail树 2
FFT 24 快速傅立叶变换
Floyd 5
floyed 5
FWT 0 快速沃尔什变换
Gomory-Hu树 1
HAOI 64 河南省选
HDU 2 杭州电子科技大学在线评测系统
HEOI 8 河北省选
Hopcroft-karps算法 1
hs的简单题 19
HtBest 4 HtBest原创题目,后期将会整理为一些集合(希望我那时候没有退役)。
HZOI 70 河北省衡水中学信息学奥林匹克竞赛
IOI 29 国际信息学奥林匹克竞赛
ISAP 1
K-D树 9 一种分割k维数据空间的数据结构
Keller系列 14
KMP 5
k短路 5 用a*算法,求解第k短的路径
LCA 19 最近公共祖先
LCS 4 最长公共子序列问题
LCT 4
LIS 1
Lucas定理 1
NOI 99 全国信息学奥林匹克竞赛
NOIP 140 全国青少年信息学奥林匹克联赛
NOI题库 0 http://noi.openjudge.cn/
NP问题 5 非确定性多项式时间复杂度问题 多项式基本技术
NTT 3 快速数论变换
PAM 1 回文自动机
pbds 1 可以用pbds库里的pairing_heap的合并过掉这道题,所以分类在pbds中。
pb_ds 1 此题用pb_ds可以水过
POJ 40 Pku Online Judge (ACM)
RMQ 12 ST算法  Range Minimum/Maximum Query,可以用线段树或者ST算法解决。
SDOI 3
SG函数 3 博弈论的工具
SPFA 3
SPOJ 19 某在线评测网站
STL 37 C++ STL 标准模板库 照着模板打一个就能A~(≧▽≦)/~啦啦啦 太难了
STL set 5
ST表 1
SYOI 32 河南省实验中学信息学奥林匹克竞赛
TopCoder 2 某在线比赛网站
Treap 1 一种常用的平衡树。
Ural 15 俄罗斯的在线评测系统,又叫 Timus OJ
USACO 242 USA Computing Olympiad 美国计算机竞赛
UVa 56 UVaOJ,来自西班牙的在线评测系统。
vector 1
Vijos 0 备战 NOIP 的在线评测系统:vijos.org
ZJOI 12 全国信息学奥林匹克竞赛浙江省队选拔赛,简称ZJOI。
一维数组 1
三分法 3
三维莫队 1
中国剩余定理 3 Chinese Remainder Theorem,简称 CRT。
主元素问题 1
主席树 32 函数式线段树 系统函数及数学库函数的熟练使用 可持久化线段树
乘法原理 3
二分优化 4
二分图 57 二分图 二分再二分 二分 二分正解
二分法 66 二分参数 二分答案 二分答案 二分求解
二叉树 2
二维数组 2
二维树状数组 5 这题是二维的 水 树状数组的应用,从一维转到二维,加一层循环即可搞定。
二维线段树 2
二进制 1
二项式定理 1
交互式 1 交互式题目
人工智能 1
仙人掌图 3 任意一条边都属于且仅属于一个环的有向强连通图,和任意一条边都至多属于一个环的无向连通图被称为仙人掌图
估价函数 1 估计打1-4张同色牌的代价,以减少分支数目
伸展树 2 一种平衡树。
位运算 33 ~ 非运算 >> 右移位运算 << 左移位运算 & 与运算 ^ 异或运算 | 或运算 卡常大法好w~
倍增法 22 倍增算法 倍增 恩 很经典的倍增思想 倍增
倒序处理 1 离线所有操作后倒序处理操作
决策单调性优化 9 动态规划的一种优化方法。 动态规划之优化
凸包 1
凸轮 1
函数调度 1
分块 42 分块之后,随便搞。
分层图 2 把原图复制分层来解决一些不同寻常的最短路问题。详见集训队2004《肖天——分层图思想及其在信息学竞赛中的应用》
分支程序设计 1 熟练使用if等分支结构
分治 64 二分查找 二分 分治 二分答案 二分合理答案 二分答案之后贪心
分组背包 4 分组背包 动态规划-背包问题-分组背包
分解质因数 1
划分树 10 可在O(logn)的时间复杂度内求出区间第k大值的一种数据结构 采用定义数据结构的方法来完成题目。 利用自己定义的数据结构来储存数据
前缀和 10
前缀和优化 6
剪枝 5 不剪你就wa到黑吧
割点 3 tarjan
动态图 1
动态开点 3
动态树 18 包含对树的分割与合并,对每个点到根路径和子树操作/查询的一类问题
动态规划 497 通过把原问题分解为形式相同、规模较小的子问题求解,适用于据有最优子结构性质的问题,同时需要满足无后效性原则。
勒让德定理 2
匈牙利算法 10
区域动规 2
区间DP 3
半平面交 5 求若干个半平面的交集。常用分治法或朱泽园提出的排序增量法(二者复杂度均为O(NlogN))解决。 复杂度
单纯形 2
单调栈 9
单调队列 31 通过维护一个内部元素保持单调性的队列用均摊O(1)的时间复杂度求出满足一定条件的区间最值 需要单调队列维护优化
博弈论 27 研究公式化了的激励结构(游戏或者博弈)间的相互作用 玄学
压位 1
双向动规 3
双连通分量 3 利用dfs求双连通分量
可持久化 14 可持久化数据结构
可持久化平衡树 1 可持久化和平衡树
合并类动态规划 11
后缀数组 26
后缀树 6
后缀自动机 22 后缀自动机
启发式合并 1
哈夫曼树 3
哈希算法 1
哈希表 6 使用哈希表可极巧妙的绕开某些问题
四分树 3
四叉树 1 Quadtree
回文串 4 回文子串问题,大多可用Manacher算法,后缀数组等字符串算法解决
回文数 1
回文自动机 5 自动机,处理各种回文串问题。
回溯 14 回溯
图论 206 图论 构图 建图 图 最小生成树 基本数据结构之一 割边
圆方树 2 解决一类静态仙人掌问题的树
坐标动归 1
基本 167 语言的基本知识及练习
基础数论 3 好好学,有意思的还在前面
31 二叉堆 可并堆 大根堆  小根堆 堆结构 heap 优先队列  Fibonacci堆 可用优先队列ac
多重背包 3
多项式求逆 1 求取多项式乘法(往往带有取模)群中某个元素(多项式)的逆元的过程,常用一种巧妙的递归NTT解决,许多题目也有CDQ分治+NTT的做法
大暴搜 2
大模拟 2
子集和变换 1
字典序 1
字典树 24 Retrieval Tree Trie Tree Trie; 又称单词查找树; 是一种树形结构; 用于保存大量的字符串。它的优点是:利用字符串的公共前缀来节约存储空间。 字典树我过了,很裸
字符串 128 字符串 string 字符串匹配 KMP算法 格式输入 通过o n+m的效率来查找模式串在目标串中出现的位置和次数 kmp算法
字符串hash 8 通过字符串hash解字符串匹配问题
字符串哈希 5
字符串处理 7
字符串排序 3 都要用得上。
完全背包 3
容斥原理 11
密码 4
对偶图 2
小学奥数 1 跪在小学奥数面前
尺取法 0 又名双指针法,two pointers。
局部搜索 2 启发式算法,解决NPC问题
左偏树 9
差分序列 7 差分序列
差分约束 12 最短路径解决差分约束系统问题
带修莫队 1
带权并查集 1
带花树 3 一般图的最大匹配
平衡树 70 平衡树,即排序二叉树,又名二叉搜索树(Binary Search Tree)。常见实现有SBT,Treap,AVL树,Splay伸展树,红黑树,Van Emde Boas,B树,STL中用红黑树实现了set,multiset,map,multimap。 I'm Van,I'm an a****t.
平面图 2
并查集 53 对不相交集合的合并和查找 UFS 查查,并
弗洛伊德 3
弦图 1 在一个图中,每一个长度大于三的环都至少有一条弦,弦是连接环上两个不相邻顶点的一条边。
弦图和区间图 1
强联通分量 2
强连通分量 8
微软亚洲研究院面试题 1
快速幂 26
悬线法 3 求解各类最大子矩形问题
打表 26 静态打表 多线程变频置换表 非稳态表 量子纠缠表 打了表就能过 动态打表 打表找规律
扩展欧几里得算法 11 //扩展欧几里德算法 int ExGCD(int a, int b, int& x, int& y) { if(b == 0) { x = 1, y = 0; return a; } int d = ExGCD(b, a%b, x, y); int temp = x; x = y; y = temp - a/b*y; return d; } int main() { int x, y, d; d = ExGCD(99, 78, x, y); cout << d << " " << x << " " << y << endl; return 0; } //定理一: 如果a,b是不都为0的任意整数,则d=gcd(a,b)是a,b的线性组合{ax+by: x,y∈Z}的最小元素. // 已知d=gcd(a,b)=gcd(b,a mod b) // //由gcd(b,a mod b)得知,d = bx + a mod b = bx + (a-floor(a/b)*b)*y = a*y + b(x-floor(a/b)*y) //当推到gcd(a,b)时,d′ = d = a*y + b(x-floor(a/b)*y) //其他比较重要定理: //定理二:d|a, d|b => d|(ax+by)  注:d|a表示a mod b == 0,即a能被b整除 //定理一推论: 对任意整数a,b如果d|a,d|b,则d|gcd(a,b) //附: int GCD(int a, int b) {     if(b == 0)   return a;   return GCD(b, a % b); } //迭代形式: int GCD(int a, int b) { while(b != 0) { int r = b; b = a % b; a = r; } return a; }
扫描线法 8
找规律 13
拓扑排序 5
拓扑排序 STL 38 将有向无环图中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若(u,v)间有一条边,则u在线性序列中出现在v之前。 快速排序 希尔,归并,快速,堆,筒...<-真假->冒泡,选择,插入... STL!
拟阵 0 拟阵是一个满足交换性的子集系统
换根 2 按照深搜序对各条边上两点的父子关系反向,同时更新贡献,反向操作不超过2n次(n为点数)
排列组合 22 ANS=C(快速幂结果-1,k-1)
排序 47 快速排序 冒泡排序 选择排序 桶排序 归并排序 基数排序 系统快排 用的排序算法越优,时间会越短。 程序好编,完美去重!
推理 1
插头DP 11 基于连通性状态压缩的动态规划
搜索法 272 BFS 广度优先搜索 宽度优先搜索 广搜 宽搜  DFS 深度优先搜索 深搜 记忆化搜索 搜索+剪枝 广度优先搜索 dfs记忆化,23333(机智法的暴搜) dfs
支配树 1
散列 32 Hash 散列 哈希 无
散列表 1
数位DP 9
数值方法 4 数值方法解函数,数值方法求极值,数值积分,Simpson公式求积分
数学 238 数学方法 组合数学 线性代数 概率论 数学知识 质因数分解  素数 数学相关 比较水 不化简表达式就想过? 出题人大概是看了3Blue1Brown的视频吧(雾
数论 98 整数性质 素数 同余 RSA加密算法 莫比乌斯反演 学好数学......
整体二分 7 对所有询问二分最后得到答案
文法分析 3 文法分析 编译原理 BNF
斜率优化 15 用平面上的点表示决策,并维护决策的凸包以降低DP的时间复杂度
斯特林数 3
映射 1
暴力 51 太暴力 太暴力
暴力枚举 4
暴搜 9
替罪羊树 2
最值子图 6 最大独立集 最小支配集 最小路径覆盖 最大闭合子图
最大公约数 1
最小公倍数 1
最小割定理 4
最小割树 2
最小生成树 40 最小生成树 MST Kruskal 克鲁斯卡尔 Prim 普利姆 Kruskal   。。
最小表示法 4
最短路 125 图论中的最短路径问题。
最短路径树 1
最长上升子序列 5 有n^2和nlogn两种算法
最长不下降子序列 1
有限状态自动机 1
李超线段树 1 永久化标记
杜教筛 1
构造 3 根据输入构造最优/最差情况下的值
枚举 5 一个一个来
栈和队列 36 FILO 栈 stack、FIFO 队列 queue的灵活运用
3
树上倍增 0
树上差分 5
树上有依赖背包 2 普通背包解决不了
树分块 1
树分治 15 树的边分治和点分治
树套树 15
树形DP 28
树状数组 71 在一个区间内实现快速查询,修改,删除的高效结构。 树状数组的离线应用
树结构 17 树 树结构 Tree 二叉树
树链剖分 34 将一棵树划分成若干条链使得每个点属于唯一一条链
概率与期望 18 概率与期望
概率分析 4
概率期望 1
模型转换 2
模式匹配 30 在串中寻找子串出现的位置 KMP算法 AC自动机 一种多串匹配的东西,俗称"自动AC机"
模拟 152 模拟 就是模拟 耐心吧 扫一遍即可 模拟 贪心 入门题 模拟算法 耐心就一定能过 找规律 模拟中 找规律 youdianshui
模拟退火 3
模板题 3 就是裸的题目,没有任何的技巧和优化,就可以AC
次小生成树 1
次短路 3
欧拉函数 8 筛法求OL函数 筛素数。。
欧拉路径 5 欧拉路径 欧拉回路
洛谷 1
浮水法 4 一种解决区间染色问题的奇怪方法 其实就是线段切割
浮点运算 3 测试计算机浮点运算能力 Super PI
清北学堂 10 人生需要规划,高中更应如此
滚动数组 3 要用到滚动数组优化空间 防止爆内存的利器
物理 3 这是一道运用了热胀冷缩知识的题A
物理题 1
特判 3
特殊判断 1
状压DP 8 233 就是状压啊
状态压缩 47 将状态用一个正整数表示
瓶颈生成树 1
生物题 9 需要一点点生物知识,不然理解题意有困难
矩形切割 1
矩阵乘 3
矩阵乘法 5
矩阵快速幂 12
矩阵树定理 2 求图的生成树数量
矩阵运算 29
离散化 29 离散化
种子填充 8 Flood Fill是一种图论算法,对于一个图来说,可以很方便的求子图的个数。
稀疏表 5 Sparse Table 稀疏表 ST ST算法
类背包 1
素数筛法 3 筛素数
红黑树 0 红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。
线性动规 6
线性基 3
线性筛 3
线性结构 15 线性表 链表 线形结构
线性规划 5 单纯形算法
线段树 127 在一个区间内实现快速查询,修改,删除的高效结构。 不解释 括号序列 线段树 链式线段树
线段树合并 1
组合数学 6
结构体 3 使用struct定义更方便
网络流 104 一类图论问题
群论 13 置换群 E8李群
背包问题 32 01背包 完全背包 有物品数量限制的背包问题
莫比乌斯反演 9 数论内容
莫队 8
虚树 1 多个相关点的树上修改,将整个树按照这些点的lca关系造出一个缩边的虚树,之后原树上链修改 根据输入造最优/最差情况下的值
表达式树 3 表达式计算与表达式树 波兰算法 波兰表达式 逆波兰表达式
解异或方程组 2
解方程组 11 高斯消元 高斯消元法解线性方程组
计数 9 统计选择的方案数
计算几何 60 计算几何 凸包 旋转卡壳 典型凸包题
计算器 1 一些改造后的计算器问题
记忆化 1
记忆化搜索 4 转换状态
贪心法 205 从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解 满足局部最优解是全局最优解的DP 可以用数学证明
连通性 48 连通块 连通度 割顶 桥 块 连通图 无向图连通分量 有向图强连通分量 弱连通分量 Tarjan 利用dfs求出强连通分量来解决问题 深搜 用途广泛的Tarjan具有缩点、求SCC/DCC/LCA等诸多用途 经典的使用tarjan求强连通分量题目 看榜 可以缩点
迭代加深搜索 7 IDDFS
逆序对 7
递归 12 将矩阵一层一层分解
递推 85 递推 总结归纳出递推公式进行求值 数值递推
链分治 1
长链剖分 1 一种基于子树深度而非节点数的树链剖分
陈丹琦分治 19 按时间分治的算法,又称CDQ分治
随机化 15 利用随机数的稳定概率
骗分 20 心态,非完美算法,精彩地骗,简单数学分析+猜测,分类讨论 直接输出答案 打结果表
高等数学 2 大学数学
高精度 62 高精度加法 高精度减法 高精度乘法 高精度除法 需要用到高精度计算
高精快速幂 2
黑白染色 2