---
title: 競程演算法與資料結構
---
<font color=#ff1010>部分內容尚未完成，此筆記是用來記錄到目前為止我學會或已知的演算法或資料結構。</font>
# **標準函式庫 STL**
## **priority_queue**
## **set**
## **multiset**
與set用法一樣但是能夠插入多個相同的資料。
* multiset::lower_bound()
* multiset::upper_bound()
## **map**
## **bitset**
* bitset::count()
回傳 bitset 序列中位元為1的數量。
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
bitset<60> bs;
bs|=25//11001
cout<<bs.count()<<endl;
//輸出：3
}
```
* bitset::any()
如果 bitset 序列中有任一位元為1則返回 True，否則返回 False。
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
bitset<60> bs;
cout<<bs.any()<<endl;
//輸出：0
bs|=25//11001
cout<<bs.any()<<endl;
//輸出：1
}
```
* bitset::none()
如果 bitset 序列中的所有位元都為0則返回 True，否則返回 False。
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
bitset<60> bs;
cout<<bs.none()<<endl;
//輸出：1
bs|=25;//11001
cout<<bs.none()<<endl;
//輸出：0
}
```
# **排序演算法 Sorting Algorithm**
## <font color=#aaffcc>**泡沫排序法 Bubble Sort**</font>
時間複雜度： $O(n^2)$
空間複雜度： $O(1)$
```cpp=
//由小排到大
void Bubble_Sort(vector<int> &arr,int len){
for(int a=0;a<len-1;a++){
for(int b=0;b<len-a-1;b++){
if(arr[b]>arr[b+1])swap(arr[b],arr[b+1]);
}
}
}
```
## <font color=#aaffcc>**選擇排序法 Selection Sort**</font>
時間複雜度： $O(n^2)$
空間複雜度： $O(1)$
```cpp=
//由小排到大
void Selection_Sort(vector<int> &arr,int len){
for(int a=0;a<len;a++){
int min_ele=arr[a],pos=a;
for(int b=a+1;b<len;b++){
if(arr[b]<arr[a]){
min_ele=arr[b];
pos=b;
}
}
swap(arr[a],arr[pos]);
}
}
```
## <font color=#aaffcc>**插入排序法 Insertion sort**</font>
時間複雜度： $O(n^2)$
空間複雜度： $O(1)$
```cpp=
//由小排到大
void Insertion_Sort(vector<int> &arr,int len){
for(int a=1;a<len;a++){
int temp=arr[a];
int j=a;
while(j>0&&arr[j-1]>temp){
arr[j]=arr[j-1];
j--;
}
arr[j]=temp;
}
}
```
## <font color=#aaffcc>**合併排序法 Merge Sort**</font>
時間複雜度： $O(n\log{n})$
空間複雜度： $O(n)$
```cpp=
//由小排到大
vector<int> Merge_Sort(vector<int> arr){
if(arr.size()==1)return arr;
vector<int> l,r;
for(int a=0;a<arr.size();a++){
if(a<arr.size()/2)l.push_back(arr[a]);
else r.push_back(arr[a]);
}
l=Merge_Sort(l);
r=Merge_Sort(r);
vector<int> sortedarr;
int l_pos=0,r_pos=0;
while(l_pos<l.size()&&r_pos<r.size()){
if(l[l_pos]<=r[r_pos])sortedarr.push_back(l[l_pos++]);
else sortedarr.push_back(r[r_pos++]);
}
while(l_pos<l.size())sortedarr.push_back(l[l_pos++]);
while(r_pos<r.size())sortedarr.push_back(r[r_pos++]);
return sortedarr;
}
```
## <font color=#aaffcc>**快速排序法 Quick Sort**</font>
時間複雜度：
* 平均：$O(n\log{n})$
* 最差：$O(n^2)$
空間複雜度： $O(\log{n})$
```cpp=
void QuickSort(vector<int> &arr,int l,int r){
if(l>=r)return;
int key=arr[l];
int lidx=l,ridx=r;
while(lidx<ridx){
while(arr[ridx]>=key&&lidx<ridx)ridx--;
while(arr[lidx]<=key&&lidx<ridx)lidx++;
swap(arr[lidx],arr[ridx]);
}
swap(arr[l],arr[lidx]);
QuickSort(arr,l,lidx-1);
QuickSort(arr,lidx+1,r);
}
```
## <font color=#aaffcc>**堆排序法 Heap Sort**</font>
時間複雜度：$O(n\log{n})$
空間複雜度：$O(1)$
```cpp=
void adj(vector<int> &arr,int root,int n){
int temp=arr[root],child=root*2+1;
while(child<n){
if(child+1<n&&arr[child+1]>arr[child])child+=1;
if(temp>=arr[child])break;
arr[(child-(child%2==0))/2]=arr[child];
child=child*2+1
}
arr[(child-(child%2==0))/2]=temp;
}
void HeapSort(vector<int> &arr){
for(int a=(arr.size()-1)/2;a>=0;a--)adj(arr,a,arr.size());
for(int a=arr.size()-1;a>=0;a--){
swap(arr[0],arr[a]);
adj(arr,0,a);
}
}
```
## <font color=#aaffcc>**基底排序法 Radix Sort**</font>
時間複雜度：$O(n\log_r{k})$，$r$ 為基底、$k$ 為 $arr$ 中最大的數字位數
空間複雜度：$O(n+k)$
```cpp=
void radixsort(vector<int> &arr,int r,int bksize){
int bucket[bksize][arr.size()][2],radix=1;
vector<vector<int>> idx(bksize,vector<int>(2,0));
while(true){
for(int a=0;a<arr.size();a++){
int i=abs(arr[a])/radix%r,p=(arr[a]>=0);
if(!p)i=9-i;
bucket[i][idx[i][p]++][p]=arr[a];
}
int arridx=0;
bool isfinish=false;
for(int a=0;a<2;a++){
if(idx[0][1]+idx[9][0]==arr.size())isfinish=true;
for(int b=0;b<bksize;b++){
for(int c=0;c<idx[b][a];c++){
arr[arridx++]=bucket[b][c][a];
}
idx[b][a]=0;
}
}
if(isfinish)break;
radix*=r;
}
}
```
# **搜尋演算法 Searching Algorithm**
## <font color=#aaffcc>**二分搜尋法 Binary Search**</font>
```cpp=
int Binary_Search(vector<int>& arr,int l,int r,const int find_ele){
//一開始傳進來的r為arr的size-1
if(l>r)return -1;
int mid=(l+r)/2;
if(arr[mid]==find_ele)return mid;
else if(arr[mid]<find_ele)return Binary_Search(arr,mid+1,r,find_ele);
else return Binary_Search(arr,l,mid-1,find_ele);
}
```
## <font color=#aaffcc>**倍增法二分搜**</font>
```cpp=
int Binary_Search(vector<int>& arr,const int find_ele){
int start=0,step=arr.size()-1;
while(step>0){
if(start+step<arr.size()&&arr[start+step]<=find_ele)start+=step;
else step/=2;
}
return start;
}
```
# **字串處理演算法 String Algorithms**
## <font color=#aaffcc>**字典樹 Trie**</font>
* 主要結構
```cpp=
struct trie{
trie* next[26]={nullptr};//如果字典範圍是小寫英文字母
int prefixCount=0;//以這個節點為前綴的字串數量
int endCount=0;//字串結尾判斷
};
trie *root=new trie();
```
* 插入字串 $O(len(str))$
```cpp=
void insert(string str){
trie *current=root;
for(int a=0;a<str.length();a++){
if(current->next[str[a]-'a']==nullptr){
current->next[str[a]-'a']=new trie();
}
current=current->next[str[a]-'a'];
current->prefixCount++;
}
current->endCount++;
}
```
* 查詢字串 $O(len(str))$
看題意決定回傳型態,這裡當作題目要求輸入有沒有出現過查詢的字串
```cpp=
bool find(string str){
trie *current=root;
for(int a=0;a<str.length();a++){
if(current->next[str[a]-'a']==nullptr)return false;
current=current->next[str[a]-'a'];
}
return true;
}
```
* 從某個前綴開始的字串總數 $O(len(str))$
```cpp=
int startWith(string str){
trie *current=root;
for(int a=0;a<str.length();a++){
if(current->next[str[a]-'a']==nullptr)return 0;
current=current->next[str[a]-'a'];
}
return current->prefixCount;
}
```
## <font color=#aaffcc>**Z Algorithm**</font>
* 演算法目的：在一個文本(Text)當中找到某個段落(Pattern)的次數或位置
* 時間複雜度： $O(n+m)$，$n$ 為Text的長度、$m$ 為Pattern的長度
要找到所求的段落位置首先需要先找到此演算法主要的核心 $Z$ 陣列，$Z$ 陣列的內容存取的是對於整個文本 $T$ 的每個後綴和的段落 $P$ 的最大共同前綴長度。
在找最大共同前綴長度之前可以先將文本 $T$ 和段落 $P$ 用一個從沒出現過的字元合併變成 $P?T$ 然後再做最大共同前綴。
例如：文本( $aabaabcaab$ )、查詢段落( $aabc$ )產生的 $Z$ 陣列如下
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| $a$ | $a$ | $b$ | $c$ | $?$ | $a$ | $a$ | $b$ | $a$ | $a$ | $b$ | $c$ | $a$ | $a$ | $b$ |
| 15 | 1 | 0 | 0 | 0 | 3 | 1 | 0 | 4 | 1 | 0 | 0 | 3 | 1 | 0 |
在 $Z$ 陣列內數值和段落長度一樣的位置就是段落出現的位置。
用暴力法求 $Z$ 陣列的話時間複雜度為 $O(nm)$。
可以使用兩個變數 $L$、$R$ 維護來降低時間複雜度至 $O(n+m)$。
$L$ 和 $R$ 代表的是一個區間，$R$ 是從 $L$ 之後和 $P?T$ 開頭重疊的最後一個位置。
在最一開始 $L=R=0$。
考慮以下情況：
1. 目前查找 $Index>R$
代表目前 $Index$ 還沒有和 $P?T$ 前綴子字串比較過，所以要重置 $L$、$R$ 的位置為 $Index$，然後開始尋找從 $L$ 開始 $R$ 可以往後擴增多少位置(最長共同前綴)。
$Z[Index]$ 的值會等於 $R-L+1$
2. 目前查找 $Index \le R$
代表目前 $Index$ 和 $P?T$ 前綴子字串比較過所以目前 $Index$ 在 $LR$ 區間內，由前面比較的資訊可以得知 $P?T[L...R]$ 會等於 $P?T[0...R-L]$，那麼$P?T[Index...R]$ 也會等於 $P?T[Index-L...R-L]$，所以我們要再考慮以下兩種情況：
1. $Z[Index-L]<R-Index+1$
如果 $Z[Index-L]$ 的數值小於 $R-Index+1$ 代表目前的 $Index$ 後面不會有更多的空間能夠使最長共同前綴變長，所以 $Z[Index]$ 會等於 Z[Index-L]
2. $Z[Index-L]\ge R-Index+1$
如果 $Z[Index-L]$ 的數值大於等於 $R-Index+1$ 代表目前的 $Index$ 後面有可能會有更多的空間能夠使目前 $Index$ 下的 $Z$ 值(最長共同前綴)變得更大所以要更新 $LR$ 區間，$L$ 更新為 $Index$，然後從原本的 $R$ 開始比較還能往後擴增多少位置(最長共同前綴)
* 一般版 Code
```cpp=
void ZFunction(string text,string pattern){
string str=pattern+'?'+text;
int Z[str.length()];
Z[0]=str.length();
int L=0,R=0;
for(int Index=1;Index<str.length();Index++){
if(Index>R){
L=Index;
R=Index;
while(str[R-L]==str[R])R++;
R--;
Z[Index]=R-L+1;
}
else{
if(Z[Index-L]<R-Index+1)Z[Index]=Z[Index-L];
else{
L=Index;
while(str[R-L]==str[R])R++;
R--;
Z[Index]=R-L+1;
}
}
}
}
```
* 簡化版 Code
```cpp=
void ZFunction(string text,string pattern){
string str=pattern+'?'+text;
int Z[str.length()];
Z[0]=str.length();
int L=0,R=0;
for(int Index=1;Index<str.length();Index++){
if(Index>R||Z[Index-L]>=R-Index+1){
if(Index>R)R=Index-1;
L=Index;
while(str[R+1-L]==str[R+1])R++;
Z[Index]=R-L+1;
}
else Z[Index]=Z[Index-L];
}
}
```
## <font color=#aaffcc>**KMP Algorithm**</font>
* 演算法目的：在一個文本(Text)當中找到一個段落(Pattern)出現的次數或位置
* 時間複雜度：$O(n+m)$，$n$ 為Text的長度、$m$ 為Pattern的長度
* Failure Function
Failure Function是KMP Algorithm內的核心概念，用意是利用字串的次長共同前後綴來減少字串比對的操作
以字串 $AABAA$ 為例所形成的Failure Function陣列如下：
| A | A | B | A | A |
|:---:|:---:|:---:|:---:|:---:|
| 0 | 1 | 0 | 1 | 2 |
求出Failure Function的方法也是利用求出Failure Function的過程中得知的資訊來減少時間複雜度。
```cpp=
vector<int> Failure_Function(string pattern){
vector<int> failfunc(pattern.length(),0);
int prefixlen=0,idx=1;
while(idx<pattern.length()){
if(pattern[prefixlen]==pattern[idx]){
prefixlen++;
}
else if(prefixlen>0){
prefixlen=failfunc[prefixlen-1];
if(prefixlen>0)continue;
}
failfunc[idx++]=prefixlen;
}
return failfunc;
}
```
利用已知的資訊(Failure Fucntion)我們可以在每次比對失敗的時候知道下一個比對的位置應該為何者。
```cpp=
int KMP(string text,string pattern){
vector<int> failfunc=Failure_Function(pattern);
int idx=0,int pIdx=0,pCount=0;
while(idx<text.length()){
if(text[idx]==pattern[pIdx]){
idx++;
pIdx++;
}
else if(pIdx>0){
pIdx=failfunc[pIdx-1];
}
else idx++;
if(pIdx==pattern.length())pCount++;
}
return pCount;
}
```
## <font color=#aaffcc>**後綴數組 Suffix Array**</font>
以字串 $ababba$ 而言他的後綴有：$\{\}、\{a\}、\{ba\}、\{bba\}、\{abba\}、\{babba\}、\{ababba\}$
Suffix Array 是一個由字串的所有後綴組成並且排序好的數列。
### <font color=#aaccff>Prefix Doubling Algorithm</font>
* 時間複雜度:$O(n\log{n})，n為字串長度$
* 定義：
1. $Pos$ 為每個後綴開始的位置
2. $Rank$ 為對每一輪排序後對結果離散化的標記
### <font color=#aaccff>DC3 Algorithm</font>
* 時間複雜度:$O(n)，n為字串長度$
*
## <font color=#aaffcc>**自動機 Automaton**</font>
## <font color=#aaffcc>**Manacher's Algorithm**</font>
* 先將查詢字串開頭與結尾與每個字符中間插入一個不會出現的字符成為一個新的字串 $mstr$。(方便處理字串長度為偶數時的中心點位置)
* 定義一個 $LPS$ 陣列，它儲存的內容為以該字符為中心能形成的最長迴文字串半徑。
例如 $acbabeba$ 的 $LPS$ 陣列內容為(有插入不會出現的字符)：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 3 | 0 | 1 | 0 | 5 | 0 | 1 | 0 | 1 | 0 |
如果不利用任何以前所得知的資訊去尋找 $LPS$ 陣列的數值最快速的方法是從目前的 $index$ 向左右去擴展尋找相同的字元增加長度
```cpp=
while(
idx+lps[idx]-1>=0&&
idx-lps[idx]+1<mstr.length()&&
mstr[idx-lps[idx]-1]==mstr[idx+lps[idx]+1]
)lps[idx]++;
```
在只有進行這樣暴力求解的過程中最差的情況會使得時間複雜度變為 $O(n^2)$。( $n$ 為字串長度)
那麼如果我們去考慮以前得知的資訊可以得知，對於一個迴文裡的所有迴文而言它的 $LPS$ 數值會是對稱的(但是還是有其他例外)。
例如：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | 1 | 0 | 3 | | | |
對於以上 $LPS$ 陣列的內容可以得知以 $Index\ 3$是一個半徑長度為3的迴文，既然它的左邊的 $LPS$ 數值為 0、1、0 那麼右邊的 $LPS$ 數值也會是 0、1、0 ，因為對於一個迴文而言它的左右會對稱所以長度會至少相等。
而例外則是左邊的對稱點的 $LPS$ 數值放在目前 $Index$ 會使得範圍超出這個迴文的話則取比較小的數值也就是 $RightBorderIndex-Index$，也就是迴文右邊界減掉目前 $Index$。
右邊界的 $Index$ 則是以 $LPS$ 數值$+Index$ 而定，邊界越右越好。
```cpp=
string Manacher(string &s){
string mstr="#";
for(auto &c:s){
mstr+=c;
mstr+='#';
}
int lps[mstr.length()]={0};
int pCenter=1,rightBorderIdx=2;//目前利用的迴文中心與右邊界
int pos=0,len=1;//查詢到的最長迴文位置與長度
for(int idx=1;idx<mstr.length();idx++){
if(idx<rightBorderIdx)lps[idx]=min(lps[pCenter*2-idx],rightBorderIdx-idx);
else lps[idx]=0;
while(
idx-lps[idx]-1>=0&&
idx+lps[idx]+1<mstr.length()&&
mstr[idx-lps[idx]-1]==mstr[idx+lps[idx]+1]
)lps[idx]++;
//如果找到一個超出右邊界的迴文則替換利用的迴文
if(idx+lps[idx]>rightBorderIdx){
rightBorderIdx=idx+lps[idx];
pCenter=idx;
}
if(lps[idx]>len){
len=lps[idx];
pos=idx;
}
}
return s.substr((pos-len)/2,len);
}
```
# **數論 Mathematics**
## <font color=#aaffcc>**質數篩**</font>
```cpp=
bool not_prime[1000005]
vector<int> prime;
void seive(){
not_prime[1]=true;
for(int a=2;a<1000000;a++){
if(!is_prime[a])prime.push_back(a);
for(int b=0;a*prime[b]<1000000;b++){
not_prime[a*prime[b]]=true;
if(a%prime[b]==0)break;
}
}
}
```
## <font color=#aaffcc>**判斷質數(6n+1方法)**</font>
```cpp=
bool is_prime(int num){
if(num<=1)return false;
if(num==2||num==3)return true;
if(num%2==0||num%3==0)return false;
for(int a=5,gap=2;a*a<=num;a+=gap,gap=6-gap){
if(num%a==0)return false;
}
return true;
}
```
## <font color=#aaffcc>**快速冪 Exponentiation By Squaring**</font>
要快速的運算$\;x^n\;$的數值我們可以將它分解成以下形式
* 若n是偶數：$x^n=(x^{\frac{n}{2}})^2$
* 若n是奇數：$x^n=x\times x^{n-1}$
從上述的分解方式可以將時間複雜度從$\;O(n)\;$縮減成$\;O(\log(n))$
```cpp=
int EXP(int x,int n){
if(n==0)return 1;
if(n%2==0){
int k=EXP(x,n/2);
return k*k;
}
else return x*EXP(x,n-1);
}
```
* 矩陣求冪
例如費氏數列的表示方式可以進行以下的轉換
原費氏數列定義：$f(n)=f(n-1)+f(n-2)$
改為矩陣表示法：$\left[\begin{array}{c}f(n)\\f(n-1)\end{array}\right]=\left[\begin{array}{cc}1 & 1 \\1 & 0\\\end{array}\right]^{n-1} \times \left[\begin{array}{c}f(1)\\f(0)\end{array}\right]$
## <font color=#aaffcc>**擴展歐幾里德算法**</font>
```cpp=
void extgcd(int a,int b,int &x,int &y){
if(b==0){
x=1;
y=0;
}
else{
extgcd(b,a%b,y,x);
y-=(a/b)*x;
}
}
```
## <font color=#aaffcc>**歐拉函數**</font>
求小於等於n的正整數與n互質的數字個數S
公式：$\varphi(n)=\prod^{}_{k=1}{(1-n^k)}$
```cpp=
int phi(int n){
int ans = n;
for(int i=2;i*i<=n;i++){
if(n % i == 0){
ans = ans - ans/i;
while(n % i==0)n /= i;
}
}
if(n > 1)ans = ans - ans/n;
return ans;
}
```
## <font color=#aaffcc>**費馬小定理 Fermat's little theorem**</font>
定義：如果$\;p\;$是質數(或偽質數)且$\;a\;$不為$\;p\;$的倍數則
* $a^{p-1} \equiv 1\mod(p)$
* $a^{p}\equiv a\mod(p)$
## <font color=#aaffcc>**模逆元 Modular Multiplicative Inverse**</font>
定義：當$\;a\;$和$\;p\;$互質模逆元才會存在
若$\;a\;$和$\;p\;$互質則$\;a\;$的模逆元為：$a^{-1}\mod(p)$
如果p為質數，那麼$\;a\;$的模逆元也等於$\;a^{p-2}\mod(p)$
證明：
* 根據費馬小定理：$a^p\equiv a\mod(p)$
* $a^{p-2}\times a^2\equiv a^{-1}\times a^2\mod(p)$
* $a^{p-2}\equiv a^{-1}\mod(p)$
擴展歐幾里德求模逆元：
* 若 $gcd$ 為 $1$ 則模逆元為 $(x+p)\mod(p)$，否則模逆元不存在
## <font color=#aaffcc>**排列組合 Permutation and Combination**</font>
* 史特靈公式 Stirling's formula(求階乘近似值)
$n!\approx\sqrt{2\pi n}(\cfrac{n}{e})^n$
* 排列
$C^n_r=\dfrac{n!}{(n-r)!\times r!}$
* 組合
$P^n_r=\dfrac{n!}{(n-r)!}$
* 重複組合
$H^n_r=C^{n+r-1}_r=\dfrac{(n+r-1)!}{(n-1)!\times r!}$
* 環狀排列組合
不能翻轉(座位)：$\dfrac{n!}{n}$、可翻轉(項鍊)：$\dfrac{n!}{n\times 2}$
## <font color=#aaffcc>**帕斯卡三角形**</font>
行數從 $0$ 開始
* $C^n_r=C^{n-1}_{r-1}+C^{n-1}_{r}$
* 每一行數字的總和 $= \sum^{n}_{k=0}C^n_k = 2^{n}$
## <font color=#aaffcc>**二項式分佈** </font>
$(x+y)^n=C^n_0x^ny^0+C^n_1x^{n-1}y^1+...+C^n_{n-1}x^1y^{n-1}+C^n_nx^0y^n$
## <font color=#aaffcc>**卡特蘭數 Catalan Number**</font>
$C_0=1、C_1=1$
遞迴式：$C_n=C_0\times C_{n-1}+C_1\times C_{n-2}+...+C_{n-1}\times C_0$
一般項公式：$C_n=\dfrac{1}{n+1}\times C^{2n}_{n}=\dfrac{(2n)!}{(n+1)!\times n!}$
## <font color=#aaffcc>**伯恩賽德引理 Burnside's Lemma**</font>
看不懂鳩命~
設 $G$ 是一個有限群，作用在集合 $X$ 上。對每個 $g$ 屬於 $G$ 令 $X^{g}$ 表示 $X$ 中在 $g$ 作用下的不動元素。伯恩賽德引理斷言軌道數（記作 $\vert X/G \vert$）
公式：$\vert X/G \vert=\dfrac{1}{\vert G\vert}\sum_{g\in G}{\vert X^g\vert}$
## <font color=#aaffcc>**波利亞計數定理 Pólya enumeration theorem**</font>
看不懂鳩命~
對於含 $n$ 個對象的置換群 $G$，用 $t$ 種顏色著色的不同方案數為
公式：$l=\dfrac{1}{\vert G\vert}\sum_{g\in G}{t^{c(a_g)}}$
## <font color=#aaffcc>**大數運算**</font>
* 加法
```cpp=
vector<int> Add(vector<int> num1,vector<int> num2){
if(num1.size()<num2.size())swap(num1,num2);
reverse(num1.begin(),num1.end());
reverse(num2.begin(),num2.end());
int carry=0;
for(int a=0;a<num1.size();a++){
int num=num1[a]+num2[a]+carry;
num1[a]=num%10;
carry=num/10;
}
if(carry>0)num1.push_back(carry);
reverse(num1.begin(),num1.end());
return num1;
}
```
* 乘法
```cpp=
vector<int> Multiply(vector<int> num1,vector<int> num2){
reverse(num1.begin(),num1.end());
reverse(num2.begin(),num2.begin());
int dp[num1.size()+num2.size()]={0};
for(int a=0;a<num1.size();a++){
for(int b=0;b<num2.size();b++)dp[a+b]+=num1[a]*num2[b];
}
vector<int> num3;
int carry=0;
for(int a=0;a<num1.size()+num2.size()-1;a++){
int num=carry+dp[a];
dp[a]=num%10;
carry=num/10;
num3.push_back(dp[a]);
}
if(carry>0)num3.push_back(carry);
reverse(num3.begin(),num3.end());
return num3;
}
```
* 大數乘冪
```cpp=
```
* 減法
```cpp=
```
* 除法
```cpp=
```
# **卷積**
## <font color=#aaffcc>**Fast Fourier Transform 快速傅立葉變換(FFT)**</font>
## <font color=#aaffcc>**Number Theoretic Transform 快速數論變換(NTT)**</font>
# **計算幾何**
## <font color=#aaffcc>**向量**</font>
### **內積公式**
* $\vec{u} \cdot \vec{v}=u_1\times v_1+u_2\times v_2$
### **外積公式**
* $\vec{u} \times \vec{v}=u_1\times v_2-u_2\times v_1$
## <font color=#aaffcc>**點線關係公式**</font>
### **斜率**
* $\dfrac{y_2-y_1}{x_2-x_1}$
### **點到點直線距離**
* $\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$
### **點到線直線距離**
### <font color=#aaffcc>**多邊形**</font>
### 鞋帶公式 Shoelace formula
## <font color=#aaffcc>**凸包**</font>
### **Andrew's Monotone Chain**
1. 先將所有點由 $x$ 座標由小到大排序後再將 $y$ 座標由小到大排序
### **Graham's Scan**
## <font color=#aaffcc>**點對演算法**</font>
### **掃描線演算法**
### **分治解法**
### **選轉卡尺**
# **動態規劃 Dynamic Programming**
## <font color=#aaffcc>**路徑問題、計數問題 Staircase Walk**</font>
問題的通常問法：給你大小為$\;n \times m\;$的區域問你從左上到右下只能往右和往下走有幾種走法
題解：建立一個與矩陣大小一樣的dp表，先將第0行與第0列的初始值設定為1，因為只往右和往下走到底只會有一種走法，其餘還沒有數值的dp表內容則會等於上一行和上一列相加的結果
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int y,x;//矩陣大小
cin>>y>>x;
int dp[y][x];
dp[0][0]=1;
for(int a=1;a<x;a++)dp[0][a]=dp[0][a-1];
for(int b=1;b<y;b++)dp[b][0]=dp[b-1][0];
for(int a=1;a<y;a++){
for(int b=1;<x;b++){
dp[a][b]=dp[a-1][b]+dp[a][b-1];
}
}
}
```
此問題變種類型：
1. 路徑上會有障礙物
2. 以特定要求行走路徑(每經過一格會加上特定數值，求極值)
## <font color=#aaffcc>**最大子序列 Maximum Subarray**</font>
題解：目前遇到的數字等於$\;n\;$，若目前數字總和加上$\;n\;$小於$\;n\;$則可以忽略掉前面加總的總和，並重新從$\;n\;$開始加總
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int len;//序列長度
cin>>len;
int num[len],dp[len];
for(auto &a:num)cin>>a;
int ans=max(num[0],0);
dp[0]=num[0];
for(int a=1;a<len;a++){
dp[a]=max(num[a],dp[a-1]+num[a]);
ans=max(dp[a],ans);
}
cout<<ans<<endl;
}
```
## <font color=#aaffcc>**最大子矩陣 Maximum SubMatrix**</font>
題解：可以將此種題型依照最大子序列的思考模式，先求每一列的前綴和，再對每一行取最大子序列
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int y,x;//矩陣的大小
cin>>y>>x;
int arr[y][x];
for(int a=0;a<y;a++){
for(int b=0;b<x;b++){
cin>>arr[a][b];
if(b>0)arr[a][b]+=arr[a][b-1];
}
}
int ans=0;
for(int a=0;a<x;a++){
int dp[y];
for(int b=0;b<=a;b++){
dp[0]=arr[0][a]-(b==a?0:arr[0][b]);
ans=max(ans,dp[0]);
for(int c=1;c<y;c++){
int k=arr[c][a]-(b==a?0:arr[c][b]);
dp[c]=max(dp[c-1]+k,k);
ans=max(ans,dp[c]);
}
}
}
cout<<ans<<endl;
}
```
## <font color=#aaffcc>**最長遞增子序列 Longest Increasing Subsequence**</font>
若推入的數字 $arr[a]$ 大於序列的最後方的數字則直接放入序列後方，
否則替換序列中大於等於 $arr[a]$ 的數字以增加序列的可擴充性。
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int len;//序列長度
cin>>len;
int arr[len];
for(auto &a:arr)cin>>a;
vector<int> dp;
for(int a=0;a<len;a++){
if(dp.size()==0)dp.push_back(arr[a]);
else {
if(arr[a]>dp.back())dp.push_back(arr[a]);
else *lower_bound(dp.begin(),dp.end(),arr[a])=arr[a];
}
}
cout<<dp.size()<<endl;
}
```
## <font color=#aaffcc>**最長回文子序列 Longest Palindromic Subsequence**</font>
dp遞迴式：$\begin{cases}
dp[b+1][b+a-1]+2，\;if\;s[b]=s[b+a]\\
max(dp[b+1][b+a]、dp[b][b+a-1])，otherwise
\end{cases}$
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
int k=s.length();
vector<vector<int>> dp(k,vector<int>(k,0));
for(int a=0;a<k;a++)dp[a][a]=1;
for(int a=1;a<k;a++){
for(int b=0;b+a<k;b++){
if(s[b]==s[b+a])dp[b][b+a]=dp[b+1][b+a-1]+2;
else dp[b][b+a]=max(dp[b+1][b+a],dp[b][b+a-1]);
}
}
cout<<dp[0][k-1]<<endl;
}
```
## <font color=#aaffcc>**最長共同子序列 Longest Common Subsequence**</font>
dp遞迴式：$\begin{cases}
max(dp[a-1][b-1]、dp[a-1][b]、dp[a][b-1])，\;if\;s1[a]=s2[b]\\
max(dp[a-1][b]、dp[a][b-1]，\;otherwise)\\
\end{cases}$
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
string s1,s2;
cin>>s1>>s2;
int dp[s1.length()+1][s2.length()+1];
for(int a=0;a<=s1.length();a++)dp[a][0]=0;
for(int a=0;a<=s2.length();a++)dp[0][a]=0;
for(int a=1;a<=s1.length();a++){
for(int b=1;b<=s2.length();b++){
if(s1[a-1]==s2[b-1])dp[a][b]=max({dp[a-1][b-1]+1,dp[a][b-1],dp[a-1][b]});
else dp[a][b]=max(dp[a-1][b],dp[a][b-1]);
}
}
cout<<dp[s1.length()][s2.length()]<<endl;
}
```
## <font color=#aaffcc>**換幣問題 Coin Changing**</font>
問題的通常問法：給你$\;n\;$種幣值，問你換成$\;m\;$元最少需要有幾枚硬幣
此問題變種類型：
1. 有多少種換法
2. 有多少種排法(硬幣換的順序可以交換)
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,money;//n是錢的種類
cin>>n>>money;
int coins[n];
for(auto &c:coins)cin>>c;
vector<int> dp(money+1,1000000000);
dp[0]=0;
for(int a=1;a<=money;a++){
for(int b=0;b<n;b++){
if(coins[b]<=a)dp[a]=min(dp[a],dp[a-coins[b]]+1);
}
}
cout<<dp[money]<<endl;
}
```
## <font color=#aaffcc>**背包問題 Knapsack Problem**</font>
問題的通常問法：給你$\;n\;$個物品的價值、重量、數量以及你能拿的物品重量上限，問你能取得多大的價值
### **0/1背包**
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;//n=物品數量,k=背包大小
cin>>n>>k;
int price[n],w[n];//price=物品價值、w=重量
for(int a=0;a<n;a++){
cin>>price[a]>>w[a];
}
int dp[n+1][k+1];
memset(dp,0,sizeof(dp));
for(int a=1;a<=n;a++){
for(int b=0;b<=k;b++){
if(b>=w[a])dp[a][b]=max(dp[a-1][b],dp[a-1][b-w[a]]+price[a]);
else dp[a][b]=dp[a-1][b];
}
}
cout<<dp[n][k];
}
```
### **0/1背包問題空間壓縮**
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;//n=物品數量,k=背包大小
cin>>n>>k;
int price[n],w[n];//price=物品價值、w=重量
for(int a=0;a<n;a++){
cin>>price[a]>>w[a];
}
int dp[k+1]={0};
for(int a=1;a<=n;a++){
for(int b=k;b>=0;b--){
if(b>=w[a])dp[b]=max(dp[b],dp[b-w[a]]+price[a]);
}
}
cout<<dp[n][k];
}
```
### **有限背包**
最簡單的做法是把每種物品數量都各做一次 0/1背包，但是這樣時間複雜度會是 $O(NKM)$ 效率極差，所以可以考慮以下優化方式。
* 分堆優化
時間複雜度：$O(NK\log{M})$，$N=$ 物品種類、$K=$ 背包大小、$M=$ 物品數量
``` cpp=
#include<bits/stdc++.h>
#define quick ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
using namespace std;
signed main(){
quick;
int n,limit;//n=物品種類、limit=背包大小
cin>>n>>limit;
int w[n],p[n],cnt[n];
for(auto &a:w)cin>>a;
for(auto &a:p)cin>>a;
for(auto &a:cnt)cin>>a;//每個物品數量
int dp[limit+1]={0};
for(int a=1;a<=n;a++){
int j=1;
while(true){
if(cnt[a-1]<=j&&cnt[a-1]>=0){
j=cnt[a-1];
cnt[a-1]=0;
}
for(int b=limit;b>=0;b--){
if(b>=j*w[a-1]){
dp[b]=max(dp[b],dp[b-j*w[a-1]]+j*p[a-1]);
}
}
if(cnt[a-1]==0)break;
else {
cnt[a-1]-=j;
j*=2;
}
}
}
cout<<dp[limit]<<endl;
}
```
* 單調對列優化
時間複雜度：
### **無限背包**
### **混合背包**
# **離線演算法 Offline Algorithm**
* 在線演算法：每次輸入都會直接給出結果
* 離線演算法：所有輸入讀進來計算後才一次輸出所有結果
## <font color=#aaffcc>**莫隊算法 Mo's Algorithm**</font>
* 演算法目的：用於解決離線區間查詢問題
* 核心概念：將整個區間分割成多個塊優化整體時間複雜度
塊的大小由區間大小($N$)與查詢次數($Q$)決定，根據算幾不等式(窩不會證明:cry:)可以得知塊的大小在 $\frac{N}{\sqrt{Q}}$ 時會有最好的時間複雜度 $O(N\sqrt{Q})$。
對於每次區間查詢左邊界與右邊界會有以下操作：
* 擴展：左邊界或右邊界範圍增加
* 收縮：左邊界或右邊界範圍減少
莫隊算法的主要功用是減少每次區間查詢對於左邊界與右邊界的操作次數。
主要作法是先把每個查尋位置以左邊界所在的塊排序，如果在同一個塊中則以右邊界大小排序。可以發現以這樣的方式排序後的查詢順序可以讓左邊界和右邊每次操作最多只會移動 $2\frac{N}{\sqrt{Q}}$次。
以莫隊算法解區間求和問題：
```cpp=
int n,q,block;
vector<int> arr(200005);
vector<pair<pair<int,int>,int>> qry;
int ans[200005];
void init(){
cin>>n;
for(int a=0;a<n;a++)cin>>arr[a];
cin>>q;
block=n/(max((int)sqrt(q),(int)1));
for(int a=0;a<q;a++){
int l,r;
cin>>l>>r;
qry.push_back({{l-1,r-1},a});
}
}
void mo_slove(){
//分塊排序
sort(qry.begin(),qry.end(),[&](const pair<pair<int,int>,int> p1,const pair<pair<int,int>,int> p2){
if(p1.first.first/block==p2.first.first){
return p1.first.second<p2.first.second;
}
else return p1.first.first/block<p2.first.first/block;
});
int l=0,r=-1,sum=0;
//區間求和操作
for(auto &cal:qry){
while(l>cal.first.first)sum+=arr[--l];
while(r<cal.first.second)sum+=arr[++r];
while(l<cal.first.first)sum-=arr[l++];
while(r>cal.first.second)sum-=arr[r--];
ans[cal.second]=sum;//紀錄答案
}
for(int a=0;a<q;a++)cout<<ans[a]<<endl;
}
```
### **帶修改莫隊**
### **樹上莫隊**
## <font color=#aaffcc>**CDQ 分治法**</font>
### **偏序問題**
# **圖論與樹 Graph Theory And Tree**
## <font color=#aaffcc>圖的表示法</font>
### **相鄰矩陣**
### **相鄰串列**
### **相鄰多元串列**
### **索引表**
## <font color=#aaffcc>**廣度優先搜尋 Breadth First Search(BFS)**</font>
* 演算法主要過程
1. 以queue實作
2. 每次加入節點到佇列後紀錄為已拜訪
3. 一次加入目前查詢節點的所有子節點
4. pop()
* 動畫示意圖
---
---
```cpp=
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> tree{
{1,2},
{3,0},
{0,4},
{1,5},
{2,6,7},
{3,8},
{4},
{4},
{5}
};
int main(){
queue<int> BFS_Queue;
bool findNode[9]={false};
BFS_Queue.push(0);//放入開頭節點
findNode[0]=true;//開頭紀錄為以查詢
while(!BFS_Queue.empty()){
int index=BFS_Queue.front();
cout<<index<<" ";
for(int a=0;a<tree[index].size();a++){
if(findNode[tree[index][a]]==true)continue;
else{
BFS_Queue.push(tree[index][a]);
findNode[tree[index][a]]=true;
}
}
BFS_Queue.pop();
}
//輸出結果：0 1 2 3 4 5 6 7 8
}
```
## <font color=#aaffcc>**深度優先搜尋 Depth First Search(DFS)**</font>
* 演算法主要過程
1. 以stack實作
2. 每次加入節點到堆疊後紀錄為已拜訪
3. 只要目前查詢節點有還沒拜訪過的子節點可以加入堆疊就優先加入
4. 如果沒有則一直pop()到有還沒拜訪過的子節點可以加入為止
* 動畫示意圖
---
---
* 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> tree{
{1,2},
{3,0},
{0,4},
{1,5},
{2,6,7},
{3,8},
{4},
{4},
{5}
};
int main(){
stack<int> DFS_Stack;
bool findNode[9]={false};
DFS_Stack.push(0);//放入開頭節點
findNode[0]=true;//開頭紀錄為以查詢
cout<<0<<" ";
while(!DFS_Stack.empty()){
int index=DFS_Stack.top();
bool findSubNode=false;
for(int a=0;a<tree[index].size();a++){
if(findNode[tree[index][a]]==false){
DFS_Stack.push(tree[index][a]);
findNode[tree[index][a]]=true;
cout<<tree[index][a]<<" ";
findSubNode=true;
break;
}
}
if(findSubNode==false)DFS_Stack.pop();
}
//輸出結果：0 1 3 5 8 2 4 6 7
}
```
深度優先搜尋也是一種遞迴演算法
```cpp=
bool vis[MAXN];
void dfs(int idx){
if(vis[idx])return;
vis[idx]=true;
for(auto &son:G[idx])dfs(son);
}
```
如果是樹的話還有以下不用 $visited$ 的寫法
```cpp=
void dfs(int idx,int pre){
for(auto &son:G[idx])if(son!=pre)dfs(son,idx);
}
```
## <font color=#aaffcc>**拓樸排序 Topological Sort**</font>
* 用途
解決事情先後順序，例如：修課、任務。
先完成某項事情才能完成另一項事情，拓樸排序可以將這些問題完成的先後順序排出來。
也可以判斷一張圖是不是 $DAG$。
* 實作
1. 先計算所有節點的入邊。
2. 將入邊為 $0$ 的節點丟入 $Queue$。
3. 將 $Queue$ 目前處理的節點丟入排序結果。
4. BFS 找到其餘可以丟入 $Queue$ 的節點，在決定可不可以丟入之前先將該節點的入邊數 $-1$，如果入邊數變為 $0$ 則丟入Queue。
5. 如果完成排序後被放入排序結果的節點數量和節點總數不同則代表這張圖不是 $DAG$。
```cpp=
vector<int> node[maxSize],result;
int in[maxSize]={0};
void topologicalSort(int n){//n為節點數
queue<int> q;
for(int a=1;a<=n;a++)if(in[a]==0)q.push(a);
while(!q.empty()){
int cur=q.front();
result.push_back(cur);
q.pop();
for(int a=0;a<node[cur].size();a++){
in[node[cur][a]]--;
if(in[node[cur][a]]==0)q.push(node[cur][a]);
}
}
}
```
## <font color=#aaffcc>**尤拉迴路與路徑 Euler Circuit and Euler Path**</font>
* 定義
在一圖上從起始點經過所有邊各一次後回到起始點稱為尤拉迴路,若不用回到起始點則稱為尤拉路徑。
* 判斷(尤拉迴路)
| 無向圖 | 有向圖 |
|:-------------------------------------------- |:---------------------------------------------------- |
| 圖中所有節點的邊數須為偶數，並且圖需要連通。 | 圖中所有節點的入邊數與出邊數需相同，並且圖需要連通。 |
* 判斷(尤拉路徑)
| 無向圖 | 有向圖 |
|:-------------------------------------------- |:---------------------------------------------------- |
| 圖中所有節點中只有兩個點的邊數<br>為奇數。並且圖需要連通或符合尤拉迴路。| 圖中只有一個節點出邊等於入邊加一，此點為起點。圖中只有一個節點入邊等於出邊加一，此點為終點。並且圖需要連通或符合尤拉迴路。 |
* 無向圖尤拉迴路實作(測試模板題：[**CSES #1691**](https://cses.fi/problemset/task/1691/))
```cpp=
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
vector<int> path;
set<int> G[MAXN];
void Euler(int n){
while(G[n].size()){
int v=*G[n].begin();
G[n].erase(v);
G[v].erase(n);
Euler(v);
}
path.push_back(n);
}
int main(){
int n,m,v,e;
bool edgeck=false;
cin>>n>>m;
for(int a=0;a<m;a++){
cin>>v>>e;
G[v].insert(e);
G[e].insert(v);
}
for(int a=1;a<=n&&!edgeck;a++)if(G[a].size()%2==1)edgeck=true;
if(edgeck)cout<<"IMPOSSIBLE"<<endl;
else {
Euler(1);
if(path.size()<m+1)cout<<"IMPOSSIBLE"<<endl;
else for(auto &p:path)cout<<p<<" ";
}
}
```
## <font color=#aaffcc>**漢米爾頓迴路與路徑 Hamiltonian Circuit and Hamiltonian Path**</font>
* 定義
在一圖上從起始點經過所有點各一次後回到起始點稱為漢米爾頓迴路,若不用回到起始點則稱為漢米爾頓路徑。
無論有向或無向圖漢米爾頓問題都是 $NP$ - $Complete$
* backtracking 解法
時間複雜度: $O(n\times n!)$
單純利用DFS暴力求解所有的可能。
* Dynamic Programming 解法
時間複雜度： $O(n^{2}\times 2^{n})$
定義 $dp[v][S]$ 為對於目前節點為 $v$ 並且已經經過的節點集合 $S$ 而言有幾種方式能到達這個狀態。
對於某一狀態 $dp[A][K]$ 只要節點 $A$ 能到達節點 $B$ 並且 $B \notin$ $K$，則代表可以轉移 $dp[A][K]$ 到 $dp[B][K\cup \{B\}]$。
集合可以用狀態壓縮實作，對於總共有8個節點的$Graph$ 內的一個集合$S\{1,3,5,6,7\}$ 可以表示為 $01110101$。
* 有向圖漢米爾頓路徑實作(測試模板題：[**CSES #1690**](https://cses.fi/problemset/task/1690/))
```cpp
#include<bits/stdc++.h>
#define mod (int)(1e9+7);
using namespace std;
vector<int> G[20];
vector<vector<int>> dp(20,vector<int>(1<<20,0));
bool vis[20][1<<20];
struct E{int v,s;};
void ham(int n){
dp[0][1]=1;
queue<E> q;
q.push({0,1});
while(!q.empty()){
E cur=q.front();
q.pop();
if(vis[cur.v][cur.s]||cur.v==n-1)continue;
vis[cur.v][cur.s]=true;
for(auto &e:G[cur.v]){
int idx=1<<e,nxt=cur.s|idx;
if((cur.s&idx)==idx)continue;
dp[e][nxt]=(dp[e][nxt]+dp[cur.v][cur.s])%mod;
q.push({e,nxt});
}
}
cout<<dp[n-1][(1<<n)-1]<<endl;
}
int main(){
int n,m,v,e;
cin>>n>>m;
for(int a=0;a<m;a++){
cin>>v>>e;
G[--v].push_back(--e);
}
ham(n);
}
```
## <font color=#aaffcc>**最低共同祖先 Lowest Common Ancestor**</font>
* 定義
對於兩個節點往上碰到的第一個相同節點就是他們的最低共同祖先。
* 倍增法求最低共同祖先
1. 先用 $DFS$ 求得所有節點的深度。
2. 建表求得對於節點 $n$ 它範圍內 $2$ 的冪次的所有祖先。
定義 $father[n][k]$ 為對於編號 $n$ 節點往上 $2^k$ 層祖先。
例：$father[n][0]$ 為 $n$ 的父節點。
所以對於 $father[n][k]$ 它會等於 $father[father[n][k-1]][k-1]。$
利用以上資訊對於 $n_1$ 與 $n_2$ 他們的最低共同祖先會由以下方法求得：
1. 先使得 $n_1$ 與 $n_2$ 的高(深)度相同。
2. 高(深)度相同後兩點若一樣則其中一點就是最低共同祖先。
3. 否則兩點盡量往上跳到不是共同祖先的節點。
4. 最後再往上跳一格就是最低共同祖先。
* 倍增法實作
求深度的過程中順便紀錄每個頂點往上一層的父節點。
```cpp=
void dfs(int n,int pre){
if(dep[n]>0)return;
father[n][0]=pre;
dep[n]=dep[pre]+1;
for(auto &son:node[n])dfs(son,n);
}
```
建立祖先表
```cpp=
//頂點數為200000
void build(int n){
for(int a=1;a<20;a++){
for(int b=1;b<=n;b++)father[b][a]=father[father[b][a-1]][a-1];
}
}
```
查詢
```cpp=
int find(int n1,int n2){
if(dep[n1]>dep[n2])return find(n2,n1);
for(int a=19;a>=0;a--){
if(dep[father[n2][a]]>=dep[n1])n2=father[n2][a];
}
if(n1==n2)return n1;
for(int a=19;a>=0;a--){
if(father[n1][a]!=father[n2][a]){
n1=father[n1][a];
n2=father[n2][a];
}
}
return father[n1][0];
}
```
## <font color=#aaffcc>**樹壓平 Euler Tour Of Tree**</font>
* 用途：**動態維護子樹**
* 尤拉序：樹在dfs的過程中拜訪節點的順序
---
---
利用尤拉序可以使得樹上操作變為區間操作問題。
* 例([**CSES #1137**](https://cses.fi/problemset/task/1137))
給你一棵有 $N$ 個節點的有權樹，節點 $1$ 為根節點，有兩種操作：
1. 把節點 $s$ 權重改為 $x$
2. 詢問以 $s$ 為根的子樹權種總和
可以發現對於每一個節點的所有子節點而言它們的進入與離開時間都會包含在子樹的根節點進入與離開時間內。
所以可以利用這些資訊與資料結構(BIT、線段數)使得此問題變成單純的區間問題。
**實作上離開節點時，時間戳記可以不用增加。**
## <font color=#aaffcc>**輕重鍊剖分 Heavy Light Decomposition**</font>
* 用途：**將樹拆分成多個序列**
樹上路徑帶修改問題在使用樹壓平可能會過於複雜或無法求得答案，這時可以考慮使用樹鍊剖分。
* 拆分
```cpp=
int father[maxsize];//每個節點的父節點
int sz[maxsize];//每個節點的子樹大小
int maxson[maxsize];//每個節點的小孩中子樹大小最大的節點
int topf[maxsize];//每個節點所在的鍊的鍊頂
int id[maxsize];//每個節點的時間戳記
```
第一次 $DFS$ 求得以下資訊：
1. 每個節點的子樹大小
2. 每個節點的父節點
3. 每個節點的小孩中子樹大小最大的節點
```cpp=
void dfs1(int n,int pre){
father[n]=pre;
sz[n]=1;
maxson[n]=0;
for(auto &son:tree[n]){
if(son!=pre){
dfs1(son,n);
sz[n]+=sz[son];
//如果目前子節點大於紀錄的最大子樹大小則替換
if(sz[son]>sz[maxson[n]])maxson[n]=son;
}
}
}
```
第二次 $DFS$ 求得以下資訊：
1. 每個節點所在的鍊的鍊頂
2. 每個節點的時間戳記
```cpp=
void dfs2(int n,int top){
topf[n]=top;
id[n]=++t;
upt(t,val[n]);//套上資料結構
//如果這個節點不是葉節點則先往下搜尋擁有最大子樹的子節點
//使得整個鍊的時間戳記連續
if(maxson[n]!=0)dfs2(maxson[n],top);
for(auto &son:tree[n]){
//如果son不是父節點或擁有最大子樹的子節點
if(father[n]!=son&&maxson[n]!=son)dfs2(son,son);
}
}
```
利用這些擁有連續時間戳記的多條鍊再套上能夠維護區間資料的資料結構就能夠方便的解決樹上路徑問題。
例：兩節點路徑上權重總合([**CSES #1138**](https://cses.fi/problemset/task/1138))或兩節點路徑上最大值([**CSES #2134**](https://cses.fi/problemset/task/2134))問題。
## <font color=#aaffcc>**樹上啟發式合併 DSU on Tree**</font>
用途：降低子樹合併時間複雜度
兩個已經有尋訪過的資訊在資料合併上的最佳化作法會是：**小集合併入大集合**
對於兩棵子數在做資料合併時若每次都將比較小的子樹資訊併入比較大的子樹，那麼每次併入大子樹的資訊最多為 $\log{N}$ ，但如果是由大並到小則每次併入的資訊最多為 $N^2$。($N$ 為節點數量)
例：[**CSES #1139**](https://cses.fi/problemset/task/1139)
## <font color=#aaffcc>**圖的連通性**</font>
* 割點(cut vertex)：
對於圖上一點 $v$ ,若把它移除會導致整張圖不連通那麼 $v$ 為割點。
* 橋(bridge)：
對於圖上一邊 $e$ ,若把它移除會導致整張圖不連通那麼 $e$ 為橋。
* 弱連通定義：
若把一張有向圖改為無向圖後此圖的任兩點至少有一條路徑能互相到達。
* 強連通定義：
對於一張圖中的任兩節點 $u$、$v$，若為強連通則 $u$ 能找到一條到達 $v$ 的路徑，$v$ 也能找到一條到達 $u$ 的路徑。
* BCC 雙連通分量定義：
* SCC 強連通分量定義：
有向圖上強連通的極大導出子圖(若此子圖包含節點 { $A、B、C$ } ，則此子圖必須包含在原圖上節點 { $A、B、C$ } 互相連接的邊)稱為強連通分量。
### <font color=#aaccff>**Tarjan's Algorithm**</font>
### <font color=#aaccff>**Kosaraju's Algorithm**</font>
定義 $G'$ 為 $G$ 的反圖(所有邊的方向相反)，無論是在 $G$ 或 $G'$ 上的 $SCC$ 均會相同。
對於圖上的 $SCC$ 而言他們互相連結的邊如果可以形成環則這些被環相連的 $SCC$ 等同於一個 $SCC$ 。
對於一個有向無環圖而言圖上的每一個節點相當於一個 $SCC$(因為如果沒有環他們一定到不了所有節點)，此時只要把拓樸順序逆著 $DFS$ 一次就能夠找到所有的 $SCC$，但是不一定每張有向圖都是無環。
對於兩節點 $x、y$ 而言，若 $x$ 可以到達 $y$ ，但 $y$ 卻無法到達 $x$ ，則這兩點可以肯定不會是在同一個 $SCC$ 內。可以發現如果直接對 $G$的 $DFS$ 序 逆著$DFS$ 的話是有可能會把 $y$ 和 $x$ 放進同一個 $SCC$ 內，但是如果是對於 $G'$ 的話則不會。
可以肯定如果是對 $G'$ 找 $DFS$ 序，那麼 $x$ 一定會出現在 $y$ 的前面(因為在 $G'$上 $x$ 到不了 $y$)。
利用 $G'$ 的 $DFS$ 序逆著 $DFS$ 拜訪 $G$ 就能夠分割一張圖上所有的 $SCC$，因為逆著拜訪時 $y$ 會先被拜訪而 $y$ 到不了 $x$。
* 先求出 $G'$ 上的 $DFS$ 序(拜訪時間大到小)
* 在對 $G'$ 上的 $DFS$ 序逆序拜訪 $G$ 上的節點
- 實作
```cpp=
#include<bits/stdc++.h>
#define quick ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define MAXN 100005
using namespace std;
vector<int> G[MAXN],RG[MAXN],ord;
int scc[MAXN]={0},sccid=0;
bool vis[MAXN]={false};
void r_dfs(int n){//在G'求DFS序
vis[n]=true;
for(auto &e:RG[n])if(!vis[e])r_dfs(e);
ord.push_back(n);
}
void dfs(int n){//在G尋找SCC
scc[n]=sccid;
for(auto &e:G[n])if(!scc[e])dfs(e);
}
void Kosaraju(int n){
for(int a=1;a<=n;a++)if(!vis[a])r_dfs(a);
for(int a=n-1;a>=0;a--){
if(scc[ord[a]]==0){
sccid++;
dfs(ord[a]);
}
}
}
int main(){
quick;
int n,m,v,e;
cin>>n>>m;
for(int a=0;a<m;a++){
cin>>v>>e;
G[v].push_back(e);
RG[e].push_back(v);
}
Kosaraju(n);
cout<<sccid<<endl;//sccid=SCC 數量
}
```
## <font color=#aaffcc>**匹配 Matching**</font>
### 二分圖匹配 Bipartite Matching
## <font color=#aaffcc>**最短路徑 Shortest Path**</font>
### <font color=#aaccff>**Floyd Warshall Algorithm**</font>
* 演算法目的
求無負權邊多源最短路徑。
* Floyd也算是一種動態規劃演算法。
```cpp=
vector<vector<int>> Floyd(int n,vector<vector<int>> graph){
for(int a=0;a<n;a++){
for(int b=0;b<n;b++){
for(int c=0;c<n;c++){
graph[b][c]=min(graph[b][c],graph[b][a]+graph[a][c]);
}
}
}
return graph;
}
```
### <font color=#aaccff>**Dijkstra Algorithm**</font>
* 演算法目的
求無負權邊單源最短路徑。
* Dijkstra Algorithm 也算是一種貪心演算法。
* 演算法步驟
1. 找出源點到其他點的距離當中最短且尚未被查詢過的點
2. 對該點進行鬆弛(詳細情況在底下的Code，簡單來說就是把到另一個點的路徑變短)
3. 將該點紀錄為查詢過
4. 重複以上步驟直到所有點都被查詢過
```cpp=
#define inf 1000000000
vector<int> Dijkstra(int n,int m,vector<vector<int>> graph){
vector<int> dis(n,inf);
dis[0]=0;
bool booked[n];
while(true){
int min_path=inf,root=-1;
for(int a=0;a<n;a++){
if(booked[a]==false&&dis[a]<min_path){
min_path=dis[a];
root=a;
}
}
if(root==-1)break;
booked[root]=true;
for(int a=0;a<n;a++){
if(dis[a]>dis[root]+graph[root][a]){
dis[a]=dis[root]+graph[root][a];
}
}
}
return dis;
}
```
* priority queue優化
可以使用priority queue搭配相鄰串列加速演算法效率，用法類似於BFS。
```cpp=
#define inf 1000000000
vector<int> Dijkstra(int n,int m,vector<pair<int,int>> graph[]){
vector<int> dis(n,inf);
dis[0]=0;
bool booked[n]={false};
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
//or priority_queue<pair<int,int>> pq;
pq.push({0,0});
while(!pq.empty()){
pair<int,int> p=pq.top();
int root=p.second;
pq.pop();
if(booked[root]==true)continue;
booked[root]=true;
for(int a=0;a<graph[root].size();a++){
int node=graph[root][a].first,d=graph[root][a].second;
if(dis[node]>dis[root]+d){
dis[node]=dis[root]+d;
pq.push({dis[node],node});
//or pq.push({-dis[node],node});
}
}
}
return dis;
}
```
### <font color=#aaccff>**Bellman-Ford Algorithm**</font>
* 演算法目的
求單源最短路徑(可以有負權邊)。
* Bellman-Ford 也算是一種動態規劃演算法。
* 鬆弛過程與 Dijkstra 一樣
$n$ 個頂點最多包含 $n-1$ 個邊的路徑所以最多只需要進行 $n-1$ 輪鬆弛，不可能會包含有迴路的路徑，若有負權迴路會形成距離無限小的最短路徑，所以 Bellman-Ford也可以利用這點來判斷一個圖上是否有負權迴路，只需判斷進行到第 $n$ 輪鬆弛時判斷有沒有某一點的路徑比上一輪鬆弛小就可以。
```cpp=
#define inf 1000000000
#define pii pair<int,int>
#define f first
#define s second
//點：n、邊：m
vector<int> BellmanFord(vector<pair<pii,int>> edge,int n,int m){
vector<int> dis(n,inf);
dis[0]=0;
bool ans=false;
for(int a=1;a<=n;a++){
for(int b=0;b<m;b++){
if(dis[edge[b].f.s]>dis[edge[b].f.f]+edge[b].s){
dis[edge[b].f.s]=dis[edge[b].f.f]+edge[b].s;
if(a==n)ans=true;//判斷是否存在負迴路
}
}
}
return dis;
}
```
* SPFA(queue 優化)
可以藉由使用 $queue$ 優化 $bellman$-$ford$。
優化的意義是把每一輪中沒辦法鬆弛的邊忽略掉，而不是暴力的鬆弛所有的邊，使得在沒有負環的情況下快速的找到最佳解。
$queue$ 儲存的資料是要用來鬆弛的節點，對於一個節點而言如果它可以找到能夠鬆弛的點 $A$ 那麼就代表 $A$ 這個點也有機會對它能走訪的其他點進行鬆弛。
```cpp=
#define pii pair<int,int>
#define ff first
#define ss second
#define inf 1e9
vector<int> SPFA(int n,vector<pii> edge[]){
bool inq[n+1]={0};
/*
* 紀錄節點是否進入queue，如果輸入資料有負環或節點能夠自己
* 指向自己的話則不須用這個，但要改成紀錄進入queue的
* 次數否則會鬆弛過多的次數導致tle。
*/
vector<int> dis(n+1,inf);
dis[1]=0;
queue<int> q;
q.push(1);
inq[1]=1;
while(!q.empty()){
int cur=q.front();
q.pop();
for(int a=0;a<edge[cur].size();a++){
if(dis[edge[cur][a].ff]>dis[cur]+edge[cur][a].ss){
dis[edge[cur][a].ff]=dis[cur]+edge[cur][a].ss;
if(!inq[edge[cur][a].ff]){
inq[edge[cur][a].ff]=true;
q.push(edge[cur][a].ff);
}
}
}
inq[cur]=false;
}
return dis;
}
```
### <font color=#aaccff>**A\* Algorithm**</font>
## <font color=#aaffcc>**最小生成樹 Minimum Spanning Tree**</font>
最小生成樹的定義：一張圖上連接所有頂點且權重總和最小的一棵樹。
測試模板題：[**CSES #1675**](https://cses.fi/problemset/task/1675/)
### <font color=#aaccff>**Kruskal's Algorithm**</font>
* 以邊來決定
* 每次加入尚未被選擇並且權重最小的邊
* 加入邊之前先確認會不會形成循環(可用併查集判斷)
- 實作
```cpp=
#include<bits/stdc++.h>
#define MAXN 100005
#define int long long
using namespace std;
struct edge{
int v,e,d;
};
bool cmp(edge e1, edge e2){return e1.d<e2.d;}
int DSU[MAXN];
vector<edge> E;
void init(int n){for(int a=1;a<=n;a++)DSU[a]=a;}
int find(int n){return DSU[n]==n?n:DSU[n]=find(DSU[n]);}
void Union(int n1,int n2){DSU[n1]=n2;}
signed main(){
int n,m,e,v,d;
cin>>n>>m;
init(n);
for(int a=0;a<m;a++){
cin>>e>>v>>d;
E.push_back({e,v,d});
}
sort(E.begin(),E.end(),cmp);
int ec=0,dis=0;
for(int a=0;a<m&&ec<n-1;a++){
int f1=find(E[a].e),f2=find(E[a].v);
if(f1==f2)continue;
Union(f1,f2);
ec++;
dis+=E[a].d;
}
if(ec==n-1)cout<<dis<<endl;
else cout<<"IMPOSSIBLE"<<endl;
}
```
### <font color=#aaccff>**Prim's Algorithm**</font>
* 以點來決定
* 任選一個點當作起點，將他的所有邊加入可選邊並記錄該點已拜訪過
* 選擇可選邊的最近點，將該點的所有邊加入可選邊(邊到達的點不能曾被到訪過)，並且紀錄該點已被拜訪過
* 選擇可選邊之前先確認會不會形成循環(可用併查集判斷)
- 實作
```cpp=
#include<bits/stdc++.h>
#define int long long
#define MAXN 100005
using namespace std;
struct edge{
int v,e,d;
bool operator()(edge e1,edge e2){return e1.d>e2.d;}
};
bool vis[MAXN]={false};
vector<edge> E[MAXN];
int DSU[MAXN];
void init(int n){for(int a=1;a<=n;a++)DSU[a]=a;}
int find(int n){return DSU[n]==n?n:DSU[n]=find(DSU[n]);}
void Union(int n1,int n2){DSU[n1]=n2;}
int Prim(int n,int m){
int ec=0,dis=0;
priority_queue<edge,vector<edge>,edge> pq;
for(auto &e:E[1])pq.push(e);
vis[1]=true;
while(!pq.empty()&&ec<n-1){
edge cur=pq.top();
pq.pop();
int g1=find(cur.v),g2=find(cur.e);
if(g1==g2)continue;
ec++;
dis+=cur.d;
Union(g1,g2);
vis[cur.e]=true;
for(auto &e:E[cur.e])if(!vis[e.e])pq.push(e);
}
if(ec!=n-1)return -1;
else return dis;
}
signed main(){
int n,m,v,e,d;
cin>>n>>m;
init(n);
for(int a=0;a<m;a++){
cin>>v>>e>>d;
E[v].push_back({v,e,d});
E[e].push_back({e,v,d});
}
int ans=Prim(n,m);
if(ans!=-1)cout<<ans<<endl;
else cout<<"IMPOSSIBLE"<<endl;
}
```
### <font color=#aaccff>**Boruvka's Algorithm**</font>
* Prim 和 Kruskal 的混和
* 每回迭代尋找對於每一個節點所在的最小生成子樹可以加入的最小權重邊
* 每次尋找先判斷選擇這條邊會不會形成循環(可用並查集判斷)
* 找到所有可以加入的邊之後再判斷是否被重複選過避免加入相同的邊兩次
- 實作
```cpp=
#include<bits/stdc++.h>
#define MAXN 100005
#define MAXM 200005
#define inf 1e18
#define int long long
using namespace std;
struct edge{int v,e,d;}E[MAXM];
int DSU[MAXN],mindis[MAXN],eid[MAXN];
bool vis[MAXM];
void init(int n){for(int a=1;a<=n;a++)DSU[a]=a;}
int find(int n){return DSU[n]==n?n:DSU[n]=find(DSU[n]);}
void Union(int n1,int n2){DSU[find(n1)]=find(n2);}
signed main(){
int n,m,ans=0,totale=0;
cin>>n>>m;
for(int a=1;a<=m;a++)cin>>E[a].v>>E[a].e>>E[a].d;
init(n);
while(true){
int ec=0;
for(int a=1;a<=n;a++)mindis[a]=inf;
for(int a=1;a<=m;a++){
int n1=find(E[a].v),n2=find(E[a].e),d=E[a].d;
if(n1==n2)continue;
ec++;
if(d<mindis[n1]||(d==mindis[n1]&&a<eid[n1]))mindis[n1]=d,eid[n1]=a;
if(d<mindis[n2]||(d==mindis[n2]&&a<eid[n2]))mindis[n2]=d,eid[n2]=a;
}
if(!ec)break;
for(int a=1;a<=n;a++){
if(mindis[a]!=inf&&!vis[eid[a]]){
Union(E[eid[a]].v,E[eid[a]].e);
ans+=E[eid[a]].d;
totale++;
vis[eid[a]]=true;
}
}
}
if(totale==n-1)cout<<ans<<endl;
else cout<<"IMPOSSIBLE"<<endl;
}
```
## <font color=#aaffcc>**網路流 Network Flow**</font>
* 最大流與最小割問題
### <font color=#aaccff>**Ford Fulkerson Algorithm**</font>
### <font color=#aaccff>**Edmonds Karp Algorithm**</font>
### <font color=#aaccff>**Dinic Algorithm**</font>
# **資料結構 Data Structure**
## <font color=#aaffcc>**併查集 Disjoint Set Union**</font>
* 查詢
```cpp=
int find(int n){
//return node[n]==n?n:node[n]=find(node[n]);
if(node[n]==n)return n;
node[n]=find(node[n]);
return root;
}
```
* 連接任兩個點
```cpp=
void Union(int x,int y){
int rootx=find(x),rooty=find(y);
if(rootx==rooty)return;
node[rootx]=rooty;
}
```
## <font color=#aaffcc>**線段樹 Segment Tree**</font>
### **樹的本體**
```cpp=
vector<int> data(10000);//資料存放
class SegmentTree{
private:
struct Node{
int seg_val;//區間數值
Node* l;//左節點
Node* r;//右節點
int lazy_tag;//用於區間更改
int range;//節點涵蓋範圍長度
};
public:
Node *root;
SegmentTree(){
root=new Node;
l=r=nullptr;
}
void build(int l,int r,Node *node);
int query(int l,int r,int L,int R,Node *node);
void node_update(int l,int r,int pos,int value,Node *node);
void seg_update(int l,int r,int L,int R,int value,Node *node);
};
```
### **建立線段樹**
```cpp=
void SegmentTree::build(int l,int r,Node* node){
if(l==r){
node->seg_val=data[l];
return ;
}
int mid=(l+r)/2;
node->l=new Node;
node->r=new Node;
build(l,mid,node->l);
build(mid+1,r,node->r);
node->seg_val=node->l->seg_val+node->r->seg_val;
}
```
### **區間查詢**
```cpp=
int SegmentTree::query(int l,int r,int L,int R,Node *node){
if(L>r||R<l)return 0;
else if(L>=l&&R<=r)return node->seg_val;
int sum=0;
int mid=(L+R)/2;
sum+=query(l,r,L,mid,node->l)+query(l,r,mid+1,R,node->r);
return sum;
}
```
### **單點修改**
```cpp=
void SegmentTree::node_update(int L,int R,int pos,int value,Node *node){
if(L==R){
node->seg_val=value;
return;
}
int mid=(L+R)/2;
if(pos<=mid)node_update(L,mid,pos,value,node->l);
else node_update(mid+1,R,pos,value,node->r);
node->seg_val=node->l->seg_val+node->r->seg_val;
}
```
### **區間修改**
```cpp=
void SegmentTree::seg_update(int l,int r,int L,int R,int value,Node *node){
if(l==L&&r==R){
node->layz_tag+=value;
return;
}
int mid=(l+r)/2;
if(R<=mid)seg_update(l,mid,L,R,value,node->l);
else if(L>mid)seg_update(mid+1,r,L,R,value,node->r);
else{
seg_update(l,mid,L,mid,value,node->l);
seg_update(mid+1,r,mid+1,R,value,node->r);
}
}
```
## <font color=#aaffcc>**樹狀陣列 Binary Index Tree**</font>
$BIT$ 是一種動態操作前綴合的資料結構，具有常數小與實作容易的優點在一般情況下支援單點修改與區間查詢這兩種操作。
* 初始設定
```cpp=
int node[max_size+1]={0};
```
* 單點修改
```cpp=
void upt(int idx,int val){
while(idx<=max_size){
node[idx]+=val;
idx+=(idx&-idx);
}
}
```
* 區間查詢(前綴查詢)
```cpp=
int query(int idx){
int sum=0;
while(idx>0){
sum+=node[idx];
idx-=(idx&-idx);
}
return sum;
}
```
$BIT$ 的建立只需要把每筆資料 $upt()$ 進去 $BIT$ 即可。
一般情況下用於建立 $BIT$ 的資料會是陣列的內容，若想要使 $BIT$ 支援區間修改的操作則需要將陣列內容轉換成差分數列後再建立成 $BIT$ ，但在這之後 $BIT$ 的區間查詢功能會變為單點查詢。
差分數列範例：
* 原始陣列內容
| 0 | 1 | 2 | 3 | 4 |
|:--- |:--- |:--- |:--- |:--- |
| 5 | 2 | 7 | 4 | 3 |
* 轉換成差分數列後的陣列內容
| 0 | 1 | 2 | 3 | 4 |
|:---:|:---:|:---:|:---:|:----:|
| 5 | -3 | 5 | -3 | -1 |
可以發現差分數列的每一位置的前綴和剛好會等於原始數列同一位置的數值。
如果對於 $(L,R)$ 此區間進行修改對於差分數列會有影響的就只有 $L$ 與 $R+1$ 這兩個位置。
## <font color=#aaffcc>**稀疏表 Sparse Table**</font>
## <font color=#aaffcc>**合併分割型樹堆 Merge Split Treap**</font>
* $Treap = Tree+Heap$
* 一種具有 $BST$ 與 $Heap$ 特性的資料結構
* 自平衡二元搜尋樹
### **結構**
```cpp=
mt19937 randnumber;//c++ 亂數
struct node{
node *l,*r;
int tk,hk;
node(int num){
tk=num;
hk=randnumber();
l=r=nullptr;
}
};
```
### **合併**
### **分割**
### **插入**
### **查詢**
## <font color=#aaffcc>**單調棧 Monotonic Stack**</font>
* 一個單純維持遞增或遞減特性的 Stack
* push()，如果是遞增單調棧只要 top() 大於推進來的元素則一直 pop() 到 top() 小於推進來的元素或 size()=0 才把元素放進 Stack
* pop()，如果是遞增單調棧一定會取得到目前為止最大的元素
## <font color=#aaffcc>**單調隊列 Monotonic Queue**</font>
* 一個單純維持遞增或遞減特性的 Queue
* 可以用 Deque 實作
* push()，如果是遞增單調隊列只要 back() 小於推進來的元素則一直 pop() 到 back() 大於推進來的元素或 size()=0 才把元素放進 Deque
* pop_front()，如果是遞增單調隊列一定會取得到目前為止最大的元素
###### tags:`競程`
Sign in with Wallet
Connect another wallet