1基础
排序
二分三分各种情况轻松写出
贪心一些常见的贪心模型
模拟大数java大数不是万能的,比如说在理工
栈,堆,队列……STL那些也可以学下
熟练各种位运算! & | ^ ~ >> <<
rand yes,no万精油,还有随机数据
2搜索
Flood fill题到难时就不萌了
DFS码短,注意爆栈
BFS把下面的都搞定之后发现还是这个最给力预处理很流氓
双向广搜可以一边预处理,另一边bfs有木有(2953) A*启发式搜索以后用得上
IDA*迭代加深A*搜索这个比楼上好用
遗传算法
蚁群算法
DLX
精确覆盖
重复覆盖
上面两种组合
3哈希
散列表哈希
map哈希
字符串哈希
逆序数哈希只有特殊情况才能使用
4树的同构
哈希法可能会出现冲突
最小表示法码长
5字符串
KMP算法扩展KMP可以了解下
RK,二维RK其实就是字符串哈希
字典树
Manacher求回文串
最小表示法
AC自动机和各种算法搭配
后缀数组
后缀树一般使用后缀数组
6图论
最短路
Dijkstra加堆优化的
SPFA还要回判负环的方法
SPFA_DFS主要目的是判负环的时候略有优点
Floyd
求路径条数最短路条数,次短路条数(DP)
次短路,k短路DP或A*
无向图最小环
差分约束bellman-ford有先天优势
树上最长路两次dfs
连通性
Tarjan
Kosaraju不常用
2-sat要会求可行解
边双连通
点双连通
匹配问题
匈牙利算法
HK算法不常用
二分图多重匹配
稳定婚配
KM匹配
带花树算法一般图匹配
一般图最小权完美匹配
生成树
prim
kruskal并查集 + 贪心
次小生成树
最小度限制生成树
最优比例生成树01分数规划
最小树形图
斯坦纳树最小网络
网络流
最大流EK
最大流SAP
上下界网络流最大流建图
混合图欧拉回路最大流建图
费用流
全局最小割
中国邮路问题不知道瑞彬哥在讲神马
有向图费用流建图
无向图一般图最小权完美匹配
最近公共祖先
RMQ_LCA用到笛卡尔树,欧拉序列,RMQ
Tarjan_LCA码长低能不易理解
倍增法在线LCA用于树链剖分
其他图论
拓扑排序
最大团NP暴力+剪枝
竞赛图完全不知道瑞彬哥在说神马
7矩阵乘法
推推题n大约为10^9的题
求路径条数N步从一个点到另一个点的所有走法
AC自动机长度为N,包含某些串,不包含另一些串的串有多少个
重复操作不大于100个数字,对他们进行交换或者加减等操作,重复10^9次8数论
欧几里德
扩展欧几里德
逆元
快速幂取余
素数筛选
因数分解
素数测试
大因数分解
阶乘分解因子
欧拉函数
同余方程
高斯消元
中国剩余定理
原根
Babystep离散对数
异或独立元
佩尔方程
int64乘法取模
指数降阶a^b % p b可以非常大
概率问题
隐马尔科夫模型
快速傅里叶变换
单纯形法解线性规划
901分数规划
二分法
Dinkelbach迭代法
10组合数学
排列与组合
鸽笼原理
容斥原理
递推
Fibonacci数列
Catalan数列
Stirling数
差分序列
生成函数
置换群
Burnside引理
Polya原理
母函数
整数拆分
默比乌斯反演
Ramsey定理
错排问题
偏序关系理论
11动态规划
背包,LCS等简单DP
树形DP
插头DP基于连通性的状态压缩DP
DP优化
单调队列
斜率优化
四边形不等式
记忆化搜索反过来dp
12状态压缩
加动归/搜索的记录状态,经典模型求哈密顿路
一些覆盖问题n皇后那样的
13博弈
N,P组合博弈
nim-sum博弈
anti-nim博弈
nim积博弈
SG值
树形博弈
极大极小过程
博弈树(胜者树)
阿尔法贝塔减枝
14数据结构
链表循环,十字,双向
树状数组一维,二维,(扩展树状数组也可以了解下)线段树一维,二维
二叉搜索树
并查集求距离,能删点的并查集写法
Splay tree
Size Balanced Tree SBT&&平衡树等
单调队列,单调栈
树链剖分
动态树数据结构万精油
笛卡尔树O(n) or O(nlogn)建树
左偏树
AVL树数据结构书上的。。
堆大顶堆,小顶堆-》(优先队列)
哈弗曼树
树的先序中序后序遍历DFS,BFS
KD-Tree空间划分
动态树LCT Link-Cut Trees
15计算几何
叉积和点积
判断线段直线相交平行
点到直线线段距离
多边形面积,周长,重心
求凸包及其应用几个经典模型,包括三维的
扫描线矩形面积周长交并,线段树扫描线
判断点与多边形关系一般多边形两种方法,凸包2分法logn判断半平面交
Voronoi图三角剖分及其应用
多圆面积问题
多边形相交
旋转卡壳对踵点,点集分割解析几何高数。。
随机算法&&模拟退火例如费马点
求对称点
直线和圆切点,交点
线段和点的旋转包括三维
最小圆覆盖
最近点对
固定圆(椭圆)覆盖最多点
作,重复10^9次