---
# System prepended metadata

title: 【子柚程式】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 指向的地址: " << p << endl; // 顯示指標 p 儲存的地址
    cout << "p 指向的值: " << *p << endl; // 解引用指標，顯示 p 指向的值（即 a 的值）

    return 0;
}

```
# 迭代器
迭代器就樣郵差一樣，根據信件的地址，去訪問那位住戶。
## 宣告
```cpp=1
vector<int>::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
```
測資說明：如下表
| <font color="#f00">（</font> | <font color="#F7A004">（</font> | <font color="#F7A004">）</font> | <font color="#f00">）</font> | <font color="#AC19C9">（</font> | <font color="#AC19C9">）</font> | <font color="#1936C9">（</font> | <font color="#1936C9">）</font> | ） | （ |
| -- | -- | -- | -- | -- | -- | -- | -- | -- | -- |
|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

| （ | （ | <font color="#f00">（</font> | <font color="#F7A004">（</font> | <font color="#F7A004">）</font> | <font color="#1936C9">（</font> | <font color="#1936C9">）</font> | <font color="#f00">）</font> |
| -- | -- | -- | -- | -- | -- | -- | -- |
|0|1|2|3|4|5|6|7|

s[3] 配對 s[4]，長度為 2
s[5] 配對 s[6]，長度為 2
s[2] 配對 s[7]，長度為 6
其餘未配對，長度為 1

| ） | <font color="#f00">（</font> | <font color="#f00">）</font> | ） | ） | （ | <font color="#1936C9">（</font> | <font color="#1936C9">）</font> |
| -- | -- | -- | -- | -- | -- | -- | -- |
|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 | <font color="#f00">**0**</font> | 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] = <font color="#F7A004">**0**</font>
* 【放】dp[0][2 – w[1]] + v[1] = dp[0][2 - 2] + v[1] = <font color="#00A600">**0**</font> + <font color="#0080FF">**1**</font> = <font color="#f00">**1**</font>

顯然 <font color="#f00">**1**</font> > <font color="#F7A004">**0**</font>，所以dp[1][2]= <font color="#f00">**1**</font>

| 標號 | 價值 | 重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | 0 | 0 | <font color="#00A600">**0**</font> | 0 | <font color="#F7A004">**0**</font> | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | <font color="#0080FF">**1**</font> | 2 | 0 | 0 | <font color="#f00">**1**</font> | 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 | <font color="#f00">**1**</font> | <font color="#f00">**1**</font> | <font color="#f00">**1**</font> | <font color="#f00">**1**</font> | <font color="#f00">**1**</font> | <font color="#f00">**1**</font> |
| 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 | <font color="#F7A004">**0**</font> | <font color="#F7A004">**0**</font> | <font color="#F7A004">**1**</font> | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 3 | <font color="#f00">**0**</font> | <font color="#f00">**0**</font> | <font color="#f00">**1**</font> | 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] = <font color="#F7A004">**1**</font>
* 【放】dp[1][3 – w[2] + v[2] = dp[1][3 - 3] + v[2] = <font color="#00A600">**0**</font> + <font color="#0080FF">**2**</font> = <font color="#f00">**2**</font>

顯然 <font color="#f00">**2**</font> > <font color="#F7A004">**1**</font>，所以dp[1][2]= <font color="#f00">**2**</font>

| 標號 | 價值 | 重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 2 | <font color="#00A600">**0**</font> | 0 | 1 | <font color="#F7A004">**1**</font> | 1 | 1 | 1 | 1 | 1 |
| 2 | <font color="#0080FF">**2**</font> | 3 | 0 | 0 | 1 | <font color="#f00">**2**</font> | 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] = <font color="#F7A004">**1**</font>
* 【放】dp[1][5 – w[2] + v[2] = dp[1][5 - 3] + v[2] = <font color="#00A600">**1**</font> + <font color="#0080FF">**2**</font> = <font color="#f00">**3**</font>

顯然 <font color="#f00">**3**</font> > <font color="#F7A004">**1**</font>，所以dp[1][2]= <font color="#f00">**3**</font>

| 標號 | 價值 | 重量 | 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 | <font color="#00A600">**1**</font> | 1 | 1 | <font color="#F7A004">**1**</font> | 1 | 1 | 1 |
| 2 | <font color="#0080FF">**2**</font> | 3 | 0 | 0 | 1 | 2 | 2 | <font color="#f00">**3**</font> | 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 的情況下，考慮所有物品放入情況，最大價值為 <font color="#f00">**8**</font> 。

| 標號 | 價值 | 重量 | 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 | <font color="#f00">**8**</font> |

---

### 小試身手

* 題目：神魔之塔是一款 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填入此格。

|  |  | <font color="#f00">l</font> | o | n | g | e | s | t |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|   | <font color="#1936C9">**0**</font> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <font color="#f00">**l**</font> | 0 | <font color="#AC19C9">**1**</font> |  |  |  |  |  |  |
| **o** | 0 |  |  |  |  |  |  |  |
| **v** | 0 |  |  |  |  |  |  |  |
| **e** | 0 |  |  |  |  |  |  |  |

接著比較 o 和 l 是否相同，發現不同，所以從上方和左方挑選最大的填入此格。

|  |  | l | <font color="#f00">o</font> | n | g | e | s | t |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|   | 0 | 0 | <font color="#1936C9">**0**</font> | 0 | 0 | 0 | 0 | 0 |
| <font color="#f00">**l**</font> | 0 | <font color="#1936C9">**1**</font> | <font color="#AC19C9">**1**</font> |  |  |  |  |  |
| **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 | <font color="#f00">e</font> | 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 | <font color="#F7A004">2</font> | 2 | 2 | 2 |
| <font color="#f00">**e**</font> | 0 | 1 | 2 | 2 | <font color="#1936C9">**2**</font> | <font color="#AC19C9">**3**</font> | 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 | <font color="#F7A004">2</font> | 2 | 2 | 2 | 2 | 2 |
| **v** | 0 | 1 | <font color="#AC19C9">**2**</font> | 2 | 2 | 2 | 2 | 2 |
| **e** | 0 | 1 | 2 | 2 | 2 | 3 | 3 | 3 |

|  |  | l | <font color="#f00">o</font> | n | g | e | s | t |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|   | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| **l** | 0 | <font color="#F7A004">1</font> | 1 | 1 | 1 | 1 | 1 | 1 |
| <font color="#f00">**o**</font> | 0 | <font color="#1936C9">**1**</font> | <font color="#AC19C9">**2**</font> | 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｝

|  |  | <font color="#f00">l</font> | o | n | g | e | s | t |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|   | <font color="#F7A004">0</font> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <font color="#f00">**l**</font> | <font color="#1936C9">**0**</font> | <font color="#AC19C9">**1**</font> | 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。

| <font color="#1936C9">1</font> | <font color="#f00">4</font> | 2 | 3 |
|---- | ---- | ---- | ---- |
| <font color="#F7A004">**1**</font> | <font color="#AC19C9">**2**</font> | 1 | 1 |

2 > 1，`max`（1 + 1 , 1）= 2。

| <font color="#1936C9">1</font> | 4 | <font color="#f00">2</font> | 3 |
|---- | ---- | ---- | ---- |
| <font color="#F7A004">**1**</font> | 2 | <font color="#AC19C9">**2**</font> | 1 |

2 < 4，不變。

| 1 | <font color="#1936C9">4</font> | <font color="#f00">2</font> | 3 |
|---- | ---- | ---- | ---- |
| 1 | <font color="#F7A004">**2**</font> | <font color="#AC19C9">**2**</font> | 1 |

3 > 1，`max`（1 + 1 , 1）= 2。

| <font color="#1936C9">1</font> | 4 | 2 | <font color="#f00">3</font> |
|---- | ---- | ---- | ---- |
| <font color="#F7A004">**1**</font> | 2 | 2 | <font color="#AC19C9">**2**</font> |

3 < 4，不變。

| 1 | <font color="#1936C9">4</font> | 2 | <font color="#f00">3</font> |
|---- | ---- | ---- | ---- |
| 1 | <font color="#F7A004">**2**</font> | 2 | <font color="#AC19C9">**2**</font> |

3 > 2，`max`（2 + 1 , 2）= 3。

| 1 | 4 | <font color="#1936C9">2</font> | <font color="#f00">3</font> |
|---- | ---- | ---- | ---- |
| 1 | 2 | <font color="#F7A004">**2**</font> | <font color="#AC19C9">**3**</font> |

故最長遞增子序列長度為3，若要找出此子序列，我們可以遵循以下規則進行反向遍歷。

* 紀錄第一個此長度的數字
* 長度為 1 時結束

首次出現長度為 3，紀錄 3。

| 1 | 4 | 2 | <font color="#f00">3</font> |
|---- | ---- | ---- | ---- |
| 1 | 2 | 2 | <font color="#AC19C9">**3**</font> |

首次出現長度為 2，紀錄 2。

| 1 | 4 | <font color="#f00">2</font> | 3 |
|---- | ---- | ---- | ---- |
| 1 | 2 | <font color="#AC19C9">**2**</font> | 3 |

長度 2 並非首次出現，跳過不紀錄。

| 1 | <font color="#f00">4</font> | 2 | 3 |
|---- | ---- | ---- | ---- |
| 1 | <font color="#AC19C9">**2**</font> | 2 | 3 |

首次出現長度為 1，紀錄 1。

| <font color="#f00">1</font> | 4 | 2 | 3 |
|---- | ---- | ---- | ---- |
| <font color="#AC19C9">**1**</font> | 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
```
我們把地圖畫成表格來看（紅色是起點，橘色是終點）

| <font color="#f00">0</font> | 0 | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

首先我們站在起點（青色是路徑）

| <font color="#00FFFF">0</font> | 0 | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

未到達終點
→分析可以走的方向：向右、向下
→選擇向右嘗試看看

| <font color="#00FFFF">0</font> | <font color="#00FFFF">0</font> | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

未到達終點
→分析可以走的方向：無
→走回上一步


| <font color="#00FFFF">0</font> | 0 | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

分析可以走的方向：向右（無法到達終點）、向下
→選擇向下嘗試看看

| <font color="#00FFFF">0</font> | 0 | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| <font color="#00FFFF">**0**</font> | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

未到達終點
→分析可以走的方向：向下

| <font color="#00FFFF">0</font> | 0 | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| <font color="#00FFFF">**0**</font> | 1 | 0 | 1 | 0 |
| <font color="#00FFFF">**0**</font> | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

未到達終點
→分析可以走的方向：向右

| <font color="#00FFFF">0</font> | 0 | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| <font color="#00FFFF">**0**</font> | 1 | 0 | 1 | 0 |
| <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

未到達終點
→分析可以走的方向：向右

| <font color="#00FFFF">0</font> | 0 | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| <font color="#00FFFF">**0**</font> | 1 | 0 | 1 | 0 |
| <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

未到達終點
→分析可以走的方向：向上、向右
→選擇向上嘗試看看

| <font color="#00FFFF">0</font> | 0 | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| <font color="#00FFFF">**0**</font> | 1 | <font color="#00FFFF">**0**</font> | 1 | 0 |
| <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

未到達終點
→分析可以走的方向：無
→走回上一步

| <font color="#00FFFF">0</font> | 0 | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| <font color="#00FFFF">**0**</font> | 1 | <font color="#00FFFF">**0**</font> | 1 | 0 |
| <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

分析可以走的方向：向上、向右
→選擇向右嘗試看看

| <font color="#00FFFF">0</font> | 0 | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| <font color="#00FFFF">**0**</font> | 1 | 0 | 1 | 0 |
| <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

未到達終點
→分析可以走的方向：向下、向右
→選擇向下嘗試看看

| <font color="#00FFFF">0</font> | 0 | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| <font color="#00FFFF">**0**</font> | 1 | 0 | 1 | 0 |
| <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | 0 |
| 1 | 1 | 1 | <font color="#00FFFF">**0**</font> | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

未到達終點
→分析可以走的方向：向下

| <font color="#00FFFF">0</font> | 0 | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| <font color="#00FFFF">**0**</font> | 1 | 0 | 1 | 0 |
| <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | 0 |
| 1 | 1 | 1 | <font color="#00FFFF">**0**</font> | 1 |
| 0 | 0 | 0 | <font color="#00FFFF">**0**</font> | <font color="#F7A004">**0**</font> |

未到達終點
→分析可以走的方向：向右、向左
→選擇向右

| <font color="#00FFFF">0</font> | 0 | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| <font color="#00FFFF">**0**</font> | 1 | 0 | 1 | 0 |
| <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> | 0 |
| 1 | 1 | 1 | <font color="#00FFFF">**0**</font> | 1 |
| 0 | 0 | 0 | <font color="#00FFFF">**0**</font> | <font color="#00FFFF">**0**</font> |

到達終點
→回傳有解、步數等資訊

上述這個方法就是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
```
我們把地圖畫成表格來看（紅色是起點，橘色是終點）

| <font color="#f00">0</font> | 0 | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

首先我們站在起點（青色是路徑），起點不需要走任何一步就能到達，所以標記為0，代表花0步可以走到這一格。

| <font color="#00FFFF">0</font> | 0 | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

這時候，假設我們自己只能走1步，請問能走到哪幾格，顯然是右方跟下方對吧，所以我們幫這兩格標記上數字1，代表花1步可以走到這一格。

| <font color="#FF3EFF">**0**</font> | <font color="#00FFFF">**1**</font> | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| <font color="#00FFFF">**1**</font> | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

以此類推，再往外走1步，標記上數字2，代表花兩步可以走到這一格。

| <font color="#FF3EFF">**0**</font> | <font color="#FF3EFF">**1**</font> | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| <font color="#FF3EFF">**1**</font> | 1 | 0 | 1 | 0 |
| <font color="#00FFFF">**2**</font> | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

下方省略講解，看圖

| <font color="#FF3EFF">**0**</font> | <font color="#FF3EFF">**1**</font> | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| <font color="#FF3EFF">**1**</font> | 1 | 0 | 1 | 0 |
| <font color="#FF3EFF">**2**</font> | <font color="#00FFFF">**3**</font> | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

| <font color="#FF3EFF">**0**</font> | <font color="#FF3EFF">**1**</font> | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| <font color="#FF3EFF">**1**</font> | 1 | 0 | 1 | 0 |
| <font color="#FF3EFF">**2**</font> | <font color="#FF3EFF">**3**</font> | <font color="#00FFFF">**4**</font> | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

| <font color="#FF3EFF">**0**</font> | <font color="#FF3EFF">**1**</font> | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| <font color="#FF3EFF">**1**</font> | 1 | <font color="#00FFFF">**5**</font> | 1 | 0 |
| <font color="#FF3EFF">**2**</font> | <font color="#FF3EFF">**3**</font> | <font color="#FF3EFF">**4**</font> | <font color="#00FFFF">**5**</font> | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

| <font color="#FF3EFF">**0**</font> | <font color="#FF3EFF">**1**</font> | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| <font color="#FF3EFF">**1**</font> | 1 | <font color="#FF3EFF">**5**</font> | 1 | 0 |
| <font color="#FF3EFF">**2**</font> | <font color="#FF3EFF">**3**</font> | <font color="#FF3EFF">**4**</font> | <font color="#FF3EFF">**5**</font> | <font color="#00FFFF">**6**</font> |
| 1 | 1 | 1 | <font color="#00FFFF">**6**</font> | 1 |
| 0 | 0 | 0 | 0 | <font color="#F7A004">**0**</font> |

| <font color="#FF3EFF">**0**</font> | <font color="#FF3EFF">**1**</font> | 1 | 0 | 0 |
| --- | --- | ---- | --- | --- |
| <font color="#FF3EFF">**1**</font> | 1 | <font color="#FF3EFF">**5**</font> | 1 | <font color="#00FFFF">**7**</font> |
| <font color="#FF3EFF">**2**</font> | <font color="#FF3EFF">**3**</font> | <font color="#FF3EFF">**4**</font> | <font color="#FF3EFF">**5**</font> | <font color="#FF3EFF">**6**</font> |
| 1 | 1 | 1 | <font color="#FF3EFF">**6**</font> | 1 |
| 0 | 0 | 0 | <font color="#00FFFF">**7**</font> | <font color="#F7A004">**0**</font> |

| <font color="#FF3EFF">**0**</font> | <font color="#FF3EFF">**1**</font> | 1 | 0 | <font color="#00FFFF">**8**</font> |
| --- | --- | ---- | --- | --- |
| <font color="#FF3EFF">**1**</font> | 1 | <font color="#FF3EFF">**5**</font> | 1 | <font color="#FF3EFF">**7**</font> |
| <font color="#FF3EFF">**2**</font> | <font color="#FF3EFF">**3**</font> | <font color="#FF3EFF">**4**</font> | <font color="#FF3EFF">**5**</font> | <font color="#FF3EFF">**6**</font> |
| 1 | 1 | 1 | <font color="#FF3EFF">**6**</font> | 1 |
| 0 | 0 | <font color="#00FFFF">**8**</font> | <font color="#FF3EFF">**7**</font> | <font color="#00FFFF">**8**</font> |

| <font color="#FF3EFF">**0**</font> | <font color="#FF3EFF">**1**</font> | 1 | <font color="#00FFFF">**9**</font> | <font color="#FF3EFF">**8**</font> |
| --- | --- | ---- | --- | --- |
| <font color="#FF3EFF">**1**</font> | 1 | <font color="#FF3EFF">**5**</font> | 1 | <font color="#FF3EFF">**7**</font> |
| <font color="#FF3EFF">**2**</font> | <font color="#FF3EFF">**3**</font> | <font color="#FF3EFF">**4**</font> | <font color="#FF3EFF">**5**</font> | <font color="#FF3EFF">**6**</font> |
| 1 | 1 | 1 | <font color="#FF3EFF">**6**</font> | 1 |
| 0 | <font color="#00FFFF">**9**</font> | <font color="#FF3EFF">**8**</font> | <font color="#FF3EFF">**7**</font> | <font color="#FF3EFF">**8**</font> |

| <font color="#FF3EFF">**0**</font> | <font color="#FF3EFF">**1**</font> | 1 | <font color="#FF3EFF">**9**</font> | <font color="#FF3EFF">**8**</font> |
| --- | --- | ---- | --- | --- |
| <font color="#FF3EFF">**1**</font> | 1 | <font color="#FF3EFF">**5**</font> | 1 | <font color="#FF3EFF">**7**</font> |
| <font color="#FF3EFF">**2**</font> | <font color="#FF3EFF">**3**</font> | <font color="#FF3EFF">**4**</font> | <font color="#FF3EFF">**5**</font> | <font color="#FF3EFF">**6**</font> |
| 1 | 1 | 1 | <font color="#FF3EFF">**6**</font> | 1 |
| <font color="#00FFFF">**10**</font> | <font color="#FF3EFF">**9**</font> | <font color="#FF3EFF">**8**</font> | <font color="#FF3EFF">**7**</font> | <font color="#FF3EFF">**8**</font> |

完成整個迷宮後，我們就可以讀取終點那格的數字，就能知道最短路徑是多少了。這個方法就是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)