# 演算法學習筆記 | by PeterOOO
# 資料結構
> 資料結構可以很大程度地加速演算法
> 資料結構就是為了加速搜尋和有效儲存而生
> 以下為好用的資料結構
| 名字 | 說明 | 注意 |
| -------- | -------- | -------- |
| STL-multiset/set | 內建的二元搜尋樹，用來加速搜尋大於等於k的最小值 | !!! 不可搜尋第k小 |
| STL - map | 可以當字典用的容器，預設為0 | |
| STL-priourity_queue | 在需要大量`pop`的場合比set快 | `pop` 為 $O(1)$，只能存取極值 |
| pbds-tree | 進階的set，可以搜尋第k小 | 常數比set大，通常用treap更靈活 |
| treap 樹堆 | 進階結構，用 `merge-split` 完成所有操作 | 時間複雜度跟樹高相關，通常比 $logn$ 慢一點 |
| segment tree 線段樹 | 一種分治的資料結構，常用於可快速合併的區間問題 | 儲存空間大、常數大 |
| sparse table 倍增表 | 除了做區間問題，還可以做模擬走路 | 空間複雜度大，需 $O(nlogn)$ |
| trie字典樹 | 查詢前綴字串數量 | 基礎版時間複雜度差，<br> 查詢$O(T)$ 插入$O(T)$ T是單次操作的字串長度 |
# 二分搜
:::success
把問題轉換成是否問題
尋找是否交界
:::
:::spoiler 實作
找大於等於目標值的最小值的==位置指標==
```cpp=
lower_bound( v.begin(),v.begin()+n, target )
```
找大於目標值的最小值的==位置指標==
```cpp=
upper_bound( v.begin(),v.begin()+n, target )
```
:::
### 例題
:::info
尋找數列 1,2,4,7,8,9 中大於5的數字的數量
:::
:::success
轉成是否問題 ， if $ai$ > 5 ，如下
:::
| 1 | 2 | 4 | 7 | 8 | 9 |
|--|--|--|--|--|--|
| F | F | F | T | T | T |
用 upper_bound() 得到第4位，可知有 6 - 4 + 1 個
-----
# 遞迴
## 核心精神: 把大問題切成小問題
### 經典1 河內塔問題
:::spoiler 題敘
有3根柱子，共有$n$個環在1號柱，全部移動到3號柱要怎麼移動?
限制:小的環一定要在大的環上面。
一開始所有環上到下由小到大。
:::
### 解法
有n個環要移到3號柱，一定要先把上面n-1個環移動到2號柱
再將底下的一個移到3號柱，再把2號柱的n-1個環移到3號柱
所以:
有2個環時，用3步就可以解決
有3個環時，用7步就可以解決
.......
......
有n個環時，用$2^n-1$步就可以解決
### 實際操作:
$f(n)$ 代表n個環要做$f(n)$ 次
$f(n)$ = $f(n-1)+1+f(n-1)$ 當$(n>=2)$
### 練習題 : [河內之塔-蘿莉塔](<https://tioj.ck.tp.edu.tw/problems/1355>)
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,step;
void solve( int num, int nowstk , int frestk ,int tarstk ){
//數量 現在 空的 目標
if(n==1){
cout<<"#"<<++step<<" :"<<" move the dish from #"<<nowstk<<" to #"<<tarstk<<'\n';
return ;
}
if( num ==2 ){
cout<<"#"<<++step<<" :"<<" move the dish from #"<<nowstk<<" to #"<<frestk<<'\n';
cout<<"#"<<++step<<" :"<<" move the dish from #"<<nowstk<<" to #"<<tarstk<<'\n';
cout<<"#"<<++step<<" :"<<" move the dish from #"<<frestk<<" to #"<<tarstk<<'\n';
return;
}
solve( num-1, nowstk , tarstk , frestk );
cout<<"#"<<++step<<" :"<<" move the dish from #"<<nowstk<<" to #"<<tarstk<<'\n';
solve( num -1 , frestk , nowstk ,tarstk);
return;
}
int main(){
cin >> n;
solve(n,1,2,3);
}
```
:::
----
# 快速冪
:::info
如何計算$a^b$
:::
$\mathcal{O}(b)$作法:
```cpp=
int a = 1;
for( int i =0 ; i<b; i++ ) a*=a
```
運用快速冪做到$\mathcal{O}(\log{} b)$
:::info
根據指數律我們得知 $a^b$ = $a^{b/2}$ * $a^{b/2}$
c++ 的除法在正數時會向0取整數
所以在b是奇數時要多乘一次
ex: $2^7$ = $2^3$ * $2^3$ * 2
:::
遞迴版:
```cpp=
int quick_power( int a , int b ){
if(b==0) return 1;
int tmp = quick_power( a , b/2 );
if( b%2==1 ){
return tmp * tmp * a;
}else{
return tmp * tmp;
}
}
```
迴圈版
```cpp=
int quick_power( int a , int b ){
int k = a,x = 1;
while( b > 0 ){
if( b & 1 ){
x *= k;
}
b>>=1;
k=k*k;
}
return x;
}
```
# 模逆元 | 用費馬小定理
在$a$、$p$互質且$p$為質數時
$a^{p-1} ≡ 1$ $(mod$ $p)$
翻成中文: $a$的$p-1$次方在模$p$時同餘1
如果要計算
$a^{-1} (mod$ $p)$ 直觀，因為$a^{-1}$是有小數點
根據 $a^{-1}$ $(mod$ $p)$ = $a^{-1} \times 1$ $(mod$ $p)$
帶入費馬小定理得: $a^{-1} \times a^{p-1}$ $(mod$ $p)$ $≡$ $a^{-1}$ $(mod$ $p)$
因此
$a^{p-2}$ $(mod$ $p)$ $≡$ $a^{-1}$ $(mod$ $p)$
計算$a$的$p-2$次方即可
# 倍增表 Sparse Table
## 核心精神
先算好跳躍$2^k$步的值
每次詢問從表中組合出答案
## 適用情境
1. 內容不會變
2. 多筆詢問
3. 所求可以從兩區塊快速合併
## 複雜度
時間複雜度:$O(nlogn + qlogn)$
空間複雜度:$O(nlogn)$
### 為什麼要存 nlogn
> 因為我們儲存從i開始往前$2^k$
> 而總結點數為n時， $2^k \le n$ ，因此n個點最多要存`logn` 個結果，總結為`( nlogn )`
## [應用1. 區間最小值 RMQ](<https://cses.fi/problemset/task/1647>)
:::spoiler 題敘
給你一個數列 $a$
有$q$筆詢問，輸出$[a,b]$內最小值
:::
### 建立一個倍增表
我們建立的一個表，
跳躍$2^k$的區間最小 $[ a_x$ , $a_x + 2^k ]$
數列: 1 , 5 , 4 , 2 , 3
| 起點 | 1 | 2 | 3 | 4 | 5 |
| -------- | -------- | -------- |------| ------| ------|
| 跳躍$2^0$區間最小 | 1 | 4 | 2 | 2 | 3 |
| 跳躍$2^1$區間最小 | $min(1,2)$ | $min(4,2)$ | $min(2,3)$ | $min(2,3)$ | $min(3,3)$ |
| 跳躍$2^2$區間最小 | $min(1,3)$ | $min(2,3)$ | $min(2,3)$ | $min(2,3)$ | $min(3,3)$ |
### 實作細節
1. $a_n$跳躍$2^k$ 取最小 = $a_n$跳躍$2^{k-1}$ 和 $a_{n+2^{k-1}}$ 跳躍$2^{k-1}$ 取最小
2. 如果$a_{n+2^{k-1}}$ 超出陣列大小，就用$a_n$
3. $a_n$ 不管跳多遠，最小值一定是$a_n$
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
int st[25][200005];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n,q;
cin >> n >> q;
vector<int> arr(n+1);
for( int i=1; i<=n;i++ ) cin >> arr[i];
for( int i =1; i<n; i++ ) {
if( arr[i] <arr[i+1] ){
st[0][i] = i;
}else{
st[0][i] = i+1;
}
}
st[0][n] = n;
for( int i =1; i<=20; i++ ){
for( int j =1 ; j<=n; j++ ){
int a = st[i-1][j];
int b = st[i-1][min(j+(1<<(i-1)),n)];
if( arr[a]<arr[b] ) st[i][j] = a;
else st[i][j] = b;
}
}
// for( int i =1; i<=n; i++ ){
// for( int j = 0; j<=4; j++ ){
// cout<<st[j][i]<<' ';
// }
// cout<<endl;
// }
while(q--){
int a,b;
cin >> a >> b;
if( a==b ){
cout<<arr[a]<<'\n';
continue;
}
int jump = b-a;
int result = (31 - __builtin_clz(jump));
int j = (1<<result) *( a!=b );
int fin = min(arr[st[result][a]],arr[st[result][max(b-j,1)]]);
cout<<fin<<'\n';
}
}
```
:::
## [應用2. 最近共同祖先 LCA](https://cses.fi/problemset/task/1688)
::: info
1 是董事長，2 ~ n是他的員工，給你2 ~ n的上一級主管(每一人的上一級只有一個)
有Q次詢問: 員工 a 和 員工 b 共同的主管中最低級的主管 ?
:::
在這個題目中，可以知道員工的上下級關係是一棵樹
我們紀錄從每個點往上跳$2^k$的點是誰
:::danger
注意:1的上級我們設為1，以維護不越界
:::
根據精神，建立st表後
如何計算a、b的LCA呢?
有以下兩種情況，我們先來看工具
### subtask : 如何判斷B是否為A的上司之一
導入dfs序的想法，dfs的先後可以判斷是否在同一條上的上級
因為若是B為A的上司，B的進入時間必小於A的進入時間，且B的跳出時間必大於A的跳出時間，也就是說以下判斷是否成立
```cpp!
tin[B] < tin[A] && tin[B] > tin[A]
```
**若 ab互為LCA**
定義 `LCA(a,b)` 為a、b的LCA
此時， LCA(a,b) = a、b中最上層的那個
**若 ab的LCA不是a或b**
LCA(a,b) = 同時是a、b上司的最低點
### 如何找LCA?
假設a有上司 X 和 Y ，且Y比X上級，
`如果Y不是b的上司，那X也不是`
`如果X是b的上司，那Y也是b的上司`
也就是說LCA有**單調性**
只要X不是共同祖先，X的下級一定不是共同祖先
因此我們從a的第$2^{20}$個上司開始嘗試
若上司是共祖，就不跳
若上司不是共祖，就不跳
反覆做20次後，會得到LCA(a,b)下一級
因此要再跳1
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & -x)
#define LL long long
vector<int> tin,tout; //時間戳
int timer =0; //計時器
vector<int> pa; //上一級
vector<vector<int>> G;
void dfs( int a ){
tin[a] = ++timer;
for(auto xx : G[a]){
if( xx == pa[a] ) continue;
dfs( xx );
}
tout[a] = ++timer;
}
int is_anc( int a, int b ){
if( tin[a] <= tin[b] && tout[a] >= tin[b] ){
return 1;
}
return 0;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n,q;
cin >> n >> q;
pa.resize(n+1);
G.resize(n+1);
tin.resize(n+1);
tout.resize(n+1);
vector<vector<int>> st(25,vector<int>(n+1));
pa[1] = 1;
for (int i = 2; i <=n; i++)
{
cin >> pa[i];
G[pa[i]].push_back(i);
}
for (int i = 1; i <=n; i++)
{
st[0][i] = pa[i];
}
//建構倍增表
for (int j = 1; j <=20; j++)
{
for (int i = 1; i <=n; i++)
{
st[j][i] = st[j-1][st[j-1][i]];
}
}
dfs(1);
for (int i = 0; i < q; i++)
{
int a, b;
cin >> a >> b;
if ( is_anc(a,b) ){
cout<<a<<'\n';
continue;
}
if( is_anc(b,a) ){
cout<<b<<'\n';
continue;
}
int nb = a;
for (int j = 20; j >=0; j--)
{
if( !is_anc(st[j][nb] , b) ){
nb = st[j][nb] ;
}
}
cout<<st[0][nb]<<"\n";
}
return 0;
}
```
:::
# 動態規劃
## o/1背包
### 狀態: 前i個物品在重量W下的最大價值
----
## 有限背包
::: spoiler 題敘
#### 給你$n$種物品每一種物品有$C$個，一個物品重$W$、價值$V$
#### 一個背包只能裝重量$T$以下，最大價值是多少?
:::
::: spoiler 限制
#### 所有數字為正整數
#### 0 < $n\times T$ <1e7
#### 0 < C、W、V < 1000
:::
## <font color = #ffda33> 二進制優化 </font>
### 作法:將數量轉成$2^k$相加，然後分開做0/1背包
### 想法?:
### EX : 7 = 1 + 2 + 4
### 或是說任何數字都可以轉成2進制
## <font color = #ffb0c0> 思維陷阱 </font>
思考一下 如果有7個要怎麼試
如果是6個用你的想法會對嗎?
:::warning
### 錯誤想法
如果是7個，那就從$2^0$開始試放1、2、4 ... $C'$，直到 $C'$ > 7
:::
#### 聰明的你一定發現了當$C$是$2^n-1$時以上是對的
#### 但是當$C$=6時 ， 也是試 1、2、4 ，但是實際上是不能做1+2+4的，因為如果$C$不是$2^n-1$，那$C$的二進制一定有至少一位是0。所以全部舉出來會多舉($>C$)。
## 改進想法
### 假設我們有6，只要可以組出3以下的$2^k$+3就能湊出1~6
### 因為每次可以湊出的範圍會$\times 2$如果 現在的範圍$\times 2$ 小於$C$
### {那現在的範圍} + {$C -以前範圍的總和$} 這些數一定可以湊出$C$以下全部的數
### 因為 現在的範圍必 >= $\frac{C}{2}$ 才會不能舉下一個2進位
### 所以$C-$現在範圍的總和這個數 搭配現在已經舉過的$2^k$ 就可以湊出$1$~$C$
### 例題
[Striker的秘密 - EXTREME](<https://tioj.ck.tp.edu.tw/problems/1407>)
----
## 無限背包
#### 練習題: [CSES Dice Combinations](https://cses.fi/problemset/task/1633)
[參考連結](https://hackmd.io/@Paul-Liao/SJHC9SE0u#%E8%83%8C%E5%8C%85%E5%95%8F%E9%A1%8C%E5%80%91)
----
## LIS 最大遞增序列
:::info
對於數列 $a$ 最長的嚴格遞增數列長度為?
:::
:::warning
example
INPUT:
5
1 5 3 6 7
OUTPUT:
4
:::
## 基本想法 時間複雜度$O(n^2)$
對於每個位置我們都試試看把它當成結尾
考量以當前的位置最長可以接誰?
| 位置 | 位置1 | 位置2 | 位置3 | 位置4 | 位置5 |
| ------- | -------- | -------- | -------- |-------- | -------- |
| 值 | 1 | 5 | 3 | 6 | 7 |
| 可接的值 | x | 1 | 1 | 1、3、5 | 1、3、5、6 |
| 最佳長度 | 0+1 | 1+1 | 1+1 | 2+1 | 3+1 |
## 進階想法 時間複雜度$O(nlogn)$
觀察:
對於每個位置為結尾，接在<$a_i$ 的最大值後一定是最好的
因為LIS有單調性，因此用二分搜<$a_i$ 的最大值
我們可以維護一個vector儲存目前看到最好的LIS
過程:
LIS : 1
LIS : 1 5
LIS : 1 3 <-把5換成3
LIS : 1 3 6
LIS : 1 3 6 7
LIS陣列長度為最大LIS長度
----
# 圖論
## 深度優先搜尋DFS
## 廣度優先搜尋BFS
## 進階版BFS - dijkutra 算法
### 限制
- 所有邊非負權重
### 練習題
:::success
**基本題**
[CSES Shortest Routes I](<https://cses.fi/problemset/task/1671/>)
**變化題**
[leetocde 1368 (名字太長)](<https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/description/>)
:::
:::warning
**進階題**
[ABC_E-Flip Edge](<https://atcoder.jp/contests/abc395/tasks/abc395_e>)
[題解](https://hackmd.io/@PeterOOO/Sk5iqWsi1e)
:::
## 最小生成樹
### Kruskal法
從最小的邊 ( a 到 b 長度 c )開始
若 a b 連通，不處理
若 a b 不連通，花費 c 連接a b
### 核心code
Union連接a b
Fa 取得 a b 的區塊，用par存父節點的區塊，初始自己為一區塊
```cpp=
int Fa( int a ){
if( par[a] == a ) return a;
return par[a] = Fa(par[a]);
}
void Union( int a , int b ){
int Fa = F(a);
int Fb = F(b);
par[Fa] = Fb;
}
```
## SCC點強連通分量
:::info
給你一個有向圖(無重邊)，
定義一個SCC為SCC中每個點都可以走到彼此
假設$u$、$v$在一個SCC，
$u$一定可以走到$v$
$v$一定可以走到$u$
試求每個點的SCC編號
:::
### 例題
:::info
[Planets and Kingdoms](https://cses.fi/problemset/task/1683)
:::
## SCC-Tarjan
參考文章:
首先來認識樹的邊 [圖來源](https://determined-wiles-eb7bd3.netlify.app/graph/connectivity/)
* tree edge - dfs下去的邊
* cross edge - 已經走過但是不是父節點
* back edge - 已經走過的父節點
* forward edge - 已經走過的子(孫)節點
tarjan 算法基於 $low$ 和 $dfn$ 計算
$dfn$ : dfs的順序
$low$ : 不經過來的tree edge可走到的最小$dfn$
### 作法
每次dfs將點$u$ push 到stack
初始化 dfn[u]，low[u] = dfn[u]
往下dfs，再依照邊縮緊low[u]
當low[u] = dfn[u]時
u為scc最後一個點，所以從stack中移除u以下的節點。
### 邊的處理
每次dfs的時候
若 v 沒拜訪過 ( tree edge )
dfs(v) 後 low[u] = min( low[u], low[v] )
若 v 有拜訪過
且 v 在stack中( back edge )
low[u] = min( low[u],low[v] )
且 v 不在stack中 ( cross edge )
u、v 必不在同一SCC，不做操作
### 參考程式
:::spoiler code
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & -x)
#define LL long long
vector<vector<int>> G;
vector<int> vis,id,dfn,low,instk;
stack<int> tarstk;
int idx ;
int timer;
void dfs( int a ){
dfn[a] = ++timer;
low[a] = timer;
vis[a] = 1;
instk[a] = 1;
tarstk.push(a);
for(auto xx : G[a]){
if( vis[xx] ){
if( instk[xx] ){
// back edge
low[a] = min( low[a],low[xx] );
}else{
//cross edge
// low[a] = min( low[a],low[xx] );
}
}else{
dfs(xx);
low[a] = min(low[a],low[xx]);
}
}
if( low[a]==dfn[a] ){
++idx;
while( tarstk.top()!=a ){
id[tarstk.top()] = idx;
instk[tarstk.top()] = 0;
tarstk.pop();
}
id[a] = idx;
instk[a] = 0;
tarstk.pop();
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n,m;
idx = 0;
cin >> n >> m;
G.resize(n+1);
dfn.resize(n+1);
low.resize(n+1);
id.resize(n+1);
vis.resize(n+1);
instk.resize(n+1);
for (int i = 0; i < m; i++)
{
int u,v;
cin >> u >> v;
G[u].push_back(v);
}
for (int i = 1; i <=n; i++)
{
if( !vis[i] )
dfs(i);
}
cout<<idx<<'\n';
for (int i = 1; i <=n; i++)
{
cout<<id[i]<<' ';
}
return 0;
}
```
:::
## SCC-Kosaraju
參考文章: [強連通分量](https://hackmd.io/@nehs-iced-7th/HkNfoOMUF?print-pdf#/)
:::success
用兩次DFS
第一次紀錄便歷順序
然後從最後的子節點開始做第二次DFS
:::
### 原理
:::warning
一個SCC中任一點$u$都可以到在SCC中的其他點$v$
同時，$v$ 也可以到 $u$
如下圖有2個SCC
:::
:::warning
對每一個SCC我們可以由DFS把它轉成一棵樹
遍歷成 A->C->B->D->E
:::
觀察正反圖
<figure class="half">
<img src="https://hackmd.io/_uploads/S1fCdh3vkx.png" width =300 height=300>
<img src="https://hackmd.io/_uploads/SJWJ82nP1e.png" width =300 height=300>
</figure>
加上DFS的順序(類似樹壓平)
我們得知對每一塊SCC的根($A$)和最後一個節點($B$)
在圖翻轉後會互換順序
翻轉後DFS走到的點即是同SCC
第一次DFS的遍歷順序
A C B D E
我們會發現 A CB A DE 是一棵樹
而且B、E是最後走到的點
如果從B開始可以走回A、C那BAC是一塊SCC
所以反過來，做DFS
### 作法
1. 第一次DFS儲存每個點的順序
2. 第二次DFS要從最後看到的節點用反向圖DFS、紀錄SCC
3. DFS2中如果下一點沒看過->DFS2
如果看過->它已經是SCC故不理它
:::spoiler code
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & -x)
#define LL long long
int n,m,cnt;
vector<vector<int>> PG,RG;//RG:逆向圖
vector<int> SCC,vis;
vector<int> path; // save dfs1 order
void dfs1( int a ){
vis[a] = 1;
for( int x : PG[a] ){
if( !vis[x] ){
dfs1(x);
}
}
path.push_back(a);
}
void dfs2( int a ){
vis[a] = 0;
SCC[a] = cnt;
for( int x : RG[a] ){
//if haven't vis by dfs2
if( vis[x] ){
dfs2(x);
}
}
}
void kosaraju(){
for( int i =1; i<=n; i++ ){
if( !vis[i] ){
// cout<<i<<" not visit"<<endl;
dfs1(i);
}
}
for ( int j = path.size()-1; j>=0;j-- )
{
int i = path[j];
if( vis[i] ){
++cnt;
dfs2(i);
}
}
cout<<cnt<<'\n';
for (int i = 1; i <=n; i++)
{
cout<<SCC[i]<<' ';
}
cout<<endl;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cnt = 0;
cin >> n >> m;
vis.resize(n+1);
vis.assign(n+1,0);
SCC.resize(n+1);
for( int i =0; i<=n; i++) SCC[i] = 0;
PG.resize(n+1);
PG.assign(n+1,vector<int>({}));
RG.resize(n+1,{});
for( int i = 0; i<m; i++ ){
int a,b;
cin >> a >> b;
PG[a].push_back(b);
RG[b].push_back(a);
}
kosaraju();
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet