---
# System prepended metadata

title: 進階程式設計(高二、高三上)
tags: [選修]

---

###### tags: `選修`
# 進階程式設計(高二、高三上)

:::success
**評量方式、學習歷程**
:::

+ 高三(上)
1. 上課基本練習 50%
2. 期中上機考(二、搜尋之前) 20% 
3. 期末上機考 20%
4. 期末作業解題報告 10%
+ 高二
1. 上課基本練習 40%
2. 期中上機考(二、搜尋之前) 20%
3. 期末上機考 20%
4. 期末作業解題報告 20%
    - 10~12題。
        * 每寫一題10分，上限120分(12題)。
        * 每個單元至多可放2題(不可以都寫同一單元的題目)。
    - 每題的子標題為
        (1) 單元、題號、題目、題目簡述
        (2) 解題動態、評分結果截圖
        (3) 解題思路
        (4) 程式碼
        (5) 反思(遇到的錯誤、修正的地方、更好的方法…)
        (6) 錯誤程式碼
    - 檢核方式
        * 請放一開始有錯，然後修正的題目，並將修正的想法寫出來。如果你每一題都是一次AC，那你應該是骨骼清奇、萬中無一的練武奇才，應該不用怕老師的檢核吧。
        * 有交期末作業解題報告者，最後一週會請你在沒有網路的狀態下重寫一題當做檢核(題目由老師挑選)，寫不出來作業直接作廢 0 分，所以作業請務必自思考己完成，如果你只想上網找程式複製貼上賺分數，就不用做這種白工了。
    - 可整合到課程學習成果，上傳至學習歷程檔案平台。 
5. [TOI推廣計畫-線上練習賽](https://toi-reg.csie.ntnu.edu.tw/)
    - 成績計算：分數/100直接加在總成績。
    - 上學期10、11、12月，下學期3、4、5月，最後一週。
    - 星期一08:00 ～ 星期五20:00。90分鐘。
    - [證書](https://drive.google.com/open?id=1DcgDKn1R33kOPc_HazdIyQDgyYxSCPlZ)
6. [APCS](https://apcs.csie.ntnu.edu.tw/)
    - 實作級分*2，直接加在總成績。
    - 3級分免上機考，上機考成績為100。
    - 4級分以上者，一切皆免，學期成績直接算100。
7. 學習歷程檔案(修課記錄、課程學習成果)(Bonus)
    - 最後一週上課結束前如果認證完成，學期總成績加分。
    - [撰寫「課程學習成果」參考資源](https://hackmd.io/@cube/HkCv90e19)。
8. 演算法進階參考
    - [中央資工演算法](https://staff.csie.ncu.edu.tw/jrjiang/alg2019/)
    - [中山資工演算法](http://par.cse.nsysu.edu.tw/~cbyang/course/algo/algo_index.htm)
    - [台大資訊系統訓練班演算法](https://www.csie.ntu.edu.tw/~d92005/course_Algorithm(2008).htm)
9. [高中資訊學科中心 科技領域加深加廣選修課程－進階程式設計](https://ghresource.mt.ntnu.edu.tw/nss/s/main/InformationTechnologyTPD05)

:::success
**程式語言(基本語法複習)**
:::

+ 巢狀 if
:::info
EX_0_1：[d065: 三人行必有我師](https://zerojudge.tw/ShowProblem?problemid=d065)
```c=
#include <iostream>
using namespace std;
int main()
{
	int a, b, c;

	while (cin >> a >> b >> c)
	{
		if (a > b && a > c)
		{
			cout << a << endl;
		}
		else
		{
			if (b > c)
			{
				cout << b << endl;
			}
			else
			{
				cout << c << endl;
			}
		}
	}
	return 0;
}

```
:::

+ for 迴圈
:::info
EX_0_2：[d490: 我也愛偶數](https://zerojudge.tw/ShowProblem?problemid=d490)
+ 先完成1+...+n
```c=
#include <iostream>
using namespace std;

int main()
{
	int a, b;

	while (cin >> a >> b)
	{
		int sum = 0;

		for (int i = a; i <= b; i++)
		{
			if (i % 2 == 0)
			{
				sum = sum + i;
			}
		}
		cout << sum << endl;
	}

	return 0;
}
```
:::
+ 一維陣列
:::info
EX_0_3：[f345: 新手練習題—陣列](https://zerojudge.tw/ShowProblem?problemid=f345)
```c=
#include <iostream>
using namespace std;

int main()
{
	int number;

	cin >> number; //輸入第一個數

	number--;

	int data[number];

	for (int i = number; i >= 0; i--) //輸入資料至陣列，順便反轉
	{
		cin >> data[i];
	}

	for (int j = 0; j < number; j++) //輸出陣列(因為最後一個數後面不能有空格，所以另外輸出)
	{
		cout << data[j] << " ";
	}

	cout << data[number]; //輸出最後一個數

	return 0;
}
```
:::
<br/>

:::success
**資料結構**
:::

## 一、堆疊
+ [常用C++ STL：stack](https://yuihuang.com/cpp-stl-stack/)
+ C++ 堆疊(Stack)常用的方法
    | 名稱 | 意義 |
    |:-----|:----------|
    |stack<int> sk |建立一個int型別的stack|
    |sk.size()   |堆疊元素數量|
    |sk.empty()  |判斷堆疊是否為空|
    |sk.push(x)  |從堆疊「頂端」加入一個元素x|
    |sk.pop()    |刪除堆疊頂端元素|
    |sk.top()    |取得堆疊頂端元素|
 
:::info
EX_1_1：[a034: 二進位制轉換](https://zerojudge.tw/ShowProblem?problemid=a034)
:::
``` ｃ=
#include <iostream>
#include <stack>
using namespace std;

int main()
{
	stack<int> sk; // 宣告一個存 int 的 stack，需含入 stack 標頭檔
	int n;
	while (cin >> n)
	{
		while (n > 0) // n大於0
		{
			sk.push(n % 2); // 將n除以2的餘數push進堆疊
			n = n / 2;		// 將n除以2
		}

		while (sk.empty() != true) // 堆疊內還有元素
		{
			cout << sk.top(); // 印出堆疊頂端元素
			sk.pop();		  // 將堆疊頂端元素移除
		}
		cout << endl; // 一筆測資完換行
	}

	return 0;
}
``` 

:::info
EX_1_2：[b838: 104北二2.括號問題](https://zerojudge.tw/ShowProblem?problemid=b838)
+ 遇「(」push
+ 遇「)」檢查stack是否是空的，如果不空pop；如果空，則括號不正確。
+ 最後再檢查stack是否是空的。
:::
:::danger
輸出錯誤：```記憶體區段錯誤！
Segmentation fault (core dumped)```
:::   

``` ｃ=
#include <iostream>
#include <stack>
using namespace std;

int main()
{
	int t;
	cin >> t;
	cin.ignore();

	while (t--)
	{
		stack<char> sk; // 宣告一個存 char 的 stack
		string s;
		int cnt = 0;
		cin >> s;

		for (int i = 0; i < s.size(); i++) // 對s中的每一個字元判斷
		{
			if (s[i] == '(') // 如果s[i]是左括號，等於要有2個等號「==」
			{
				sk.push(s[i]); // 將s[i]放到堆疊
			}
			else if (s[i] == ')') // s[i]是右括號
			{
				if (sk.top() == '(' && sk.empty() == false) // 如果堆疊內有左括號，堆疊size>0
				{
					sk.pop(); // pop出一個左括號
					cnt++;	  // 計數加1
				}
				else // 沒有左括號，表示式子不正確
				{
					cnt = 0; // 計數設為0，設定為一個等號「=」
					break;	 // 跳出迴圈
				}
			}
		}

		if (sk.empty() == false) // 最後堆疊內還有左括號
		{
			cnt = 0; // 計數設為0
		}
		cout << cnt << endl;
	}
	return 0;
}
``` 
    
    

:::warning
[b923: stack 堆疊的模板題](https://zerojudge.tw/ShowProblem?problemid=b923)
:::
    
:::danger
這題打不開
:::

:::warning
[d318: 11185 - Ternary](https://zerojudge.tw/ShowProblem?problemid=d318)
:::

:::warning
[a132: 10931 - Parity](https://zerojudge.tw/ShowProblem?problemid=a132)
+ 以stack記錄除2的餘數
+ stack:push、pop、top
:::

:::warning
[a565: 2.p&q的邂逅](https://zerojudge.tw/ShowProblem?problemid=a565)
+ 以getline(cin,line)讀取一行前，用 cin.ignore() 將 n 之後的換行字元讀掉。
+ C++ IO加速
ios::sync_with_stdio(false);
cin.tie(0);
:::


<br/>

## 二、佇列
+ [常用C++ STL：queue](https://yuihuang.com/cpp-stl-queue/)
+ [常用C++ STL：priority_queue](https://yuihuang.com/cpp-stl-priority-queue/)
+ C++ 佇列(Queue)常用的方法
    | 名稱    | 意義 |
    |:--------|:----------|
    |queue<int> q |建立一個int型別的queue|
    |q.size()     |佇列元素數量|
    |q.empty()    |判斷是否為空|
    |q.push(x)    |從佇列「後端」加入一個元素x|
    |q.pop()      |從「前端」刪除一個元素|
    |q.front()    |取得前端元素|
    |q.back()     |取得後端元素|       
	
:::info
EX_2_1：[e155: 10935 - Throwing cards away I](https://zerojudge.tw/ShowProblem?problemid=e155)
:::

``` ｃ=
#include <iostream>
~
using namespace std;

int main()
{
    int n;
    while(cin >> n && n>0)
    {
        ~         // 宣告一個存放 int 的 queue，需含入 queue 標頭檔

        for ~     // 將 1~n 放到佇列
            ~
        ~         // 設一個布林變數(first)，初值為true，代表是否為第一個

        cout << "Discarded cards: ";
        while ~   //當佇列的size大於1
        {
            if ~  // 如果不是第一個要印出來的元素，要先印出「, 」
                cout << ", ";
            
            ~     // 印出佇列前端元素
            ~     // 從前端刪除一個元素
            ~     // 讀取前端的元素，並從後端加入
            ~     // 從前端刪除一個元素
            ~     // first布林變數設為false
        }
        cout << endl << "Remaining card: " << q.front() << endl;
    }

    return 0;
}
```

:::info
EX_2_2：[a982: 迷宮問題#1](https://zerojudge.tw/ShowProblem?problemid=a982)
+ [0-18 pair | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/02/0-18/)
+ [圖的搜尋](https://jason-chen-1992.weebly.com/home/-graph-searching-methods)
    - [深度優先搜尋(Depth First Search, DFS)](http://simonsays-tw.com/web/DFS-BFS/DepthFirstSearch.html)：以堆疊(Stack)、遞迴來實作。
    - [廣度優先搜尋(Breadth First Search, BFS)](http://simonsays-tw.com/web/DFS-BFS/BreadthFirstSearch.html)：以佇列(Queue)來實作。
:::

``` ｃ=
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int main()
{
    int n;
    while(cin >> n)
    {
        char maze[105][105];
        int len[105][105];
        ~          // 宣告一個存放 pair 的 queue
        memset(len,-1,sizeof(len)); // 將len陣列的初值都設為-1，表示沒走過

        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                cin >> maze[i][j];

        q.push({1,1});
        len[1][1]=1;
        maze[1][1]='#';

        while ~     // 當 queue 內還有點
        {
            ~       // 讀取 queue 內的點
            ~       // pop 掉這個點
            int r=p.first,c=p.second;
            
            if(maze[r+0][c+1]=='.') // 右
            {
                ~   // 將 {r,c+1} push 至 queue
                ~   // 右邊點的長度為目前點的長度+1;
                ~   // 右邊點設為 '#' 表示走過
            }

            ~       // 下
            ~       // 左
            ~       // 上
        }

        if(len[n-2][n-2]==-1)
            cout << "No solution!\n";
        else
            cout << len[n-2][n-2] << endl;
    }

    return 0;
}
```
``` ｃ=
// Q：如何以迴圈，讓程式碼更精簡
int n,dr[4]={~, ~, ~, ~},dc[4]={~, ~, ~, ~}; // 以陣列表示座標要調整的數值

            for(int i=0;i<4;i++)      // 四個方向
            {
                // 亦可多設下一點座標變數 nr,nc 讓程式碼更清楚
                if(maze[~][~]=='.')   // 下一個點的座標
                {
                    ~   // 將下一個點 push 至 queue
                    ~   // 下一個點的長度為目前點的長度+1;
                    ~   // 下一點設為 '#' 表示走過
                }
            }   
```

:::warning
[e447: queue 練習](https://zerojudge.tw/ShowProblem?problemid=e447)
:::

:::warning
[d900: NOIP2010 2.接水问题](https://zerojudge.tw/ShowProblem?problemid=d900)
+ [0-22 priority_queue | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/10/0-22/)
+ 依輸入序，取佇列中最小值相加後再放入佇列。
:::

:::warning
[d406: 倒水時間](https://zerojudge.tw/ShowProblem?problemid=d406)
+ BFS，以STL queue實作。
:::

<br/>

## 三、串列
+ [C++ STL list](https://sites.google.com/site/zsgititit/home/jin-jiec-cheng-shi-she-ji/stl/list)
+ C++ 串列(List)常用的方法
    | 名稱    | 意義 |
    |:--------|:----------|
    |list<int> lst |建立一個int型別的list|
    |lst.begin()   |lst第一個元素的位子|
    |lst.end()     |lst最後一個元素的位子|
    |lst.push_back(x) |從lst「後端」加入一個元素x|
    |lst.pop_back()   |從lst「後端」刪除一個元素|
    |lst.insert(it,x) |在it位子插入元素x|
    |lst.erase(it)    |刪除it位子的元素|
    |lst.remove(x)    |將lst中所有值為x的元素刪除|
    |lst.size()       |lst元素數量|

:::info
EX_3_1：[陸行鳥大賽車](https://neoj.sprout.tw/problem/21/)
+ list:push_back、insert、erase
+ [find，需含入 algorithm 標頭檔](https://shengyu7697.github.io/std-find/)
+ C\+\+ 11設定
    - CodeBlocks：Settings / Compiler / Have g++ follow the C\+\+11 ISO C++ language standard
    - Dev-C\+\+：專案 / 專案選項 / 編譯器訊息 / 程式碼產生 / 語言標準(-std) / ISO C\+\+11
+ list find 時間複雜度為O(n)，會過不了最後兩筆測資 → [以陣列模擬 list](https://chino.taipei/code-TOJ-21-%E9%99%B8%E8%A1%8C%E9%B3%A5%E5%A4%A7%E8%B3%BD%E8%BB%8A/)。
+ 交換函式：swap()
:::

``` c=
#include <iostream>
#include <algorithm>
#include <list>
using namespace std;

int main()
{
    int n,m,t,x;
    while(cin >> n)
    {
        ~       // 宣告可以存放 int 的list(命名為lst)
        for ~   // 將 1~n 放入 lst
            ~

        cin >> m;
        for(int i=0;i<m;i++)
        {
            cin >> t >> x;
            if(t==0)    // x受攻擊
            {
                ~       // 找到 x 的位置(it)
                ~       // 刪除 x (使用it來刪除)
            }
            else if(t==1)  // x衡刺
            {
                ~       // 找到 x 的位置(it)
                ~       // 先將 itp 設為 it 
                ~       // 將 itp 調整成 it 的前一個位置 
                if ~    // 如果 x 不是開頭 (使用 it 來判斷)
                {
                    ~   // 刪除 x (使用it來刪除)
                    ~   // 將 x 插入至 itp 所指的位置
                }
            }
        }

        for ~ // 印出 lst 裏的每個元素
            ~ 
        cout << endl;
    }
    
    return 0;
}
```

:::warning
[a870: 10. List Maker](https://zerojudge.tw/ShowProblem?problemid=a870)
:::


<br/>
<br/>

:::success
**演算法**
:::
     
## 一、排序演算法
+ [思考排序的演算法](https://zh.wikipedia.org/wiki/十三張)
+ [Sorting 排序](https://yuihuang.com/sorting/)

### 1. 氣泡排序(Bubble Sort)
+ [bubble sort](https://pjchender.blogspot.com/2017/09/bubble-sort.html)：兩兩相比，數字大的往後擺，好像數字大的元素慢慢「浮」到右端。
+ [Bubble Sort | GeeksforGeeks - YouTube](https://www.youtube.com/watch?v=nmhjrI-aW5o)    

:::info
EX_1_1：[a539: 10327 - Flip Sort](https://zerojudge.tw/ShowProblem?problemid=a539)
:::

```c=
// bubble sort
#include <iostream>
using namespace std;

int main()
{
    int n,a[1005];
    while(cin >> n)
    {
        int cnt=0;
        for(int i=0;i<n;i++)
            cin >> a[i];
        
        for ~            // 5 個數字排序只需 4 個循環
        {
            for ~        // 每次兩兩比較，每次比較索引值「0、1」「1、2」「2、3」「3、4」 的數字
            {
                if ~     // 如果左邊比右邊大
                {
                    ~    // 以swap函式交換
                    cnt++;
                }
            }
        }

        cout << "Minimum exchange operations : " << cnt << endl;
    }

    return 0;
}
```

:::warning
[e561: 00299 - Train Swapping](https://zerojudge.tw/ShowProblem?problemid=e561)
+ 計算 Bubble Sort 交換的次數。
+ swap()
:::

### 2. 交換排序(Exchange Sort) vs. 選擇排序(Selection Sort)  
+ [exchange sort](http://it-easy.tw/sorting-algorithm/)：對每個基準點，如果之後的數比它小就交換。
+ [selection sort](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E5%85%A5%E9%96%80-%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F%E8%88%87%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E6%B3%95-23d4bc7085ff)：跟交換排序法類似，但交換次數較少。對每個基準點，找到其後最小的數值，並進行對調。
+ [Selection Sort | GeeksforGeeks - YouTube](https://www.youtube.com/watch?v=xWBP4lzkoyM)    

:::info
EX_1_2：[d452: 二、直線最小距離和](https://zerojudge.tw/ShowProblem?problemid=d452) (以選擇排序實作)
+ 排序後求中位數，中位數與數組各數的距離和最小
:::

```c=
// exchange sort
#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int t,n,a[105];
    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i=0;i<n;i++)
            cin >> a[i];

        for(int i=0;i<n-1;i++)       // 對每個基準點 i 
            for(int j=i+1;j<n;j++)   // 從 i 的右邊開始找最小值
                if(a[j]<a[i])        // 如果檢查的這個數 < 第 i 個數
                    swap(a[j],a[i]); // 以 swap 函式交換這兩個數;
        
        int sum=0;
        for(int i=0;i<n;i++)
            sum+=abs(a[n/2]-a[i]);
        cout << sum << endl;
    }
    
    return 0;
}
```

```c=
// selection sort
        
        for ~                 // 對每個基準點 i，0 到 ?(最後一個不用看)
        {
            int minIdx=i;     // 預設目前最小值的 index 為 i
            for ~             // 從 i 的右邊開始找更小的數值
            {
                if(a[~]<a[~]) // 如果右邊的值 < 目前最小值
                    minIdx=j; // 更新 minIdx
            }
            ~  // 把找到的最小值(minIdx的值)和基準點交換
        }       
```


### 3. 插入排序(Insertion Sort)
+ [insertion sort](https://kopu.chat/2017/06/22/插入排序insertion-sort/)：將還未排序的元素插入到已排序數列中的正確位子。
+ [Insertion Sort | GeeksforGeeks - YouTube](https://www.youtube.com/watch?v=OGzPmgsI-pQ)
                                               
:::info
EX_1_3：[a104: 排序](https://zerojudge.tw/ShowProblem?problemid=a104) (以插入排序實作)
:::

```c=
// insertion sort
#include <iostream>
using namespace std;

int main()
{
    int n,a[1005];
    while(cin >> n)
    {
        for(int i=0;i<n;i++)
            cin >> a[i];

        for ~ // 第 0 個元素不用處理，當成已排好序的數列
        {
            int key=a[i],j=i-1; // key(a[i]) 是正在處理的數值，設 j 是 i 的前一個
            while ~             // 前面的元素(a[?])大於 key，而且 j 沒有小於邊界(j>=0)
            {
                ~               // 前面的元素(a[?])比 key 大，所以往右移
                ~               // j減1
            }
            a[~]=key;           // 將key放入正確位置
        }

        for(int i=0;i<n;i++)
            cout << a[i] << " ";
        cout << endl;
    }

    return 0;
}
```

:::warning
[c010: 10107 - What is the Median?](https://zerojudge.tw/ShowProblem?problemid=c010)
+ 每次輸入都排序會TLE。
+ 以insertion sort的觀念，在已排序的數列中，找出新數字的正確位置。
:::



### 4. 快速排序(Quick Sort)
+ [quick sort1](https://ithelp.ithome.com.tw/articles/10202330?sc=iThelpR)
+ [quick sort2](http://notepad.yehyeh.net/Content/Algorithm/Sort/Quick/Quick.php)


### 5. 合併排序(Merge Sort)
+ [merge sort](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E9%80%B2%E9%9A%8E-%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F%E6%B3%95-6252651c6f7e)
+ [Merge Sort | GeeksforGeeks - YouTube](https://www.youtube.com/watch?v=JSceec-wEyw)	

### 6. 排序演算法效率比較
+ [Sorting Algorithms Animations](https://www.toptal.com/developers/sorting-algorithms)
+ [Comparison Sorting Algorithms](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html)
+ [排序演算法整理](http://notepad.yehyeh.net/Content/Algorithm/Sort/Sort.php)
![](https://i.imgur.com/BYBK9Bh.png)

### 7. 排序演算法應用
+ [常用C++ algorithm：sort](https://yuihuang.com/cpp-algorithm-sort/)
```c=
#include <iostream>
#include <algorithm>
using namespace std;

bool cmp(int a,int b)
{
    if(a>b)
        return true;
    else
        return false;
    // 精簡寫法
}

int main()
{
    int a[5]={2,3,1,4,5};
    sort(a,a+5,cmp);
    for(auto e:a)
        cout << e << " ";

    return 0;
}
```
:::info
EX_1_4：[b966: 第 3 題 線段覆蓋長度](https://zerojudge.tw/ShowProblem?problemid=b966) ([測f855](https://zerojudge.tw/ShowProblem?problemid=f855))
+ 開10^7^bool陣列，讀一筆線段就從L標計到R，最後計算標計的數量。時間O(n)*O(10^7^)可行嗎？ 空間？
+ 將輸入線段依左端點座標排序。則前後兩線段的關係只可能為重疊(包含相連)或不重疊(新線段)
    - 如果下一線段的左端點 > 前一線段的右端點，表示前一線段已結束，計算並加總覆蓋長度。
    - 如果下一線段的左端點 <= 前一線段的右端點，表示前一條線段可延續，調整前一線段右端點位置即可。
+ [【題解】ZeroJudge b966: 第 3 題 線段覆蓋長度](https://yuihuang.com/zj-b966/)
+ [結構(struct)](https://kopu.chat/2017/05/30/c-%E8%AA%9E%E8%A8%80%EF%BC%9A%E7%B5%90%E6%A7%8B%EF%BC%88struct%EF%BC%89%E8%87%AA%E8%A8%82%E4%B8%8D%E5%90%8C%E8%B3%87%E6%96%99%E5%9E%8B%E6%85%8B%E7%B6%81%E4%B8%80%E8%B5%B7/)
    ``` c
    // 自訂的資料型別 
    struct 結構名稱
    {
        資料型別 變數1;
        資料型別 變數2;
        ...
    };
+ [掃描線演算法(sweep line algorithm)](http://web.ntnu.edu.tw/~algo/Point2.html)
:::

```c=
#include <iostream>
#include <algorithm>
using namespace std;

~ // 定義存放線段開始端點座標(st)、結束端點座標(ed)的結構，並開一個s[10005]的陣列，裏面的元素為此結構。

bool cmp(seg a,seg b) // 自訂比較函式
{
    /*
    if(a.st < b.st)
        return true;
    else
        return false;
    */
    return ~; // 將上面四行精簡
}

int main()
{
    int n;
    while(cin >> n)
    {
        for(int i=0;i<n;i++)
            cin >> s[i].st >> s[i].ed;

        ~   // 排序，自訂比較函式
        
        /*
        先將排序結果印出來看看
        */

        int L=0,R=0,total=0; // L、R為前一線段的開始、結束座標
        for(int i=0;i<n;i++)
        {
            if ~   // 如果「沒有重疊」，此線段的左端點 > 前一線段的右端點
            {
                ~  // 結算前一線段的總長度
                ~  // 以此線段「開始」座標更新 L
                ~  // 以此線段「結束」座標更新 R
            }
            else   // 如果「有重疊」，此線段的左端點 <= 前一線段的右端點，表示有可能延伸前一線段
                ~  // 更新前一線段的右端點為：max(前一線段右端點，此線段右端點)
        }
        cout << total+(R-L) << endl;
        //Q：答案為何還要加(R-L)？
    }

    return 0;
}
```

:::warning
[a737: 10041 - Vito's family](https://zerojudge.tw/ShowProblem?problemid=a737)
+ 將所有親戚的門牌號碼排序，中位數即為 Vito 新家的門牌號碼。
:::

:::warning
[d150: 11369 - Shopaholic](https://zerojudge.tw/ShowProblem?problemid=d150)
+ 將商品價格降序(大->小)排序，再取每三個內的最小值。
+ for(int i=2;i<n;i+=3)
:::


:::warning
[d385: 10905 - Children’s Game](https://zerojudge.tw/ShowProblem?problemid=d385)
+ 將數字以字串讀入，字串可以直接相加，例如 "12"+"34" 為 "1234"。
+ 字串比可直接比較大小(以字典序)，例如"ab"<"cd"，"ab"<"ac"。
+ 排序方式為兩個字串前後互換試試看，看誰在前面可形成較大的數字。排序完成後，全部字串照順序接起來即是答案。例如給定的字串"123"、"124"、"56"、90”，按順序連接它們可得到"1231245690"。如果交換"123"、"124"，可得到更好的結果"1241235690"。
+ 比較函式：(a+b)>(b+a)時為要的順序。
:::

<br/>

## 二、搜尋演算法
+ 數列需先排序好才可使用二分搜尋。
+ [要定義好搜尋的區間是\[a,b\]或\[a,b)或其它](https://www.itread01.com/content/1548961212.html)
    - [程式設計中左閉右開區間的廣泛應用](https://codingnote.cc/zh-tw/p/183343/)
+ 區間選擇不正會確導致無窮迴圈，陣列越界 → 模擬剩下兩個元素時，是否能正確執行到結束。
:::info
EX_2_1：[d732: 二分搜尋法](https://zerojudge.tw/ShowProblem?problemid=d732)
+ 陣列從index 1 開始存。
+ 先試試循序搜尋會如何？檔名：d732(60%)
:::

``` c=
#include <iostream>
using namespace std;

int main()
{
    int n,k,x,a[100005];
    while(cin >> n >> k)
    {
        for(int i=1;i<=n;i++)
            cin >> a[i];

        while(k--)
        {
            cin >> x;
            ~    // 設一個 bool 變數，表示有沒有找到，預設為 false
            for ~      // 從頭開始找
            {
                if ~   // 如果找到
                {
                    cout << i << endl;
                    ~  // bool 變數設為 true，表示找到。
                    ~  // 跳出 for 迴圈
                }
            }

            if ~ // 沒找到。Q：不可以直接在 for 迴圈裏的 if 直接加 else 印出 0，搜尋 3 會印出？
                cout << 0 << endl;
        }
        
    }

    return 0;
}
```
``` c=
        while(k--)
        {
            cin >> x;
            ~             // int L=？,R=？,m; 
                          // 左閉，右閉
            while ~       // 左邊界index <= 右邊界index
            {
                ~         // 計算 m
                if ~      // 如果找到
                {
                    cout << m << endl;
                    break;
                }
                else if ~  // 中間值 > x
                     ~     // 往左半找
                else       // 中間值 < x
                     ~     // 往右半找
            }
            if ~           // 如果 左邊界index > 右邊界index，表示沒找到
                cout << 0 << endl;
        }                
```
:::info
EX_2_2：[f815: TOI_y21m4_a01遊戲升等](https://zerojudge.tw/ShowProblem?problemid=f815)
+ [最小值最大化](https://blog.csdn.net/qq_43690454/article/details/104020240)
+ 對答案二分搜。假設一個答案，檢查這個答案是不是符合條件限制，以二分搜尋的方式逼進最大值。
+ 結束狀況討論
![](https://i.imgur.com/Y2vsqCR.png =500x)
:::

``` c=
#include <iostream>
using namespace std;

long long lv[20005],n;
long long gold(int m) // 計算到等級 m 需要的金幣
{
    long long sum=0;
    for(int i=0;i<n;i++)
        if ~   // 如果士兵等級 < m
            ~  // 計算需要的花費後加總

    return sum;
}

int main()
{
    long long c,L=1,R=20000001,m; //左閉，右開，假設最大等級為2千萬
    cin >> n >> c;

    for(int i=0;i<n;i++)
        cin >> lv[i];

    while(L<R)
    {
        ~      // 預期的等級 m
        if ~   // 需要的金幣 > 預算
            ~  // 往左半找
        else
            ~  // 往右半找
    }
    cout << ~ << endl; // Q：答案在？

    return 0;
}
// Bonus：以左閉，右閉改寫看看。
```

:::warning
[f679: 公會成員](https://zerojudge.tw/ShowProblem?problemid=f679)
+ 想偷懶，排序可用STL sort，二分搜尋可用lower_bound。
:::

:::warning
[c575: APCS 2017-0304-4基地台](https://zerojudge.tw/ShowProblem?problemid=c575)
+ 對n個服務點排序，並計算服務點兩兩相鄰距離。若要分成K群，則找出前K-1個最大的兩兩相離距離，作為分群切割處。(時間複雜度高)
+ 實做可用二分搜尋的觀點。因為基地台直徑的答案一定介於1~(最遠服務點-最近服務點)。先假設可能答案為最大最小值中間，測試k個基地台可否覆蓋所有服務點，不行則調整基地台直徑，以二分搜尋法找出答案(直接對答案進行二分搜尋)。
:::

:::warning
[c904: 天龍國的蜜蘋果](https://zerojudge.tw/ShowProblem?problemid=c904)
+ 最大化平均值
+ [解題參考1](https://www.twblogs.net/a/5c9e53cabd9eee7523887628)
+ [解題參考2](https://blog.csdn.net/karry_zzj/article/details/70232097)
:::

<br/>

## 三、貪婪(greedy)演算法
+ 假設一個問題可以藉由一系列的選擇來解決，貪婪演算法為在每一步的選擇中，都採取在當前狀態下的最佳選擇，從而希望導致結果是最佳解的演算法。


:::info
EX_3_1：[TCFSH CIRC Judge d042: 例題 P-4-1. 少林寺的代幣](https://judge.tcirc.tw/ShowProblem?problemid=d042)
:::
```c=
#include <iostream>
using namespace std;

int main()
{
    int coin[4]={1,5,10,50},m,n;
    cin >> m;
    while(m--)
    {
        int num=0;  // 代幣數量
        cin >> n;
        for ~       // 從 50 元開始換
        {
            ~       // 計算可換出的數量
            ~       // 剩下沒換零錢的金額
        }
        cout << num << endl;
    }

    return 0;
}
```

:::info
EX_3_2：[f627: 1. 礦砂採集](https://zerojudge.tw/ShowProblem?problemid=f627)
+ [分數背包問題(Fractional Knapsack Problem)](http://web.ntnu.edu.tw/~algo/KnapsackProblem.html)(選擇物品時，可以只拿物品的一部分，不必須全部拿)
    - 如果物品不可分割(0-1背包問題)，greedy可行嗎？(範例如[六、2_2. 0-1背包問題](#0-1背包問題))
+ 依單位重量價值由大到小排序(搭配比較函式greater)。
+ 不斷將單位重量價值最大的礦砂放入背包，直到背包已滿或沒有礦砂可放入。
+ STL [vector(1)](https://yuihuang.com/cpp-stl-vector/) [(2)](https://zrn-code.github.io/2020/07/19/vector/)
:::
```c=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n,m,w,p;
    while(cin >> n >> m)
    {
        ~      // 宣告存放礦沙的 vector
        for(int i=0;i<n;i++)
        {
            cin >> w >> p;
            ~  // pair排序會先以first為基準，相同再比second。因為要根據單位重量價值排序，所以將{p,w}放入vector，
        }

        ~      // 根據單位重量價值由大到小排序
        
        /* 先印出來看看
        cout << endl;
        for(auto e:ore)
            cout << e.first << " " << e.second << endl;
        */
        
        int sum=0;   //礦沙總價值
        for ~        // 將每個 pair 取出
        {
            if ~     // 背包重量 > 此礦沙重量
            {
                ~    // 更新總價值(將此礦沙全部放入背包)
                ~    // 背包重量扣掉此礦沙重量
            }
            else     // 背包重量 <= 此礦沙重量，沒空間可以放下一個
            {
                ~    // 更新總價值(背包剩下的重量全部放此礦沙)
                break;
            }
        }
        cout << sum << endl;
    }

    return 0;
}
```

:::warning
[TCFSH CIRC Judge d044: 例題 P-4-3. 十年磨一劍(最少完成時間)](https://judge.tcirc.tw/ShowProblem?problemid=d044)
+ minimum completion time 經典題
+ 放在越前面的工作，等它的人越多，所以短的工作先做。
::: 
                
:::warning
[e538: 11389 - The Bus Driver Problem](https://zerojudge.tw/ShowProblem?problemid=e538)
+ 將早晨巴士路線由小->大排序，傍晚巴士路線由大->小排序。( sort搭配比較函式 greater<int>() )
+ 最短的早晨巴士路線搭配最長的傍晚巴士路線，會使支付的總加班費最小。
:::

:::warning
[f832: 隕石 (Meteorite)](https://zerojudge.tw/ShowProblem?problemid=f832)
+ 將隕石重量、捕捉器容量排序
+ 由捕捉器容量大到小，決定是否可以裝入此時最大重量的隕石。
:::

<br/>

## 四、分治(divide & conquer)演算法
### 1. 遞迴複習
:::info
EX_4_1：[a623: 3. Combination](https://zerojudge.tw/ShowProblem?problemid=a623)
+ 以遞迴求組合數。
+ $C^n_k = C^{n-1}_k + C^{n-1}_{k-1}$ 
+ $n==k \ || \  k==0$ 時，只有一種組合方式。
:::
```c=
#include<iostream>
using namespace std;

int c(int n, int m)
{
    if ~  // 終止條件
        return 1;
    else
        ~ // 遞迴呼叫
}

int main()
{
    int n,m;
    while(cin >> n >> m)
    {
        cout << c(n,m) << endl;
    }
    return 0;
}
```

:::warning
[e357: 遞迴函數練習](https://zerojudge.tw/ShowProblem?problemid=e357)
:::


:::warning
[c002: 10696 - f91](https://zerojudge.tw/ShowProblem?problemid=c002)
:::

### 2. 步驟
+ 分割(divid)：將原本的問題分割成多個子問題(規模較小的同類問題)。
+ 克服(conquer)：當子問題劃分得足夠小時，用相同的演算法遞迴地解決所有的子問題。
+ 合併(combine)：合併(merge)所有子問題的解答成為原本問題的解答。
### 3.分治經典問題
+ [找出較輕的假幣](https://market73228.pixnet.net/blog/post/11996380)
+ 二分搜尋
+ 快速排序
+ 合併排序
+ [河內塔](http://www.novelgames.com/zh-HK/tower/)
+ [逆序數對](https://zh.wikipedia.org/wiki/%E9%80%86%E5%BA%8F%E5%AF%B9)
+ [平面最近點對](https://oi-wiki.org/geometry/nearest-points/)
+ [缺陷棋盤填滿](https://xie.infoq.cn/article/65ba1aaa2135b23eb6180e3ff)


:::info
EX_4_2：[d219: 00374 - Big Mod](https://zerojudge.tw/ShowProblem?problemid=d219)
+ [分配律](https://zh.wikipedia.org/wiki/%E6%A8%A1%E9%99%A4)
+ (A\*B)%M=[ (A%M)\*(B%M) ]%M→B^P^%M=[ (B^P/2^%M)\*(B^P/2^%M) ]%M
+ EX：4\*5%3=(4%3)\*(5%3)、5\*8%3=(5%3)\*(8%3)%3
:::
```c=
#include<iostream>
using namespace std;

int dc(int b,int p,int m)
{
    if(p==0)
        return 1;
    else if (p==1)
        return b;
    else
    {
        ~  // 先算出 b^(p/2)%m，要宣告為long long，Why?
        if ~
            return ~          // p為偶數，( b^(p/2)%m * b^(p/2)%m ) % m
        else
            ~                 // p為奇數要比偶數時多乘一次b
    }
}

int main()
{
    int b,p,m;
    while(cin >> b >> p >> m)
        cout << dc(b,p,m) << endl;

    return 0;
}
```

:::info
EX_4_3：[d153: 六、智力测验](https://zerojudge.tw/ShowProblem?problemid=d153)(以快速排序實作)
+ 時間複雜度O(n^2^)的排序法會TLE
+ [步驟說明](https://www.youtube.com/watch?v=AsQW27DT82I&t=1m1s)
+ 陣列傳到函式，參數接收的是陣列位址。
:::

```c=
#include <iostream>
using namespace std;

void quickSort(int a[],int L,int R)
{
    if(L>=R)
        return;

    int i=L,j=R;   // 最左邊的元素設為「基準點」
    while ~       // 將小於「基準點」的元素放在它左邊，大於的放右邊。i==j時停止。
    {
        while ~   // 從右「向左」找『小於』基準點的元素。 a[j]>=「基準點」 且 i<j 時繼續找
            j--;
        while ~   // 從左「向右」找『大於』基準點的元素
            ~     // 將 i 向右移

        ~         // 以 swap 函式，讓小於「基準點」的放左邊，大於「基準點」的放右邊
    }

    ~             // 「基準點」交換至中間

    quickSort(a, L, i-1); // 左半繼續做 quickSort
    ~                     // 右半繼續做 quickSort
}

int main()
{
    int t,n,a[40005];
    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i=0;i<n;i++)
            cin >> a[i];

        quickSort(a,0,n-1);
        cout << a[(n-1)/2] << endl;
    }

    return 0;
}
```

:::warning
[d636: 大爆炸bomb](https://zerojudge.tw/ShowProblem?problemid=d636)
:::

:::warning
[a227: 三龍杯 -> 河內之塔](https://zerojudge.tw/ShowProblem?problemid=a227)
+ [解題參考]((http://notepad.yehyeh.net/Content/DS/CH02/4.php))
:::


:::warning
[a638: Closest-pair problem](https://zerojudge.tw/ShowProblem?problemid=a638)
+ [演算法筆記](https://web.ntnu.edu.tw/~algo/Point2.html#3)
+ 橫跨兩側的最近點對，只要依序窮舉中線左側距離 d 以內的點，作為左端點；再找右側距離 d 以內的點，作為右端點。
:::

<br/>

## 五、樹搜尋(tree search)與回溯(backtracking)演算法
+ 許多問題尋找解答的過程可以表示成樹，建構出解答空間樹(solution space tree)，因此找解答就轉變成一個樹搜尋問題。
+ DFS vs. 回溯(backtracking)
    - DFS 會遍訪每一個未拜訪過的節點，如果該節點已無可拜訪的節點，就會退回該節點的父節點再遍訪其它分支的節點。
    - backtracking 在進行未拜訪節點選擇時，可以先選擇可能會有好結果的分支，或是提早判斷若無解，就不遞迴至下一層，而是回溯退回先前的節點。(偷吃步)
+ [DFS 遇到拜訪過的節點會馬上回溯，backtracking 遇到不合理的解答會馬上回溯。](http://web.ntnu.edu.tw/~algo/Backtracking.html#1)    

:::info
EX_5_1：[d908: 4. 最佳路徑](https://zerojudge.tw/ShowProblem?problemid=d908)
+ [深度優先搜尋(depth-first search, DFS)演算法](https://jason-chen-1992.weebly.com/home/-graph-searching-methods)
+ [相鄰矩陣表示法(Adjacency Matrix)](http://web.ntnu.edu.tw/~algo/Graph.html#3)
+ Q：未加16行會造成什麼錯誤？
![](https://i.imgur.com/570OAbQ.png =200x)
:::

```c=
#include <iostream>
#include <cstring>
using namespace std;
int g[26][26],vst[26],mx;

void dfs(int now, int sum)
{
    if(sum > mx)
        mx=sum;

    for ~       //從此點(now) 往下檢查 26 個字母是否相連
        if ~    // 如果 now 有連到 i ，且 i 還沒走過
        {
            ~   // 將 i 設為走過(以 1 表示)
            ~   // 從 i 繼續往下走，路徑的權重總和要加 now->i 這一段的權重
            ~   // 取消 i 設為走過(以 0 表示)，讓其它點可以連到 i
        }
}

int main()
{
    char s,u,v;
    int n,w;
    while(cin >> s >> n)
    {
        memset(g,0,sizeof(g));
        ~       // 將 vst 陣列歸 0
        mx=0;

        for(int i=0;i<n;i++)
        {
            cin >> u >> v >> w;
            g[u-'A'][v-'A']=w;  // 將相鄰矩陣g[u(轉為數字)][v(轉為數字)]的值設為w，A 轉為 0，B 為 1 …，
        }

        /* 先把範例一的相鄰矩陣印出來看看
        0 7 1 0 0 0
        0 0 0 3 5 0
        0 0 0 0 0 2
        0 0 0 0 0 4
        0 0 0 0 0 0
        0 0 0 0 0 0
        */

        ~       // 從 s 開始走，路徑的權重總和為 0
        cout << mx << endl;
    }

    return 0;
}
// Q：NA(score:80%)？
// A：有些線段會重複，記錄此線段的最大權重。
```

:::info
EX_5_2：[d324: 00750 - 8 Queens Chess Problem](https://zerojudge.tw/ShowProblem?problemid=d324)
+ backtracking
+ 一維陣列 row[9]，陣列索引為皇后的col，值為皇后的row。
    - [1-based indexing](https://xlinux.nist.gov/dads/HTML/oneBasedIndexing.html)
+ [皇后衝突的判斷](https://iter01.com/588856.html)
+ [棋盤](https://www.datagenetics.com/blog/august42012/)
+ [不同邏輯寫法](https://yuihuang.com/zj-d324/)
:::

```c=
#include <iostream>
using namespace std ;
int qr,qc,row[9],cnt;   // index 為皇后的 col，值為 row

void print()
{
    if(row[qc]==qr)     // 符合題目皇后必須放的位子才印出來
    {
        cout << " " << cnt++ << "      ";
        for(int i=1;i<=8;i++)
            cout << row[i] <<" ";
        cout << endl;
    }
}

bool attack(int r,int c)
{
    for ~                // 檢查是否衝突到之前已擺放的皇后
        if ~             // 在同一列或對角(abs)
            return true; // 表示衝突到
    return false;
}

void place(int c)        // 填第幾 col ，即填第幾個皇后
{
    for ~                // 每一列(1~8)都試試看
        if ~             // 如果放在 r 列, c 欄的皇后不會衝突之前已擺放的皇后
        {
            ~            // 記錄此皇后的位置
            if(c==8)     
                print();
            else
                ~        // 繼續擺下一個皇后
        }
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> qr >> qc;
        cout <<"SOLN       COLUMN"<<endl;
        cout <<" #      1 2 3 4 5 6 7 8"<<endl<<endl;
        cnt=1;
        place(1);
        cout <<endl;
    }
    
    return 0;
}               
```

:::info
EX_5_3：[c812: 1. 觀光景點](https://zerojudge.tw/ShowProblem?problemid=c812)
+  [相鄰串列表示法(Adjacency Lists)](http://web.ntnu.edu.tw/~algo/Graph.html#4)
+ [整數最大值可用0x3f3f3f3f](https://blog.csdn.net/jiange_zh/article/details/50198097)
+ [C++ 17 結構化綁定](https://zh-blog.logan.tw/2019/10/29/cxx-17-structured-binding/)
:::
```c=
#include <iostream>
#include <vector>
using namespace std;

vector< pair<int,int> > g[5005]; // g 的 idx 為來源點，pair 記錄目地點和兩點間的相關性值
bool vst[5005]={0};
int q,ans=0;

void dfs(int now,int r)
{
    ~                   // 將現在的點(now)設為走過
    if(r>=q)
        ans++;

    for ~               // 對每個連到 now 的節點(nxt)
        if ~            // 如果 nxt 沒走過
            ~           // 從 nxt 繼續往下走，重新估算路徑的相關性
    // 以C++ 17 結構化綁定改寫上三行
}

int main()
{
    int n,vk,i,j,rij;
    cin >> n >> vk >> q;
    for(int a=0;a<n-1;a++)
    {
        cin >> i >> j >> rij;
        g[i].push_back({j,rij});
        ~                  // 無向圖，i 連到 j ， j 也連到 i
    }

    dfs(vk,0x3f3f3f3f);
    cout << ~ << endl;    // 答案不是 ans，Why？

    return 0;
}
```

:::warning
[d626: 小畫家真好用](https://zerojudge.tw/ShowProblem?problemid=d626)
+ 全域變數
+ 分四個方向做DFS
:::

:::warning
[a290: 新手訓練系列 ~ 圖論](https://zerojudge.tw/ShowProblem?problemid=a290)
:::

:::warning
[b967: 第 4 題 血緣關係](https://zerojudge.tw/ShowProblem?problemid=b967)
+ max_element
+ [解題參考1](https://yuihuang.com/zj-b967/) (farthest of farthest：以任意點(0)為根，找離它最遠的點(v)，再以此點(v)為根，找最大深度)
+ [解題參考2](https://sites.google.com/site/zsgititit/zi-xun-neng-li-jian-ding/apcs/10503di4ti-xue-yuan-guan-xi)
:::

:::warning
[f161: 3. 尋寶之旅](https://zerojudge.tw/ShowProblem?problemid=f161)
+ 在 DFS 過程中，每次走到一個節點，就將該點顏色數量加一。當 DFS 返回父節點時，把該點顏色數減一，以表示回復到沒有走到此點的狀態。
+ 在拜訪每個節點時，檢查該點的顏色數量有沒有超過最大值。
+ 寶石的顏色號碼不超過10^9^，記錄每一顏色的寶石數用陣列會太大，離散化可以用 [STL map](http://larry850806.github.io/2016/06/06/STL1/#map)。
:::


<br/>

## 六、動態規劃(Dynamic Programming、DP)
+ [動態規劃簡介](https://mropengate.blogspot.com/2015/01/algorithm-ch2-dynamic-programming.html)
    - [範例](https://emn178.pixnet.net/blog/post/89039215)
+ [一個問題若能用 DP 求解，該問題含有以下三個性質](https://hackmd.io/@3xOSPTI6QMGdj6jgMMe08w/HknO-zmQI/https%3A%2F%2Fhackmd.io%2Fs%2FByfT8JZ9E#Week-9-Dynamic-Programming-%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83)
    - 最佳子結構：最佳解可由子問題的最佳解求得。
    - 無後效性：子問題的解一但確定，就不會受到更大的問題的求解決策影響。
    - 重複子問題：子問題為同樣的問題。
+ [規劃步驟](https://hackmd.io/@peienwu/H1avUP5lu)
    1. 定義子問題(狀態定義)。
    2. 找出問題與子問題之間的遞迴關係(狀態轉移方程)。
    3. 規劃初始狀態及轉移順序，避免以遞迴的方式進行計算。
+ 一個DP如果狀態有O(n^x^)而狀態轉移方程涉及O(n^y^)個狀態，一般可稱為xDyD的DP。

### 1. 1D0D                
:::info
EX_6_1：[TCFSH CIRC Judge d067: P-6-2. 不連續的表演酬勞](https://judge.tcirc.tw/ShowProblem?problemid=d067)
+ 每天可以獲得的酬勞放在一維陣列p[]中。
+ 狀態定義： dp[i] 是前 i 天可以獲得的最大報酬。
+ 狀態轉移方程
    - 如果第 i 天不選，前 i 天的獲利就是前 i-1 天的獲利 dp[i]=dp[i-1]。
    - 如果第 i 天要選，可以獲利 p[i]，但是第 i-1 天就不可以選，因此最大的獲利是 p[i]+dp[i-2]。
    - dp[i]=max(dp[i-1], p[i]+dp[i-2])。
:::

```c=
#include <iostream>
using namespace std;

int main()
{
    int n;
    while(cin >> n)
    {
        int p[100005],dp[100005]; // dp[i] 記錄第 1~i 天的最大報酬
        for(int i=0;i<n;i++)
            cin >> p[i];

        dp[0]=~;
        dp[1]=~;

        for ~  // 計算2~n天的報酬
            ~  // 遞迴關係式

        cout << dp[n-1] << endl;
    }
    return 0;
}
```

:::warning
[d038: 00900 - Brick Wall Patterns](https://zerojudge.tw/ShowProblem?problemid=d038)
+ dp(1)=1，dp(2)=2
+ dp(n)=dp(n-1) + dp(n-2)
:::

:::warning
[d054: 11310 - DELIVERY DEBACLE](https://zerojudge.tw/ShowProblem?problemid=d054)
+ dp(0)=1，dp(1)=1，dp(2)=5
+ dp(n)=dp(n-1) + 4\*dp(n-2) + 2\*dp(n-3)
+ [解題參考](http://kos74185foracm.blogspot.kr/2011/06/11310-delivery-debacle.html)
:::


### 2. 2D0D
#### 2_1. [最長共同子序列(LCS)](https://yuihuang.com/dp-lcs/)
+ 狀態定義
    - lcs(i, j) 為 x 的前 i 個字元（x[0]~x[i-1]），與 y 的前 j 個字元（y[0]~y[j-1]），最長共同子序列的長度。
    - x 字串的 index 由 0 開始，長度 i 的最元素為x[i-1]。      
+ 狀態轉移方程
    - $$
lcs(i,j)=
\begin{cases}
0 \qquad\qquad\qquad\qquad\qquad\qquad\qquad\ \ \   if \ i=0 \ or \ j=0
\\[2ex]                
lcs(i-1,\ j-1)+1\qquad\qquad\qquad\ \ if \ x[i]=y[j]
\\[2ex]
max(lcs(i-1,j),\ lcs(i,j-1))\qquad otherwise
\end{cases}\qquad\qquad\qquad\qquad\qquad\qquad\qquad
$$
+ [步驟說明](https://www.youtube.com/watch?v=uX-PJiNVHrs&t=17m33s)
:::info
EX_6_2：[c001: 10405 - Longest Common Subsequence](https://zerojudge.tw/ShowProblem?problemid=c001)
:::

```c=
#include <iostream>
#include <cstring>
using namespace std;
int dp[1005][1005];

int main()
{
    string x,y;
    while (cin >> x >> y)
    {
        memset(dp,0,sizeof(dp));
        for ~          // x 的所有元素
            for ~      // y 的所有元素
                if ~   // x,y 最後一個元素相同
                    ~
                else   // x,y 最後一個元素不同
                    ~

        cout << dp[x.size()][y.size()] <<endl ;
    }

    return 0;
}
```
:::warning
[d378: 最小路徑](https://zerojudge.tw/ShowProblem?problemid=d378)
+ [解題參考](https://yuihuang.com/zj-d378/)
:::

:::warning
[a133: 10066 - The Twin Towers](https://zerojudge.tw/ShowProblem?problemid=a133)
+ [解題參考](http://par.cse.nsysu.edu.tw/~advprog/advprog2013/tip/10066.ppt)
:::

:::warning
[a252: Another LCS](https://zerojudge.tw/ShowProblem?problemid=a252)
:::

#### 2_2. <span id="0-1背包問題">[0-1背包問題](https://yuihuang.com/0-1-knapsack/)</span>
+ 有 n 個物品，每個物品有重量 w 跟價值 v，背包有最大負重，求在物品不可以分割不重複的情況下，背包可以裝的最大價值為何？
    - 相對於分數背包問題，在選擇物品時，要麼完整地選擇，要麼不選擇，不可以只拿物品的一部份(物品不可分割)。
    - Greedy不行，假設背包負重30kg，會得到190，但最大價值為200。
        |物品|重量|價值|價值/重量比|
        |:-:|:-:|:-:|:-:|
        |1  |5  |50 |10|
        |2  |10 |60 |6 |
        |3  |20 |140|7 |              
    - 窮舉法會太多狀況，n 個物品，每個物品可以選擇拿或不拿，會有 2^n^ 種可能性要考慮(例如 d637，n=10000)。
+ 狀態定義
    - dp[i][j]表示只考慮拿前 i 個物品，放入最大負重為 j 的背包時，可以得到的最大價值。
    - [圖示](https://yuihuang.com/0-1-knapsack/)
+ 狀態轉移方程
    - 假設第 i 項物品的重量為 w[i]，價值為 v[i]。
    - 如果 w[i]>j，根本不可能挑選。
    - 如果拿第 i 項物品，背包重量剩 j-w[i] (可以從i-1項挑選)，亦即在負重 j 時，第 i 個物品不拿時的價值，與拿了第 i 個物品時的價值，選擇較好的那個。
    - $$
dp(i,\ j)=\begin{cases}
0 \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\ \ \  if \ i=0 \ or \ j=0                
\\[2ex]                
dp(i-1,\ j) \qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\  if \ w[i]> j\\[2ex]
max(\ dp(i-1,\ j),\ dp(i-1,\ j-w[i]) + v[i]\ )\quad otherwise \qquad\qquad\qquad\qquad\qquad
\end{cases}
$$
    - [圖示](https://www.wandouip.com/t5i75076/)

:::info
EX_6_3：[d637: 路過的鴨duck](https://zerojudge.tw/ShowProblem?problemid=d637)
+ [解題參考](https://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/d637-duck)
:::

```c=
#include<iostream>
#include<cstring>
using namespace std;
#define N 10000               // 飼料數->物品數量
#define M 100                 // 胃容量->背包重量
int dp[N+1][M+1],w[N+1],v[N+1],n; // w[i]表飼料的體積(物品重量)，v[i]表飼料的飽足感(物品價值)


int main()
{
    while(cin >> n)
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
            cin >> w[i] >> v[i];

        for ~              // 考慮每一個物品要不要拿
            for ~          // 考慮每一個背包重量
                if ~       // 如果第 i 個物品的重量 > 背包重量，則不拿
                    ~      
                else
                    ~      // 如果如果第 i 個物品放的下，在拿或不拿中選較大的

        cout << dp[n][M] << endl;
    }
    
    return 0;
}
```

:::info
EX_6_4：[b184: 5. 裝貨櫃問題](https://zerojudge.tw/ShowProblem?problemid=b184)
+ [空間優化](https://hackmd.io/@3xOSPTI6QMGdj6jgMMe08w/ByfT8JZ9E?type=view#01-%E8%83%8C%E5%8C%85%E5%95%8F%E9%A1%8C)
    - [圖示](https://hackmd.io/@peienwu/H1avUP5lu#01%E8%83%8C%E5%8C%85%E5%95%8F%E9%A1%8C)
+ 若狀態定義 dp(j) 為背包重量為 j 時的最大價值。
+ 對第 i 個物品，考慮不拿或拿，狀態轉移方程為
    - dp(j)=max( dp(j), dp(j−w[i])+v[i] )
    - j 必須為從大到小，否則可能會造成重複拿物品。
:::

```c=
#include <iostream>
using namespace std;

int main()
{
    int n;
    while (cin >> n)
    {
        int dp[101]={0},w[101],v[101];
        for(int i=1;i<=n;i++)
            cin >> w[i] >> v[i];

        for ~      // 考慮每一貨物要不要拿
            for ~  // 對這個貨物，從體積 100 往前檢查
                ~  // 裝這個貨物的價值比較大，dp[j]就設定成新的(較大的)價值

        cout << dp[100] << endl;
    }

    return 0;
}
```

:::warning
[b140: NOIP2005 3.採藥](https://zerojudge.tw/ShowProblem?problemid=b140)
:::

:::warning
[b131: NOIP2006 2.开心的金明](http://zerojudge.tw/ShowProblem?problemid=b131)
+ [解題參考](https://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/b131-noip2006-2)
:::

:::warning                
[TCFSH CIRC Judge d075: Q-6-10. 置物櫃出租 (APCS201810)](https://judge.tcirc.tw/ShowProblem?problemid=d075)
+ 以0-1背包問題的方法，計算剩下空間(總空間-王老要的空間)的最大利益。
+ 目前的利益-剩下空間的最大利益即是王老損失的利益。
+ [解題參考](https://www.youtube.com/watch?v=0SNyjUl2t4A)
:::
                
#### 2_3. (Bonus) 零錢問題
+ [狀態定義 & 狀態轉移方程](https://yuihuang.com/change-coins/)
:::info
EX_6_5：[d904: 換零錢](https://zerojudge.tw/ShowProblem?problemid=d904)
+ [整數最大值可用0x3f3f3f3f](https://blog.csdn.net/jiange_zh/article/details/50198097)
+ memset(a,0x3f,sizeof(a)); 需含入cstring
+ [解題參考](https://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/d904)               
+ 零錢可重複，檢查金額時，不需如 b184 大到小檢查。
:::
                
```c=
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    int c,n;
    while(cin >> c >> n )
    {
        int coin[n],dp[c+1]; // dp[]存每種金額，最少的硬幣數量
        memset(dp,0x3f,sizeof(dp));
        dp[0]=0;

        for(int i=0;i<n;i++)
            cin >> coin[i];

        for ~             // 對每一個種硬幣
            for ~         // 對每一金額(硬幣幣值以上金額)，重新檢查硬幣數是否會改變
                dp[j]= ~  // 如果拿此硬幣會讓此金額的硬幣數量減少，則更新

        cout << dp[c] << endl;
    }

    return 0;
}
```

:::warning
[d253: 00674 - Coin Change](https://zerojudge.tw/ShowProblem?problemid=d253)
+ [解題參考](https://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/d253-674---coin-change)
:::

:::warning
[b232: TOI2009 第四題：分房子](https://zerojudge.tw/ShowProblem?problemid=b232)
+ 將1,3,5,7,9…視為幣值，n間房子視為金額
+ dp[j]=dp[j]+dp[j-coins[i]]
:::
                

### 3. 1D1D                 
+ 有O(n)個子問題(狀態)，一個子問題(狀態)的計算會牽涉O(n)個前置狀態。
+ 如果直接計算時間複雜度為O(n^2^)，很多1D1D的問題會利用資料結構或問題的特性來降低複雜度。

#### [最長遞增子序列(LIS)](http://web.ntnu.edu.tw/~algo/Subsequence.html)
+ 狀態定義
    - dp[i] 表示以 s[i] 為結尾的最長遞增子序列長度(s[0]~s[i]的LIS長度)
+ 狀態轉移方程
    - dp[i]=max{ dp[j]+1：0<=j<i and s[j]<s[i] }
+ 範例
    | s[0] | s[1] | s[2] | s[3] | s[4] | s[5] |
    |:----:|:----:|:----:|:----:|:----:|:----:|
    |  2   |  5   |  4   |  1   |  6   |  3   |
+ dp 陣列
    |     s[]為結尾      |  2  |  5  |  4  |  1  |  6  |  3  |
    |:------------------:|:---:|:---:|:---:|:---:|:---:|:---:|
    |  LIS 的元素    |  2  | 2 5 | 2 4 |  1  | 2 4 6| 1 3 |
    |      LIS 長度       |  1  |     |     |     |     |     |
    |   5 可接在 2 後    |  1  |  2  |     |     |     |     |
    |   4 可接在 2 後    |  1  |  2  |  2  |     |     |     |
    | 1 無法接在任何數後  |  1  |  2  |  2  |  1  |     |     |
    |   6 可接在 4 後    |  1  |  2  |  2  |  1  |  3  |     |
    |   3 可接在 1 後    |  1  |  2  |  2  |  1  |  3  |  2  |
    
:::info
EX_6_6：[TCFSH CIRC Judge d078: P-6-15. 一覽衆山小](https://judge.tcirc.tw/ShowProblem?problemid=d078)
+ [STL vector](https://yuihuang.com/cpp-stl-vector/)
+ [STL max_element](https://shengyu7697.github.io/std-max_element/)
+ [常用C++ algorithm：lower_bound & upper_bound](https://yuihuang.com/cpp-algorithm-lower-bound-upper-bound/)
+ 先完成O(n^2^)的方法，檔名：d078(40%)                
:::
```c=
    while(cin >> n)
    {
        vector<int> s;   // 方法一
        for(int i=0;i<n;i++)
        {
            int t;
            cin >> t;
            s.push_back(t);
        }
        
        vector<int> s(n); // 方法二
        for(int i=0;i<n;i++)
            cin >> s[i];
        
        // 方法三(C++11，vector要先宣告長度)
        
        for(int e:s)
            cout << e;
    }                
```
                
```c=
// O(n^2)，NA(score:40%) 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    while(cin >> n)
    {
        vector<int> s(n); // 戰力值，若以C++11寫法，vector要先宣告長度
        ~ // 宣告一個vector dp，dp[i]表示以s[i]為结尾的最長遞增子序列長度(s[0]~s[i]的LIS長度)。初始化為1(每一個數字本身就是長度為一的 LIS)

        ~ // 輸入戰力值

        for ~         // 找出 s[i] 能接在哪些數字後面
            for ~     // 檢查 j=0~i-1
                if ~  // 如果 s[i] 能接在 s[j] 後面
                    ~ // 更新 dp[i]

        ~ // dp[]之中最大的值即為 LIS 的長度
    }
                
    return 0;
}
```
+ 上面的做法，對每個 i 點，都要往前搜尋所有的 j 點，時間複雜度為O(n^2^)，如何加速？(省略不必要的計算)
    - 如果 s[i]<=s[j](j<i)，但 dp[i]>=dp[j]，表示s[i]的值比較小，但有比較長的LIS。那麼可以接在s[j]後面的一定也可以接在s[i]後面。
    - 每一種可能的 LIS 長度，留目前最小的可能結尾。以陣列 last[L] 記錄 LIS 長度為 L 的最後一個元素(選值最小的，讓後續數字有機會發展出更長的 LIS)
    - last 陣列的元素是單調遞增的。
+ 範例
    | s[0] | s[1] | s[2] | s[3] | s[4] | s[5] | s[6] | s[7]    |
    |:----:|:----:|:----:|:----:|:----:|:----:|:----:| --- |
    |  2   |  8   |  6   |  7   |  1   |  3   |  4   |  5  |
+ last 陣列
    | LIS 長度        |  1  |  2  |  3  |  4  |  5  |概念|
    |:--------------:|:---:|:---:|:---:|:---:|:---:|:---:|
    |此長度的最後一個元素|2| | | | | |
    | |2|8| | | | |
    | |2|6| | | |26 取代 28|
    | |2|6|7| | |7可加在6後，變成長度3|
    | |1|6|7| | ||
    | |1|3|7| | |13 取代 26|
    | |1|3|4| | |134 取代 267|
    | |1|3|4|5| ||
+ [如果要印出 LIS 的元素](https://yuihuang.com/dp-lis/)
```c=
// O(nlog(n))
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n,s;
    while(cin >> n)
    {
        vector<int> last;
        for(int i=0;i<n;i++)
        {
            cin >> s;
            ~      // 在目前 last 陣列中找 >=s 的最小值，以 s 覆蓋此元素可能產生更長的 LIS
            if ~   // 如果找不到
                ~  // 將 s 放在 last 最後
            else   // 如果找的到
                ~  // 取代這個值
        }
        cout << last.size() << endl;
    }
    
    return 0;
}
```

:::info
EX_6_7：[f608: 4. 飛黃騰達](https://zerojudge.tw/ShowProblem?problemid=f608)
+ 將點依 x 座標排序後，對 y 座標求 LIS的簡單變形(嚴格遞增改為非遞減)。
+ 排序時 x 相等則比較 y，可以用 pair 來記錄點，預設即會這樣比較。
+ [C++ 17 結構化綁定](https://zh-blog.logan.tw/2019/10/29/cxx-17-structured-binding/)
+ 飛黃可以向右或向上移動，y 座標相等可以加到 lis -> upper_bound()
![](https://i.imgur.com/pzY8jW7.png)
:::

```c=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    while(cin >> n)
    {
        ~  // 宣告存 pair 的 vector
        vector<int> lis; // 存 y 座標的 lis
        
        ~  // 讀入果實座標，若以C++11寫法，vector要先宣告長度
            ~
        /*
        for(int i=0;i<n;i++)
        {
            int x,y;
            cin >> x >> y;
            v.push_back({x,y});
        }
        */
                
        ~  // 先根據 x 座標排序(小->大)，如果 x 座標一樣，再根據 y 座標排序

        for ~      // 對每個座標
        {
            ~      // 在目前 lis 陣列中找 > 此點 y 座標的最小值，覆蓋此元素可能產生更長的 LIS
            if ~   // 如果找不到
                ~  // 將此點 y 座標放在 lis 最後
            else
                ~  // 如果找的到，取代這個值
        }
        cout << lis.size() << endl;
    }

  return 0;
}
```

:::warning
[TCFSH CIRC Judge d076: P-6-11. Catalan number](https://judge.tcirc.tw/ShowProblem?problemid=d076)
:::
                
:::warning
[d242: 00481 - What Goes Up](https://zerojudge.tw/ShowProblem?problemid=d242)
+ [解題參考](https://yuihuang.com/zj-d242/)
+ [需多一個 position 陣列](http://web.ntnu.edu.tw/~algo/LongestIncreasingSubsequence.html#3)
:::

:::warning
[d052: 11456 - Trainsorting](https://zerojudge.tw/ShowProblem?problemid=d052)
+ [由於火車可以選擇接在前方或後方，所以將原本的數列前接上顛倒的數列](https://yuihuang.com/zj-d052/)，再找 LIS。
:::

                
### 4. 2D1D                 
#### [切棍子的最小成本](https://www.freesion.com/article/49081335466/)
+ 狀態定義
    - cost(i,j) 表示第 i 點到第 j 點這段的最低切割成本。
    - 以座標 0 與 L 當作第 0 與第 n+1 點，即求 cost(0,n+1)
+ 狀態轉移方程
    - $$
cost(i,\ j)=\begin{cases}
0 \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad  if \ j=i+1                
\\[2ex]
\min\limits_{i<k<j}\{\ cost(i,\ k) + cost(k,\ j) + p[j]-p[i]\ \}\quad otherwise \qquad\qquad\qquad\qquad\qquad
\end{cases}
$$
+ 範例
![](https://i.imgur.com/VQXQTsx.jpg =450x)



:::info
EX_6_8：[TCFSH CIRC Judge d079: P-6-17. 切棍子](https://judge.tcirc.tw/ShowProblem?problemid=d079)
:::

```c=
#include <iostream>
using namespace std;

int main()
{
    int n,L;
    while(cin >> n >> L)
    {
        int cost[205][205],p[205];
        p[0]=0;
        p[n+1]=L;
        for(int i=1;i<=n;i++)
            cin >> p[i];

        for(int i=0;i<n+1;i++)
            cost[i][i+1]=0;     // 點相鄰 cost 為 0

        for(int len=2; len<=n+1; len++)   // 多用一個變數 len=j-i，代表點i~點j之間的長度，比較好思考。
        {
            for ~ // 計算 cost(i, j)
            {
                int j=i+len, minCost=0x3f3f3f3f;
                for ~  // 對 i~j 中間每個切割點 k 計算 cost
                    ~  // 求 i~k cost + k~j cost 的最小值
                ~      // 得到最小值後，總成本還要加上點i~點j之間的距離。
            }
        }
        cout << cost[0][n+1] << endl;
    }
    return 0;
}                
```
                
:::warning
[TCFSH CIRC Judge d086: Q-6-18. 矩陣乘法鏈](https://judge.tcirc.tw/ShowProblem?problemid=d086)
+ [矩陣相乘次序(Matrix Chain Multiplication)](https://web.ntnu.edu.tw/~algo/DynamicProgramming.html#4)                 
+ dp(i, j)為從第 i 個矩陣乘到第 j 個矩陣，最少的相乘次數。
+ r[i]為第 i 個矩陣的列數。
+ c[i]為第 i 個矩陣的欄數。                
+ $$ dp(i, j) = \min\limits_{i\le k<j} \{ dp(i, k) + dp(k+1, j) + r[i]*c[k]*c[j] \} \qquad\qquad\qquad\qquad\qquad\qquad\qquad$$
:::

                
:::warning
[f817: TOI_y21m4_a03枯枝](https://zerojudge.tw/ShowProblem?problemid=f817)
+ dp[i][j] = dp[i][i] + min( max(dp[i+1][k], dp[k+1][j])，i+1 ≦ k < j)
:::

                
## 七、基本圖論(Graph)
+ [【筆記】基礎圖論](https://yuihuang.com/graph-basic/)
+ [圖論概念 - FJCU CPC 訓練網](https://determined-wiles-eb7bd3.netlify.app/graph/concept/)
### 1. 全點對最短路徑 Floyd-Warshall algorithm
:::info
EX_7_1：[d908: 4. 最佳路徑](https://zerojudge.tw/ShowProblem?problemid=d908)
+ 以 [Floyd-Warshall](https://web.ntnu.edu.tw/~algo/Path3.html) 改寫
+ vector 2維陣列[(1)](https://ramihaha.tw/c-program-container-vector-array-linklist/)、[(2)](https://www.itread01.com/content/1546469675.html)
+ [STL max_element](https://shengyu7697.github.io/std-max_element/)
:::

```c=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    char s,u,v;
    int n,w;
    while(cin >> s >> n)
    {
        ~ // 以 vector 宣告2維陣列，並設定大小(才能用index寫入)與初值。
        for(int i=0;i<n;i++)
        {
            cin >> u >> v >> w;
            g[u-'A'][v-'A']=max(w,g[u-'A'][v-'A']);  // 將相鄰矩陣g[u(轉為數字)][v(轉為數字)]的值設為w，A 轉為 0，B 為 1 …，
        }

        for ~ // 每個中繼點
            for ~ // 每個起點
                for ~ // 每個終點
                    if ~ // 如果 i->k 有路，且k->j 有路
                        g[i][j]= ~  // 鬆弛(relaxation)，如果i->k->j 比較大，則更新
        
        cout << *max_element(g[s-'A'].begin(),g[s-'A'].end()) << endl;
    }

    return 0;
}
```

:::warning
[a874: 14. Trace Route](https://zerojudge.tw/ShowProblem?problemid=a874)
+ [陣列初值可設 0x3f3f3f3f 或 0x3fffffff](https://yuihuang.com/floyd-warshall-algorithm/)                
:::

:::warning
[e792: a3.旅行(Trip)](https://zerojudge.tw/ShowProblem?problemid=e792)
+ [解題參考](https://toi-reg.csie.ntnu.edu.tw/wp-content/uploads/question/201912/A3-Trip.pptx)
:::
                
:::warning
[a674: 10048 - Audiophobia](https://zerojudge.tw/ShowProblem?problemid=a674)
+ a[i][j]=min( a[i][j], max(a[i][k], a[k][j]) )
:::

### 2. 並查集(Disjoint Sets)
+ [Disjoint Sets 資料結構 : 樹狀儲存](https://web.ntnu.edu.tw/~algo/Set.html#9)
:::info
EX_7_2：[a445: 新手訓練系列- 我的朋友很少](https://zerojudge.tw/ShowProblem?problemid=a445)
:::

```c=
#include <iostream>
using namespace std;
int p[10005];    // 記錄每個結點的根結點，以根結點為每個集合的代表

int find(int x)  // 找 x 的根結點
{
    if ~ // 如果 x 的根結點==自己，表示 x 為根結點
        ~
    else
        ~ // 以 p[x] 繼續向上查詢
    // 進階：在向上查詢的同時，把在路徑上的每個節點都直接連接到根結點上，以後查詢時就能直接查詢到根節點，下次 find 會較快。
}

int main()
{
    int N,M,Q,a,b;
    while(cin >> N >> M >> Q)
    {
        for(int i=0;i<10005;i++)
            ~  // 一開始每個人的根結點都是自己

        for(int i=0;i<M;i++)
        {
            cin >> a >> b;
            ~ // a 的根結點接到 b 的根結點下
        }

        for(int i=0;i<Q;i++)
        {
            cin >> a >> b;
            cout << (find(a)==find(b) ? ":)" : ":(") << endl;
        }
    }
    
    return 0;
}
```

:::warning
[d813: 10583 - Ubiquitous Religions](https://zerojudge.tw/ShowProblem?problemid=d813)
+ 先假設宗教有 n 個，當a,b的根結點不同要 union 時，就減1。
:::

### 3. 最小生成樹(Minimun Spanning Tree)
+ [Kruskal 演算法](https://www.itread01.com/content/1545066724.html)為一個使用貪婪法 (greedy method) 的演算法，一開始為一空樹，每次在不讓圖中含有任何迴路(cycle)下尋找圖中最小權重的邊加入樹中，直到所有點皆在樹中即完成。
+ Prim演算法與 Dijkstra 演算法類似，屢次找出不在樹上，離樹最近的點。

:::info
EX_7_3：[a129: 最小生成樹](https://zerojudge.tw/ShowProblem?problemid=a129)
:::

```c=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct edge
{
    int x,y,cost;
};

int p[100005];

bool cmp(edge a, edge b)
{
    return a.cost < b.cost;
}

int find(int x) // 找 x 的根結點
{
    ~
}

int main()
{
    int n,m,x,y,c;
    while(cin >> n >> m)
    {
        vector<edge> v;
        long long ans=0,edgCnt=0;

        for(int i=0;i<n;i++)
            p[i]=i;

        for(int i=0;i<m;i++)
        {
            cin >> x >> y >> c;
            v.push_back({x, y, c});
        }

        sort(v.begin(), v.end(), cmp);

        for ~ // 依邊的權重小->大開始檢查
        {
            x=find(e.x); // 找到此邊 x 端點的根結點
            ~            // 找到此邊 y 端點的根結點
            if ~         // 如果兩個根結點『不相同』，代表不是屬於同一個集合，則此邊可選。否則會形成迴路，不應選。
            {
                ~  // 將此邊兩端點的集合連起來
                ans+=e.cost;
                edgCnt++;
            }
        }
        cout << (edgCnt==n-1 ? ans : -1) << endl;
    }

    return 0;
}
```
:::warning
[d909: 公路局長好煩惱！？](https://zerojudge.tw/ShowProblem?problemid=d909)
:::

### 4. 樹
+ [演算法筆記 - Tree](http://web.ntnu.edu.tw/~algo/Tree.html)
:::info
EX_7_4：[c463: apcs 樹狀圖分析 (Tree Analyses)](https://zerojudge.tw/ShowProblem?problemid=c463)
:::
```c=             
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

vector<int> child[100005];  // node i 的孩子
int parent[100005];         // node i 的父親
int h[100005];              // node i 的高
                
void findH(int node)  // 找結點高度
{
    h[node]=0;
    for ~  // 對此結點的每個孩子
    {
        ~  // 以遞迴找每個孩子的樹高
        ~  // 此結點的樹高為孩子樹高最大者+1
    }
}

int main()
{
    int n,root;
    while(cin >> n)
    {
        memset(parent,-1,sizeof(parent));
        for(int i=1;i<=n;i++)
        {
            int deg,chNum;
            cin >> deg;
            for(int j=1;j<=deg;j++)
            {
                cin >> chNum;
                ~ // 將孩子編號放入child[i]
                ~ // 將此孩子編號的父親設為 i
            }
        }

        for ~     // 遍歷每個點找根結點
            if ~  // 此結點沒父親即根結點
            {
                root=i;
                break;
            }

        findH(root);

        long long sum=0;
        for(int i=1;i<=n;i++)
            sum+=h[i];
        cout << root << endl << sum << endl;
    }

    return 0;
}
```                
:::warning
[b967: 第 4 題 血緣關係](https://zerojudge.tw/ShowProblem?problemid=b967)
:::

### 5. 二分圖（Bipartite graph)
+ [二分圖判斷](https://www.itread01.com/content/1545440778.html)
+ [圖論入門———深度優先搜尋實現二分圖判定(dfs染色)](https://www.itread01.com/content/1546276331.html)   
:::info
EX_7_5：[c889: 2. 二分圖](https://zerojudge.tw/ShowProblem?problemid=c889)
+ [位元運算(&、|、^)](https://www.86duino.com/?p=1411&lang=TW)
:::
```c=
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int color[100005],cnt[2]; // color記錄每個點的顏色，cnt記錄AB子集的頂點數
vector <int> g[100005];

bool dfs(int u, int c) // 用DFS塗色，判斷二分圖
{
    bool ans=1;
    ~     // 將 u 點的顏色設為 c
    ~     // c 顏色的點多 1 個
    for ~ // 對每個跟 u 相鄰的點 v
    {
        if ~  // 相鄰點同色，不是二分圖
            return 0;
        if ~  // 相鄰點沒上色，預計其顏色為c^1，繼續dfs下去
            ans &= ~ 
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n,m,a,b,ans;
    cin >> n >> m;
    memset(color,-1,sizeof(color));
    for(int i=0;i<m;i++)
    {
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for(int i=1;i<=n;i++)
    {
        if ~ // 如果這個點還沒上色
        {
            cnt[0]=cnt[1]=0;
            if ~ // 如果不是2分圖
            {
                cout << 0 << endl;
                return 0;
            }
            ans+=min(cnt[0],cnt[1]);
        }
    }
    cout << ans << endl;

    return 0;
}
```

:::warning
[d768: 10004 – Bicoloring](https://zerojudge.tw/ShowProblem?problemid=d768)
+ 清空 vector
```c
vector<int> g[205];
for(int i=0;i<205;i++)
    g[i].clear();
```
:::
                
:::warning
[g598: 4. 真假子圖](https://zerojudge.tw/ShowProblem?problemid=g598)
+ 二分圖判斷+二分搜尋
+ [解題參考](https://hackmd.io/@peienwu/APCS1107)    
:::                
              

### 6. 拓撲排序(Topological Sort)
+ [拓撲排序-kahn's algorithm](http://slides.com/sylveon/basic-graph#/5/2)
:::info
EX_7_6：[f167: m4a1-社團 Club](https://zerojudge.tw/ShowProblem?problemid=f167)
:::
```c=
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n,m,a,b;
    vector<int> g[1005],todo,sol,in(1005); // 入度(In-degree)
    
    cin >> n >> m;
    while(m--)
    {
        cin >> a >> b;  // 有向邊 a->b
        g[a].push_back(b);
        ~    // 點 b 的 In-degree +1
    }

    for(int i=1;i<=n;i++) // 將 In-degree 為 0 的點，加入 todo
        ~ 
            ~ 

    while ~ // 當 todo 不是空的
    {
        int u=todo.back(); // 任意拿一個出來
        todo.pop_back();
        sol.push_back(u);

        for ~ // 對每個跟 u 相鄰的點 v
        {
            ~       // 將點 v 的 In-degree -1
            if ~    // 如果點 v 的In-degree 為 0
                ~   // 將點 v 加入 todo
        }
    }

    if(sol.size()==n)
    {
        cout << "YES" << endl;
        for(int e:sol)
            cout << e << endl;
    }
    else
        cout << "NO" << endl;

    return 0;
}                                   
```
                
:::warning
[a552: 模型](https://zerojudge.tw/ShowProblem?problemid=a552)
+ 要回答字典序最小的解，可以使用                                  priority_queue 當 todo 的容器。
    -  priority_queue< int,vector<int>,greater<int> > pq; 
:::
    
