【子柚程式】C++進階講義

# 前言本文章宗旨為帶領已有部分程式基礎的學生，學習更多高深語法、函式、演算法等。此篇文章建議有三級分以上的程度再來閱讀，如果需要基礎篇的同學，不妨參考我的上一篇講義（下方連結），能夠幫你很好的入門C++，最後祝福大家，在這篇講義中能有所收穫。 * 上一篇講義在這裡→[C++新手入門](https://hackmd.io/@37aitHUHRnKghKiwEbbHmg/SJHsKyJkp) # 進階架構對於三級分以上的題目，有些時候會出現TLE（Time Limit Exceeded，超出時間限制）的狀況，而除了程式本身的複雜度之外，有一部分的原因是輸入輸出操作（I/O）的效率過低。為了解決這個問題，我們會在程式碼開頭額外加上這兩行。 ```cpp=1 #include <bits/stdc++.h> using namespace std; //副函式撰寫區 int main() { ios::sync_with_stdio(0); // 關閉 C++ 流和 C 流的同步 cin.tie(0); // 取消 cin 和 cout 的綁定 return 0; } ``` ## ios::sync_with_stdio(0) C++ 的 `iostream`（如 `cin` , `cout`）和 C 標準庫中的 I/O 函數（如 `scanf`, `printf`）默認是同步的，也就是說，在C++中，你仍然可以使用 `scanf`, `printf` 。不過，這樣的同步機制會增加不必要的性能開銷。 ## cin.tie(0) 默認情況下，C++ 的 `cin` 和 `cout` 是互相綁定的。每當你使用 `cin` 進行輸入時，C++ 會自動刷新 `cout` 的緩衝區，以確保所有尚未顯示的內容會在輸入操作之前顯示出來。這樣的設計可以保證輸出和輸入的順序，但同時也會增加性能開銷。 # char/string 在先前的學習中，我們大多數時間都是進行數字運算，而對於字串和字元的學習基本沒有。事實上，字串和字元擁有許多功能，可以幫助我們解決問題，特別是在處理輸入測試資料時。以下是 `char` 和 `string` 的語法。 ```cpp=1 // char(字元) char c1; char c2 = 'R'; // string(字串) string s1; string s2 = "Hello"; string s3 = "World"; string s4 = s2 + " " + s3; // s4="Hello World" ``` 你知道嗎，其實字串就像是字元陣列一樣，是可以用 s[n] 來調用其中一個字元的。 ```cpp string s="Hello World" ``` ![image](https://hackmd.io/_uploads/ry533jR1Jg.png) ## ASCII ASCII（美國標準信息交換碼，American Standard Code for Information Interchange）是一種字符編碼標準，在計算機和通信設備中表示文本和符號。 * 字符集：ASCII 定義了128個字符的集合，包括英文字母（大小寫）、數字、標點符號和控制字符。 * 編碼範圍：每個字符都由一個7位的二進制數表示，範圍從0到127。這使得 ASCII 能夠表示128個不同的字符。 * 數字（48-57）：從0到9。 * 大寫字母（65-90）：從A到Z。 * 小寫字母（97-122）：從a到z。 * 標點符號和其他符號：如逗號、句號、驚嘆號、問號等。 ![image](https://hackmd.io/_uploads/r1jRzo0kkl.png) 圖片來源：https://www.sciencebuddies.org/science-fair-projects/references/ascii-table 這裡我們試著思考一下，如果今天我有一個字串 "123456" ，實際上在 ASCII 中對應到的編號分別是 31 32 33 34 35 36，若我想將這個字串轉換成整數，這時候我該怎麼做呢？答案其實不難，我們只需要將數字平移就好了，原本對應的區間是31～36，只要我通通減去30，區間就會變成1～6了，這時候就和原本的數字相對應了，於是查找表中編號30的字元，發現是 '0' ，至此我們可以將字串轉換成整數的程式碼完成了。 ```cpp=1 string s="123456"; int n=0; // 利用 for 迴圈遍歷字串 s for(char c : s){ n = n * 10 + (c - '0'); // 乘以10是為了進位，因為我們是從最大的那個位數開始讀取的 } cout << n; ``` ### 輸出結果 ``` 123456 ``` --- ## 小試身手 * 題目：子柚是個很喜歡數學的學生，尤其喜歡計算非常大的數字，現在他希望可以進行20位數以上的乘法運算，請幫助他實現這個願望。 * 輸入說明：第一行為一個整數 $\text{n}$，第二行為一個個位數 $\text{m}$。$\left(20 \leq \log n \leq 100\right)$ * 輸出說明：請輸出 $\text{n × m}$ 的結果。 ### 範例輸入1 ``` 600000000000000000000000000000000000000 2 ``` ### 範例輸出1 ``` 1200000000000000000000000000000000000000 ``` --- ### 參考解答 ```cpp=1 #include <bits/stdc++.h> using namespace std; int main() { string n; int m; string result = ""; // 儲存乘法結果 int carry = 0; // 進位 cin >> n >> m; // 從最後一位開始逐位相乘 for (int i = n.size() - 1; i >= 0; --i) { int digit = (n[i] - '0') * m + carry; // 計算每位數的乘積加上進位 result = char(digit % 10 + '0') + result; // 將當前位的結果添加到結果字符的前面 carry = digit / 10; // 更新進位 } // 如果還有進位，繼續處理 while (carry) { result = char(carry % 10 + '0') + result; // 將進位添加到結果字符的前面 carry /= 10; } cout << result << endl; return 0; } ``` ## 練習題 [a021. 大數運算](https://zerojudge.tw/ShowProblem?problemid=a021) [q182. 2. 字串操作](https://zerojudge.tw/ShowProblem?problemid=q182) # 常用函式以下是常用函式，熟記的話可以節省不少時間，且標頭檔都用 `#include<bits/stdc++.h>` 即可。 | 函式 | 用途 | 範例 | |---------------|------------------------------|------------------------------------------| | `abs(x)` | 取絕對值 | `abs(-5) = 5` | | `min(a, b)` | 取最小值 | `min(3, 7) = 3` | | `max(a, b)` | 取最大值 | `max(3, 7) = 7` | | `sqrt(x)` | 取平方根 | `sqrt(16) = 4` | | `pow(x, y)` | 指數運算 | `pow(2, 3) = 8` | | `floor(x)` | 向下取整 | `floor(3.7) = 3` | | `ceil(x)` | 向上取整 | `ceil(3.2) = 4` | | `round(x)` | 四捨五入 | `round(3.5) = 4` | | `log(x)` | 取自然對數（ln） | `log(2.71828) = 約 1` | | `log10(x)` | 取以 10 為底的對數 | `log10(100) = 2` | | `sin(x)` | 計算正弦 | `sin(3.14159 / 2) = 約 1` | | `cos(x)` | 計算餘弦 | `cos(0) = 1` | | `tan(x)` | 計算正切 | `tan(3.14159 / 4) = 約 1` | | `hypot(x, y)`| 計算歐幾里得距離 √(x²+y²) | `hypot(3, 4) // 5` | | `gcd(a, b)` | 計算最大公因數 | `gcd(12, 18) // 6` | | `lcm(a, b)` | 計算最小公倍數 | `lcm(12, 18) // 36` | | `swap(a, b)` | 交換兩個值 | `swap(x, y)` | | `reverse(begin, end)` | 反轉範圍內元素(陣列) | `reverse(v.begin(), v.end())` | # 指標我們每個人的家都有地址，當然，變數也有，而我們要怎麼取得變數的地址，或者怎麼靠地址找到變數，就得依賴指標。 ```cpp=1 #include <bits/stdc++.h> using namespace std; int main() { int a = 10; // 一個普通的整數變數 int *p = &a; // 指標 p 儲存變數 a 的地址 cout << "a 的地址: " << &a << endl; // 顯示 a 的地址 cout << "p 指向的地址: " <::iterator it // 宣告迭代器 it ``` ## 移動 ```cpp=1 it++ // 迭代器向前一格 ++it // 迭代器向前一格 it-- // 迭代器向後一格 --it // 迭代器向後一格 ``` ## 常用迭代器 ```cpp=1 v.begin() // v陣列的起點 v.end() // V陣列的終點 ``` ## 公式解-遍歷陣列 ```cpp=1 #include <bits/stdc++.h> using namespace std; int main() { vector<int> v={1,2,3,4,5}; for(vector<int>::iterator it=v.begin();it!=v.end();it++){ cout << *it << " "; } return 0; } ``` ## 進階操作-auto `auto` 是一種透過編譯器來自動推測變數型態的關鍵字，好處是可以化簡代碼。 ```cpp=1 #include <bits/stdc++.h> using namespace std; int main() { vector<int> v={1,2,3,4,5}; for(auto it=v.begin();it!=v.end();it++){ cout << *it << " "; } return 0; } ``` ## 大師操作-range-based ```cpp=1 #include <bits/stdc++.h> using namespace std; int main() { vector<int> v={1,2,3,4,5}; for(auto it : v){ cout << *it << " "; } return 0; } ``` # 副函式以往，我們的程式都寫在 `main` 當中，但有些重複出現的功能，像是判斷二維陣列的邊界條件，若是每個 `if` 都重寫會導致程式碼可閱讀性降低，如下方範例。 ```cpp=1 #include <bits/stdc++.h> using namespace std; int main() { int rows = 3; int cols = 3; // 迷宮陣列：0代表可以走，1代表牆壁 int grid[3][3] = { {0, 1, 0}, {0, 0, 0}, {0, 1, 0} }; // 可移動的四個方向：上、下、左、右 int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; string direction_names[4] = {"Up", "Down", "Left", "Right"}; // 起點為 (1, 1) 這是中間的位置 int startX = 1, startY = 1; // 顯示起始位置 cout << "Starting at: (" << startX << ", " << startY << ")\n"; // 遍歷四個方向，看看哪些方向是可以走的 for (int i = 0; i < 4; i++) { int newX = startX + directions[i][0]; int newY = startY + directions[i][1]; // 檢查新位置是否合法：在邊界內，且不是牆壁 if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[newX][newY] == 0) { // 輸出可以走的方向 cout << "You can move " << direction_names[i] << " to: (" << newX << ", " << newY << ")\n"; } } return 0; } ``` ### 輸出結果 ``` Starting at: (1, 1) You can move Left to: (1, 0) You can move Right to: (1, 2) ``` 看完上面的，有沒有覺得頭昏眼花， `if` 裡面太多東西了吧！所以當我們把這個判斷的條件從主函式 `main` 提出來後，整個程式碼就可以變得精簡許多。 ```cpp=1 #include <bits/stdc++.h> using namespace std; // 全域變數 int rows = 3; int cols = 3; int grid[3][3] = { {0, 1, 0}, {0, 0, 0}, {0, 1, 0} }; // 副函式：判斷新位置是否合法 bool canMove(int x, int y) { return x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == 0; } int main() { // 可移動的四個方向：上、下、左、右 int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; string direction_names[4] = {"Up", "Down", "Left", "Right"}; // 起點為 (1, 1) 這是中間的位置 int startX = 1, startY = 1; // 顯示起始位置 cout << "Starting at: (" << startX << ", " << startY << ")\n"; // 遍歷四個方向，看看哪些方向是可以走的 for (int i = 0; i < 4; i++) { int newX = startX + directions[i][0]; int newY = startY + directions[i][1]; // 使用 canMove 函式檢查新位置是否合法 if (canMove(newX, newY)) { cout << "You can move " << direction_names[i] << " to: (" << newX << ", " << newY << ")\n"; } } return 0; } ``` ### 輸出結果 ``` Starting at: (1, 1) You can move Left to: (1, 0) You can move Right to: (1, 2) ``` 可以看得出來，兩者的功能是完全相同的，但使用副函式可以讓程式碼可閱讀性及可維護性變高許多。看了這兩個範例後，我們就可以來學習如何將主函式 `main` 中的程式打包成副函式了。 ## 副函式基本守則 1. 如果非全域變數，就必須要傳遞變數給副函式。（忘記的可以去複習變數範圍） ```cpp=1 #include <bits/stdc++.h> using namespace std; // 傳遞變數，位置一一對應，資料型態也要相同 // 整數 x 對應到整數 a ，整數 y 對應到整數 b void add(int a, int b) { // 可以在這裡進行某些操作 } int main() { int x = 5, y = 3; add(x, y); // 傳遞變數 x 和 y 到 add 函式 return 0; } ``` 2. 傳遞陣列時，直接使用陣列的名字當指標就可以了。 ```cpp=1 #include <bits/stdc++.h> using namespace std; // 一維整數陣列 nums 對應到一維整數陣列 arr // 可以不用給定大小 void sumArray(int arr[]) { // 可以在這裡進行某些操作 } int main() { int nums[] = {1, 2, 3, 4, 5}; sumArray(nums); // 傳遞陣列到副函式 return 0; } ``` 3. 如果是二維陣列，則必須將大小先訂好至少一個。 ```cpp=1 #include <bits/stdc++.h> using namespace std; // 二維整數陣列 grid 對應二維整數陣列 arr // 需先給定一個維度的大小 void sum2DArray(int arr[][3]) { // 可以在這裡進行某些操作 } int main() { int grid[2][3] = { {1, 2, 3}, {4, 5, 6} }; sum2DArray(grid); // 傳遞二維陣列 return 0; } ``` 4. 若是希望傳遞過去的東西不要被更改，可以加上 `const` 來保護變數。 ```cpp=1 // 確保陣列操作時不會更改其內容 void Array(const int arr[]) { // 可以在這裡進行某些操作 } ``` ## int `int` 代表此副函式最後會回傳一個整數，常見的使用方法為「遞迴」，我們在下一個章節會提到。 ```cpp=1 #include <bits/stdc++.h> using namespace std; // 副函式：計算兩個數字的和，並返回結果 int sum(int a, int b) { return a + b; } int main() { int x, y; cin >> x >> y; // 調用 sum 函式，並將結果存儲在 result 中 int result = sum(x, y); cout << "The sum of " << x << " and " << y << " is " << result << endl; return 0; } ``` ## void `void` 代表「無」，即該函式不返回任何資料或結果。通常用於僅執行某些操作（如打印訊息、修改參數等）而不需要返回結果的函式。特別注意，如果需要終止 `void` 類型的副函式的話，仍然可以使用 `return` ，只不過不需要加入回傳值（就寫一個 `return` 就好了）。 ```cpp=1 #include <bits/stdc++.h> using namespace std; // 副函式：檢查數字是否為正數，若是則打印，否則提前退出 void printPositiveNumber(int num) { if (num <= 0) { cout << "The number is not positive. Exiting function." << endl; return; // 提前結束函式執行 } cout << "The number is positive: " << num << endl; } int main() { int num; cin >> num; // 呼叫函式處理數字 printPositiveNumber(num); return 0; } ``` ## bool `bool` 會回傳 `true` 或者 `false`，通常用於判斷此操作是否合法，前面的迷宮就是用到這個類型的副函式。 ```cpp=1 #include <bits/stdc++.h> using namespace std; // 副函式：檢查一個數字是否是 2 的倍數 bool isMultipleOfTwo(int n) { return n % 2 == 0; /* 可以看成下方這樣子 if(n % 2 == 0){ return true; } else{ return false; }*/ } int main() { int num; cin >> num; // 調用 isMultipleOfTwo 函式，檢查 num 是否是 2 的倍數 if (isMultipleOfTwo(num)) { cout << num << " is a multiple of 2." << endl; } else { cout << num << " is not a multiple of 2." << endl; } return 0; } ``` # 遞迴在高一上的數學，我們學習到了遞迴這個觀念，透過一定的運算規則，例如費氏數列： * f(0)=0 * f(1)=1 * f(n)=f(n-1)=f(n-2) n>=2 而這種東西透過副函式反覆呼叫自己就能很好的實現，以費氏數列舉例如下。 ```cpp=1 #include <bits/stdc++.h> using namespace std; // 遞迴函式：計算費氏數列的第 n 項 int fibonacci(int n) { if (n == 0) { return 0; // f(0) = 0 } else if (n == 1) { return 1; // f(1) = 1 } else { return fibonacci(n - 1) + fibonacci(n - 2); // f(n) = f(n-1) + f(n-2) n>=2 } } int main() { int n; cin >> n; // 輸出第 n 項費氏數列的值 cout << "Fibonacci number at position " << n << " is: " << fibonacci(n) << endl; return 0; } ``` ## 練習題 [c002. 10696 - f91](https://zerojudge.tw/ShowProblem?problemid=c002) [f640. 函數運算式求值](https://zerojudge.tw/ShowProblem?problemid=f640) # sort(排序) `sort` 是一個內建比較函式，可以幫助我們將陣列的資料排序，以下是 `sort` 的語法。 ```cpp=1 sort(arr.begin(), arr.end()); // 升序排序 sort(arr.begin(), arr.end(), compare); // 使用自定義的排序 ``` 關於自定義排序，你需要寫一個副函式來判斷，以下是參考寫法。 ```cpp=1 bool compare(int a, int b) { return a > b; // a 大於 b 時返回 true，實現降序排序 } ``` # vector(動態陣列) `vector` 是一種動態陣列，相較我們之前學習的陣列，`vector` 提供了「不需要預先設定大小」的優勢，並且可以很方便的插入或刪除陣列中任何位置的資料，讓我們看看 `vector` 的語法吧！ ## 宣告 ```cpp=1 // 一維陣列 vector<int> v1; // 空的 vector，元素類型為 int vector<int> v2(10); // 大小為 10 的 vector，元素初始值為 0 vector<int> v3(10, 5); // 大小為 10 的 vector，所有元素初始值為 5 vector<int> v4 = {1, 2, 3, 4, 5}; // 初始化列表 // 二維陣列 vector<vector<int>> v5; // 空的二維 vector，元素類型為 int ``` ## 插入資料 ```cpp=1 v.push_back(5); // 在 vector 的尾端插入元素 5 v.insert(v.begin(), 3); // 在 vector 的開頭插入元素 3 v.insert(v.begin() + 2, 7); // 在 vector 的第三個位置插入元素 7 ``` ## 刪除資料 ```cpp=1 v.pop_back(); // 刪除 vector 最尾端的元素 v.erase(v.begin()); // 刪除 vector 開頭的元素 v.erase(iterator); // 刪除 vector 中 iterator 所指的元素 v.erase(v.begin()+1, v.begin() + 4); // 刪除 vector 中第 2 ~ 4個元素 v.erase(iterator1, iterator2); // 刪除 vector 中 iterator1 到 iterator2 的元素 v.clear(); // 刪除所有元素 ``` ## 其它 ```cpp=1 v.size(); // 回傳 vector 目前的大小 v.resize(5); // 調整 vector 大小為 5 swap(v1, v2); // 交換兩個 vector 的元素 v.empty(); // 回傳一個 bool ，如果 vector 為空回傳 True，反之 False ``` --- 以下是幾種比較常用到的模板寫法。 ## 公式解-輸入總數已知 * 當題目敘述有「第一行輸入一個整數 $\text{n}$ ，接下來有 $\text{n}$ 行的測試資料」時可以使用下方寫法。 ```cpp=1 #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; // 資料總數 vector<int> v(n); // 宣告一個大小為 n 的 vector for (int i = 0; i < n; i++) { cin >> v[i]; // 讀取使用者輸入的數字 } for (int i = 0; i < n; i++) { cout << v[i] << " "; // 輸出每個數字 } return 0; } ``` ## 公式解-輸入終止條件已知 * 當題目敘述有「測試資料有數筆，當輸入 0 時終止」時可以使用下方寫法。 ```cpp=1 #include <bits/stdc++.h> using namespace std; int main() { vector<int> v; // 宣告一個空的 vector int n; while (cin >> n) { if(n == 0){ // 預設終止條件為 0 (此處可以根據題目條件更改) break; } v.push_back(n); // 將輸入的數字加入 vector } for (int i = 0; i < v.size(); i++) { // 用 v.size() 來取得陣列大小 cout << v[i] << " "; } return 0; } ``` ## 進階操作-pair 正常來說，陣列中的每一格只能儲存一個資料，但有些時候測試資料會存在前後關聯性，例如說該產品的「成本」和「利益」，這時候分成兩個 `vector` 儲存，在進行某些操作時可能會出問題，像是常見的 `sort` ，如果對「成本」進行小到大排序，利益就無法對齊原本的成本，但若使用 `pair` 來處理，就可以把這個產品的「成本」和「利益」綁在一起，移動的時候也一起搬，這樣就不會亂掉了！ ```cpp vector<int> v; ``` ![image](https://hackmd.io/_uploads/ByeSCFAJye.png) ```cpp vector<pair<int, int>> v; ``` ![image](https://hackmd.io/_uploads/SJybx901Jl.png) 可以看到 `pair` 的每個房間都可以儲存兩個資料 { first, second }，調用方式如上圖，先指定房間後加上 .first 或.second 就可以調用數值了，記得一定要加「.」喔！ --- ## 小試身手 * 題目：子柚擁有多間工廠，分別生產不同的產品。由於近期資金短缺，公司決定優先生產成本較低的產品。請根據產品的生產成本由低到高的順序，輸出對應產品的利益。 * 輸入說明：第一行為一個整數 $\text{n}$，表示產品的數量。接下來的 $\text{n}$ 行，每行包含兩個整數，分別代表該產品的成本和對應的利益，以空格分隔。 * 輸出說明：請根據成本從低到高的順序，輸出每個產品的利益，數字之間用空格分隔。 ### 範例輸入1 ``` 7 50 60 60 40 30 50 10 80 80 90 40 30 90 10 ``` ### 範例輸出1 ``` 80 50 30 60 40 90 10 ``` --- ### 參考解答你可以把資料用兩個 `vector` 儲存起來，並且對儲存成本的那個陣列進行 `sort` ，但這時候會發現，成本由小排到大了，但利益「並沒有跟著動」，而你又不知道現在的產品編號順序是多少，也就無法正確的照順序輸出利益。 (請注意，下方的產品編號只是輔助說明，並沒有被存在 `vector` 中，所以無法調用。) | vector編號 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | -------- | --- | --- | --- | --- | --- | --- | --- | | 產品編號 | 4 | 3 | 6 | 1 | 2 | 5 | 7 | | 成本 | 10 | 30 | 40 | 50 | 60 | 80 | 90 | | vector編號 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | -------- | --- | --- | --- | --- | --- | --- | --- | | 產品編號 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | 利益 | 60 | 40 | 50 | 80 | 90 | 30 | 10 | 所以這時候我們就要使用 `pair` 來幫助我們把兩個資料儲存成「一組」，放在一起。 (請注意，現在只有一個 `vector` ！但是這個 `vector` 的每一個格子可以存放兩個整數。) | vector編號 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | -------- | --- | --- | --- | --- | --- | --- | --- | | 產品編號 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | 成本 | 50 | 60 | 30 | 10 | 80 | 40 | 90 | | 利益 | 60 | 40 | 50 | 80 | 90 | 30 | 10 | 這時候再進行 `sort` 就會發現！成本跟利益一起動了！ | vector編號 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | -------- | --- | --- | --- | --- | --- | --- | --- | | 產品編號 | 4 | 3 | 6 | 1 | 2 | 5 | 7 | | 成本 | 10 | 30 | 40 | 50 | 60 | 80 | 90 | | 利益 | 80 | 50 | 30 | 60 | 40 | 90 | 10 | 此時將 `vector` 輸出就會得到題目所求了！ ``` 輸出結果：80 50 30 60 40 90 10 ``` 以下是參考代碼。 ```cpp=1 #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<pair<int, int>> vp; // 宣告一個 pair<first, second> 的 vector for (int i = 0; i < n; i++) { int a, b; cin >> a >> b; // a 是成本, b 是利益 vp.push_back({a, b}); } // 按成本 (first) 進行排序 sort(vp.begin(), vp.end()); for (int i = 0; i < n; i++) { cout << vp[i].second << " "; } cout << endl; return 0; } ``` # set `set` 是 STL 中一個用來儲存元素的容器，具有以下特性 * 元素不重複 * 自動排序（小到大） * 搜尋效率高（底層邏輯基於紅黑數） ## 宣告 ```cpp=1 set<int> a // 宣告一個名稱為 a，存放整數的 set set<int> b = {10, 20, 30, 40, 50}; // 初始化列表 ``` ## 插入資料 ```cpp=1 a.insert(num) // 插入 num 到 set 之中 // 由於會自動排序，所以不需要指定插入位置 ``` ## 刪除資料 ```cpp=1 a.erase(sum) // 將 sum 從 set 之中刪除 a.erase(iterator) // 刪除 iterator 所指位置的元素 a.clear() // 清空 set ``` ## 其他 ```cpp=1 a.size() // 回傳整數表示 set 的大小 a.empty() // 回傳一個 bool ，如果 vector 為空回傳 True，反之 False ``` ## 進階操作-find 有些時候，我們希望知道一個元素是否在容器之中，如果存在的話又是在哪個位置，這時候我們就可以用 `find` 來幫助我們搜尋。 ```cpp=1 #include <bits/stdc++.h> using namespace std; int main() { set<int> numbers = {10, 20, 30, 40, 50}; int target = 30; auto it = numbers.find(target); // it 當指標，指向numbers 中 target 的位置 // 若沒有找到則 it 指向 numbers 的尾端 if (it != numbers.end()) { cout << "Found " << target << " in the set." << endl; } else { cout << target << " not found in the set." << endl; } return 0; } ``` --- ## 小試身手 * 題目：子柚的班上有 $\text{n}$ 名學生，在一場考試中，子柚得到的成績為 $\text{x}$ ，他想知道自己的成績在班上的排名是多少。（同分者排名相同，其他人不需調整名次） * 輸入：第一行輸入兩個整數 $\text{n}$ 和 $\text{m}$ ，輸入用空格分開，接著輸入 $\text{n}$ 個整數，代表班上每個人的成績（包含子柚本人）。$\left(2\leq \text{n}\leq 100\right)\left(0\leq \text{m}\leq 100\right)\left(0\leq \text{x}\leq 100\right)$ * 輸出：輸出子柚在班上的排名，輸出格式請參照範例輸出。 ### 範例輸入1 ``` 5 90 60 70 80 90 100 ``` ### 範例輸出1 ``` 子柚在這場考試中排名第 2 名 ``` 測資說明：成績高到低為 100 90 80 70 60 ，第 1 名 100 分，第 2 名 90 分，第 3 名 80 分，以此類推，故 90 分排名第 2 名，輸出「子柚在這場考試中排名第 2 名」。 ### 範例輸入2 ``` 7 42 87 36 58 42 91 86 87 ``` ### 範例輸出2 ``` 子柚在這場考試中排名第 5 名 ``` 測資說明：成績高到低為 91 87 87 86 58 42 36 ，其中 87 分的兩位並列第 2 名，第 3 名為 86 分，第 4 名為 58 分，依此類推，故 42 分排名第 5 名，輸出「子柚在這場考試中排名第 5 名」。 --- ### 參考解答 ```cpp=1 #include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; set<int> scores; for (int i = 0; i < n; ++i) { int score; cin >> score; scores.insert(score); } // 使用反向迭代器遍歷 set，從最大分數開始計算排名 int rank = 1; // 排名從 1 開始 for (auto it = scores.rbegin(); it != scores.rend(); ++it) { // 如果當前分數等於子柚的成績，則輸出排名 if (*it == m) { cout << "子柚在這場考試中排名第 " << rank << " 名" << endl; break; } rank++; } return 0; } ``` --- # map `map` 是 STL 中一個用來儲存鍵值對（key-value pair）的容器，具有以下特性： * 鍵（`key`）不重複，每個鍵對應一個值（`value`） * 鍵自動排序（默認按鍵由小到大排序） * 搜尋效率高（底層邏輯基於紅黑樹） ## 宣告 ```cpp=1 map<int, string> a; // 宣告一個名稱為 a，存放「整數」鍵對應「字串」的 map map<int, string> b = {{1, "apple"}, {2, "banana"}, {3, "cherry"}}; // 初始化 ``` ## 插入資料 ```cpp=1 a.insert({key, value}); // 插入一個鍵值對 (key, value) 到 map 中 a[key] = value; // 也可以用這種方式來插入鍵值對 ``` * 如果插入的 `key` 已經存在，則 `insert` 不會成功，且不會覆蓋現有的 `value`，但使用 `a[]` 則會覆蓋先前結果。 ## 刪除資料 ```cpp=1 a.erase(key); // 刪除指定 key 的元素 a.erase(iterator); // 刪除 iterator 所指位置的元素 a.clear(); // 清空 map ``` ## 其他 ```cpp=1 a.size(); // 回傳整數，表示 map 的大小 a.empty(); // 回傳布林值，若 map 為空則返回 true，否則返回 false iterator->first // 取得 value 對應的 key iterator->second // 取得 key 對應的 value ``` --- ## 小試身手 * 題目：在數學中，班佛定律（Benford's law）描述了真實數字數據集中首位數字的頻率分布。首位數字 $a \left( a = 1, 2, 3, 4, \ldots, 8, 9 \right)$ 出現的概率為 $\log(1+\dfrac{1}{a})$ 。它可用於檢查各種數據是否有造假。現在子柚正在稽查公司的財務報表，請替他透過班佛法則來檢查數據是否有造假。 * 輸入：輸入一個整數 $\text{t}$ 代表接下來會有 $\text{t}$ 筆測資。每筆測資輸入多個正整數 $\text{n}$，若 $\text{n}$ 等於 $-1$ 代表輸入結束。 * 輸出：若數字 $a$ 為首的出現概率偏離理論值 $7\%$ （含）以上時，則此財務報表的數據有造假，輸出 $\text{fake}$。反之輸出 $\text{real}$。 * 第一子題（20%）：$\text{t} = 1 , \text{n} \leq 10^3$ 第二子題（40%）：$\text{t} \leq 10 , \text{n} \leq 10^6$ 第三子題（40%）：$\text{t} \leq 100 , \text{n} \leq 10^{10}$ ### 範例輸入1 ``` 1 12 16 54 87 54 95 3 2 65 7 57 95 12 58 100 16 57 8 4 5 9 17 54 21 53 -1 ``` ### 範例輸出1 ``` fake ``` 測資說明：數字分布如下： | 數字 | 實際值 | 理論值 | |------|--------|--------| | 1 | 24% | 30% | | 2 | 8% | 18% | | 3 | 4% | 12% | | 4 | 4% | 10% | | 5 | 32% | 8% | | 6 | 4% | 7% | | 7 | 4% | 6% | | 8 | 8% | 5% | | 9 | 12% | 5% | ### 範例輸入2 ``` 1 10 20 14 40 49 6 13 58 39 23 79 12 1 31 100 30 38 2 15 54 39 20 98 1 40 2 68 94 59 14 16 11 71 18 36 9 50 55 54 1 26 73 19 48 20 23 11 97 75 16 38 2 22 26 13 19 21 48 98 2 36 56 66 14 4 25 22 19 53 100 37 28 41 69 23 55 23 34 14 43 96 19 19 90 22 12 19 1 30 28 25 72 13 58 13 34 16 58 100 21 -1 ``` ### 範例輸出2 ``` real ``` 測資說明：數字分布如下： | 數字 | 實際值 | 理論值 | |------|--------|--------| | 1 | 31% | 30% | | 2 | 22% | 18% | | 3 | 12% | 12% | | 4 | 8% | 10% | | 5 | 11% | 8% | | 6 | 4% | 7% | | 7 | 5% | 6% | | 8 | 0% | 5% | | 9 | 7% | 5% | ### 參考解答 ```cpp=1 #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { map<int, int> freq; // 記錄每個首位數字的出現次數 int total = 0; // 數據的總數 long long n; while (cin >> n && n != -1) { // 找到首位數字 int first_digit = n; while (first_digit >= 10) { first_digit /= 10; } freq[first_digit]++; // 此數字對應的計數器+1 total++; } bool fake = false; for (int a = 1; a <= 9; a++) { double observed = (double)freq[a] / total; // 實際值 double expected = log10(1.0 + (1.0 / a)); // 理論值 cout << a << " " << observed << " " << expected << endl; // 若偏離超過 7%，則認定為 fake if (abs(observed - expected) > 0.07) { fake = true; break; } } if (fake) { cout << "fake" << endl; } else { cout << "real" << endl; } } return 0; } ``` --- # struct 在某些時候，`int` `float` 等宣告方式可能無法滿足我們的需求，例如座標點，需要同時儲存兩個資料，這時候我們就可以用 `struct` 來自定宣告型式，方法如下： ```cpp=1 #include <bits/stdc++.h> using namespace std; // struct必須宣告在副函式的位置 // 定義一個struct來表示座標點，類型名稱叫Point struct Point { float x; // x 座標 float y; // y 座標 }; // 這裡要分號 int main() { // 宣告一個 Point 類型的變數 Point p; // 輸入座標 cin >> p.x >> p.y; // 輸出座標 cout << "輸入的座標是: (" << p.x << ", " << p.y << ")" << endl; return 0; } ``` `struct` 好用的地方就在，不需要用 `pair` ，或者多個陣列來儲存輸入資料，對於維護性和可讀性有顯著提升。 --- # typedef `typedef` 主要用來為既有的資料型別取別名，使程式碼更簡潔、可讀性更高，特別是在多重 `pair`、數字與字串交錯使用時，能讓程式碼結構更加清晰。 ## 基本用法 ```cpp typedef 現有型別新名稱; ``` 例如，我希望記錄每位同學的姓名(字串)、身高(整數)、體重(浮點數)，此時我可以這樣宣告： ```cpp typedef pair<string,pair<int,float>> data; data students[n]; // 直接用data當資料型別 ``` 如果不使用 `typedef`，就要在宣告陣列的時候完整的寫出來： ```cpp pair<string,pair<int,float>> students[n] ``` 看似相同，但若有多個陣列要宣告，那版面的整潔就會有差別。 --- # defind `defind` 也是用來宣告資料型別，但通常用於簡稱。同時 `defind` 也可以用來宣告變數的值，在某些觀念題可能會看到這種用法。 ## 基本用法 ```cpp #define MAXN 1000 #define long long = LL LL arr[MAXN]; // 宣告一個存放 long long ，陣列大小為 1000 的陣列 ``` # queue `queue` 是 C++ 標準模板庫（STL）中的一種容器，是一個 FIFO（First In, First Out）結構，具有以下特性： * 元素只能從尾端插入（push），從前端移除（pop）。 * 不允許隨機訪問元素，只能訪問前端（front）或者尾端（back）。 ## 宣告 ```cpp=1 queue<int> q; // 宣告一個存放整數的 queue ``` ## 插入資料 ```cpp=1 q.push(value); // 將元素 value 從 queue 尾端插入 ``` ## 移除資料 ```cpp=1 q.pop(); // 移除 queue 前端的元素 ``` ## 存取資料 ```cpp=1 q.front(); // 取得 queue 前端的元素 q.back(); // 取得 queue 尾端的元素 ``` ## 其他操作 ```cpp=1 q.size(); // 回傳整數，表示 queue 的大小 q.empty(); // 回傳布林值，若 queue 為空則返回 true，否則返回 false ``` ## 圖解程式 ```cpp queue<int> q; // 創建一個儲存整數的 queue q.push(10); // 從 queue 的尾端插入 10 ``` ![image](https://hackmd.io/_uploads/S1lb0SGrkg.png) ```cpp q.push(20); // 從 queue 的尾端插入 20 ``` ![Screenshot 2024-12-20 09.51.37](https://hackmd.io/_uploads/HkaVCrzB1e.png) ```cpp q.push(30); // 從 queue 的尾端插入 30 ``` ![image](https://hackmd.io/_uploads/B1NyJIfS1g.png) ```cpp cout << q.front() << " "; // 輸出 queue 前端的元素 q.pop(); // 刪除 queue 前端的元素 ``` ``` 輸出：10 ``` ![image](https://hackmd.io/_uploads/Skfq6rzHyg.png) ```cpp cout << q.front() << " "; // 輸出 queue 前端的元素 q.pop(); // 刪除 queue 前端的元素 ``` ``` 輸出：20 ``` ![image](https://hackmd.io/_uploads/B1PzCSMrye.png) ```cpp cout << q.front() << " "; // 輸出 queue 前端的元素 q.pop(); // 刪除 queue 前端的元素 ``` ``` 輸出：30 ``` ### 範例程式 ```cpp=1 #include <bits/stdc++.h> using namespace std; int main() { queue<int> q; q.push(10); q.push(20); q.push(30); while(!q.empty()){ cout << q.front() << " "; q.pop(); } return 0; } ``` ### 輸出結果 ``` 10 20 30 ``` --- ## 小試身手 * 題目：子柚在和水木目玩桌遊，規則是抽取將撲克牌洗好後堆一疊放在桌上，每人輪流抽取撲克牌最上方的一張，大聲唸出數字後，將對應數量的牌從牌堆最上方拿到底部（一次只能拿一張），直到只剩下一張牌在桌上為止。 * 輸入：輸入一串字串，代表牌堆由上而下的所有數字。（J代表11、Q代表12、K代表13）（保證數字為非負整數） * 輸出：輸出最後一張牌的數字。（11請輸出J、12請輸出Q、13請輸出K） * 第一子題（20％）：字串長度不超過10，數字在1~9之間。第二子題（40％）：字串長度不超過50，數字保證沒有10。第三子題（40％）：無額外限制。 ### 範例輸入1 ``` 123456789 ``` ### 範例輸出1 ``` 5 ``` ### 範例輸入2 ``` 13579JK246810Q ``` ### 範例輸出2 ``` 6 ``` :::spoiler 參考解答 ```cpp=1 #include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); string s; cin>>s; queue<int>q; for(int i=0;i<s.size();i++){ if(s[i]=='1'){ if(i==s.size()-1)q.push(1); else if(s[++i]=='0')q.push(10); else{ q.push(1); q.push(s[i]-'0'); } } else if(s[i]=='J')q.push(11); else if(s[i]=='Q')q.push(12); else if(s[i]=='K')q.push(13); else q.push(s[i]-'0'); } int t; while(q.size()!=1){ t=q.front();q.pop(); for(int i=0;i<t;i++){ q.push(q.front()); q.pop(); } } switch(q.front()){ case 11:cout<<'J';break; case 12:cout<<'Q';break; case 13:cout<<'K';break; default:cout<<q.front(); } } ``` ::: --- # priority_queue `priority_queue` 是一個基於堆（heap）的容器，具有以下特性： * 元素按照優先級排序，預設為大頂堆（降序）。 * 元素只能從尾端插入（push），從前端移除（pop）。 ## 宣告 ```cpp=1 priority_queue<int> pq; // 宣告一個存放整數的大頂堆 priority_queue<int, vector<int>, greater<int>> min_pq; // 宣告一個存放整數的小頂堆 ``` ## 插入資料 ```cpp=1 pq.push(value); // 將元素 value 插入到隊列中 ``` ## 移除資料 ```cpp=1 pq.pop(); // 移除隊列中優先級最高的元素 ``` ## 存取資料 ```cpp=1 pq.top(); // 取得隊列中優先級最高的元素 ``` ## 其他操作 ```cpp=1 pq.size(); // 回傳整數，表示隊列的大小 pq.empty(); // 回傳布林值，若隊列為空則返回 true，否則返回 false ``` ## 圖解程式 ```cpp priority_queue<int> pq; // 宣告一個最大堆 pq.push(10); // 插入 10 (自動照優先級排列) ``` ![image](https://hackmd.io/_uploads/By6kq8MHyl.png) ```cpp pq.push(20); // 插入 20(自動照優先級排列) ``` ![image](https://hackmd.io/_uploads/SkCcdLGB1x.png) ```cpp pq.push(15); // 插入 15(自動照優先級排列) ``` ![image](https://hackmd.io/_uploads/H1ygO8MrJe.png) ```cpp cout << pq.top() << " "; // 輸出優先級最高的元素 pq.pop(); // 移除優先級最高的元素 ``` ``` 輸出結果：20 ``` ![image](https://hackmd.io/_uploads/Hk9__8zSyg.png) ```cpp cout << pq.top() << " "; // 輸出優先級最高的元素 pq.pop(); // 移除優先級最高的元素 ``` ``` 輸出結果：15 ``` ![image](https://hackmd.io/_uploads/By6kq8MHyl.png) ```cpp cout << pq.top() << " "; // 輸出優先級最高的元素 pq.pop(); // 移除優先級最高的元素 ``` ``` 輸出結果：10 ``` ### 範例程式 ```cpp=1 #include <bits/stdc++.h> using namespace std; int main() { priority_queue<int> pq; pq.push(10); pq.push(20); pq.push(15); while(!pq.empty()){ cout << pq.top() << " "; pq.pop(); } return 0; } ``` ### 輸出結果 ``` 20 15 10 ``` --- ## 小試身手 * 題目：子柚開了一間理髮廳，標榜「笑著進來，笑著出去」，吸引了許多人前來朝聖。近日因排隊人龍過長，子柚決定實施 VIP 制度，VIP 等級越高的人可以越優先理髮，VIP等相同的則需要照先來後到的順序排隊。這是預計到訪的客人名單（已照時間順序排列），請替子柚計算接待完所有顧客所需花費的時間。 * 輸入：第一行輸入一個整數 $\text{n}$ ，代表理髮店的座位總數。接下來每行輸入兩個整數，代表每位顧客的 $\text{VIP}$ 等級和理髮所需時間 $\text{t}$ （單位：分鐘），若 $\text{VIP}$ 等級為 $-1$ 但 $\text{t}$ 不為 $0$ ，則代表經過 $\text{t}$ 分鐘（沒有新客人拜訪）。輸入直到 $\text{VIP}$ 等級和 $\text{t}$ 皆為 $-1$ 結束。 * 輸出：輸出所需時間（格式：dd/hh/mm）（詳見範例輸出，dd 位數可大於 $2$） * 第一子題（10％）：$\text{n} = 1, \text{m} \leq 10, \text{VIP} = 0$ 第二子題（20％）：$\text{n} \leq 3, \text{m} \leq 20, -1 \leq \text{VIP} \leq 0$ 第三子題（30％）：$\text{n} \leq 3, \text{m} \leq 20, -1 \leq \text{VIP} \leq 5$ 第四子題（40％）：無額外限制 ### 範例輸入1 ``` 1 0 10 0 20 0 30 0 40 0 50 -1 -1 ``` ### 範例輸出1 ``` 00/02/30 ``` ### 範例輸入2 ``` 3 0 10 2 20 4 15 3 30 -1 5 5 25 3 20 2 10 -1 10 5 5 -1 -1 ``` ### 範例輸出2 ``` 00/00/50 ``` ### 參考解答 ```cpp=1 #include<bits/stdc++.h> #define ff first #define ss second using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n; cin>>n; int ans=0; int a[n]={}; priority_queue<pair<int,int>>pq; int v=0,t=0; while(cin>>v>>t&&(v!=-1&&t!=-1)){ if(v!=-1)pq.push({v,t}); if(v==-1){ ans+=t; for(int i=0;i<n;i++){ a[i]-=t; while(a[i]<=0){ a[i]+=pq.top().ss; pq.pop(); } } } } while(!pq.empty()){ auto p=pq.top();pq.pop(); } } ``` --- # deque deque（double-ended queue）是 C++ 標準模板庫（STL）中的一種容器，具有以下特性： * 支援從前端與尾端插入與移除元素 * 允許隨機訪問元素（類似 vector） * 插入與刪除操作在兩端的效率都很高 ## 宣告 ```cpp=1 deque<int> dq; // 宣告一個存放整數的 deque ``` ## 插入資料 ```cpp=1 dq.push_back(value); // 將元素 value 插入到 deque 尾端 dq.push_front(value); // 將元素 value 插入到 deque 前端 ``` ## 移除資料 ```cpp=1 dq.pop_back(); // 移除 deque 尾端的元素 dq.pop_front(); // 移除 deque 前端的元素 ``` ## 存取資料 ```cpp=1 dq.front(); // 取得 deque 前端的元素 dq.back(); // 取得 deque 尾端的元素 dq[i]; // 以隨機存取方式取得第 i 個元素（類似陣列或 vector） ``` ## 其他操作 ```cpp=1 dq.size(); // 回傳整數，表示 deque 的大小 dq.empty(); // 回傳布林值，若 deque 為空則返回 true，否則返回 false dq.clear(); // 移除所有元素，使 deque 變為空 ``` ## 圖解程式 ```cpp deque<int> dq; // 宣告一個存放整數的 deque dq.push_front(10); // 將元素 10 插入到 deque 前端 ``` ![螢幕擷取畫面 2025-06-08 193233](https://hackmd.io/_uploads/Sy0-rxQXeg.png) ```cpp dq.push_front(20); // 將元素 20 插入到 deque 前端 ``` ![螢幕擷取畫面 2025-06-08 193248](https://hackmd.io/_uploads/B1mfHeQmel.png) ```cpp dq.push_back(30); // 將元素 30 插入到 deque 尾端 ``` ![螢幕擷取畫面 2025-06-08 193302](https://hackmd.io/_uploads/SJFfBemXlx.png) ```cpp cout << dq.front() << " "; dq.pop_front(); // 移除 dq 前端的元素 ``` ``` 輸出結果：20 ``` ![螢幕擷取畫面 2025-06-08 193314](https://hackmd.io/_uploads/SyAMSgX7ll.png) ```cpp cout << dq.back() << " "; dq.pop_back(); // 移除 dq 尾端的元素 ``` ``` 輸出結果：30 ``` ![螢幕擷取畫面 2025-06-08 193233](https://hackmd.io/_uploads/BJGXSlmXlg.png) ```cpp cout << dq.front() << " "; dq.pop_front(); // 移除 dq 前端的元素 ``` ``` 輸出結果：10 ``` ## 範例程式 ```cpp=1 #include<bits/stdc++.h> using namespace std; int main(){ deque<int> dq; dq.push_front(10); dq.push_front(20); dq.push_back(30); for(int i=0;i<dq.size();i++){ if(i%2==0){ cout << dq.front() << " "; dq.pop_front(); } else{ cout << dq.back() << " "; dq.pop_back(); } } return 0; } ``` ### 輸出結果 ``` 30 20 10 ``` # stack `stack` 是 C++ 標準模板庫（STL）中的一種容器，是一個 LIFO（Last In, First Out）結構，具有以下特性： * 元素只能從頂端插入（push）和移除（pop）。 * 不允許隨機訪問元素，只能訪問頂端（top）。 ## 宣告 ```cpp=1 stack<int> s; // 宣告一個存放整數的 stack ``` ## 插入資料 ```cpp=1 s.push(value); // 將元素 value 從 stack 頂端插入 ``` ## 移除資料 ```cpp=1 s.pop(); // 移除 stack 頂端的元素 ``` ## 存取資料 ```cpp=1 s.top(); // 取得 stack 頂端的元素 ``` ## 其他操作 ```cpp=1 s.size(); // 回傳整數，表示 stack 的大小 s.empty(); // 回傳布林值，若 stack 為空則返回 true，否則返回 false ``` ## 圖解程式 ```cpp stack<int> s; // 創建一個儲存整數的 stack s.push(10); // 將 10 插入 stack 頂端 ``` ![{3BBEE0B2-A8BF-45D5-AE61-3A6454A5D2BC}](https://hackmd.io/_uploads/Bkl-fi5Skg.png) ```cpp s.push(20); // 將 20 插入 stack 頂端 ``` ![{1274A787-61C2-4F4C-A7AD-C1A5ACC8BFD3}](https://hackmd.io/_uploads/rkHuMjcS1g.png) ```cpp s.push(30); // 將 30 插入 stack 頂端 ``` ![{1172FADA-B015-4E39-B061-F64BDEF48787}](https://hackmd.io/_uploads/rJycGo9Hkx.png) ```cpp cout << s.top() << " "; // 輸出 stack 頂端的元素 s.pop(); // 移除 stack 頂端的元素 ``` ``` 輸出：30 ``` ![{1274A787-61C2-4F4C-A7AD-C1A5ACC8BFD3}](https://hackmd.io/_uploads/rkHuMjcS1g.png) ```cpp cout << s.top() << " "; // 輸出 stack 頂端的元素 s.pop(); // 移除 stack 頂端的元素 ``` ``` 輸出：20 ``` ![{3BBEE0B2-A8BF-45D5-AE61-3A6454A5D2BC}](https://hackmd.io/_uploads/Bkl-fi5Skg.png) ```cpp cout << s.top() << " "; // 輸出 stack 頂端的元素 s.pop(); // 移除 stack 頂端的元素 ``` ``` 輸出：10 ``` ### 範例程式 ```cpp=1 #include <bits/stdc++.h> using namespace std; int main() { stack<int> s; s.push(10); s.push(20); s.push(30); while(!s.empty()){ cout << s.top() << " "; s.pop(); } return 0; } ``` ### 輸出結果 ``` 30 20 10 ``` --- ## 小試身手 * 題目：子柚在課堂上用原子筆隨意寫下括號，接著嘗試替括號配對，並找出「最大的括號有多長」。規則如下： 1 . 配對的左右括號必須是「距離最近的」 2 . 每個括號長度視為 1 （包含未配對括號） * 輸入：第一行輸入一個正整數 $\text{n}$ ，接下來 $\text{n}$ 行每行輸入一個字串 * 輸出：針對每一筆資料輸出最長有效括號長度，用換行隔開 * 第一子題（40％）：$n < 10$,字串長度不超過 $50$ 第二子題（60％）：無額外限制 ### 範例輸入1 ``` 3 (())()())( (((()()) )()))(() ``` ### 範例輸出1 ``` 4 6 2 ``` 測資說明：如下表 | （ | （ | ） | ） | （ | ） | （ | ） | ） | （ | | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | |0|1|2|3|4|5|6|7|8|9| s[0] 配對 s[3]，長度為 4 s[1] 配對 s[2]，長度為 2 s[4] 配對 s[5]，長度為 2 s[6] 配對 s[7]，長度為 2 其餘未配對，長度為 1 | （ | （ | （ | （ | ） | （ | ） | ） | | -- | -- | -- | -- | -- | -- | -- | -- | |0|1|2|3|4|5|6|7| s[3] 配對 s[4]，長度為 2 s[5] 配對 s[6]，長度為 2 s[2] 配對 s[7]，長度為 6 其餘未配對，長度為 1 | ） | （ | ） | ） | ） | （ | （ | ） | | -- | -- | -- | -- | -- | -- | -- | -- | |0|1|2|3|4|5|6|7| s[1] 配對 s[2]，長度為 2 s[6] 配對 s[7]，長度為 2 其餘未配對，長度為 1 ### 範例輸入2 ``` 1 ）（（）（（（）））（）（）（（（（）））））（（（（））（（）（））） ``` ### 範例輸出2 ``` 22 ``` ### 參考解答 --- # permutation 當我們要生成排列組合的時候，往往要花費大量時間來列出所有可能，在程式裡可能會使用多重 `for` 迴圈或者遞迴來處理，但往往時間複雜度都會很高。好在STL標準模板庫中有提供一種自動推導字典排序的函式，讓我們來看看 `permutation` 的用法吧！ ## 字典序字典序是透過ASCII編碼來比較大小，可以觀察數字 0 ~ 9 ，大寫字母 A ~ Z ，小寫字母 a ~ z 所對應的編碼，詳見下圖： ![image](https://hackmd.io/_uploads/r1jRzo0kkl.png) 圖片來源：https://www.sciencebuddies.org/science-fair-projects/references/ascii-table ### 以先後順序比較按照每個元素的順序，從第一個元素開始逐個比較，直到確定大小。例如： * `apple` < `banana`（因為 `a` 比 `b` 小）。 * `car` < `cat`（因為 `r` 比 `t` 小）。 ### 數字字典序把數字看作字符串來比較每一位，例如： * `123` < `132`（因為 `2` 比 `3` 小）。 * `12` < `120`（因為第 3 位空缺，看作比非空的小）。 ## 常用-生成所有排序 ```cpp=1 #include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; int a[N]; // 初始化陣列 a 為 1 到 N for (int i = 0; i < N; i++) { a[i] = i + 1; } // 生成所有字典序排列 do { for (int i = 0; i < N; i++) { cout << a[i] << " "; } cout << endl; } while (next_permutation(a, a + N)); // 將陣列 a 排成下一個字典序 // 若字典序已經最大則會回傳 false return 0; } ``` * 若陣列非升序排列，可視情況決定要不要先 `sort` ### 輸入 ``` 4 ``` ### 輸出結果 ``` 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 ``` --- # DP 動態規劃是用來降低複雜度最好的方式，但往往都需要一點巧思，將複雜的問題轉化成簡單的子問題，找到一個共同的規則套用在問題中。 --- ## 0/1背包背包問題指的是有一堆物品要放入背包，這些物品各自有不同的「重量」與「價值」，背包有重量限制，你的目標是找出在不超過重量限制的情況下，可以獲得的最大價值，舉例如下：背包限重8 |編號|重量|價值| |-|-|-| |1|2|1| |2|3|2| |3|4|5| |4|5|6| 如果使用窮舉法，可以找到以下可能： ``` 1+2+3+4：重量14 價值14 （超重） 1+2+3 ：重量9 價值8 （超重） 1+2+4 ：重量10 價值9 （超重） 1+3+4 ：重量11 價值12 （超重） 2+3+4 ：重量12 價值13 （超重） 1+2 ：重量5 價值3 1+3 ：重量6 價值6 1+4 ：重量7 價值7 2+3 ：重量7 價值7 2+4 ：重量8 價值8 3+4 ：重量9 價值11 （超重） 1 ：重量2 價值1 2 ：重量3 價值2 3 ：重量4 價值5 4 ：重量5 價值6 ``` 答案為 8，但窮舉法的時間複雜度是 $O(2^n)$，當物品種類變多，效率會變很差。 ### 演算法講解窮舉法之所以不方便解決這個問題，是因為物品過多，導致組合數太多。既然如此，為何我們不考慮先討論兩個物品就好呢？找出兩個問題的解後，再放入第三個物品，一次增加一種。於是我們畫出一個表格，第一行代表重量上限。並且因為可以選擇都不放，所以我們加入一個價值、重量皆為 0 的物品，方便討論。假設有 n 種物品，背包最大負重為 w ，初始化二維陣列 dp[n+1][n+1]。宣告兩個一維陣列儲存價值和重量，m 物品價值為 v[m]，重量為 w[m]。考慮第 i 種物品，最大重量為 j 的背包，dp[ｉ+ 1][ｊ]的最佳解，我們必須比較【放 / 不放】取利益： * 【不放】不考慮此物品時最佳解（dp[ｉ][ｊ]） * 【放】不考慮此物品，並且重量上限排除此物品的最佳解 + 本物品價值（dp[ｉ][ｊ – w[ｉ]] + v[ｉ]）在遍歷時要注意，ｊ必須大於等於 v[ｉ]，否則會越界（跑到陣列外）。若ｊ小於 v[ｉ]，由於無法將物品放入背包，故最佳解必為【不放】。 ※ 紅色那格為 dp[0][0] | 標號 | 價值 | 重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |---| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | 0 | 0 | 0 | **0** | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 2 | 2 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 3 | 5 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 4 | 6 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 我們先對編號 1 的物體進行討論。由於ｊ必須大於等於 v[ｉ]，所以從重量上限 2 開始討論。考慮【放 / 不放】： * 【不放】dp[0][2] = **0** * 【放】dp[0][2 – w[1]] + v[1] = dp[0][2 - 2] + v[1] = **0** + **1** = **1** 顯然 **1** > **0**，所以dp[1][2]= **1** | 標號 | 價值 | 重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |---| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | 0 | 0 | 0 | **0** | 0 | **0** | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | **1** | 2 | 0 | 0 | **1** | 0 | 0 | 0 | 0 | 0 | 0 | | 2 | 2 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 3 | 5 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 4 | 6 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 顯然對於重量上限 3~8 最佳解都會是 1。 | 標號 | 價值 | 重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |---| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 1 | 2 | 0 | 0 | 1 | **1** | **1** | **1** | **1** | **1** | **1** | | 2 | 2 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 3 | 5 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 4 | 6 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 接著加入編號 2 的物體進行討論。由於ｊ必須大於等於 v[ｉ]，所以最佳解必為【不放】。 | 標號 | 價值 | 重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |---| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 1 | 2 | **0** | **0** | **1** | 1 | 1 | 1 | 1 | 1 | 1 | | 2 | 2 | 3 | **0** | **0** | **1** | 0 | 0 | 0 | 0 | 0 | 0 | | 3 | 5 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 4 | 6 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 重量上限 3 時，考慮【放 / 不放】： * 【不放】dp[1][3] = **1** * 【放】dp[1][3 – w[2] + v[2] = dp[1][3 - 3] + v[2] = **0** + **2** = **2** 顯然 **2** > **1**，所以dp[1][2]= **2** | 標號 | 價值 | 重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |---| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 1 | 2 | **0** | 0 | 1 | **1** | 1 | 1 | 1 | 1 | 1 | | 2 | **2** | 3 | 0 | 0 | 1 | **2** | 0 | 0 | 0 | 0 | 0 | | 3 | 5 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 4 | 6 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 接著重量上限 5 的時候，考慮【放 / 不放】： * 【不放】dp[1][5] = **1** * 【放】dp[1][5 – w[2] + v[2] = dp[1][5 - 3] + v[2] = **1** + **2** = **3** 顯然 **3** > **1**，所以dp[1][2]= **3** | 標號 | 價值 | 重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |---| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 1 | 2 | 0 | 0 | **1** | 1 | 1 | **1** | 1 | 1 | 1 | | 2 | **2** | 3 | 0 | 0 | 1 | 2 | 2 | **3** | 0 | 0 | 0 | | 3 | 5 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 4 | 6 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 依此類推，完成表格，最後我們可以看到，背包重量上限 8 的情況下，考慮所有物品放入情況，最大價值為 **8** 。 | 標號 | 價值 | 重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |---| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 1 | 1 | 2 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | | 2 | 2 | 3 | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 | | 3 | 5 | 4 | 0 | 0 | 1 | 2 | 5 | 5 | 6 | 7 | 7 | | 4 | 6 | 5 | 0 | 0 | 1 | 2 | 5 | 6 | 6 | 7 | **8** | --- ### 小試身手 * 題目：神魔之塔是一款 2013 年所發行的轉珠遊戲，至今每月活躍玩家仍有破百萬。在遊戲中，每場戰鬥最多能出場六名英雄（不一定要上滿六名英雄），隊伍根據召喚師等級有隊伍空間上限，每隻英雄都有自己所佔的空間，以及各項屬性。現在子柚有 $\text{n}$ 名英雄，每名英雄所占隊伍空間為 $S_i$ ，綜合戰力為 $C_i$ ，帳號等級為 $\text{L}$ ，召喚師等級和隊伍空間上限的換算如下表，請替子柚找出最佳的隊伍配置。（照字典排序小到大輸出）帳號起始召喚師等級 1 ，這 1 級也算進去升 1 等內（也就是5等的時候背包上限會+1）起始背包空間上限為 85 。 | 等級區間 | 隊伍空間上限 | | -------- | -------- | | 0~99(含) | 每 5 等增加 1 | | 100~199(含) | 每 2 等增加 1 | | 200~399(含) | 每 5 等增加 1 | | 400~1000(含) | 每 10 等增加 1 | 舉例： 9 等的時候背包上限為 86 84 等的時候背包上限為 101 263 等的時候背包上限為 167 810 等的時候背包上限為 236 * 輸入說明：第一行輸入兩個整數 $\text{n}$ 和 $\text{L}$ ，第二行開始每行輸入兩個整數 $S_i$ 和 $C_i$ ，其中 $i$ 為英雄編號$\left(1 \leq i \leq \text{n}\right)$ * 輸出說明：輸出最高戰力 #### 範例輸入1 ``` 7 84 18 97 11 65 12 66 6 41 13 71 30 154 19 118 ``` #### 範例輸出1 ``` 547 ``` :::spoiler **參考解答** ```cpp=1 #include<bits/stdc++.h> using namespace std; const int c[]={0,100,200,400,INT_MAX}; const int c2[]={5,2,5,10,-1}; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n,L; cin>>n>>L; int w=85; for(int i=1;i<=4;i++){ if(L>c[i])w+=(c[i]-c[i-1])/c2[i-1]; else{ w+=(L-c[i-1])/c2[i-1]; break; } } vector<vector<int>>dp(w+1,vector<int>(7,0)); vector<vector<int>>v(n,vector<int>(2)); for(int i=0;i<n;i++)cin>>v[i][0]>>v[i][1]; for(int i=0;i<n;i++){ for(int j=w;j>=0;j--){ for(int k=6;k>=1;k--){ if(j>=v[i][0])dp[j][k]=max(dp[j][k],dp[j-v[i][0]][k-1]+v[i][1]); } } } int ans=-1; for(int i=0;i<=6;i++)ans=max(ans,dp[w][i]); cout<<ans; } ``` ::: --- ## LCS（Longest Common Subsequence） LCS（最長共同子序列）的定義為出現於每一個序列、而且是最長的子序列，舉例如下： ``` longest love ``` 不難發現，兩者的最長共同子序列為 loe，再看一個例子： ``` abcdefghijklmnzyxwvutsrqpo opqrstuvwxyzabcdefghijklmn ``` 這時候就頭昏眼花了吧，有沒有什麼方法可以讓我們有系統性的找出最長共同子序列呢？ --- ### 演算法講解回到最一開始的舉例，但我們這次把問題拆解： ``` longest love ``` 既然第一個字母 l 相同，那我其實只需要找到 ongest 和 ove 的最長共同子序列，再補上 l 就是答案了。 ``` ongest ove ``` 既然第一個字母 o 相同，那我其實只需要找到 ngest 和 ve 的最長共同子序列，再補上 o 就是答案了。 ``` ngest ve ``` v 和 ngest 都沒有相同的字母，那其實找 e 和 negst 的最長共同子序列就好了。 ``` ngest e ``` e 和 ng 都沒有相同的字母，其實只要找 e 和 est 的最長共同子序列就好了。 ``` est e ``` 既然第一個字母 e 相同，那我其實只需要找到 st 和空序列的最長共同子序列，再補上 e 就是答案了，但是任何序列和空序列的最長共同子序列一定是空序列，因此不需再往下做。回頭把最長共同子序列拼出來，依序可得 e o l，反向排列後即是答案 loe。這次我初始化的一個二維陣列，並且在遍歷的過程中遵守兩個規則： * 相同，從左上那格+1填入 * 不同，從上方和左方挑選最大的填入 ### 起始條件 ```cpp int dp[m][n]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ dp[i][j]=1; } } ``` ### 狀態轉移方程 ```cpp if(string1[i]==string2[j]){ dp[i][j]=dp[i-1][j-1]+1; } else{ dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } ``` ### 解答 ```cpp cout << dp[m-1][n-1]; ``` | | | l | o | n | g | e | s | t | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | **l** | 0 | | | | | | | | | **o** | 0 | | | | | | | | | **v** | 0 | | | | | | | | | **e** | 0 | | | | | | | | 從左上開始，先比較 l 和 l 是否相同，發現相同，所以從左上那格+1填入此格。 | | | l | o | n | g | e | s | t | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | | **0** | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | **l** | 0 | **1** | | | | | | | | **o** | 0 | | | | | | | | | **v** | 0 | | | | | | | | | **e** | 0 | | | | | | | | 接著比較 o 和 l 是否相同，發現不同，所以從上方和左方挑選最大的填入此格。 | | | l | o | n | g | e | s | t | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | | 0 | 0 | **0** | 0 | 0 | 0 | 0 | 0 | | **l** | 0 | **1** | **1** | | | | | | | **o** | 0 | | | | | | | | | **v** | 0 | | | | | | | | | **e** | 0 | | | | | | | | 遍歷完後，會得到下方表格： | | | l | o | n | g | e | s | t | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | **l** | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | | **o** | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | | **v** | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | | **e** | 0 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 此時若題目只詢問最長共同子序列長度，就只需要輸出最後一格就好了，但想知道這個序列是什麼也難不倒我們，只需要按照下方規則從最後一格遍歷回來： * 優先往大的地方走（只能往左和往上） * 發現下一格數字改變，記錄字母於陣列中，並且跳到左上方的格子 | | | l | o | n | g | e | s | t | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | **l** | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | | **o** | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | | **v** | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | | **e** | 0 | 1 | 2 | 2 | **2** | **3** | 3 | 3 | 陣列：｛e｝優先往大的地方走（但是只能往左和往上）。 | | | l | o | n | g | e | s | t | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | **l** | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | | **o** | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | | **v** | 0 | 1 | **2** | 2 | 2 | 2 | 2 | 2 | | **e** | 0 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | | | | l | o | n | g | e | s | t | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | **l** | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | | **o** | 0 | **1** | **2** | 2 | 2 | 2 | 2 | 2 | | **v** | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | | **e** | 0 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 陣列：｛e, o｝ | | | l | o | n | g | e | s | t | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | **l** | **0** | **1** | 1 | 1 | 1 | 1 | 1 | 1 | | **o** | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | | **v** | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | | **e** | 0 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 陣列：｛e, o, l｝最後反向輸出陣列即可得到最長共同子序列 loe 。 * 網路上找到的 [LCS操作練習](https://alchemist-al.com/algorithms/longest-common-subsequence) --- ### 小試身手 * 題目：子柚和ㄚ豪在上英文課時想打瞌睡，為了避免自己睡著，兩人決定比賽尋找課文文句的最長共同子序列（LCS），並且將找到的子序列輸出出來，其中空格與標點符號不計，大小寫視為相同。 * 輸入說明：輸入共有兩行含有空格的字串 * 輸出說明：第一行輸出一個整數 $\text{n}$ 代表最長共同子序列的長度，第二行輸出最長共同子序列的字串（以小寫字母輸出），若最長共同子序列為空字串，則輸出 $\text{Nothing}$。$\left( 0 \leq n \leq 100 \right)$ #### 範例輸入1 ``` Athletes often experience muscle pain because of their workout routines. It is advisable to stop exercising as soon as one is hurt to prevent more serious injuries. ``` #### 範例輸出1 ``` 30 tletotexercsinasoeirortrouines(或aletsoexerisinasoeirororouines) ``` --- :::spoiler **參考解答** ```cpp=1 #include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); string a,b; string s="",s2=""; getline(cin,a); for(auto i:a)if(isalpha(i))s+=tolower(i); getline(cin,b); for(auto i:b)if(isalpha(i))s2+=tolower(i); vector<vector<int>>v(s.size()+1,vector<int>(s2.size()+1,0)); for(int i=1;i<=s.size();i++){ for(int j=1;j<=s2.size();j++){ if(s[i-1]==s2[j-1])v[i][j]=v[i-1][j-1]+1; else v[i][j]=max(v[i-1][j],v[i][j-1]); } } cout<<v[s.size()][s2.size()]<<'\n'; if(v[s.size()][s2.size()]==0)cout<<"Nothing"; vector<char>v2; int i=s.size(),j=s2.size(); while(v2.size()!=v[s.size()][s2.size()]){ if(v[i][j]==max(v[i-1][j],v[i][j-1])+1){ v2.push_back(s[i-1]); i--; j--; } else{ if(v[i-1][j]>v[i][j-1])i--; else j--; } } for(int i=v2.size()-1;i>=0;i--)cout<<v2[i]; } ``` ::: --- ## LIS(Longest Increasing Subsequence) LIS（最長遞增子序列）的定義為所有子序列中，遞增的、最長的子序列，舉例如下： ``` 1 4 2 3 ``` 我們可以把所有子序列找出來： ``` 1 4 2 3 1 4 2 1 4 3 1 2 3 1 4 1 2 1 3 1 4 2 3 4 2 4 3 4 2 3 2 3 ``` 其中不屬於遞增（由小到大）的我們將其移除，留下遞增子序列： ``` 1 2 3 1 4 1 2 1 3 1 2 3 2 3 ``` 這之中最長的為 1 2 3，故最長遞增子序列為 1 2 3，長度為3。但窮舉出每一種可能效率太低了，下面我們學習一種演算法來提高效率。 --- ### 演算法講解首先將n個數字先存入a[n]陣列中，並且初始化長度為1。接著宣告一個陣列dp[n]，陣列中的值代表「以此數字為結尾的最長遞增子序列長度」。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | 1 | 1 | 1 | 1 | * 若本項大於前一項，代表可以再放入這一項到子序列後方，則長度為 `max`（前項+1 , 本項） * 若本項小於前項，代表無法放入這一項到子序列後方，則長度不變 ### 起始條件每個元素單獨成為 LIS 時，長度至少為 1。 ```cpp int dp[n]; for(int i=0;i<n;i++){ dp[i]=1; } ``` ### 狀態轉移方程 ```cpp if(a[i]>a[i-1]){ dp[i]=max(dp[i-1]+1,dp[i]); } else{ dp[i]=dp[i-1]; } ``` ### 解答 ```cpp cout << dp[n-1]; ``` 按照這個邏輯，我們用雙重 `for` 迴圈來比較每一項之間的大小關係。 4 > 1，`max`（1 + 1 , 1）= 2。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | **1** | **2** | 1 | 1 | 2 > 1，`max`（1 + 1 , 1）= 2。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | **1** | 2 | **2** | 1 | 2 < 4，不變。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | 1 | **2** | **2** | 1 | 3 > 1，`max`（1 + 1 , 1）= 2。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | **1** | 2 | 2 | **2** | 3 < 4，不變。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | 1 | **2** | 2 | **2** | 3 > 2，`max`（2 + 1 , 2）= 3。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | 1 | 2 | **2** | **3** | 故最長遞增子序列長度為3，若要找出此子序列，我們可以遵循以下規則進行反向遍歷。 * 紀錄第一個此長度的數字 * 長度為 1 時結束首次出現長度為 3，紀錄 3。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | 1 | 2 | 2 | **3** | 首次出現長度為 2，紀錄 2。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | 1 | 2 | **2** | 3 | 長度 2 並非首次出現，跳過不紀錄。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | 1 | **2** | 2 | 3 | 首次出現長度為 1，紀錄 1。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | **1** | 2 | 2 | 3 | * 網路上找到的 [LIS操作練習](https://alchemist-al.com/algorithms/longest-increasing-subsequence) --- ### 補充(只求LIS長度) 若是題目只求LIS長度，我們可以用偷懶一點的方式：嘗試找到LIS每個位置中可以擺放的最小值。(複雜度：$nlogn$) ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> a(n); // 原序列 for(int i=0;i<n;i++){ cin >> a[i]; } vector<int> b; // LIS每個位置的最小值 for(int i=0;i<n;i++){ if(b.empty() or b.back()<a[i]){ // 空序列or現在這個數比LIS最後一位還大 b.push_back(a[i]); // 插入到LIS最後方 } else{ *lower_bound(b.begin(),b.end(),a[i])=a[i]; // 使用二分搜找到第一個大於a[i]的數字，將其替換成更小的a[i]。 } } cout << b.size(); // 輸出LIS長度 return 0; } ``` ### 小試身手 * 題目：子柚和ㄚ豪在對樂透時，發現網站的數字分成開出順序和大小順序，而有些時候又非常恰巧兩者順序會相同，於是兩人就想找出開出數序中由小到大最長的排序方式。 ![{40BC8F76-9208-420D-B8FD-E5B0C4D9B145}](https://hackmd.io/_uploads/r1Err6CNkx.png) ![{7AE41533-D76F-4607-A8EE-6EDF6D95C049}](https://hackmd.io/_uploads/BJYvI6CVJg.png) * 輸入說明：第一行輸入一個整數 $\text{n}$ ，第二行輸入 $\text{n}$ 個用空格隔開的數字。 * 輸出說明：第一行輸出一個整數 $\text{m}$，表示最長遞增子序列的長度；第二行輸出最長遞增子序列（若有多個，輸出字典序最小的那一個）。 $\left(0 < m \leq 1000\right)$ * 第一子題（40%）：$\text{n} = 7 , 0 < \text{m} \leq 7$ 第二子題（60%）：$0 < \text{n} \leq 10000 , 0 \leq \text{m} \leq 1000$ #### 範例輸入1 ``` 7 29 38 28 11 07 39 33 ``` #### 範例輸出1 ``` 3 29 38 39 ``` #### 範例輸入2 ``` 15 63 24 98 2 4 68 24 64 21 9 67 34 128 91 45 ``` #### 範例輸出2 ``` 6 2 4 24 64 67 91 ``` --- :::spoiler **參考解答** ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n;cin>>n; vector<int>v(n); for(int i=0;i<n;i++)cin>>v[i]; vector<int>a(n,1); int ans=1; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if(v[j]>v[i])a[j]=max(a[i]+1,a[j]); } ans=max(a[i],ans); } cout<<ans<<'\n'; vector<int>tmp; for(int i=n-1;i>=0&&ans!=0;i--){ if(a[i]==ans){ tmp.push_back(v[i]); ans--; } } for(int i=tmp.size()-1;i>=0;i--)cout<<tmp[i]<<' '; } ``` ::: --- # BFS&DFS BFS（Breadth-First Search，廣度優先搜尋）是一種圖論演算法，常用於尋找最短路徑、遍歷圖中的所有節點或解決迷宮問題等。它的主要特點是逐層擴展，即先探索與當前節點距離為 1 的所有節點，再探索距離為 2、3... 直到遍歷完整個圖。 DFS（Depth-First Search，深度優先搜尋）是一種遍歷或搜尋圖的演算法，它的基本思想是「一條路走到底」，直到無法繼續後才回溯，並探索其他可能的路徑。DFS 可用來解決拓撲排序、圖遍歷、迷宮求解等問題。 ![image](https://hackmd.io/_uploads/B1HyBhg91g.png) ## 演算法講解以下我將示範如何使用BFS和DFS解決迷宮問題。迷宮問題的基本要素包括：起點、終點、障礙物。我們的目標是找到一條從起點到終點的可行路徑。來試看看走迷宮吧！ ### DFS實作 ``` 地圖大小：5 5 起點：0 0 終點：4 4 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 ``` 我們把地圖畫成表格來看（紅色是起點，橘色是終點） | 0 | 0 | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | 0 | 1 | 0 | 1 | 0 | | 0 | 0 | 0 | 0 | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | 首先我們站在起點（青色是路徑） | 0 | 0 | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | 0 | 1 | 0 | 1 | 0 | | 0 | 0 | 0 | 0 | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | 未到達終點 →分析可以走的方向：向右、向下 →選擇向右嘗試看看 | 0 | 0 | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | 0 | 1 | 0 | 1 | 0 | | 0 | 0 | 0 | 0 | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | 未到達終點 →分析可以走的方向：無 →走回上一步 | 0 | 0 | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | 0 | 1 | 0 | 1 | 0 | | 0 | 0 | 0 | 0 | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | 分析可以走的方向：向右（無法到達終點）、向下 →選擇向下嘗試看看 | 0 | 0 | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | **0** | 1 | 0 | 1 | 0 | | 0 | 0 | 0 | 0 | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | 未到達終點 →分析可以走的方向：向下 | 0 | 0 | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | **0** | 1 | 0 | 1 | 0 | | **0** | 0 | 0 | 0 | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | 未到達終點 →分析可以走的方向：向右 | 0 | 0 | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | **0** | 1 | 0 | 1 | 0 | | **0** | **0** | 0 | 0 | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | 未到達終點 →分析可以走的方向：向右 | 0 | 0 | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | **0** | 1 | 0 | 1 | 0 | | **0** | **0** | **0** | 0 | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | 未到達終點 →分析可以走的方向：向上、向右 →選擇向上嘗試看看 | 0 | 0 | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | **0** | 1 | **0** | 1 | 0 | | **0** | **0** | **0** | 0 | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | 未到達終點 →分析可以走的方向：無 →走回上一步 | 0 | 0 | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | **0** | 1 | **0** | 1 | 0 | | **0** | **0** | **0** | 0 | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | 分析可以走的方向：向上、向右 →選擇向右嘗試看看 | 0 | 0 | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | **0** | 1 | 0 | 1 | 0 | | **0** | **0** | **0** | **0** | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | 未到達終點 →分析可以走的方向：向下、向右 →選擇向下嘗試看看 | 0 | 0 | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | **0** | 1 | 0 | 1 | 0 | | **0** | **0** | **0** | **0** | 0 | | 1 | 1 | 1 | **0** | 1 | | 0 | 0 | 0 | 0 | **0** | 未到達終點 →分析可以走的方向：向下 | 0 | 0 | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | **0** | 1 | 0 | 1 | 0 | | **0** | **0** | **0** | **0** | 0 | | 1 | 1 | 1 | **0** | 1 | | 0 | 0 | 0 | **0** | **0** | 未到達終點 →分析可以走的方向：向右、向左 →選擇向右 | 0 | 0 | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | **0** | 1 | 0 | 1 | 0 | | **0** | **0** | **0** | **0** | 0 | | 1 | 1 | 1 | **0** | 1 | | 0 | 0 | 0 | **0** | **0** | 到達終點 →回傳有解、步數等資訊上述這個方法就是DFS的模型，我們可以用程式將這個邏輯寫出來，如下 ### DFS解 ```cpp= #include <bits/stdc++.h> using namespace std; const int MAX_N = 100; int maze[MAX_N][MAX_N]; // 迷宮地圖 bool visited[MAX_N][MAX_N]; // 記錄是否訪問過 int n, m; int min_steps = INT_MAX; // 記錄最短步數 // 方向向量：右、下、左、上 int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; void dfs(int x, int y, int steps, int ex, int ey) { if (x == ex && y == ey) { min_steps = min(min_steps, steps); return; } visited[x][y] = true; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && ny >= 0 && nx < n && ny < m && maze[nx][ny] == 0 && !visited[nx][ny]) { dfs(nx, ny, steps + 1, ex, ey); } } visited[x][y] = false; // 回溯 } int main() { cin >> n >> m; int sx, sy, ex, ey; cin >> sx >> sy >> ex >> ey; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> maze[i][j]; memset(visited, false, sizeof(visited)); dfs(sx, sy, 0, ex, ey); if (min_steps == INT_MAX) cout << "無法到達終點\n"; else cout << "最短路徑長度：" << min_steps << endl; return 0; } ``` --- 先求有，再求好，剛才雖然成功走出迷宮了，但前面走了一些冤枉路，也不太確定這是不是最短路徑，這時候我們的目標從「走出迷宮」變成以「最短路徑走出迷宮」，具體該怎麼做呢，讓我們繼續看下去。 ### BFS實作 ``` 地圖大小：5 5 起點：0 0 終點：4 4 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 ``` 我們把地圖畫成表格來看（紅色是起點，橘色是終點） | 0 | 0 | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | 0 | 1 | 0 | 1 | 0 | | 0 | 0 | 0 | 0 | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | 首先我們站在起點（青色是路徑），起點不需要走任何一步就能到達，所以標記為0，代表花0步可以走到這一格。 | 0 | 0 | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | 0 | 1 | 0 | 1 | 0 | | 0 | 0 | 0 | 0 | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | 這時候，假設我們自己只能走1步，請問能走到哪幾格，顯然是右方跟下方對吧，所以我們幫這兩格標記上數字1，代表花1步可以走到這一格。 | **0** | **1** | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | **1** | 1 | 0 | 1 | 0 | | 0 | 0 | 0 | 0 | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | 以此類推，再往外走1步，標記上數字2，代表花兩步可以走到這一格。 | **0** | **1** | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | **1** | 1 | 0 | 1 | 0 | | **2** | 0 | 0 | 0 | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | 下方省略講解，看圖 | **0** | **1** | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | **1** | 1 | 0 | 1 | 0 | | **2** | **3** | 0 | 0 | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | | **0** | **1** | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | **1** | 1 | 0 | 1 | 0 | | **2** | **3** | **4** | 0 | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | | **0** | **1** | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | **1** | 1 | **5** | 1 | 0 | | **2** | **3** | **4** | **5** | 0 | | 1 | 1 | 1 | 0 | 1 | | 0 | 0 | 0 | 0 | **0** | | **0** | **1** | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | **1** | 1 | **5** | 1 | 0 | | **2** | **3** | **4** | **5** | **6** | | 1 | 1 | 1 | **6** | 1 | | 0 | 0 | 0 | 0 | **0** | | **0** | **1** | 1 | 0 | 0 | | --- | --- | ---- | --- | --- | | **1** | 1 | **5** | 1 | **7** | | **2** | **3** | **4** | **5** | **6** | | 1 | 1 | 1 | **6** | 1 | | 0 | 0 | 0 | **7** | **0** | | **0** | **1** | 1 | 0 | **8** | | --- | --- | ---- | --- | --- | | **1** | 1 | **5** | 1 | **7** | | **2** | **3** | **4** | **5** | **6** | | 1 | 1 | 1 | **6** | 1 | | 0 | 0 | **8** | **7** | **8** | | **0** | **1** | 1 | **9** | **8** | | --- | --- | ---- | --- | --- | | **1** | 1 | **5** | 1 | **7** | | **2** | **3** | **4** | **5** | **6** | | 1 | 1 | 1 | **6** | 1 | | 0 | **9** | **8** | **7** | **8** | | **0** | **1** | 1 | **9** | **8** | | --- | --- | ---- | --- | --- | | **1** | 1 | **5** | 1 | **7** | | **2** | **3** | **4** | **5** | **6** | | 1 | 1 | 1 | **6** | 1 | | **10** | **9** | **8** | **7** | **8** | 完成整個迷宮後，我們就可以讀取終點那格的數字，就能知道最短路徑是多少了。這個方法就是BFS的模型，我們可以用程式將這個邏輯寫出來，如下 ### BFS解 ```cpp= #include <bits/stdc++.h> using namespace std; const int MAX_N = 100; int maze[MAX_N][MAX_N]; // 迷宮地圖，0 表示可走，1 表示牆壁 int dist[MAX_N][MAX_N]; // 記錄從起點到該點的距離 int n, m; // 迷宮大小（行數與列數） // 方向向量：右、下、左、上 int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; struct Node { int x, y, d; }; int bfs(int sx, int sy, int ex, int ey) { queue<Node> q; q.push({sx, sy, 0}); dist[sx][sy] = 0; while (!q.empty()) { Node cur = q.front(); q.pop(); // 抵達終點 if (cur.x == ex && cur.y == ey) return cur.d; // 探索四個方向 for (int i = 0; i < 4; i++) { int nx = cur.x + dx[i]; int ny = cur.y + dy[i]; if (nx >= 0 && ny >= 0 && nx < n && ny < m && maze[nx][ny] == 0 && dist[nx][ny] == -1) { dist[nx][ny] = cur.d + 1; q.push({nx, ny, cur.d + 1}); } } } return -1; // 無法到達 } int main() { cin >> n >> m; int sx, sy, ex, ey; cin >> sx >> sy >> ex >> ey; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { cin >> maze[i][j]; dist[i][j] = -1; // 初始化距離 } int result = bfs(sx, sy, ex, ey); if (result == -1) cout << "無法到達終點\n"; else cout << "最短路徑長度：" << result << endl; return 0; } ``` # 貪心演算法貪心演算法（Greedy Algorithm）是一種在每一個選擇中都做出當前最佳選擇的算法。透過每次選擇當下的局部最優解，最終達到全局最優解。貪心演算法並非適用於所有問題，只有在「貪心選擇性質」和「最優子結構性質」滿足的情況下，才能保證全局最優。簡而言之，貪心演算法只能用在「局部」可以放大到「全局」的題目。貪心演算法並沒有一個簡單的公式解法，主要依據題目的不同，將問題拆解成子問題，並對每一個子問題找到最佳解，從而得到問題的最佳解。下方舉例幾種適用貪心演算法的題目及演算法，可以仔細觀察題目是如何被拆解成子問題的。 ## Dijkstra Dijkstra 演算法是一種「單源最短路徑演算法」，用於計算從起點（源點）到圖中所有其他節點的最短路徑長度。它主要適用於「邊長權重為非負數」的圖。 ### 核心思路初始化二維陣列 w 紀錄邊長權重初始化一維陣列 d 紀錄每個節點的最短距離初始化一維陣列 visited 紀錄該節點是否拜訪過（以該點為出發點）初始化一維陣列 pre 紀錄該節點的前一個節點 →從未訪問的節點中，選擇距離最小的節點 u →將 u 標記為已訪問 →對於 u 的所有未訪問的鄰居節點 v，若經由 u 到 v 的距離小於目前記錄的距離，則進行更新 $d[v]=min(d[v],d[u]+w(u,v))$ 並將該鄰居節點 v 的前一個節點設為 u ### 演算法講解題目如下，假設A為起點 ![image](https://hackmd.io/_uploads/HymG87Q5ke.png) 初始化陣列 | | A | B | C | D | E | F | | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | **A** | 0 | 4 | 5 | 0 | 0 | 0 | | **B** | 4 | 0 | 11 | 9 | 7 | 0 | | **C** | 5 | 11 | 0 | 0 | 3 | 0 | | **D** | 0 | 9 | 0 | 0 | 13 | 2 | | **E** | 0 | 7 | 3 | 13 | 0 | 6 | | **F** | 0 | 0 | 0 | 2 | 6 | 0 | | A | B | C | D | E | F | | ---- | ---- | ---- | ---- | ---- | ---- | | 0 | INT_MAX | INT_MAX | INT_MAX | INT_MAX | INT_MAX | | false | false | false | false | false | false | | - | - | - | - | - | - | 從未訪問的節點中，選擇距離最小的節點A 拜訪A鄰居節點B、C * B：0+4=4 < INT_MAX → 更新 * C：0+5=5 < INT_MAX → 更新 | A | B | C | D | E | F | | ---- | ---- | ---- | ---- | ---- | ---- | | 0 | 4 | 5 | INT_MAX | INT_MAX | INT_MAX | | true | false | false | false | false | false | | - | A | A | - | - | - | 從未訪問的節點中，選擇距離最小的節點B 拜訪B鄰居節點D、E * D：4+9=13 < INT_MAX → 更新 * E：4+7=11 < INT_MAX → 更新 | A | B | C | D | E | F | | ---- | ---- | ---- | ---- | ---- | ---- | | 0 | 4 | 5 | 13 | 11 | INT_MAX | | true | true | false | false | false | false | | - | A | A | B | B | - | 從未訪問的節點中，選擇距離最小的節點C 拜訪C鄰居節點E（B已經訪問過） * E：5+3=8 < 11 → 更新 | A | B | C | D | E | F | | ---- | ---- | ---- | ---- | ---- | ---- | | 0 | 4 | 5 | 13 | 8 | INT_MAX | | true | true | true | false | false | false | | - | A | A | B | C | - | 從未訪問的節點中，選擇距離最小的節點E 拜訪E鄰居節點D、F（B、C已經訪問過） * D：8+13=21 > 13 → 不更新 * F：8+6=14 < INT_MAX → 更新 | A | B | C | D | E | F | | ---- | ---- | ---- | ---- | ---- | ---- | | 0 | 4 | 5 | 13 | 8 | 14 | | true | true | true | false | true | false | | - | A | A | B | C | E | 從未訪問的節點中，選擇距離最小的節點D 拜訪D鄰居節點F（B、E已經訪問過） * F：13+2=15 > 14 → 不更新 | A | B | C | D | E | F | | ---- | ---- | ---- | ---- | ---- | ---- | | 0 | 4 | 5 | 13 | 8 | 14 | | true | true | true | true | true | false | | - | A | A | B | C | E | 從未訪問的節點中，選擇距離最小的節點F 沒有可拜訪的節點 | A | B | C | D | E | F | | ---- | ---- | ---- | ---- | ---- | ---- | | 0 | 4 | 5 | 13 | 8 | 14 | | true | true | true | true | true | true | | - | A | A | B | C | E | 從A出發，最短路徑結果如下： | 終點 | 最短距離 | 路徑 | | ---- | ---- | ---- | | A | 0 | A | | B | 4 | A→B | | C | 5 | A→C | | D | 13 | A→B→D | | E | 8 | A→C→E | | F | 14 | A→C→E→F | --- # Floyd-Warshall Floyd-Warshall 演算法使用三層迴圈，固定中間點來計算任意兩點之間的最短距離或最小最大權重等。雖然此演算法簡單直觀，但時間複雜度較高，通常是 $O(n^3)$，因此需要根據具體問題的情況來選擇是否使用。 ## 最短距離 ```cpp for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ for(int k=0;k<n;k++){ int dis=a[j][i]+a[i][k]; // i 作為 j 走到 k 的中繼點 a[j][k]=min(dis,a[j][k]); // 維護最短距離 } } } ``` ## 最小最大權重（Minimax Path） ```cpp for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ for(int k=0;k<n;k++){ int dis=max(a[j][i],a[i][k]); // i 作為 j 走到 k 的中繼點 a[j][k]=min(dis,a[j][k]); // 維護最小權重 } } } ``` ## 最大最小權重（Maximin Path） ```cpp for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ for(int k=0;k<n;k++){ int dis=min(a[j][i],a[i][k]); // i 作為 j 走到 k 的中繼點 a[j][k]=max(dis,a[j][k]); // 維護最大權重 } } } ``` ## 練習題 [c128. 00544 - Heavy Cargo](https://zerojudge.tw/ShowProblem?problemid=c128) # 快速冪取餘數是程式中常見的手法，但有些時候數字太大，連long long都存不下，該怎麼處理呢?答案很簡單，用數學的方式處理~ $(a×b)\text{ mod }m = ((a \text{ mod } m)×(b \text{ mod } m)) \text{ mod } m$ 利用此數學性質，我們可以在每一步計算時取餘數，每次將指數減半，從而避免中間結果過大。整個過程只需要 $O(log (n))$的時間複雜度，非常高效。 ## 二進制快速冪 ```cpp #include <iostream> using namespace std; long long binary_pow(long long base, long long exp, long long mod) { long long result = 1; base = base % mod; // 確保 base 小於 mod while (exp > 0) { if (exp % 2 == 1) { // 當 exp 是奇數時，乘上 base result = (result * base) % mod; } base = (base * base) % mod; // base 每次平方 exp /= 2; // exp 右移一位 } return result; } int main() { long long k, n; cin >> k >> n; cout << binary_pow(10, k, n) << endl; return 0; } ``` ## 非二進制快速冪 ```cpp #include <iostream> using namespace std; long long quick_pow(long long base, long long exp, long long mod) { long long result = 1; while (exp > 0) { if (exp % 2 == 1) { result = (result * base) % mod; } base = (base * base) % mod; exp /= 2; } return result; } int main() { long long k, n; cin >> k >> n; cout << quick_pow(10, k, n) << endl; return 0; } ``` ## 練習題 [b467. NOIP2013 Day1.1.转圈游戏](https://zerojudge.tw/ShowProblem?problemid=b467) # 並查集（DSU）並查集（Disjoint Set Union, DSU）是一種用來處理不相交集合（disjoint sets）操作的資料結構，常見於圖論中的聯通性問題。查詢（Find）：查詢某一元素所屬的集合。合併（Union）：將兩個集合合併成一個集合。 ## 舉例在一款線上遊戲中，每位玩家一開始都是獨自行動，也就是說，每個人都擁有自己的小公會（自己是自己的會長）。隨著遊戲進行，玩家們可以互相組隊，形成新的公會，而不同的公會也可能進一步合併成更大的公會。為了管理整個公會系統，我們需要支援兩種操作：合併公會（Union）：兩個公會合併成一個大公會。查詢所屬公會（Find）：快速查出某位玩家目前所屬的公會（以會長代表）。當兩個公會合併後，系統會指定其中一位作為新的會長，代表整個新公會。而每個該公會的玩家都會歸順到這位新會長下。 ## 主要操作 ```cpp // f(now): 查詢現在這位玩家所屬公會的代表（公會會長） // 同時做「路徑壓縮」，讓玩家以後能更快找到自己的會長 int f(int now) { if (p[now] == now) { // 如果自己就是自己的會長（代表），直接回傳 return now; } else { // 否則，往上找到會長，並把自己直接連到會長（壓縮路徑） return p[now] = f(p[now]); } } // 初始化：一開始每位玩家都創自己的公會（自己是自己的會長） for (int i = 0; i < n; i++) { p[i] = i; } // 進行 m 次公會合併操作 for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; // 讀入要合併的兩位玩家 a = f(a); // 找出 a 所屬的公會會長 b = f(b); // 找出 b 所屬的公會會長 if (a != b) { // 如果他們不在同一個公會，就把 a 的公會併入 b 的公會 p[a] = b; } } ``` ## 練習題 [a445. 新手訓練系列- 我的朋友很少](https://zerojudge.tw/ShowProblem?problemid=a445) # 最小生成樹（MST）在圖論中，最小生成樹（Minimum Spanning Tree, MST）是一棵包含所有節點且權重總和最小的無環子圖。換句話說，給定一個無向加權圖，我們希望找到一個連接所有節點的子圖，使得： * 沒有環 * 剛好連接所有節點 * 權重總和最小 ## Kruskal 演算法 Kruskal 演算法是一種貪心法（Greedy Algorithm），其步驟如下： 1. 將所有邊按照權重排序（從小到大）。 2. 使用並查集（Union-Find）來維護集合狀態。 3. 依次選擇最小的邊，如果不會形成環則加入 MST。 4. 重複步驟 3，直到加入 (n-1) 條邊為止（假設圖中有 n 個節點）。時間複雜度主要來自邊的排序，為 $O(m \text{ log } m)$，其中 m 是邊的數量。 ```cpp=1 #include<bits/stdc++.h> using namespace std; vector<int> p; // 並查集 int f(int now){ if(p[now]==now) return now; else{ p[now]=f(p[now]); return p[now]; } } int main(){ ios::sync_with_stdio(0); cin.tie(0); int n,m; typedef pair<int,pair<int,int>> node; // (A到B邊的權重,A點,B點) while(cin >> n >> m){ int need=n-1; // n個節點的樹應該會有n-1條邊 vector<node> v; p.resize(n); for(int i=0;i<m;i++){ int a,b,c; cin >> a >> b >> c; v.push_back({c,{a,b}}); v.push_back({c,{b,a}}); } sort(v.begin(),v.end()); // 從邊長權重最小開始考慮 // 並查集預設，每個節點都是單獨的集合 for(int i=0;i<n;i++){ p[i]=i; } long long sum=0; for(auto h : v){ int x=f(h.second.first); int y=f(h.second.second); // 不可繞成環 if(x==y){ continue; } else{ p[x]=y; need--; sum+=h.first; } } if(need==0){ cout << sum << endl; } else{ cout << "-1" << endl; // 無法生成MST，依題意輸出 } } return 0; } ``` ## Prim 演算法 Prim 演算法與 Kruskal 不同，它是基於逐步擴展樹的方式來構造 MST。演算法的步驟如下： 1. 從任意節點開始（通常選擇 0 號節點）。 2. 使用最小堆（Priority Queue）記錄鄰近的邊，並維護一個「已選擇的節點集合」。 3. 每次選擇與當前 MST 相連且權重最小的邊，將新的節點加入 MST。 4. 重複步驟 3，直到所有節點都被加入 MST。 ```cpp= #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; while (cin >> n >> m) { /* 建立鄰接表：adj[u] 內存放 (v, w)，表示 u ↔ v 之間有一條權重為 w 的無向邊 */ vector<vector<pair<int, int>>> adj(n); for (int i = 0; i < m; ++i) { int a, b, c; cin >> a >> b >> c; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } /* Prim 相關資料結構 */ vector<bool> inMST(n, false); // 節點是否已納入 MST vector<int> best(n, 1e9); // 目前連進每個節點的最小邊權 priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int, int>>> pq; // (邊權, 節點) 的最小堆 /* 從 0 號節點出發 */ best[0] = 0; pq.push({0, 0}); int total = 0; // MST 權重總和 int picked = 0; // 已選進 MST 的節點數 /* 主迴圈：每次拉出與 MST 相連且最小的邊 */ while (!pq.empty() && picked < n) { auto [w, u] = pq.top(); pq.pop(); if (inMST[u]) continue; // 重複點，跳過 inMST[u] = true; // 把 u 納入 MST total += w; // 加上這條邊的權重 picked++; // 已選節點數量+1 /* 更新鄰接節點的最佳邊權 */ for (auto [v, wt] : adj[u]) { if (!inMST[v] && wt < best[v]) { best[v] = wt; pq.push({best[v], v}); } } } /* 判斷是否成功連通所有節點 */ if (picked == n) { cout << total << '\n'; // 成功：輸出最小權重和 } else { cout << -1 << '\n'; // 失敗：圖不連通，無法形成 MST } } return 0; } ``` ## 練習題 [a129. 最小生成樹](https://zerojudge.tw/ShowProblem?problemid=a129) # 拓樸排序在tree中，我們可以輕易找到點的層級順序，但在有向圖中，我們似乎無法給出一個準確的排序來滿足由高層級往低層級的拜訪，拓樸排序問題因此而生。 ## 原始問題考慮一個有向圖，上方有n個點m條邊，點依序編號1~n，希望找到一種排序p1,p2,p3,...,pn，滿足對於任意一條邊x→y(x=pi,y=pj)都有i<j呢? ![image](https://hackmd.io/_uploads/SyTkYnnqye.png) ## 思路若是一個點存在任何的入度，那它一定不是序列的第一個數。反之，若是一個點沒有任何入度，則它可以成為序列的第一個數。找到序列的第一個數後，就可以把該點的出度都拔掉，產生下一個獨立的子問題，遞迴求解即可得到拓樸排序。 ## 遞迴演算法 1. 找到入度為0的點p 2. 把 p 和它所有的出度都拔掉，形成一張新的有向圖 3. 回到1.求解新的有向圖，並把序列接在 p 後面 ## BFS演算法 1. 把所有入度為0的點都推入queue 2. 從queue中取出點p 3. 把p的出度都拔掉，維護相關點的入度值(若點q的入度有p，則此時p移除，入度-1) 4. 若某點在3.的執行中入度變成0，推入queue 5. 若queue不為空，繼續2. 6. 算法結束後，若得到一組解，可證得此圖為有向無環圖(DAG)；反之則此圖必存在環 ## 拓樸排序-BFS版本 ```cpp=1 #include <bits/stdc++.h> using namespace std; vector<int> adj[1000]; int in[1000]; vector<int> topo; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; memset(in, 0, sizeof(in)); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); in[v]++; } queue<int> q; for (int i = 0; i < n; i++) { if (in[i] == 0) { q.push(i); } } while (!q.empty()) { int now = q.front(); q.pop(); topo.push_back(now); for (int nxt : adj[now]) { in[nxt]--; if (in[nxt] == 0) { q.push(nxt); } } } if (topo.size() == n) { for (int x : topo) cout << x << " "; cout << "\n"; } else { cout << "Cycle detected\n"; } return 0; } ``` ## 練習題 [b333. NOIP2013 4.车站分级](https://zerojudge.tw/ShowProblem?problemid=b333) ## DAG longest path ```cpp= #include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int m; // 測試資料組數 cin >> m; while (m--) { int n; // 節點數 cin >> n; vector<int> t(n + 1); // t[i] 表示完成第 i 個項目所需的天數 vector<vector<int>> out(n + 1); // out[i] 表示第 i 個項目的下游項目編號 vector<int> in(n + 1, 0); // in[i] 表示第 i 個項目的入邊數（上游項目數目） vector<int> s(n + 1, 0); // s[i] 表示完成第 i 個項目時，累計花費的時間 for (int i = 1; i <= n; ++i) { int a, b; cin >> a >> b; t[i] = a; for (int j = 0; j < b; ++j) { int c; cin >> c; out[i].push_back(c); in[c]++; } } queue<int> q; for (int i = 1; i <= n; ++i) { if (in[i] == 0) q.push(i); } int ans = 0; while (!q.empty()) { int now = q.front(); q.pop(); s[now] += t[now]; ans = max(ans, s[now]); for (int i : out[now]) { s[i] = max(s[i], s[now]); in[i]--; if (in[i] == 0) q.push(i); } } cout << ans << "\n"; } return 0; } ``` ## 練習題 [a454. TOI2010 第二題：專案時程](https://zerojudge.tw/ShowProblem?problemid=a454) # 尤拉路徑（Eulerian Path）在圖論中，尤拉路徑（Eulerian Path）是指一條不重複經過任何邊的路徑，這條路徑可以穿越所有邊一次且只一次。如果這條路徑的起點和終點相同，我們稱它為尤拉迴路（Eulerian Circuit）或尤拉環（Eulerian Cycle）。 ## 存在條件 ### 無向圖尤拉路徑存在的條件： * 圖是連通的（除了孤立點以外） * 有 0 或 2 個奇數度數的節點（度數 = 與該點相連的邊的條數）尤拉迴路存在的條件： * 圖是連通的 * 所有節點的度數都是偶數 ### 有向圖尤拉路徑存在的條件： * 圖是連通的（忽略方向） * 至多有一個點滿足出度 = 入度 + 1（起點） * 至多有一個點滿足入度 = 出度 + 1（終點） * 其他所有點的入度等於出度尤拉迴路存在的條件： * 圖是連通的 * 每個點的入度 = 出度 ## Hierholzer 演算法 1. 判斷是否存在尤拉路徑／迴路： 2. 從合法起點出發：若有奇數度點，就從其中之一出發若全為偶數度，則任一點皆可當起點 3. 沿著還沒走過的邊一直往下走，直到走到底： 4. 回朔插入路徑：當走到底（沒有可走邊）時，就把當前節點加入最終路徑中（小路徑插入主路徑） 5. 最後檢查是否所有邊都走過： ```cpp=1 #include <bits/stdc++.h> using namespace std; const int MAXN = 100005; vector<multiset<int>> adj; // 每個節點的鄰邊集合 vector<int> path; // 儲存最後走出來的尤拉路徑 // Step 4：遞迴 DFS，邊走邊把路徑插入 void dfs(int u) { while (!adj[u].empty()) { int v = *adj[u].begin(); // 取出最小鄰點 v adj[u].erase(adj[u].begin()); // 刪除 u → v 的邊 adj[v].erase(adj[v].find(u)); // 刪除 v → u 的對應邊（無向圖） dfs(v); // 繼續走下去 } path.push_back(u); // 回朔階段，把這個點加入答案路徑 } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; // n = 節點數, m = 邊數 cin >> n >> m; adj.assign(n, multiset<int>()); // 初始化每個節點的鄰邊集合 // 讀入圖的邊（無向圖） for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[u].insert(v); adj[v].insert(u); } // Step 1：檢查圖中奇數度的點數量 int odd = 0, start = 0; for (int i = 0; i < n; i++) { if (adj[i].size() % 2 == 1) { odd++; start = i; // 找一個奇數度點當作起點 } } // Step 1：尤拉路徑僅可能出現在 0 或 2 個奇數度點的圖中 if (odd != 0 && odd != 2) { cout << "No Eulerian Path\n"; return 0; } // Step 2：從起點開始 DFS（奇數度點優先，否則任意點） dfs(start); // Step 5：檢查是否所有邊都被走過（路徑長度應為 m + 1） if (path.size() != m + 1) { cout << "No Eulerian Path (Disconnected)\n"; } else { reverse(path.begin(), path.end()); // 反轉結果得到正向路徑 cout << "Eulerian Path:\n"; for (int u : path) { cout << u << " "; } cout << "\n"; } return 0; } ``` ## 練習題 [1084 . 一筆畫問題](https://tioj.ck.tp.edu.tw/problems/1084) # LCA 紀錄DFS完整拜訪過程，包含深度跟點的名稱 ![image](https://hackmd.io/_uploads/r1DQ_Uxj1l.png) 接著直接查詢 ![image](https://hackmd.io/_uploads/SJ0HdIloJl.png) ```cpp= #include<bits/stdc++.h> using namespace std; vector<int> depth; vector<int> nodes; vector<vector<int>> a; vector<bool> visited; int n,q; void dfs(int now,int d,int les){ visited[now]=true; depth.push_back(d); nodes.push_back(now); for(auto h : a[now]){ if(!visited[h]){ dfs(h,d+1,now); } } if(d-1>=0){ depth.push_back(d-1); nodes.push_back(les); } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> q; a.resize(n); visited.resize(n); for(int i=0;i<n;i++){ int x; while(cin >> x){ if(x==0){ break; } x--; a[i].push_back(x); } } dfs(0,0,0); for(int i=0;i<q;i++){ int f,g; cin >> f >> g; f--; g--; int index1,index2; for(int j=nodes.size()-1;j>=0;j--){ if(nodes[j]==f){ index1=j; break; } } for(int j=nodes.size()-1;j>=0;j--){ if(nodes[j]==g){ index2=j; break; } } int minn=INT_MAX; int index3; if(index1>index2){ swap(index1,index2); } for(int j=index1;j<=index2;j++){ if(depth[j]<minn){ minn=depth[j]; index3=j; } } cout << nodes[index3]+1 << " "; cout << abs(depth[index1]-depth[index3])+abs(depth[index2]-depth[index3]) << endl; } return 0; } ``` ## 線上資源 [Lowest Common Ancestor (LCA) Problem | Eulerian path method](https://www.youtube.com/watch?v=sD1IoalFomA&t=95s) ## 練習題 [d767. 血緣關係](https://zerojudge.tw/ShowProblem?problemid=d767)