算法快闪 算法讲解回忆¶
图论¶
djstr:vis标记是否用来松弛过。如果是就continue,否则标记为是。只有没用来松弛过的点可以被松弛
spfa:vis标记是否在队列里,如果在就不push
floyd:枚举中转点,再枚举两个点,松弛
kruskal:将边从小到大排序,贪心加入,并查集维护连通性
prim:维护堆中存储当前联通块周边的点到联通块的距离,每次取出最近的更新
字符串¶
kmp:nxt_i为最长的长度使得其前后缀匹配。nxt是对于子串(即不是主串)而言的。是为了加速再主串上的匹配。
哈希:先考虑数值哈希
acam:
马拉车:
dp¶
背包:
数位dp:记忆化搜索,在每一位的可选数字里面每一个都搜下去
状态压缩:二进制数记录当前的状态
数据结构¶
线段树
st表:倍增,数组记录从i往后2^k个数的信息。注意init时是循环顺序!
树状数组:
平衡树:
数论¶
线性筛:
phi函数:
exgcd:
crt: