复习随笔

复习

配合yizimi的板子库食用效果更佳。

前言

高中过后一直没有复习,大一要打天梯赛时才想起来复习。这个是个人的算法复习过程,尽量按照顺序进行复习,主要顺序是按照我自己的板子库的顺序复习。也算是对板子库的一个解释吧。

一、数论

1.快速幂

主要的思路就是分治,当幂数过大时,一般采用幂数2进制寻找幂数底数相乘。时间复杂度\(O(logn)\)

2.欧拉函数

欧拉函数\(\varphi(x)\) 返回的是小于x的自然数中与x互质的数的个数,我们有:

\[\varphi(x) = x * \prod_{i = 1}^{n} (1 - p_i) \]

一般利用费马小定理用于求逆元。

3.乘法逆元(线性求逆)

线性求逆的推导:

\(i\)在模\(p\)意义下的逆元为\(inv[i]\),设 \(k *i + r = p\), 所以 \(k* i + r \equiv 0 (mod \ p)\),移项得 \(k *i \equiv -r (mod \ p)\) ,则 \(\frac{1}{i} \equiv -\frac{k}{r} (mod\ p)\) ,则 \(\frac{1}{i}\)\(inv[i]\) ,即 \(inv[i] \equiv k - k* inv[r] (mod\ p)\) ,因为\(r < i\) 所以可以递推。

4.线性筛素数

(1)埃式筛法

不是理论上的\(O(n)\),时间复杂度是\(O(nloglogn)\),因为\(\lim_{n \to \infty}loglogn = c\) 而且其常数较小,写起来思路较简单,故仍被广泛利用。主要思路是排除合数,未被标记的数即为素数

(2)欧拉筛法

理论上真正的\(O(n)\)算法,是从欧拉筛法的基础上只被它的最小质因子筛选一次,避免筛选重复。

5.扩展欧几里得

证明:
假设有$$ax_1 + by_1 = gcd(a, b)$$成立,则由欧几里得算法得:$$gcd(a, b) = gcd(b, a\ mod\ b)$$又有:$$bx_2 + (a\ mod\ b)y_2 = gcd(b, a\ mod\ b)$$则合并等式得:$$ax_1 + by_1 = bx_2 + (a\ mod\ b)y_2$$

\[a\ mod\ b = a - \lfloor a/b \rfloor*b \]
\[ax_1 + by_1 = ay_2 + b*(x_2-\lfloor a/b \rfloor)y_2 \]

最后有

\[x_1 = y_2 \\ y_2 = x_2 - \lfloor a/b \rfloor y_2 \]

因为\(gcd(a, 0) = a\),即在$ b=0$ 时有 \(x = 1, y = 0\)
然后回推即可。

6.单个数求逆元

在同余的情况下,相除x和相乘x的逆元是等价的。当然,同余是不可能去除一个数x,我们就去乘其逆元。一般运用费马小定理,或线性求逆,或扩展欧几里得算法来计算。

7.矩阵加速

利用矩阵乘法的特性和其矩阵快速幂的特性来加速递推式的递推,不过要求线性递推,可以将\(O(n)\)优化成\(O(logn)\)

8.整除分块

很少用到这个知识,就是当进行整除的时候,总有一个区间整除一个数的时候答案相同,也包括根号等计算,可以用此信息来缩小计算时间。

9.博弈论

大坑未填,只会一个计算方法,不知道原理

二、图论

1.并查集

并查集通过记录父亲节点来确定两个数字是否在一个集合,可以通过链表的方法,记录的父亲关系更全面,或者用路径压缩,更快的确定二者所在的集合是否相同。时间复杂度一般为\(O(\alpha(n))\)。对于合并,可以采用放在小子树的方法来缩短树高,也可以用随机合并的玄学方法来进行合并,不会被卡。毕竟你也不知道会怎么合并

2.Kruskal算法(克鲁斯卡尔算法, 最小生成树算法)

主要思想是贪心算法,可以将每一条边按长度进行排序,然后采用并查集来查询和合并贪心的找最短的长度的边进行合并,注意不能连接已经在一个集合中的点了。
理论时间复杂度为\(O(mlogm)\)

3.Dijkstra算法(单源最短路算法)

主要使用DP思想。主要的思路是松弛操作,也就是

\[dis[v] = dis[x] + w \]

我们每次寻找最短的dis[x]进行更新,可以运用优先队列优化,时间复杂度\(O(nlogn)\),也可以用线段树维护最短的点,时间复杂度相同,就是空间占的较大。

4.SPFA算法(单源最短路径算法)

传说中已经死了的算法,但是SPFA还是有很大的用途,来源于Bullman Ford算法,就是每次更新松弛一个距离,就将这个距离放入队列,然后以便通过这个点松弛其他的点。时间复杂度\(O(me)\)(实际是\(O(玄学)\)

SPFA用于求负环,网络最大流,最小费用最大流等等,所以人们仍然没有放弃使用这个算法。

5.Floyd算法(多源最短路径)

通过枚举第一个点,第二个点,和其中经过的第三个点,将每两个点的最短路径松弛出来,时间复杂度\(O(n^3)\)

6.二分图染色

二分图染色是一种用来判断给定图是否为二分图的方法,在图上不停的BFS或DFS,并进行染色,保证相邻两点颜色一定不同。

一般会结合DP进行考察,一般结合DAG上的推论来考察。

本部分参考关于二分图染色的几点总结

7.拓扑排序

采用BFS的方法,将节点按照BFS的顺序排序,并可同时进行出度和入度的计算。

8.tarjan求强联通分量

在有向图中,强联通指两个节点可以互通,若一个图中的所有点都可互通,那么这个图叫做强联通图。我们在一个有向图中,寻找极大的强联通子图的大小就是强联通分量。

tarjan基于DFS,其中用\(dfn[i]\)来作为时间戳(被搜到的次序),一旦某个点被DFS到,这个时间戳就不再改变,而\(low[i]\)指在该子树中,且仍在栈里的最小时间戳,像是确立了一个关系,\(low[i]\)相同的点在同一个强联通分量中。

首先从每个没有记时间戳的点开始DFS,我们根据\(1 - N\)的顺序来进行,所以我们回溯的时候\(low[]\)记录路径上最小的时间戳,来确定强联通分量。

时间复杂度\(O(n)\)

9.树分治

(1)点分治

点分治是处理树上路径的工具,点分治的精髓是将一颗树拆分成许多棵子树处理,并不断进行。

我们分治的方法是从树的重心开始分(这样的话时间复杂度会降低到\(O(logn)\)

求解树的重心的方法:
更新\(sze[i]\)表示以i为根节点的子树的节点数量(即子树大小),\(maxp[i]\)表示i节点为根的子树中的最大子树,在DFS中的回溯中进行DP,求maxp的时候需要用到容斥原理

先对当前的节点进行更新答案,然后进行分治下方节点答案,此中用容斥定理来除去不合理的答案,……

(挖坑待填)

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-02 15:22
中北大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议