随缘更新,希望能帮到你,不过肯定能帮到我就是了。
\(\LaTeX\) 写的不是很严谨,其中的 “\(=\)” 具体是等于还是赋值就自己悟吧。
不知道该怎么归类的算法
二分
对具有单调性的东西快速查找合法边界,\(O(log_n)\),模板,oiwiki。
二分查找
对具有单调性的数组操作,每次以 \(mid = {l+r\over 2}\) 作为边界将搜索范围缩小 \(len\over 2\),细节非常多。
二分答案
如果答案具有单调性(有一个明确的“合法 & 不合法”的分界点,一侧所有都合法另一侧所有都不合法),就对答案进行二分,直到找到最小(最大)的合法答案。
数据结构
栈和队列太简单不想写。
并查集
快速查询两个点之间的连通性,连通块个数与大小,复杂度不会算,模板,oiwiki。
记录每个点的父亲,初始每个点的父亲都是自己,合并时将一个点的祖宗的父亲从自己设置为另一个点的祖宗,查询联通性时查询祖宗是否相等,初始连通块个数为 \(n\),每合并一次连通块个数 \(-1\),连通块大小在合并时从被合并的集合加给合并的集合。
前缀和与差分
oiwiki
前缀和
快速查询离线数组区间和,初始化 / 修改 \(O(n)\),查询 \(O(1)\),模板。
已有一个数组 \(arr\),维护一个数组 \(pre\) 满足 \(pre_i = pre_{i-1}+arr_i\)(即“数组的前 \(n\) 项和”), \(\sum_{i=l}^{r}arr_i\) 的答案即为 \(pre_r - pre_{l-1}\)。
差分
快速区间修改,修改 \(O(1)\),查询 \(O(n)\),模板。
对于数组 \(arr\),它的差分数组为 \(s_i=arr_{i}-arr_{i-1}\),对区间 \([l,r]\) 加上一个数字 \(a\) 即为 \(s_l = s_l+a,s_r = s_{r+1}-a\),查询时对 \(s\) 做一遍前缀和即可。
哈希表,堆
我不会。
链式前向星
存图用的,模板。
我也不知道这么写为什么对。
图论
DFS
我不会。
BFS
无边权时查找达到某个状态(点)的最少步骤(最短路径),oiwiki图论,oiwiki搜索。
设定好(可以是多个)初始状态,维护一个队列,将所有初始状态压入队列,每次拿出队头,遍历所有这个队头可以扩展到的状态并压入队列,因为没有边权所以 \(dist_j = dist_t + 1\),如果 \(dist_j \ne 0\) 即这个点被搜过,跳过即可。
没找着我写的模板,所以不放。