跳转至

算法快闪 算法讲解回忆

图论

djstr:vis标记是否用来松弛过。如果是就continue,否则标记为是。只有没用来松弛过的点可以被松弛

spfa:vis标记是否在队列里,如果在就不push

floyd:枚举中转点,再枚举两个点,松弛

kruskal:将边从小到大排序,贪心加入,并查集维护连通性

prim:维护堆中存储当前联通块周边的点到联通块的距离,每次取出最近的更新

字符串

kmp:nxt_i为最长的长度使得其前后缀匹配。nxt是对于子串(即不是主串)而言的。是为了加速再主串上的匹配。

哈希:先考虑数值哈希

acam:

马拉车:

dp

背包:

数位dp:记忆化搜索,在每一位的可选数字里面每一个都搜下去

状态压缩:二进制数记录当前的状态

数据结构

线段树

st表:倍增,数组记录从i往后2^k个数的信息。注意init时是循环顺序!

树状数组:

平衡树:

数论

线性筛:

phi函数:

exgcd:

crt: