---
# System prepended metadata

title: Algo｜競程演算法
tags: [Algo]

---

# 競程演算法

## 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
        - ![](https://i.imgur.com/fWRX1Vc.png)
    - 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



