復習
配合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$$
最后有
\[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的時候需要用到容斥原理
先對當前的節點進行更新答案，然后進行分治下方節點答案，此中用容斥定理來除去不合理的答案，……
（挖坑待填）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/211572.html
標籤：其他