PCCA筆記 - HackMD

# PCCA筆記 \# 暴力演算法 NCTU_Aether \- 暴力解決一切 \- 除了時間複雜度跟空間複雜度 \-\-\-\- \## Overview \- 基本工具 \- DFS \- BFS \- 時間複雜度與剪枝 \- 圖論的DFS \- 其他 \-\-\-\- \### 開始之前... 如果有任何問題，歡迎隨時打斷我們 \-\-\- \## 基本工具 \- 迴圈 \- 遞回 \-\-\-\- \### 迴圈(for, while) 使用C的for或while來遍歷所有可能、結果簡單直觀，但無法容易地寫樹的分歧 \-\-\-\- \### 遞迴函數呼叫自己。 example 階乘： <img src ="http://www.flag.com.tw/db/preview/images/F2733\_2\_C.jpg" height =450\\> \-\-\-\- ```c++ // 迴圈 // fac(x) = 1\*2\*...*x int fac_loop(int x){ int result = 1; for(int i = 1; i <= x; i++) result *= i; return result; } // 遞迴 // fac(0) = 1 // fac(x) = x * fac(x - 1) int fac(int x){ if(x == 0) return 1; else return x * fac(x - 1); } ``` \-\-\-\- \### 例題 \-\-\-\- \### GCD(最大公因數) 我們可以透過輾轉相除法來尋找最大公因數 <img src = "https://upload.wikimedia.org/wikipedia/commons/e/e2/Euclidean\_algorithm\_252\_105\_animation_flipped.gif" height = 500 /> \-\-\-\- ``` int gcd(int a, int b) { if(b == 0) return a; else return gcd(b, a % b); } ``` \-\-\-\- \### 快速冪考慮一個int x，我想要算$x^n \\mod m$ $x^{2k} = (x^k)^2\\mod m$ $x^{2k+1}=x^{2k}*x\\mod m$ ```c++ int power(int x, int n, int m){ if(n&1) return power(x,n-1,m)*x%m; return power(x*x%m,n/2,m); } ``` \-\-\-\- \### 全排列根據數字大小或字典序的關係，找出所有從小到大的排列 2, 9, 7 的全排序： 2, 7, 9 2, 9, 7 7, 2, 9 7, 9, 2 9, 2, 7 9, 7, 2 \-\-\-\- \- 迴圈：使用next_permutation，它會依據字典序找到下個排列情況，如果找不到回傳0 ```c++ vector<int> arr; void printAll(){ sort(arr.begin(),arr.end()); do{ for(int i=0;i<arr.size();++i) printf("%d ",arr\[i\]); puts(""); } while(next_permutation(arr.begin(),arr.end())); } ``` \-\-\-\- \- 遞迴 ```c++ vector<int> arr; vector<int> prefix; void printAll(int begin, int end){ if(end-begin<=0){ for(int i=0;i<arr.size();++i) printf("%d ",arr\[i\]); puts(""); } else for(int p=begin;p<end;++p){ swap(arr\[begin\],arr\[p\]); printAll(begin+1,end); swap(arr\[begin\],arr\[p\]); } } ``` \-\-\-\- \### 全組合給一個非空集合，印出所有可能的非空子集 \-\-\-\- 可以利用位元運算實作： $\\{2, 7, 9\\}$的所有非空子集： $1 \\mapsto_b 001 \\mapsto \\{2\\}$ $2 \\mapsto_b 010 \\mapsto \\{7\\}$ $3 \\mapsto_b 011 \\mapsto \\{2, 7\\}$ ... $6 \\mapsto_b 110 \\mapsto \\{7, 9\\}$ $7 \\mapsto_b 111 \\mapsto \\{2, 7, 9\\}$ \- 如果集合長度64以內，可以直接壓縮在unsigned long long裡面 \-\-\-\- \- 迴圈 ```c++ vector<int> arr; void printAll(){ int n = arr.size(); //0<n<=64; for(unsigned long long i=(1<<n)-1;i;--i){ for(int j=0;j<arr.size();++j) if(i&(1<<j)) printf("%d ",arr\[j\]); puts(""); } } ``` \-\-\-\- \- 遞迴 ```c++ vector<int> arr; vector<int> prefix; void printAll(int begin, int end){ if(end-begin<=0){ for(int i=0;i<prefix.size();++i) printf("%d ",prefix\[i\]); puts(""); } else{ prefix.push_back(arr\[begin\]); printAll(begin+1,end); prefix.pop_back(); printAll(begin+1,end); } } ``` \-\-\- \## DFS(depth-first search) 深度優先搜索也可以使用stack(後進先出)實作。這邊以遞迴為主。複雜度 O(V + E) <img src="https://upload.wikimedia.org/wikipedia/commons/7/7f/Depth-First-Search.gif" width = 400> \-\-\-\- \### 例題 \-\-\-\- \### 狀態DFS 狀態DFS是針對某些抽象的狀態移轉進行DFS 可以透過紀錄哪些狀態出現過，來避免重複搜索。有些題目不常出現重複情況時，可不紀錄。 \-\-\-\- 考慮狀態是一個int，int有兩種移轉可以做$f(x)=x^2$以及 $g(x) = 2x+1$; 今天給定狀態起點u，終點v，且v > u > 1，我們想要找到任一轉移路徑(如果存在) $u\\mapsto u\_1\\mapsto u\_2,...,u_k\\mapsto v$ \-\-\-\- 若 u = 10, v = 42，就能透過dfs找到其路徑。 !\[\](https://i.imgur.com/D6lfmAL.jpg) \-\-\-\- ```c++ inline int f(x){ return x*x;} inline int g(x){ return 2*x+1;} vector<int> stk; void dfs(int u, int v) { stk.push_back(u) if(u==v){ for(int i=0;i<stk.size();++i) printf("%d ",stk\[i\]); puts(""); } else if(u<v){ dfs(f(u),v); dfs(g(u),v); } stk.pop_back(); } ``` \-\-\-\- \### 算面積下面是一個10x10的圖，"."為空格，"#"為障礙物，問s所在的區域面積為多少。 ``` .......... ..#....... .#s#...... #..#...... ...###.... .....#.... ######.... .......... .......... .......... s = (2, 2) ``` \-\-\-\- 方法：利用遞迴尋找鄰近非障礙物點，每找到一點，將面積加一，直到遍歷完整個區域。 ```c++ char graph\[10\]\[10\]; // input int ans = 0; // answer void dfs(int cur\_x, int cur\_y) { if(cur\_x < 0 || cur\_x >= 10 || cur\_y < 0 || cur\_y >= 10) return; if(graph\[cur\_x\]\[cur\_y\] == '#') return; ans += 1; graph\[cur\_x\]\[cur\_y\] = '#'; int dx\[4\] = {1, 0, -1, 0}; int dy\[4\] = {0, 1, 0, -1}; for(int i = 0; i < 4; i++) { int new\_x = cur\_x + dx\[i\]; int new\_y = cur\_y + dy\[i\]; dfs(new\_x, new\_y); } return; } ``` \-\-\- \## BFS(Breadth-first search) 廣度優先搜尋一般使用queue(先進先出)實作。可以拿來取代一些dfs。複雜度 O(V + E) <img src="https://upload.wikimedia.org/wikipedia/commons/5/5d/Breadth-First-Search-Algorithm.gif" width = 400/> \-\-\-\- \### 狀態BFS 同樣考慮兩種轉移$f(x), g(x)$，我們要用BFS記錄起點$u$到終點$v$的一條最短路徑，這時候，我們建立一個查詢結構，紀錄每個點是由哪個點而來此地假設轉移值域都小於N \-\-\-\- ```c++ extern int f(int); extern int g(int); extern int N; int bfs(int u, int v){ vector<int> intro(N,-1); vector<bool> vis(N,false); queue<int> que; que.push(u); while(que.size()){ int cur = que.front(); que.pop(); if(cur==v) break; int nxt = f(cur); if(!vis\[nxt\]){ vis\[nxt\] = true; que.push(nxt); } nxt = g(cur); if(!vis\[nxt\]){ vis\[nxt\] = true; intro\[nxt\] = cur; que.push(nxt); } } vector<int> stk; for(int p=v;p!=-1;p=intro\[p\]) stk.push_back(p); while(stk.size()){ printf("%d ",stk.back()); stk.pop_back(); } } ``` \-\-\-\- \### 尋找最短路徑下圖為一個10x10的格子圖，'.'為空格，'#'為障礙，給定一起點s,終點t，求兩點最短路徑長。 ``` s......... .#######.. .......#.. .#..#..#.. .####..#.. .#t.#..#.. ......... .######... .......#.. ........#. s = (0, 0), t = (2, 2) ``` \-\-\-\- 方法：我們可以利用BFS搜尋，並記錄每點的路徑長，直到找到終點，並印出他的路徑長 ```c++ #include<queue> #include<iostream> using namespace std; struct tri{ int x, y, n; }; int main() { char g\[10\]\[10\]; for(int i = 0; i < 10; i++) for(int j = 0; j < 10; j++) cin >> g\[i\]\[j\]; int sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty; queue<tri> q; q.push((tri){sx, sy, 0}); int ans; while(q.size() != 0) { tri tmp = q.front(); q.pop(); int x = tmp.x, y = tmp.y, n = tmp.n; if(g\[x\]\[y\] == '#') continue; g\[x\]\[y\] = '#'; if(x == tx && y == ty) { ans = n; break; } int dx\[4\] = {1, 0, -1, 0}; int dy\[4\] = {0, 1, 0, -1}; for(int i = 0; i < 4; i++) { int new\_x = x + dx\[i\], new\_y = y + dy\[i\]; if(new\_x >= 10 || new\_x < 0) continue; if(new\_y >= 10 || new\_y < 0) continue; q.push((tri){new\_x, new\_y, n + 1}); } } cout << ans << endl; } ``` \-\-\- \## 時間複雜度暴力演算法雖然能解決很多問題，但其時間複雜度可能相當的差 \-\-\-\- 譬如：費氏數列 F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2) 如果直接寫出 ```g++ int F(int n) { if(n == 0 || n == 1) return n; else return F(n - 1) + F(n - 2); } ``` \-\-\-\- <img src = "https://www.cs.cmu.edu/~adamchik/15-121/lectures/Recursions/pix/fib.bmp" width = 500 /> 其時間複雜度是O(F(n))，如果 n = 30， F(n) = 832040 算起來相當耗時。 \-\-\-\- 在競賽中就很可能因為演算法的複雜度太高，導致TLE。為了避免TLE，我們就需要減少時間複雜度，加速演算法。而其方法有很多，有剪枝或DP...等等，像是費氏的算法就可以用DP(動態規劃)來加速。 \-\-\-\- ```g++ int F(int n) { int fib\[n + 1\]; fib\[0\] = 0; fib\[1\] = 1; for(int i = 2; i <= n; i++) fib\[i\] = fib\[i - 1\] + fib\[i - 2\]; return fib\[n\]; } ``` 如果你不重複計算已經算過的值，這樣時間複雜度就會被降到O(n)了。這部分會在之後的DP課程上有更多的補充。 \-\-\-\- 其實透過遞迴快速冪我們能做出更快的作法，考慮Fibonacci Squence $f\_n = f\_{n-1}+f_{n-2}$ 我們有 $\\begin{pmatrix} f\_n \\\ f\_{n-1} \\end{pmatrix} = A \\begin{pmatrix} f_{n-1} \\\ f_{n-2} \\end{pmatrix}= A^{n-1}\\begin{pmatrix} f_{1} \\\ f_{0} \\end{pmatrix}$ 其中$A = \\begin{pmatrix} 1 & 1 \\\ 1 & 0 \\end{pmatrix}$ 套用剛剛的快速冪算法可以快速算出$f_n$，複雜度是$O(\\log n)$ \-\-\-\- ```g++ struct Matrix A{ int a,b,c,d; // a b // c d Matrix operator*(Matrix const& r)const; Matrix(int a, int b,int c,int d); }; Matrix pow(Matrix& A, int e) { if(e & 1) return pow(A, e - 1) * A; else return pow(A * A, e / 2); } int F(int n) { Matrix A(1, 1, 1, 0); return pow(A, n).b; } ``` \-\-\-\- \### 剪枝剪枝是減少暴力演算法複雜度的主要方法之一。在演算法進行中，如果遇到在做下去也不會得到結果的分支時，就不在需要向下做了。 \-\-\-\- \#### 八皇后 !\[\](http://7vzmyh.com1.z0.glb.clouddn.com/blog-eight\_queen\_chessborad.png) \-\-\-\- 剪枝的經典題。一個8x8的棋盤上，皇后能攻擊上下左右及對角線的敵人。問有幾種排法能排出8個皇后同時在棋盤上，而不能互相攻擊到。 \-\-\-\- 如果窮舉所有可能再做驗證，總共要驗證C(64, 8) = 4426165368個可能。會消耗相當大的時間。 \-\-\-\- 如果你有做一些觀察的話，根據規則，在同一行，同一列放皇后是不符合結果的， \-\-\-\- 所以你只需要考慮有同一行或列僅有一個皇后的情況。這樣就只剩8!種可能，在進行驗證，就不會消耗太多時間。如果你再考慮對角線的話，又更能減少複雜度。 \-\-\- \## 圖的DFS \-\-\-\- \### 建圖輸入N, M代表點的數量跟邊的數量，點從0 ~ n-1，接下來M行，每行有s, t，代表起點與終點。邊是雙向的。 \-\-\-\- ```c++ vector<vector<int> > adjList; int main() { int n, m; cin >> n >> m; adjList.resize(n); for(int i = 0; i < m; i++) { int s, t; cin >> s >> t; adjList\[s\].push_back(t); adjList\[t\].push_back(s); } } ``` \-\-\-\- 考慮一張有向圖用鄰接串列紀錄，如何做DFS呢？這邊用DFS印出某個點可以到的所有其他點 \- 遞迴 ```c++ vector<vector<int> > adjList; vector<int> vis; void dfs(int v){ vis\[v\] = 1; printf("%d\\n",v); for(int i=0;i<adjList\[v\].size();++i){ int nxt = adjList\[v\]\[i\]; if(!visit\[nxt\]) dfs(nxt); } } ``` \-\-\-\- \- 利用stack(std::vector)後進先出的特性 ```c++ vector<vector<int> > adjList; void dfs(int v){ vector<int> vis(adjList.size(),0); vector<int> stk(1,v); vis\[v\] = 1; while(stk.size()){ int cur = stk.back(); stk.pop_back(); printf("%d\\n",cur); for(int i=0;i<adjList\[cur\].size();++i){ int nxt = adjList\[cur\]\[i\]; if(vis\[nxt\]) continue; vis\[nxt\] = 1; stk.push_back(nxt); } } } ``` \-\-\-\- \### BFS \- 利用queue先進先出的特性 ```c++ vector<vector<int> > adjList; void bfs(int v){ vector<int> vis(adjList.size(),0); queue<int> q; q.push(v); vis\[v\] = 1; while(stk.size()){ int cur = q.front(); q.pop(); printf("%d\\n",cur); for(int i=0;i<adjList\[cur\].size();++i){ int nxt = adjList\[cur\]\[i\]; if(vis\[nxt\]) continue; vis\[nxt\] = 1; q.push(nxt); } } } ``` \-\-\- \## 其他 \### 雙向BFS(Meet-in-the-Middle) 有時候做BFS，產出的BFS tree太大，這時候如果我們有BFS的起點終點，可以從兩頭做BFS讓它們在中間相遇，兩端產生的BFS tree深度約是原本的一半，所以樹的大小會變成原本的$\\tilde O(\\sqrt{n})$階 \-\-\-\- <img src ="https://infoarena.ro/blog/meet-in-the-middle?action=download&file=12fig26.gif&safe_only=true" height = 600/> \-\-\-\- 考慮某張無權無向圖用鄰接串列紀錄，輸入兩點$u, v$，輸出最短路徑長度 ```c++ vector<vector<int> > adjList; int sortestPath(int u, int v){ int n = adjList.size(); queue<int> que\[2\]; vector<int> len\[2\] = {vector<int>(n,0),vector<int>(n,0)}; vector<int> vis\[2\] = {vector<int>(n,0),vector<int>(n,0)}; que\[0\].push(u); que\[1\].push(v); vis\[u\] = 1, vis\[v\] = 1; for(int p=0;que\[p\].size();p=!p){ pair<int,int> cur = que\[p\].front(); que\[p\].pop(); for(int i=0;i<adjList\[cur.first\].size();++i){ int nxt = adjList\[cur.first\]\[i\]; if(vis\[p\]\[nxt\]) continue; if(vis\[!p\]\[nxt\]) return len\[p\]\[nxt\]+len\[!p\]\[nxt\]+1; que\[p\].push(nxt); vis\[p\]\[nxt\] = len\[cur\]+1; } } return -1; } ``` \-\-\-\- \### 分塊暴搜對於數據規模$n$的問題有時候可以拆分成$\\sqrt{n}$個$\\sqrt{n}$大小的小塊解決 \-\-\-\- !\[\](https://i.imgur.com/sO30zDL.jpg) \-\-\-\- 考慮輸入一條長度$n=10000$的正整數序列$a$ 每個query給定$i, j$，輸出$\\max{a\[i:j\]}$ 那麼建立一個summary array $mA\[i\] = \\max{\\{a\[j\]:i\\sqrt{n}\\leq j<(i+1)\\sqrt{n})\\}}$ 可以有單次查詢$O(\\sqrt{n})$的效率 \-\-\-\- ```c++ int arr\[10000\]; int mA\[100\]; const int sqtn = 100; void init(){ memset(arr,0,sizeof(mA)); for(int i=0;i<sqtn;++i) for(int j=0;j<sqtn;++j){ mA\[i\] = max(arr\[i*sqtn+j\],mA\[i\]); } } int getMax(int from, int to){ //\[from,to) int out = 0; for(int base=0,i=0;base<to;++i,base+=sqtn){ if(base+sqtn<=from || to<=base) continue; if(from<=base && base+sqtn<=to) out = max(out, mA\[i\]); else for(int j=0;j<sqtn;++j){ int idx = base+j; if(from<=idx && idx<to) out = max(out, arr\[idx\]); } } } ``` \-\-\- \## Q&A

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.