進階程式設計(C++)

###### tags: `選修` # 進階程式設計(C++) :::success **評量、學習歷程** ::: ### 1. 評量方式 + 上課基本練習(遲交期限：1週) **40%** + 作業題數 **20%** (期中10%+期末10%) - 作業登記表： - [歷年作業登記表](https://hackmd.io/@cube/r1Cw2JgDT) - 每寫完一題作業，請將程式碼連結登錄於作業登記表，以統計作業題數。請小心不要改到別人的資料。惡意編刪別人的資料，視情節扣分或校規處理。 - 作業原始分數：解題數 $*$ 15 (最高120分) ``` if 上機考分數>=60 作業實得分數=作業原始分數 else 作業實得分數=作業原始分數*(上機考成績/60) ``` - 不要為了衝題數，做複製貼上、不求甚解這種沒意義的事。上機考0分，全部都寫也是0分。 - 不寫作業，除了無作業成績，上機考時網路會斷線，沒有任何參考資料，也必定寫不出來，請每個單元至少完成 2 題作業，熟練基本語法。**(不寫作業被當的機會很高，除非你有本事上機考2次都及格)** - 不要考前才寫作業，初學程式會有很多錯誤，要花時間除錯。請自我要求每週至少要寫 1 題作業，上機考才會比較保險。 - 不會的可以去參考網路上的程式碼、解法，同學也可以互相討論，而且是鼓勵的。不論如何，都要在了解解法後，不看別人的程式碼，自己親自寫一遍。 - 有做作業，考差了才有補救的機會，作業題為期末解題報告的題目。 + 期中上機考(二、搜尋教完後 1 週) **20%** + 期末上機考(倒數第 2 週) **20%** + 期末解題報告 **10%** (高二) - 非必要，想高分或不及格的同學請保握最後機會。 - 繳交期限：最後一週上課前 1 天。 - 分數：每一題 10 分。每個單元至多可放 2 題 (不可以都寫同一單元的題目) - 報告格式： * 第1頁為解題目錄(單元、題號、題目、頁碼)。 * 每題的子標題為 (1) 單元、題號、題目、題目簡述 (2) 解題動態、評分結果截圖 (3) 解題思路 (4) 程式碼 (5) 反思(遇到的錯誤、修正的地方、更好的方法…) (6) 錯誤程式碼 - 檢核方式： * 有交解題報告者，最後一週會請你在沒有網路的狀態下重寫一題當做檢核(題目由老師挑選)，寫不出來作業直接作廢不算分，請務必自行思考完成。 * 不要為了分數直接複製貼上別人的程式碼，那是無意義的行為，檢核時你就會現出原形，就不用做這種白工了。 - 可整合上課內容後完成課程學習成果，上傳至學習歷程檔案平台。請儘量挑選一開始有錯，然後修正的題目，將修正的想法寫出來更能顯示出反思的能力。 ### 2. [TOI推廣計畫-線上練習賽](https://tpmso.org/toi/index.php/reg/) + 成績計算：分數/100直接加在總成績。 + 上學期10、11、12月，下學期3、4、5月，最後一週。 + 星期一08:00 ～星期五20:00。90分鐘。 + [證書](https://drive.google.com/open?id=1DcgDKn1R33kOPc_HazdIyQDgyYxSCPlZ) ### 3. [APCS](https://apcs.csie.ntnu.edu.tw/) + 實作級分*2，直接加在總成績。 + 3級分免上機考，上機考成績為100。 + 4級分以上者，一切皆免，學期成績直接算100。 ### 4. 學習歷程檔案(修課記錄、課程學習成果) + 最後一週上課結束前如果認證完成，學期總成績加分。 + [撰寫「課程學習成果」參考資源](https://hackmd.io/@cube/HkCv90e19)。 ### 5. 修課建議目標 + 低：成績及格(修課記錄)。 + 中：能產出課程學習成果。 + 高：參加 APCS 檢定，實作達到 3 級分以上。 ### 6. 演算法進階參考 + [中央資工演算法](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) ### 7. [高中資訊學科中心科技領域加深加廣選修課程－進階程式設計](https://ghresource.mt.ntnu.edu.tw/nss/s/main/InformationTechnologyTPD05) ### 8. 軟體 + [Code::Blocks](http://cs.cysh.cy.edu.tw/software/software_download.html) + [Dev-C++](http://cs.cysh.cy.edu.tw/software/software_download.html) + [VSCode](https://hackmd.io/@liaojason2/vscodecppwindows )([無法debug處理](https://stackoverflow.com/questions/37405975/c-for-vs-code-unable-to-start-debugging-program-path-is-missing-or-invalid?fbclid=IwAR1QQOzXkI6LQc2n0L3q0Sywp_Fx92igG83ngDbhLJrMdZXvaFEqtOW04hM)) + [GDB online Debugger | Compiler - Code, Compile, Run, Debug online C, C++](https://www.onlinegdb.com/) + [The collaborative browser based IDE - Replit](https://replit.com/) :::success **程式語言(基本語法複習)** ::: + 巢狀 if :::info EX_0_1：[d065: 三人行必有我師](https://zerojudge.tw/ShowProblem?problemid=d065) ::: + for 迴圈 :::info EX_0_2：[d490: 我也愛偶數](https://zerojudge.tw/ShowProblem?problemid=d490) + 先完成1+...+n ::: + 一維陣列 :::info EX_0_3：[f345: 新手練習題—陣列](https://zerojudge.tw/ShowProblem?problemid=f345) ::: :::success **資料結構** ::: ## 一、堆疊 + [0-19 queue 與 stack | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/03/0-19/) + 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<bits/stdc++.h> ::: ``` ｃ= #include <iostream> ~ using namespace std; int main() { ~ // 宣告一個存 int 的 stack，需含入 stack 標頭檔 int n; while(cin >> n) { while ~ // n大於0 { ~ // 將n除以2的餘數push進堆疊 ~ // 將n除以2 } while ~ // 堆疊內還有元素 { ~ // 印出堆疊頂端元素 ~ // 將堆疊頂端元素移除 } ~ // 一筆測資完換行 } return 0; } ``` :::info EX_1_2：[b838: 104北二2.括號問題](https://zerojudge.tw/ShowProblem?problemid=b838) + 遇「(」push + 遇「)」檢查stack是否是空的，如果不空pop；如果空，則括號不正確。 + 最後再檢查stack是否是空的。 ::: ``` ｃ= #include <iostream> #include <stack> using namespace std; int main() { int t; cin >> t; cin.ignore(); while(t--) { ~ // 宣告一個存 char 的 stack string s; int cnt=0; cin >> s; for ~ // 對s中的每一個字元判斷 { if ~ // 如果s[i]是左括號，等於要有2個等號「==」 ~ // 將s[i]放到堆疊 else // s[i]是右括號 { if ~ // 如果堆疊內有左括號，堆疊size>0。sk.top()=='(' 會記憶體區段錯誤(Segmentation fault)，不能讀空的堆疊 { ~ // pop出一個左括號 ~ // 計數加1 } else // 沒有左括號，表示式子不正確(多了右括號) { ~ // 計數設為0，設定為一個等號「=」 ~ // 跳出迴圈 } } } if ~ // 最後堆疊內還有左括號(多了左括號) ~ // 計數設為0 cout << cnt << endl; } return 0; } ``` :::warning [i213: stack 練習](https://zerojudge.tw/ShowProblem?problemid=i213) ::: :::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); ::: ## 二、佇列 ### 1. queue + [0-19 queue 與 stack | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/03/0-19/) + 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 ~ // 下一點設為 '#' 表示走過 } } ``` ### 2. priority_queue + [0-22 priority_queue | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/10/0-22/) | 名稱 | 意義 | |:--------|:----------| |priority_queue <int> pq |建立一個 int 型別的 priority queue，資料預設由大到小排序| |priority_queue<int, vector<int>, greater<int>> pq |建立一個 int 型別的 priority queue，資料改為由小到大排序| |pq.push(x) |加入一個元素 x 到 pq| |pq.pop() |刪除最大值| |pq.top() |取出 pq 裏的最大值| :::info EX_2_3：[b151: NOIP2004 2.合并果子](https://zerojudge.tw/ShowProblem?problemid=b151) + 取 priority_queue 中兩個最小值相加後再放入佇列。 + 預設 pq.top()為取最大值，欲取最小值要使用 greater<int> 當比較函式(Container也要寫)。 - priority_queue<Type, Container, Functional> ::: ``` ｃ= #include <iostream> #include <queue> using namespace std; int main() { int n,a; while(cin >> n) { // 宣告一個 priority_queue 存每堆的果子數 for(int i=0;i<n;i++) { cin >> a; pq.push(a); } int g1,g2,sum=0; while(pq.size()>1) { ~ // 取出最小的值放到 g1 ~ // pop 掉 ~ // 取出次小的值放到 g2 ~ // pop 掉 ~ // 將 g1+g2 加到總體力耗費值 ~ // 將 g1+g2 重新 push 進 pq } cout << sum << endl; } return 0; } ``` :::warning [e447: queue 練習](https://zerojudge.tw/ShowProblem?problemid=e447) ::: :::warning [d900: NOIP2010 2.接水问题](https://zerojudge.tw/ShowProblem?problemid=d900) + 依輸入序，取佇列中最小值相加後再放入佇列。 ::: :::warning [d406: 倒水時間](https://zerojudge.tw/ShowProblem?problemid=d406) + BFS，以STL queue實作。 ::: ## 三、串列 + [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()](https://mropengate.blogspot.com/2015/07/cc-vector-stl.html) |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://cplusplus.com/reference/algorithm/find/) + list find 時間複雜度為O(n)，會過不了最後兩筆測資 → [以陣列模擬 list](https://www.chino.taipei/code-TOJ-21-%E9%99%B8%E8%A1%8C%E9%B3%A5%E5%A4%A7%E8%B3%BD%E8%BB%8A/)。 + C++11：auto、[range-based for loop](https://blog.csdn.net/hailong0715/article/details/54172848) ::: ``` 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 (使用lst.remove來刪除) else if(t==1) // x衡刺 { ~ // 找到 x 的位置(it) ~ // 先將 itp 設為 it ~ // 將 itp 調整成 it 的前一個位置 if ~ // 如果 x 不是開頭 (使用 it 來判斷) { ~ // 刪除 x (使用it來刪除) ~ // 將 x 插入至 itp 所指的位置 } } } for ~ // 以 range-based for loop，印出 lst 裏的每個元素 ~ /* 1.解釋指標觀念 int a[3]={1,2,3}; cout << *a; 2.iterator 解釋 list<int>::iterator it=lst.begin(); cout << *it; it++; cout << *it; 3.示範 iterator 寫法 */ cout << endl; } return 0; } ``` :::warning [a870: 10. List Maker](https://zerojudge.tw/ShowProblem?problemid=a870) ::: :::success **演算法** ::: ## 一、排序演算法 + [思考排序的演算法](https://zh.wikipedia.org/wiki/十三張) ### 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) + 交換函式：swap() ::: ```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://ithelp.ithome.com.tw/articles/10276719)：跟交換排序法類似，但交換次數較少。對每個基準點，找到其後最小的數值，並進行對調。 + [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. 排序演算法應用 + [0-13 排序 | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/11/16/0-13/) ```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^)可行嗎？空間？ + 將輸入線段依左端點座標排序。則前後兩線段的關係只可能為重疊(包含相連)或不重疊(新線段) - 如果下一線段的左端點 > 前一線段的右端點，表示前一線段已結束，計算並加總覆蓋長度。 - 如果下一線段的左端點 <= 前一線段的右端點，表示前一條線段可延續，調整前一線段右端點位置即可。 + [結構(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= // 暴力法(TLE，20%) #include <bits/stdc++.h> using namespace std; bool seg[10000000]={0}; int main() { int n; while(cin >> n) { int st,ed,cnt=0; for(int i=0;i<n;i++) { cin >> st >> ed; for(int j=st;j<ed;j++) seg[j]=1; } for(int i=0;i<10000000;i++) if(seg[i]==1) cnt++; cout << cnt << endl; } return 0; } ``` ```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)時為要的順序。 ::: ## 二、搜尋演算法 + 數列需先排序好才可使用二分搜尋。 + [要定義好搜尋的區間是\[a,b\]或\[a,b)或其它](https://www.itread01.com/content/1548961212.html) - [程式設計中左閉右開區間的廣泛應用](https://www.cnblogs.com/fighlone/p/13526864.html) + 區間選擇不正會確導致無窮迴圈，陣列越界 → 模擬剩下兩個元素時，是否能正確執行到結束。 :::info EX_2_1：[d732: 二分搜尋法](https://zerojudge.tw/ShowProblem?problemid=d732) + 陣列從index 1 開始存。 + 自行練習循序搜尋，結果會如何？(TLE，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 <> 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://www.796t.com/content/1551625085.html)([e616](https://zerojudge.tw/ShowProblem?problemid=e616)) + 對答案二分搜。假設一個答案，檢查這個答案是不是符合條件限制，以二分搜尋的方式逼進最大值。 + 結束狀況討論 ![](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) ::: ## 三、貪婪(greedy)演算法 + 假設一個問題可以藉由一系列的選擇來解決，貪婪演算法為在每一步的選擇中，都採取在當前狀態下的最佳選擇，從而希望導致結果是最佳解的演算法。 + [使用貪婪策略的演算法](https://blog.csdn.net/weixin_46072771/article/details/106365035) - 活動選擇(Activity Selection Problem) - 物品可分割背包問題(Fractional Knapsack Problem) - 霍夫曼編碼（Huffman Coding） - 最小生成樹(Min spanning tree problem) : Kruskal’s algorithm and Prim’s algorithm - Dijkstra 最短路徑演算法 :::info EX_3_1：[TCFSH CIRC Judge d042: 例題 P-4-1. 少林寺的代幣](https://judge.tcirc.tw/ShowProblem?problemid=d042) + 當代幣之間不一定是倍數關係時(如 1、3、4)，局部最佳解不一定會組成全局最佳解。 ::: ```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](https://cplusplus.com/reference/functional/greater/))。 + 不斷將單位重量價值最大的礦砂放入背包，直到背包已滿或沒有礦砂可放入。 + STL [vector(1)](https://emanlaicepsa.github.io/2020/11/30/0-17/) [(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 [TCFSH CIRC Judge d045: 例題 P-4-4. 幾場華山論劍(activity selection)](https://judge.tcirc.tw/ShowProblem?problemid=d045) + activity selection problem 經典題 + 若[x,y]是還未選取線段中右端點最小的線段，那麼最佳解一定會挑選[x,y]。 + 一開始依照右端點由小到大排序，然後不斷將最小右端的線段挑進最佳解，略過與它重疊的線段。 + 排序自訂比較函數的偷懶寫法→利用pair。 ::: :::warning [f832: 隕石 (Meteorite)](https://zerojudge.tw/ShowProblem?problemid=f832) + 將隕石重量、捕捉器容量排序 + 由捕捉器容量大到小，決定是否可以裝入此時最大重量的隕石。 ::: ## 四、分治(divide & conquer)演算法 ### 1. 遞迴複習 :::info EX_4_1：[a623: 3. Combination](https://zerojudge.tw/ShowProblem?problemid=a623) + 以遞迴求組合數。 + $C^n_m = C^{n-1}_m + C^{n-1}_{m-1}$ + $n==m \ || \ m==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; } ``` :::info EX_4_2：[f637: DF-expression](https://zerojudge.tw/ShowProblem?problemid=f637) + [解題參考](https://www.youtube.com/watch?v=LMlQIJoU6PA) + 測資 | ![](https://i.imgur.com/PqOBL6H.png =140x) | ![](https://i.imgur.com/oQ5mLc9.png =140x) |![](https://i.imgur.com/GDhJApH.png =140x) |![](https://i.imgur.com/cvJNgmb.png =250x)| | :--- | :--- | :--- | :--- | | 1 8 ans=64 | 20101 8 ans=32 | 202010101 8 ans=24 || ::: ```c= #include <iostream> using namespace std; int idx,n; string s; int f(int n) { char c=s[idx++]; if(c=='0') return 0; else if ~ // 1 表示全部都是黑色，回傳 n*n ~ else // 2 表示均分為四小塊，用遞迴把四小塊的結果加總回傳 { int sum=0; for ~ ~ return sum; } } int main() { while(cin >> s >> n) { idx=0; cout << f(n) << 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)所有子問題的解答成為原本問題的解答。(不一定所有的問題都需要，快速排序 vs. 合併排序) ### 3.優點 + 將問題分割，較易解決困難的問題。(河內塔) + 可以找出比較有效率的演算法。(合併排序) + 能夠平行處理。(快速排序) ### 4.分治經典問題 + [找出較輕的假幣](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_3：[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 + Q：為何變數都宣告為 int，範例測資 1、2 對，但 3 會錯？ A：第 16 行 half\*half\*b 有可能會超過 int，所以第 12 行要宣告為 long long。 ::: ```c= #include<iostream> using namespace std; int dc(int b,int p,int m) { if(p==0) return 1; else if(p==1) return ~ else { int half= ~ // 先算出 b^(p/2)%m 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_4：[a233: 排序法~~~ 挑戰極限](https://zerojudge.tw/ShowProblem?problemid=a233)(以合併排序實作) + 時間複雜度O(n^2^)的排序法會TLE + [步驟說明](https://hackmd.io/@Aquamay/H1nxBOLcO/https%3A%2F%2Fhackmd.io%2F%40Aquamay%2FHJgJ3hxkou) ::: ```c= #include <iostream> using namespace std; int a[1000005],tmp[1000005]; // [L, R) void merge_sort(int L,int R) { if(L+1>=R) return; int mid=(L+R)/2; merge_sort(L,mid); // 左半邊以 merge_sort 排序好 ~ // 右半邊以 merge_sort 排序好 int i=L, j=mid, idx=0; // i 是左半邊開始 index，j 是右半邊開始 index，idx 是 tmp 的 index while ~ // 將左、右半邊已排序好的序列，依序放至 tmp 陣列。(i、j 還沒到底) { if(a[i]<a[j]) tmp[idx++]=a[i++]; // 將 a[i]放至tmp else ~ // 將 a[j]放至tmp } while(i<mid) // 當左半邊沒放完，依序放至 tmp 陣列 tmp[idx++]=a[i++]; while ~ // 當右半邊沒放完，依序放至 tmp 陣列 ~ for(int k=L;k<R;k++) // 將 tmp 拷貝回 a 陣列 a[k]=tmp[k-L]; } int main() { int n; while(cin >> n) { for(int i=0;i<n;i++) cin >> a[i]; merge_sort(0,n); for(int i=0;i<n;i++) cout << a[i] << " "; cout << endl; } return 0; } ``` ```c= // 15~29 更精簡寫法 int j=mid, idx=0; // i 是左半邊開始 index，j 是右半邊開始 index，idx 是 tmp 的 index for(int i=L;i<mid;i++) // 於每個左邊的元素 a[i] { while(j<R && a[j]<a[i]) // 先把右邊比 a[i] 小的 a[j] 複製到 tmp[] tmp[idx++]=a[j++]; tmp[idx++]=a[i]; // 然後再把 a[i] 複製到 tmp[] } for(int k=L;k<j;k++) // 將 tmp 拷貝回 a 陣列。i 迴圈結束後，右邊可能有剩下的元素(比左半都大)，它們都已經在正確的位置上，所以不需要處理 (k<R->k<j)。 a[k]=tmp[k-L]; ``` :::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 [TCFSH CIRC Judge d064: P-5-4. 反序數量 (APCS201806) ](https://judge.tcirc.tw/ShowProblem?problemid=d064) + 類似 a233 合併排序 + [資訊之芽算法班第六週 Divide and conquer](https://www.csie.ntu.edu.tw/~sprout/algo2019/ppt_pdf/week06/divide_and_conquer.pdf) + 如果看成從前往後掃，對於每個數a[i]只要能求在i之前有多少大於它的數，即可用線段樹來做。[參考網站](https://zh.codeprj.com/blog/4c8dff1.html) ::: ## 五、樹搜尋(tree search)與回溯(backtracking)演算法 + 許多問題尋找解答的過程可以表示成樹，建構出解答空間樹(solution space tree)，因此找解答就轉變成一個樹搜尋問題。 + [回溯法](https://www.youtube.com/watch?v=nrHTtjkYEyQ)是暴搜法的一種，用來枚舉所有的候選解。在進行未拜訪節點選擇時，可以先選擇可能會有好結果的分支，或是提早判斷若無解，就不遞迴至下一層，而是回溯退回先前的節點。 + [DFS](https://jason-chen-1992.weebly.com/home/-graph-searching-methods) vs. 回溯 (backtracking) - DFS 可視為回溯法的一種型態，DFS 會遍訪每一個未拜訪過的子節點，如果該節點為樹葉節點，就退回其父節點再遍訪其它分支的節點，強調搜尋的順序。 - 回溯法強調剪枝(pruning)，剪掉不符合條件的分枝，不再繼續遞迴下去。 - [DFS 遇到拜訪過的節點會馬上回溯，backtracking 遇到不合理的解答會馬上回溯。](http://web.ntnu.edu.tw/~algo/Backtracking.html#1) :::info EX_5_1：[d908: 4. 最佳路徑](https://zerojudge.tw/ShowProblem?problemid=d908) + DFS + [相鄰矩陣表示法(Adjacency Matrix)](http://web.ntnu.edu.tw/~algo/Graph.html#3) + 因為有向圖測資沒有環，可先不加 vis 陣列。 + Q：NA(score:80%)？ A：有些線段會重複，記錄此線段的最大權重。 + Q.. 如果加 2 條邊(E C 10、C B 20) 造成環，會造成什麼結果？ A：DFS 會無窮迴圈 → 增加 vis 陣列記錄走過的點 | ![](https://i.imgur.com/yPYWUSs.png =180x) | A 8 A B 7 A C 1 B D 3 B E 5 C F 2 D F 4 E C 10 C B 20 | | :-------- | -------- | + Q：如果只記錄走過的點，未加15行，答案為何會錯誤？ 22 (A->B->E->C) A：正確答案為 28 (A->C->B->D->F)。未加15行，當 A->B->D->$\cdots$ 走過 B 後，會讓 A->C 無法再走到 B。 ::: ```c= #include <iostream> #include <cstring> using namespace std; int g[26][26]; // 增加 vis 陣列 int dfs(int now) { int sum=0; //從此點往下的路徑總和 for ~ //從此點(now) 往下檢查 26 個字母是否相連 if ~ // 如果 now 有連到 i (而且 i 沒走過) { // i 設為走過 ~ // 從 i 繼續往下走，路徑的權重總和為 now->i 這一段的權重 + 從 i dfs 下去的權重和。取最大值。 // i 取消走過 } return sum; } int main() { char s,u,v; int n,w; while(cin >> s >> n) { memset(g,0,sizeof(g)); // vis 陣列歸零 for(int i=0;i<n;i++) { cin >> u >> v >> 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 */ cout << dfs(s-'A') << endl; // 從 s 開始走 } return 0; } ``` :::info EX_5_2：[d324: 00750 - 8 Queens Chess Problem](https://zerojudge.tw/ShowProblem?problemid=d324) + backtracking + 以一維陣列 row[9] ([1-based indexing](https://xlinux.nist.gov/dads/HTML/oneBasedIndexing.html)) 記錄皇后的座標。陣列索引為皇后的col，值為皇后的row。 | ![](https://i.imgur.com/9bVpKmW.png =180x) | q[1]={1,1}; q[2]={3,2}; q[3]={5,3}; $\vdots$ row[1]=1; row[2]=3; row[3]=5; $\vdots$| | -------- | :--------: | + [皇后衝突的判斷](https://iter01.com/kmw2YoS.html) [![](https://i.imgur.com/JWKOD70.png =63x)](https://i.imgur.com/JWKOD70.png)　[![](https://i.imgur.com/kmw2YoS.png =50x)](https://i.imgur.com/kmw2YoS.png) + [棋盤](https://www.datagenetics.com/blog/august42012/) ::: ```c= #include <iostream> using namespace std ; int qr,qc,row[9],cnt; // index 為皇后的 col，值為 row void print() { if ~ // 符合題目皇后必須放的位子才印出來 { 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) ```c int g[5][5]; // 相鄰矩陣 vector<int> g[5]; // 相鄰串列，vector 裏放相鄰的點 vector<pair<int,int>> g[5] // 以 pair 記錄相鄰的點和邊 ``` + [整數最大值可用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 <bits/stdc++.h> using namespace std; ~ // 宣告陣列 g，idx 為來源點，內容為 vector。vector 可放 pair 記錄目地點和兩點間的相關性值。 bool vis[5005]={0}; // 無向圖，走過要記錄，以免往回走造成無窮迴圈 int q,ans=0; void dfs(int now,int r) // r 為起點到現在的點(now) 的相關性 { if ~ // 起點到現在的點(now) 的相關性至少為 q ans++; for ~ // 對每個連到 now 的節點(nxt) { if ~ // 如果 nxt 沒走過 { ~ // 將 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 } /* 先把範例二的相鄰串列印出來看看 for(int i=1;i<=6;i++) { cout << i << " : "; for ~ cout << "{" << ~ << "," << ~ << "} "; cout << endl; } 1 : {6,4} 2 : {4,10} {3,6} 3 : {6,3} {5,8} {2,6} 4 : {2,10} 5 : {3,8} 6 : {3,3} {1,4} */ vis[vk]=true; dfs(vk,0x3f3f3f3f); cout << ~ << endl; // 答案不是 ans，Why？ return 0; } ``` :::warning [j124: 3. 石窟探險](https://zerojudge.tw/ShowProblem?problemid=j124) + 類似 d908 ::: :::warning [a290: 新手訓練系列 ~ 圖論](https://zerojudge.tw/ShowProblem?problemid=a290) ::: :::warning [TCFSH CIRC Judge d091: P-7-2. 開車蒐集寶物](https://judge.tcirc.tw/ShowProblem?problemid=d091) + 相鄰串列 + 對未看過的點做 DFS，找連通區塊的權重總和。 ::: :::warning [b967: 第 4 題血緣關係](https://zerojudge.tw/ShowProblem?problemid=b967) + max_element + [解題參考](https://sites.google.com/site/zsgititit/zi-xun-neng-li-jian-ding/apcs/10503di4ti-xue-yuan-guan-xi) (farthest of farthest：以任意點(0)為根，找離它最遠的點(v)，再以此點(v)為根，找最大深度) ::: :::warning [f161: 3. 尋寶之旅](https://zerojudge.tw/ShowProblem?problemid=f161) + 在 DFS 過程中，每次走到一個節點，就將該點顏色數量加一。當 DFS 返回父節點時，把該點顏色數減一，以表示回復到沒有走到此點的狀態。 + 在拜訪每個節點時，檢查該點的顏色數量有沒有超過最大值。 + 寶石的顏色號碼不超過10^9^，記錄每一顏色的寶石數用陣列會太大，離散化可以用 [STL map](http://larry850806.github.io/2016/06/06/STL1/#map)。 ::: ## 六、動態規劃(Dynamic Programming、DP) + [動態規劃簡介](https://mropengate.blogspot.com/2015/01/algorithm-ch2-dynamic-programming.html) + [一個問題若能用 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) - 最佳子結構(optimal substructure)：最佳解能夠由子問題的最佳解構成。([分治與貪心法同樣有著這個特性](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-DP#%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83%E5%95%8F%E9%A1%8C%E7%9A%84%E7%89%B9%E6%80%A7)) - 重疊子問題(overlapping subproblem) - 無後效性：子問題的解一但確定，就不會受到更大的問題的求解決策影響。 + 規劃步驟 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=1;i<=n;i++) cin >> p[i]; dp[1]=~; dp[2]=~; for ~ // 計算第3~n天的報酬 ~ // 遞迴關係式 cout << dp[n] << 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://www.796t.com/content/1546179722.html) + 狀態定義 - 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://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/d378) ::: :::warning [a133: 10066 - The Twin Towers](https://zerojudge.tw/ShowProblem?problemid=a133) + [解題參考](https://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/a133-10066---the-twin-towers) ::: :::warning [i402: 4. 內積](https://zerojudge.tw/ShowProblem?problemid=i402) + [解題參考](https://www.youtube.com/watch?v=EvyyRNAnAtE) ::: :::warning [a252: Another LCS](https://zerojudge.tw/ShowProblem?problemid=a252) ::: #### 2_2. [0-1背包問題](https://www.cnblogs.com/lyeeer/p/12771929.html) + 有 n 個物品，每個物品有重量 w 跟價值 v，背包有最大負重，求在物品不可以分割不重複的情況下，背包可以裝的最大價值為何？ - 相對於物品可分割背包問題，在選擇物品時，要麼完整地選擇，要麼不選擇，不可以只拿物品的一部份(物品不可分割)。 - Greedy不行，假設背包負重30kg，會得到190(50+140)，但最大價值為200(60+140)。 |物品|重量|價值|價值/重量比| |:-:|:-:|:-:|:-:| |1 |5 |50 |10| |2 |10 |60 |6 | |3 |20 |140|7 | - 窮舉法會太多狀況，n 個物品，每個物品可以選擇拿或不拿，會有 2^n^ 種可能性要考慮(例如 d637，n=10000)。 + 狀態定義 - dp[i][j]表示只考慮拿前 i 個物品，放入最大負重為 j 的背包時，可以得到的最大價值。 + 狀態轉移方程 - 假設第 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://i.imgur.com/W3NOKXG.png) :::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://blog.csdn.net/weixin_44176696/article/details/105209974)：更新藍色格子只需要紅色格子的資料。 ![](https://i.imgur.com/6IPdibf.png) + 若狀態定義 dp(j) 為背包重量為 j 時的最大價值。 + 對第 i 個物品，考慮不拿或拿，狀態轉移方程為 - dp(j)=max( dp(j), dp(j-w[i])+v[i] ) + Q：[如果如上一題由背包重量小->大更新表格，會有什麼問題？](https://hackmd.io/@3xOSPTI6QMGdj6jgMMe08w/ByfT8JZ9E?type=view#01-%E8%83%8C%E5%8C%85%E5%95%8F%E9%A1%8C) A：若 dp(j−w[i]) 已經拿 i 物品，更新到 dp(j) 時，拿 i 物品也有較大價值，因為 dp(j)=dp(j−w[i])+v[i]，dp[j] 相當於拿了兩次 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) + 測資加強：[e465: 置物櫃分配](http://zerojudge.tw/ShowProblem?problemid=e465) + 以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 | 7 | 4 | 1 | 8 | 3 | + dp 陣列 | s[] | 2 | 7 | 4 | 1 | 8 | 3 | |:------------------:|:---:|:---:|:---:|:---:|:---:|:---:| | LIS 的元素 | 2 | 2 7 | 2 4 | 1 | 2 4 8| 1 3 | | dp 陣列值 (s[]為結尾的LIS 長度) | 1 | | | | | | | 7 可接在 2 後 | 1 | 2 | | | | | | 4 可接在 2 後 | 1 | 2 | 2 | | | | | 1 無法接在任何數後 | 1 | 2 | 2 | 1 | | | | 8 可接在 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(1)](https://emanlaicepsa.github.io/2020/11/30/0-17/) [(2)](https://zrn-code.github.io/2020/07/19/vector/) + [STL max_element](https://shengyu7697.github.io/std-max_element/) + [0-14 常用工具/函式(lower_bound & upper_bound) | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/11/18/0-14/) + 先完成O(n^2^)的方法。(TLE，40%) ::: ```c= // vector 輸入 #include<bits/stdc++.h> using namespace std; int main() { int n; cin >> n; // 方法一 vector<int> v; for(int i=0;i<n;i++) { int t; cin >> t; v.push_back(t); } // 方法二 vector<int> v(n); // vector要先宣告長度 for(int i=0;i<n;i++) cin >> v[i]; // 方法三(C++11) vector<int> v(n); // vector要先宣告長度 for(int& e:v) cin >> e; for(int e:v) 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] (i>j)，但 dp[i]>=dp[j]，表示s[i]的值比較小，但有比較長的 LIS。那麼可以接在 s[j] 後面的一定也可以接在 s[i] 後面。 * 例如上一個例子，2 4 可以取代 2 7，後面如果有 5 可發展出更長的 LIS。所以對之後的數字，2 7 不需要再檢查。 * Q：如果刪除沒有用的子問題結果，會剩下甚麼呢？ A：每一種 LIS 長度只會有一個狀態被留下來$\Rightarrow$ 結尾數值最小的狀態。 | s[] | 2 | 7 | 4 | 1 | 8 | 3 | |:-----:|:---:|:---:|:---:|:---:|:---:|:---:| | LIS 的元素 | 2 | 2 7 | 2 4 | 1 | 2 4 8| 1 3 | | LIS 長度| ~~1~~ | ~~2~~ | ~~2~~ | 1 | 3 | 2 | * Q：增加一個元素 5 ，表格會調整為？ | s[] | 2 | 7 | 4 | 1 | 8 | 3 | 5 | |:-----:|:---:|:---:|:---:|:---:|:---:|:---:|:---:| | LIS 的元素 | 2 | 2 7 | 2 4 | 1 | 2 4 8| 1 3 |1 3 5| | LIS 長度| ~~1~~ | ~~2~~ | ~~2~~ | 1 | ~~3~~ | 2 | 3| - 以陣列 last[L] 記錄 LIS 長度為 L 的最後一個元素(選值最小的，讓後續數字有機會發展出更長的 LIS) + 範例 | s[0] | s[1] | s[2] | s[3] | s[4] | s[5] | s[6] | s[7] | |:----:|:----:|:----:|:----:|:----:|:----:|:----:| :---: | | 2 | 8 | 6 | 7 | 1 | 3 | 4 | 9 | + last 陣列 | LIS 長度 | 1 | 2 | 3 | 4 |概念| |:--------------:|:---:|:---:|:---:|:---:|:---| |最後一個元素|2| | | |s[0]=2 | | |2|8 (2 8)| | |s[1]=8 | | |2|6 (2 6)| | |s[2]=6，26 取代 28| | |2|6|7 (2 6 7)| |s[3]=7，7可加在6後，變成長度3| | |1|6|7| |s[4]=1| | |1|3 (1 3)|7| |s[5]=3，3可以取代6(13->26)， **找到第一個>=3的元素並取代**| | |1|3|4 (1 3 4)| |s[6]=4，134 取代 267， 找到第一個>=4的元素並取代| | |1|3|4|9 (1 3 4 9)|s[7]=9，找不到直接加在最後面| + last 陣列的元素是單調遞增的，要找 s[i] 可以接在誰後面時，不用循序找，可以用二分搜加速。 ```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; } ``` + [如果要印出 LIS 的元素](https://yuihuang.com/dp-lis/) :::info EX_6_7：[f608: 4. 飛黃騰達](https://zerojudge.tw/ShowProblem?problemid=f608) + [最長嚴格遞增子序列(LIS)的變形](https://www.youtube.com/watch?v=vLS3fCeGpeI) - 將所有點依 x 座標排序後，每個點的 y 座標可看成一個整數序列。對任意 i<j 若y[i]<=y[j]，表示 i 點可以走到 j 點，所以每一種走法就是一個非遞減子序列，本題就是要找一個最長的非遞減子序列(Longest Non-Decreasing Subsequence)。 - 範例 | ![](https://i.imgur.com/bmnj6RK.png =235x) $\bf\fbox 1$ 5 $\bf\fbox 1$ $\bf\fbox 3$ 2 $\bf\fbox 4$ $\bf\fbox 4$ 6 3 $\bf\fbox 5$ 4 $\bf\fbox 1$ 5 $\bf\fbox 1$ 3 $\bf\fbox 2$ $\bf\fbox 4$ $\bf\fbox 4$ $\bf\fbox 6$ 3 5 4 $\vdots$| 11 1 1 1 5 2 1 2 3 3 2 3 4 4 4 4 6 5 3 5 5 6 4 Ans：6| | :--------: | :-------- | - 飛黃可以向上或『向右』移動，y 座標相等可以加到非遞減子序列。 LIS 在 last 陣列中尋找第一個『>=』(lower_bound) 的元素，這裏要改為尋找第一個『>』(upper_bound) 的元素(數值相同要保留，不要覆蓋掉)。 ![](https://i.imgur.com/kRdyVp9.png =150x) + 排序時 x 相等則比較 y，可以用 pair 來記錄點，預設即會這樣比較。 + [C++ 17 結構化綁定](https://zh-blog.logan.tw/2019/10/29/cxx-17-structured-binding/) ::: ```c= #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; while(cin >> n) { ~ // 宣告存 pair 的 vector，若以 C++11 寫法讀入，vector要先宣告長度 vector<int> lis; // 存 y 座標的 lis ~ // 讀入果實座標，若以 C++11 寫法，vector要先宣告長度，C++ 17 結構化綁定 ~ /* for(int i=0;i<n;i++) { int x,y; cin >> x >> y; v.push_back({x,y}); } for(auto& e:v) cin >> e.first >> e.second; */ ~ // 先根據 x 座標排序(小->大)，如果 x 座標一樣，再根據 y 座標排序 for ~ // 對每個座標 { ~ // 在目前 lis 陣列中找 > 此點 y 座標的最小值，覆蓋此元素可能產生更長的 LIS if ~ // 如果找不到 ~ // 將此點 y 座標從尾端加入 lis else ~ // 如果找的到，取代這個值 } cout << lis.size() << endl; } return 0; } ``` :::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/TYhEJsX.jpg =500x) :::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 演算法 :::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://tpmso.org/toi/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. 單源最短路徑 Dijkstra 演算法 + Dijkstra 為使用貪婪策略(Greedy)的演算法，可以在加權圖上計算一點到所有點的最短路徑。 + 圖可以是有向或無向，邊的權重不可以是負的。 + [【筆記】Dijkstra algorithm 單點源最短路徑](https://yuihuang.com/dijkstra-algorithm/) + [最短路径查找—Dijkstra算法](https://www.youtube.com/watch?v=JLARzu7coEs) + [Dijkstra 算法寻找有权图中最短路 Finding Shortest Path in Weighted Graphs](https://www.youtube.com/watch?v=uyNJxsH16nc) :::info EX_7_2：[TCFSH CIRC Judge d096: P-7-9. 最短路徑](https://judge.tcirc.tw/ShowProblem?problemid=d096) + 每次都要找最小值，所以使用優先佇列，可以用 STL priority queue 或 set 實作(set 裏的元素會自動小->大排序)。 + [0-20 set | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/07/0-20/) ::: ```c= #include<bits/stdc++.h> using namespace std; int main() { int n,m,u,v,w; vector< pair<int,int> > adj[10005]; // Adjacency list ~ // dist vector 記錄距離起點 0 的距離，初值先預設為無窮大 cin >> n >> m; for(int i=0;i<m;i++) { cin >> u >> v >> w; adj[u].push_back({v,w}); adj[v].push_back({u,w}); } set<pair<int,int>> pq; // 將{dist[點],點} 放入set，set預設會小->大排序 pq.insert({dist[0]=0,0}); while(!pq.empty()) // 每次處理一個點 { auto [t,u]=*pq.begin(); // 找到未處理的點中 d[] 最小的那個點 u pq.erase(pq.begin()); for ~ // 從 u 拓展到其相鄰的點 v { if ~ // 如果透過 u 到 v 的距離，小於原本 v 記錄的距離 { ~ // 將 pq 裏舊的 v 刪除 ~ // 將 v 更新後的資訊加入 pq } } } int maxDist=-1,cnt=0; for(int i=0;i<n;i++) { if(dist[i]==0x3f3f3f3f) cnt++; else if(dist[i]>maxDist) maxDist=dist[i]; } cout << maxDist << endl << cnt << endl; return 0; } ``` :::warning [d793: 00929 - Number Maze](https://zerojudge.tw/ShowProblem?problemid=d793) + 把數字迷宮想成無向圖，每個格子與四個方向的格子相連。 + 以 Dijkstra 演算法求出左上角到右下角的最短距離。 ::: ### 3. 並查集(Disjoint Sets) + [Disjoint Sets 資料結構 : 樹狀儲存](https://web.ntnu.edu.tw/~algo/Set.html#9) :::info EX_7_3：[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。 ::: ### 4. 最小生成樹(Minimun Spanning Tree) + [Kruskal 演算法](https://www.itread01.com/content/1545066724.html)為一個使用貪婪法 (greedy method) 的演算法，一開始為一空樹，每次在不讓圖中含有任何迴路(cycle)下尋找圖中最小權重的邊加入樹中，直到所有點皆在樹中即完成。 + Prim演算法與 Dijkstra 演算法類似，屢次找出不在樹上，離樹最近的點。 :::info EX_7_4：[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 [e810: 2.潛水 (Diving)](https://zerojudge.tw/ShowProblem?problemid=e810) + [題目](https://tpmso.org/toi/wp-content/uploads/question/201911/A2-Diving.pdf) + [解題參考](https://tpmso.org/toi/wp-content/uploads/question/201911/A2-Diving.pptx) ::: :::warning [d909: 公路局長好煩惱！？](https://zerojudge.tw/ShowProblem?problemid=d909) ::: ### 5. 樹 + [演算法筆記 - Tree](http://web.ntnu.edu.tw/~algo/Tree.html) :::info EX_7_5：[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) ::: ### 6. 二分圖（Bipartite graph) + [二分圖判斷](https://www.itread01.com/content/1545440778.html) + [圖論入門———深度優先搜尋實現二分圖判定(dfs染色)](https://www.itread01.com/content/1546276331.html) :::info EX_7_6：[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) ::: ### 7. 拓撲排序(Topological Sort) + [拓撲排序-kahn's algorithm](http://slides.com/sylveon/basic-graph#/5/2) :::info EX_7_7：[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; ::: :::warning [k734. 4. 開啟寶盒](https://zerojudge.tw/ShowProblem?problemid=k734) + [解題參考](https://hackmd.io/@o2sU2kaQTFW6FIkUj2M-xQ/rkL6-NhU2) :::