学习算法用处总结
一、基础算法
1、RMQ(st表)
可以通过预处理的方法查询区间最大值和最小值
只适用于静态问题,时间复杂度$O(nlog(n))$
预处理$f[i][j]$表示前从$i$开始的长度为$2^j$的区间最大值
二、数据结构
1、单链表和双链表
$O(1)$删除和插入
2、单调栈
维护一个单调递增或递减的序列,存储信息使得想要的结果
3、单调队列(滑动窗口)
维护窗口最值或者一个单调递增或递减的队列,某些程序会有大作用
4、kmp
$O(n)$匹配模式串和子串,维护重要的$next$数组
5、trie
存储数字或字符串出现次数,可以减少数据冗余,可以查询删除
可求最大异或和
6、可持久化trie
储存每一个字符串或数字的历史版本,可进行区间的查询,求区间的最大异或和
7、并查集
可以将两个集合合并成一个集合,可以维护集合的数量
可以查询集合是否在一个集合,时间复杂度$O(n)$
可以用并查集做一次的区间覆盖时间复杂度$O(n)$
维护多个集合的相互关系可以做很多事情
8、堆
维护一个大根堆或者小根堆,堆里面的数不是有序的,只是保证了根都是最小值或者最大值
9、哈希
开放寻址法和拉链法,一般情况$O(1)$,但是可以卡到$n^2$,尽量少用,是个概率算法
字符串哈希一般取$131$,$99$的概率不会碰到重复值
10、树状数组
可以在$O(log(n))$的时间复杂内修改和查询一个区间的值
11、线段树
可以实现单点,区间的修改和查询
有一个扩展的扫描线的应用,可以查询区域面积(长方形)
12、权值线段树
可以把一个区间分段,在区间长度$O(log(n))$下,维护一个区间的出现的树
13、可持久化线段树
存下每一个线段树的版本可以查询区间的第k小值
14、平衡树(treap)
插入数值 $x$
删除数值 $x$(若有多个相同的数,应只删除一个)
查询数值 $x$ 的排名(若有多个相同的数,应输出最小的排名)
查询排名为 $x$ 的数值
求数值 $x$ 的前驱(前驱定义为小于 $x$ 的最大的数)
求数值 $x$ 的后继(后继定义为大于 $x$ 的最小的数)
最主要的两个操作就是$split$(分裂)和$merge$(合并),可以按照权值分裂,也可以按照数的个数来分裂
15、AC自动机
相当于$kmp$的扩展用法,$kmp$是一个模式串匹配一个字串,$AC$自动机是一个模式串匹配一堆字串
$AC$自动机的有一个常数优化做法是$trie$图,时间复杂度是$O(n)$的
16、splay
17、树套树
18、块状链表
19、莫队
暴力区间查询的优化算法,通过分块将左端点分块,每次
左端点
块内移动不超过$n^{1 \over 2}$时间复杂度,左端点
块间移动总个数不超过$n^{1 \over 2}$块,右端点
每一移动不超过$n$,时间复杂度为$O(n ^{3 \over 2})$
20、树链剖分
21、动态树
22、DLX之精确覆盖问题
23、DLX之重复覆盖问题
24、左偏树
25、后缀数组
26、后缀自动机
27、点分治
28、点分树
29、CDQ分治
30、仙人掌
三、搜索与图论
$BFS$用于求最小值,第一次到达即为最小值
1、dfs & bfs
树的深度遍历、宽度遍历、字典序、$N$皇后等…
2、拓扑排序
判断是否有环
3、最短路算法
(1) $Dijkstra$:$n^2$ 算法就算起点$s$到终点$e$的距离 可以用堆优化加到$O(nlog(n))$
(2) $bellman-ford$: $n * m$ 用来做有边数限制的最短路,$m$为最短路
(3) $spfa$: 可以用来求最短路,可以判断负环,一般时间复杂度为$O(n * logn)$,最差为$O(n * m)$,$v$被更新的条件是$u$被更新
(4) $Floyd$: 现学的唯一一个多源最短路算法
4、最小生成树
(1) $Prim$: $n^2$的时间复杂度,和$Dijkstra$非常像
(2) $Kruskal$: $O(nlog(n))$ 因为要排序
5、染色法判定二分图
没有单数环
6、匈牙利算法
二分图的最大匹配
7、双端队列bfs
用于边权为0和1的最短路算法
8、Flood Fill(走迷宫类型)
在线性时间内找到某个点的连通块
9、用bfs走最短路
bfs具有当每个点的距离相等时,第一次搜到就是最近点
四、数学知识
五、动态规划
1、背包问题
有 N 件物品和一个容量是 V 的背包。每件物品只能使用次数在每个题目不一定。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
2、线性DP
数字三角形,最长上升子序列,最长公共子序列,最短编辑距离啥的
3、区间DP
三层循环,第一层为长度,第二层为枚举区间,第三层枚举分界点
4、单调队列优化DP
5、斜率优化DP(凸包优化DP)
维持好一个斜率的关系就好
六、贪心
1、区间问题
可根据区间左端点或右端点排序,贪心的选择,使其得到想要的结果
2、Huffman树
合并果子问题,把一个问题分成多个子问题,子问题达到最优解时,证明两个子问题的最优解相加就是问题的最优解
3、绝对值不等式
货仓选址问题,在多个位置之间选择一个位置,使得所有地址到达此位置之和最小
4、推公式
考虑两个位置交换前和交换后,对其他位置的价值不产生影响,考虑交换前后最优解