# 競程演算法
## 5.幾何
- Segment Intersection：$O(nlogn)$
- 從左到右依序將線段的端點 y 座標，加入、刪除 binary search tree
- 每次加入或刪除時，取出該線段和相鄰的線段，用O(1)比對是否相交
- Nearest Pair：$O(nlogn)$
- 先將 y 座標由上到下排好
- 用 x 座標，將點分成 L 和 R 兩份
- 遞迴的找 L 和 R 的最近點對
- 尋找 跨L及R 的最近點對
- $T(n) = 2 T(n/2) + O(n)$
- Convex Hull：$O(nc)$
- 先找到左。每次找斜率最大的線，之後旋轉平面。
- Convex Hull：$O(nlogn)$
- 先找到左，依此點把斜率排序。
- 用 for 迴圈，依序由前 i-1 點的凸包，算出前 i 點的凸包。
- Farthest Pair：$O(nlogn)$
- 先用 $O(nlogn)$ 找出凸包。
- 用旋轉卡尺，找出凸包上最長對角線。$O(n)$
- Plane Sweep
- [多邊形內格子點](https://ideone.com/goTxmy)
- [矩形面積聯集](https://ideone.com/PxG0eb)
- [矩形面積聯集](https://ideone.com/Ysp4ID)
- [半平面交](https://ideone.com/0I1kqY)
- [多邊形內格子面積](https://ideone.com/V2zn5a)
## 6.圖論
- DFS
- 有向圖拓樸排序：finish time 由大到小
- 有向圖強連通分量：先跑 DFS，再依 finish time 由大到小，對 transpose 做 DFS
- 原因：$G$ 上 finish time 最大 component，沒有 incoming edge。
- 連通性
- DFS樹
- 無向圖：樹邊、回邊
- 有向圖：樹邊、回邊、前向邊(forward)、交錯邊(cross)
- 邊雙連通
- 點雙連通
- Minimum Spanning Trees
- Kruskal’s algorithm：排序所有邊
- $O(ElogV)+O(E\alpha(E,V))$ $~~~~~\rightarrow$ sort + union
- union 最小成本的邊對應兩點，直到產生n-1邊
- Prim’s algorithm：找 connected componet 對外最小邊
- 直接做 $O(E+V^2)$、**Fibonacci heap $O(E+VlogV)$**
- 挑選和 V 相鄰的最小鄰居，直到所有點被加入 V
- Borůvka(Sollin)’s algorithm：為每個 connected componet 找最小對外邊
- $O(ElogV)$ $~~~~~\rightarrow$每次$O(E)$，把點數減半
- output 每個 node 最輕的鄰居，並根據此邊 contract node，直到剩下一個 node
- Shortest Path
- Bellman-Ford：O(EV)
- 對每個邊做relaxing，做 n-1 個 phase。
- $d[v]=min(d[v],d[u]+w)$
- 如果第 n 個 phase 仍有更新，表示有負環。
- Lawler：O(E+V)
- **假設圖上無環DAG**，先做 topologic sort。
- 對該順序的點，依序對所有 Outgoing 邊 relax。
- Dijkstra：直接做 $O(E+V^2)$、**Fibonacci heap $O(E+VlogV)$**
- **假設圖上無負邊**
- 挑選剩下點中離 V 最近的點，加入 V
- 加入的同時，更新其他還沒加入 V 的點的值
- All Pair Distance
- Floyd-Warshall
- 
- Johnson
- 1.先用Bellman-Ford，reweight每個點，$h(i)=d(0,i)$
- 2.Dijkstra n次，$O(V)\cdot O(E+VlogV)$
- Matching
## 7.網路流
- 定義：
- $G(V,E)$ 是有向圖，包含源點 $s$、匯點 $t$，每個邊 $e$ 有非負流量限制 $c(e)$
- 滿足條件：
- Capacity：$f(e)\le c(e)$ 對每個邊 $e$
- Conservation：$f^+(v)=f^-(v)$ 對每個點 $v\notin\{s,t\}$
- flow ： $F = f^-(s) = f^+(t)$
- 剩餘網路 $N(f)$ ：滿足以下兩者其一，則剩餘網路上有 $(u,v)$ 邊
- 正流：$c(u,v)-f(u,v)\ge 0$
- 逆流：$f(v,u)\ge 0$
- 增廣路徑： 剩餘網路中 $s$ 到 $t$ 的路徑
- 定理：
- 固定 flow $F$ 下
- 給定任意點集合 $a\in S$，必有 $F = f(S,\bar{S})-f(\bar{S},S)$
- $F = f(S,\bar{S})-f(\bar{S},S)$ 為定值
- $F \le c(S)$ 為定值
- 若 $F = c(S)$，則 $F$ 是 maximum flow，$E(S,\bar{S})$ 是 minimum capacity cut
- 演算法：
- 每次找增廣路徑要 $O(m)$ 時間
- Ford-Fulkerson： $f$ 次 $\rightarrow$ $O(mf)$ (非多項式)
- 每次找任意增廣路徑填滿
- Edmonds-Karp： $mn$ 次 $\rightarrow$ $O(nm^2)$
- 每次找最短增廣路徑填滿
- **Dinic**：
- 先用 BFS 建立分層圖，再一次找到所有最短增廣路
- https://ideone.com/cRRIk1
- **ISAP**：
- 最小費用最大流：
- Ref : http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=f6cdf7ef750d7dc79c7d599b942acbaaee86a2e3e
## 8.DP
- 插頭 DP ： https://blog.csdn.net/sf____/article/details/15026397
## 9.資料結構
- 線段樹
- [BIT](https://ideone.com/g2sb4E)
- [單點修改，區間查詢](https://ideone.com/LZmB8i)
- [區間修改，單點查詢](https://ideone.com/8JvKLS)
- 區間修改，區間查詢：[加值](https://ideone.com/nqVPVx)、[pushdown](https://ideone.com/O9LGNm)
- [TMP](https://ideone.com/kMxXJ3)
- Priority Queue
```clike=
#include <bits/stdc++.h>
using namespace std;
struct node{
int dis, gas, pos;
bool operator<(const node& r) const{
return dis > r.dis;
}
};
int main(){
priority_queue<node> pq;
return 0;
}
```
## 10.組合賽局
- 組合賽局：雙方輪流操作、資訊公開、決定性、有限步結束
- 轉移函數 $F(x,a)=\{y_1,~...~,y_n\}$
- 勝負函數 $S(x,a)\in\{-1,0,1\}$
- 無和局對稱遊戲：$F(x,a)=F(x,b)$ 且 $S(x,a)=S(x,b)$
- 無和局對稱遊戲的任何一個盤面，必定是先手必勝或是後手必勝
- 由終止盤面逆著拓樸順序分析
- Nim：有 N 堆石頭，分別 $a_1,...,a_N$ 顆，兩人輪流拿，每次可以從一堆拿至少一顆，無法拿就輸了
- 特徵值 $X=a_1\oplus a_2\oplus ...\oplus a_N$
- 先手必勝 $\leftrightarrow$ $X\ne 0$
- SG Value
- 終止盤面為 0
- 最小的非負整數，未出現在走到的狀態的 SG Value
- 定理：對稱遊戲中，盤面 $x$ 先手必勝 $\leftrightarrow$ $SG(x)\ne 0$
- $SG \ne 0$ ： 必可以走到 $SG = 0$
- $SG = 0$ ： 無步可走，或是走到 $SG \ne 0$
- 分析 Nim 遊戲的 SG Value：
- 沒有石頭：$SG = 0$
- 一堆 $1$ 顆石頭：$SG = 1$
- 一堆 $2$ 顆石頭：$SG = 2$
- 一堆 $x$ 顆石頭：$SG = x$
- $SG = a_1\oplus a_2\oplus ...\oplus a_N$ (SG 定理)
- 無和局對稱遊戲和：
- `Game sum`：兩獨立對稱遊戲 $x_1,x_2$ 的和 $x_1+x_2$ 代表將兩個遊戲擺在一起的新遊戲，每次只能挑其中一邊動一步。
- `Sprague-Grundy 定理`：獨立無和對稱遊戲 $x_1,x_2$ 中，$SG(x_1+x_2)=SG(x_1)\oplus SG(x_2)$
- 1.盤面 $x_1+x_2$ 不可能走到任何 $SG(x_1)\oplus SG(x_2)$ 的盤面
- 2.盤面 $x_1+x_2$ 可以走到任何 $SG$ 小於 $SG(x_1)\oplus SG(x_2)$ 的盤面
- 非對稱遊戲 Hackenbush
- 題目
- https://codeforces.com/problemset/problem/603/C
- https://codeforces.com/problemset/problem/317/D
- https://codeforces.com/gym/100365/attachments
## 11.String
- 後綴數組：
- KMP ：
- Z-value : https://ideone.com/ZwT1EE
- Z-value Palindrome：
- PalTree：
- SAIS：
- BWT：
- Smallest Rotation：
- Cyclic LCS：
- AC 自動機：
## 12.其他
- Master Theorem : 如果 $T(n)=aT(\frac{n}{b})+f(n)$ 且 $a\ge1 b>1$
- 1.$f(n)=O(n^{log_ba-\epsilon})$ for $\epsilon>0$， 則 $T(n)=\theta(n^{log_ba}).$
- 2.$f(n)=\theta(n^{log_ba})$， 則 $T(n)=\theta(n^{log_ba}).$
- 3.$f(n)=\Omega(n^{log_ba+\epsilon})$ for $\epsilon>0$ 且 $af(\frac{n}{b})\le cf(n)$ for $c<1$ and large n， 則 $T(n)=\theta(f(n)).$
- [Hash](https://codeforces.com/blog/entry/62393) : https://ideone.com/icjSYZ
- Selection : https://ideone.com/Kyh24S
- [c++ regex](https://blog.csdn.net/qq_34802416/article/details/79307102)
- [Python timeit](https://www.itread01.com/content/1541840844.html)
- [c++ __builtin_popcount()](https://www.cnblogs.com/ECJTUACM-873284962/p/7352303.html)
## 參考資料
- [PECaveros/codebook](https://github.com/tzupengwang/PECaveros/blob/master/codebook/codebook.pdf)
- [国家集训队2009论文集](https://github.com/oeddyo/algorithm/tree/master/resources/%E7%89%9B%E4%BA%BA%E8%B0%88ACM%E7%BB%8F%E9%AA%8C(%E5%8C%85%E6%8B%AC%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F%E8%AE%BA%E6%96%87)/%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F%E8%AE%BA%E6%96%87/%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F2009%E8%AE%BA%E6%96%87%E9%9B%86)
- 啟發式合併、平面圖最大團、三分搜、主席樹、Fractional Cascading、模擬退火、burnside
Sign in with Wallet
Connect another wallet