###### tags: `選修` # AP325 練習題單 + [AP325講義(中正大學 吳邦一教授)](https://drive.google.com/drive/mobile/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m?usp=sharing) + [APCS實作題檢測(Facebook)](https://www.facebook.com/groups/359446638362710) + [TCFSH CIRC Judge(例題與習題)](https://judge.tcirc.tw/) <br/> ## 一、遞迴 ### 1.1. 基本觀念與用法 ### 1.2. 實作遞迴定義 :::info [d001: 例題 P-1-1. 合成函數(1)](https://judge.tcirc.tw/ShowProblem?problemid=d001) ::: :::warning [d002: 習題 Q-1-2. 合成函數(2) (APCS201902)](https://judge.tcirc.tw/ShowProblem?problemid=d002) + [題目參考](https://zerojudge.tw/ShowProblem?problemid=f640) ::: :::info [d003: 例題 P-1-3. 棍子中點切割](https://judge.tcirc.tw/ShowProblem?problemid=d003) + 選每段最接近中點的切割點,會得到最小的切割總成本。 ::: :::warning [d004: 習題 Q-1-4. 支點切割 (APCS201802) (@@)](https://judge.tcirc.tw/ShowProblem?problemid=d004) + [題目參考](https://zerojudge.tw/ShowProblem?problemid=f638) ::: :::warning [d005: 習題 Q-1-5. 二維黑白影像編碼 (APCS201810)](https://judge.tcirc.tw/ShowProblem?problemid=d005) + [解題參考](https://yuihuang.com/nuts-apcs1071027-3/) ::: ### 1.3. 以遞迴窮舉暴搜 :::info [d006: 例題 P-1-7. 子集合乘積](https://judge.tcirc.tw/ShowProblem?problemid=d006) ::: :::warning [d007: 習題 Q-1-8. 子集合的和 (APCS201810, subtask)](https://judge.tcirc.tw/ShowProblem?problemid=d007) ::: :::warning [d008: 習題 Q-1-10. 最多得分的皇后](https://judge.tcirc.tw/ShowProblem?problemid=d008) + 先練習 P-1-9. N-Queen解的個數 ::: <br/> ## 二、排序與二分搜 ### 2.1. 排序 :::info [d010: 例題 P-2-1. 不同的數—排序](https://judge.tcirc.tw/ShowProblem?problemid=d010) + STL set ::: ### 2.2. 搜尋 :::info [d011: 例題 P-2-2. 離散化 – sort](https://judge.tcirc.tw/ShowProblem?problemid=d011) + 將原陣列a中的相異元素排序在b陣列中,對於原陣列a中的元素,置換成它在b陣列中的index。 + 在b陣列中找到a[i]可用二分搜加速。 + 或STL map (map 的元素會按 Key 排序) + [離散化](https://meteor.today/article/IeFmpe) ::: :::warning d024: 例題 P-2-15. 圓環出口 (APCS202007) + 前綴和(prefix sum) + 二分搜 + [解題參考](https://hackmd.io/@emanlaicepsa/APCS202007?fbclid=IwAR167sM5rLEjyCItz0QxNcXz2MjtuWMiH0-9dPHPfJvQWENkfJ0tSR5TVZo#p3) + 因為 qi 不會超過 p 的總和,所以將原序列複製一次再求前綴和,可簡化操作。如果沒有此限制,也只需將 qi 預先 mod p的總和即可。 ::: ### 2.3. 其他相關技巧介紹 #### 快速冪 :::info [d012: 例題 P-2-3. 快速冪](https://judge.tcirc.tw/ShowProblem?problemid=d012) + [快速冪](https://meteor.today/article/PL8R-c) ::: #### 模逆元 :::warning [d017: 習題 Q-2-8. 模逆元 (*)](https://judge.tcirc.tw/ShowProblem?problemid=d017) + [費馬小定理](https://www.youtube.com/watch?v=SyK3IXPITco) + 若 P 為質數,對任意正整數 a,(a^P-2^ % P) 是 a 在[1, P-1]區間的唯一乘法反元素。 + [數學上的模逆元](https://meteor.today/article/5hal9d)、[程式設計上的模逆元](https://meteor.today/article/TKXPid) ::: #### 快速計算費式數列 :::warning [d014: 習題 Q-2-5. 快速計算費式數列第 n 項](https://judge.tcirc.tw/ShowProblem?problemid=d014) + [費氏數列 - 矩陣推導篇](https://puremathcrush.blogspot.tw/2015/09/blog-post.html) + [矩陣快速冪加速實作](http://acm.cs.nthu.edu.tw/problem/10322/) + [程式設計上的矩陣快速冪](https://meteor.today/article/GEzRKd) ::: ### 2.4. 其他例題與習題 :::info [d015: 例題 P-2-6. Two-Number problem](https://judge.tcirc.tw/ShowProblem?problemid=d015) + 將A陣列與B陣列分別排序,對A中的每一個元素,在B中以滑動的方式找K-a~i~。 + 或STL set ::: :::warning [d016: 習題 Q-2-7. 互補團隊 (APCS201906)](https://judge.tcirc.tw/ShowProblem?problemid=d016) + 以一個整數表示一個集合,第i個bit設為1代表第i個字母在集合中。兩個互補團隊的數字 xor 後會等於 2^m^ -1。 + 若 a xor b = c 則 a xor c = b ::: :::info [d020: 例題 P-2-11. 最接近的區間和 (*)](https://judge.tcirc.tw/ShowProblem?problemid=d020) + 只用前綴和,O(n^2^) 會 TLE。 + set+2分搜尋 O(nlog(n)) ::: :::warning [d021: 習題 Q-2-12. 最接近的子矩陣和 (108 高中全國賽) (*)](https://judge.tcirc.tw/ShowProblem?problemid=d021) + 只用前綴和會 TLE。 ::: <br/> ## 三、佇列與堆疊 ### 3.1. 基本原理與實作 ### 3.2. 應用例題與習題 #### 堆疊 :::info [d026: 例題 P-3-2. 括弧配對](https://judge.tcirc.tw/ShowProblem?problemid=d026) ::: :::warning [d027: 習題 Q-3-3. 加減乘除](https://judge.tcirc.tw/ShowProblem?problemid=d027) + [中序式轉後序式](https://market.cloud.edu.tw/content/senior/computer/ks_ks/et/datastruct/compute/compute.htm) + 以堆疊1記錄運算元(數字),堆疊2記錄運算子(+-*/)。 - 遇到運算元就放入堆疊1。 - 遇到運算子則和堆疊2上端的運算子比較優先權,如果比較小,則堆疊2內的運算子先運算。 + 空的stack執行sk.top()會錯誤 ::: :::info [d028: 例題 P-3-4. 最接近的高人 (APCS201902, subtask)](https://judge.tcirc.tw/ShowProblem?problemid=d028) + 維護一個遞減的序列(前->後或後->前) + 均攤分析(amortized analysis) 經典題。 ::: :::warning [d029: 習題 Q-3-5. 帶著板凳排雞排的高人 (APCS201902)](https://judge.tcirc.tw/ShowProblem?problemid=d029) + 最左邊界的無限大高度,初值要超過 2*10^7^ ::: #### 佇列 + [C++ queue 和 deque的区别](https://blog.csdn.net/qq_25800311/article/details/89060069) :::info [d030: 例題 P-3-6. 砍樹 (APCS202001)](https://judge.tcirc.tw/ShowProblem?problemid=d030) + 亦有使用堆疊的做法 ::: :::warning [d036: 習題 Q-3-12. 完美彩帶 (APCS201906)](https://judge.tcirc.tw/ShowProblem?problemid=d036) + 滑動視窗,使用queue或deque,模擬區間由左向右滑,左邊出去一個顏色(front pop),右邊進來一個顏色(back push)。比對queue內相異顏色數量是不是等於M。 ::: #### 滑動視窗(Sliding window) :::info [d031: 例題 P-3-7. 正整數序列之最接近的區間和](https://judge.tcirc.tw/ShowProblem?problemid=d031) ::: :::info [d032: 例題 P-3-8. 固定長度區間的最大區段差](https://judge.tcirc.tw/ShowProblem?problemid=d032) + multiset + 亦可用deque會更快 ::: :::warning [d037: 習題Q-3-13. X差值範圍內的最大Y差值](https://judge.tcirc.tw/ShowProblem?problemid=d037) ::: :::info [d033: 例題 P-3-9. 最多色彩帶](https://judge.tcirc.tw/ShowProblem?problemid=d033) ::: :::info [d034: 例題 P-3-10. 全彩彩帶 (需離散化或字典) (@@)](https://judge.tcirc.tw/ShowProblem?problemid=d034) + 顏色編號可能達到10億,map<int, int>記錄該顏色的數量(key表顏色,value表數量)。(離散化觀念) + 因為順序不重要,可用unordered_map查詢會更快。 ::: :::warning [d035: 習題 Q-3-11. 最長的相異色彩帶](https://judge.tcirc.tw/ShowProblem?problemid=d035) + 以queue儲存最長相異色彩帶,往右的顏色如果重複,將queue中此顏色之前的顏色刪除。 ::: <br/> ## 四、貪心演算法與掃瞄線演算法 ### 4.1. 基本原理 :::info [d042: 例題 P-4-1. 少林寺的代幣](https://judge.tcirc.tw/ShowProblem?problemid=d042) ::: ### 4.2. 例題與習題 #### 4.2.1. 單欄位資料排序 :::info [d043: 例題 P-4-2. 笑傲江湖之三戰](https://judge.tcirc.tw/ShowProblem?problemid=d043) + STL sort ::: :::info [d044: 例題 P-4-3. 十年磨一劍(最少完成時間)](https://judge.tcirc.tw/ShowProblem?problemid=d044) + minimum completion time 經典題 ::: #### 4.2.2. 結構資料排序 :::info [d045: 例題 P-4-4. 幾場華山論劍(activity selection)](https://judge.tcirc.tw/ShowProblem?problemid=d045) + activity selection problem 經典題 ::: :::info [d046: 例題 P-4-5. 嵩山磨劍坊的問題(加權最小完成時間)](https://judge.tcirc.tw/ShowProblem?problemid=d045) + t/w 值小的排在前面, + 假設磨a,b之前劍所需的時間為x,則之前的順序,不會影響(a,b)或(b,a)的扣款總額的計算,所以只要考慮a,b順序即可。 - (a,b)-> [x+t(a)]*w(a) + [x+t(a)+t(b)]*w(b) = x(w(a)+w(b)) + t(a)*w(a) + t(b)*w(b) + t(a)*w(b) - (b,a)-> [x+t(b)]*w(b) + [x+t(a)+t(b)]*w(a) = x(w(a)+w(b)) + t(a)*w(a) + t(b)*w(b) + t(b)*w(a) - 依兩兩劍(a,b)完成時間*重要性的值排序(a.t * b.w < b.t * a.w) ::: :::warning [d047: Q-4-6. 少林寺的自動寄物櫃(APCS201710)](https://judge.tcirc.tw/ShowProblem?problemid=d047) + 假設a,b其上物品的重量為x,則這些物品的順序,不會影響(a,b)或(b,a)消耗的能量的計算,所以只要考慮a,b順序即可。 - (a,b)-> x*f(a) + (x+w(a))*f(b) = x(f(a)+f(b)) + w(a)*f(b) - (b,a)-> x*f(b) + (x+w(b))*f(a) = x(f(a)+f(b)) + w(b)*f(a) - 依兩兩物品(a,b) 其上重量*頻率的值排序(a.w * b.f < b.w * a.f) ::: #### 4.2.3. 以PQ處理動態資料(*) :::info [d048: P-4-7. 岳不群的併派問題(Two-way merge) (*)](https://judge.tcirc.tw/ShowProblem?problemid=d048) + priority_queue< LL, deque<LL>, greater<LL> > pq; ::: :::warning [d053: Q-4-8. 先到先服務 (*)](https://judge.tcirc.tw/ShowProblem?problemid=d053) + 依輸入序,將其時間與優先佇列中最小值相加後,再放入優先佇列。 ::: #### 4.2.4. 外掛二分搜 :::info [d049: P-4-9. 基地台 (APCS201703)](https://judge.tcirc.tw/ShowProblem?problemid=d049) ::: :::warning [d054: Q-4-10. 恢復能量的白雲熊膽丸](https://judge.tcirc.tw/ShowProblem?problemid=d054) + 每次檢測的能量可能 < p[i]。 ::: #### 4.2.5. 掃描線演算法sweep-line :::info [d050: P-4-11. 線段聯集 (APCS 201603)](https://judge.tcirc.tw/ShowProblem?problemid=d050) ::: :::warning [d051: P-4-12. 一次買賣](https://judge.tcirc.tw/ShowProblem?problemid=d051) ::: :::warning [d052: P-4-13. 最大連續子陣列](https://judge.tcirc.tw/ShowProblem?problemid=d052) + 配合前綴和,可以做到O(n^2^),但還是會TLE。 + 拋棄繼承 ::: :::info [d055: P-4-14. 控制點(2D-max)](https://judge.tcirc.tw/ShowProblem?problemid=d055) + 點的x由小到大序列時,極大點的y是嚴格遞減的。 ::: :::warning [d056: P-4-15. 最靠近的一對(closest pair) (@@))](https://judge.tcirc.tw/ShowProblem?problemid=d056) + [D&C (1)](http://web.ntnu.edu.tw/~algo/Point2.html#3)、[(2)](https://oi-wiki.org/geometry/nearest-points/)、[(3)](https://kknews.cc/code/3aa48ko.amp) ::: ### 4.3. 其他習題 :::warning [d057: Q-4-16. 賺錢與罰款](https://judge.tcirc.tw/ShowProblem?problemid=d057) + Q-4-8 變化題 ::: :::warning [d058: Q-4-17. 死線高手](https://judge.tcirc.tw/ShowProblem?problemid=d058) ::: :::warning [d059: Q-4-18. 少林寺的櫃姐 (@@)(*)](https://judge.tcirc.tw/ShowProblem?problemid=d059) ::: :::warning [d060: Q-4-19. 五嶽盟主的會議場所](https://judge.tcirc.tw/ShowProblem?problemid=d060) ::: :::warning [d061: Q-4-20. 監看華山練功場](https://judge.tcirc.tw/ShowProblem?problemid=d061) ::: <br/> ## 五、分治演算法 ### 5.1. 基本原理 ### 5.2. 例題與習題 :::info [d064: P-5-4. 反序數量 (APCS201806)](https://judge.tcirc.tw/ShowProblem?problemid=d064) ::: :::warning [a233: 排序法~~~ 挑戰極限](https://zerojudge.tw/ShowProblem?problemid=a233) + ZeroJudge Merge Sort ::: :::info [d065: P-5-7. 大樓外牆廣告](https://judge.tcirc.tw/ShowProblem?problemid=d065) + 以最小高為中間的切割點,如果每次的最低點都在邊緣,例如輸入高度是遞增或遞減,時間複雜度會高到O(n^2^)。 ::: <br/> ## 六、動態規劃 ### 6.1. 基本原理 #### 6.1.1. 基本思維與步驟 #### 6.1.2. 狀態轉移 #### 6.1.3. 分類與複雜度 #### 6.1.4. Top-down memoization ### 6.2. 例題與習題 #### 6.2.1. 1D0D :::info [d066: P-6-1. 小朋友上樓梯最小成本](https://judge.tcirc.tw/ShowProblem?problemid=d066) ::: :::info [d067: P-6-2. 不連續的表演酬勞](https://judge.tcirc.tw/ShowProblem?problemid=d067) ::: :::info [d068: P-6-3. 最小監控鄰居的成本](https://judge.tcirc.tw/ShowProblem?problemid=d068) + 設dp[i]是前i個點的最小監控成本(最後一點選在i)。 + dp[i] = c[i] + min(dp[i-1], dp[i-2], dp[i-3]) for i>2 ::: :::warning [d072: Q-6-4. 闖關二選一](https://judge.tcirc.tw/ShowProblem?problemid=d072) + 每個關卡通過的成本只跟上一關有關(跟更早的無關),設dp[i][j]為第i關、第j種狀態的最低成本(i<=n,j=0或1)。 + dp[i][j] = min( dp[i-1][0]+abs(pwd[i-1][0]-pwd[i][j]), dp[i-1][1]+abs(pwd[i-1][1]-pwd[i][j]) ); ::: :::warning [d073: Q-6-5. 二維最大子矩陣](https://judge.tcirc.tw/ShowProblem?problemid=d073) + [O(n4)](http://chchwy.blogspot.tw/2008/11/acm108-maximum-sum-ac.html) + [O(n3)](http://hanting1225.blogspot.tw/2015/11/uva-108-maximum-sum.html) ::: #### 6.2.2. 2D0D :::info [d069: P-6-6. 方格棋盤路線](https://judge.tcirc.tw/ShowProblem?problemid=d069) ::: :::info [d070: P-6-7. LCS](https://judge.tcirc.tw/ShowProblem?problemid=d070) + LCS(Longest Common Subsequence,最長共同子序列),序列分析的重要問題 ::: :::warning [d074: Q-6-8. Local alignment](https://judge.tcirc.tw/ShowProblem?problemid=d074) + LCS ::: :::info [d071: P-6-9. 大賣場免費大搬家](https://judge.tcirc.tw/ShowProblem?problemid=d071) + 0/1-knapsack 經典題。 ::: :::warning [d075: Q-6-10. 置物櫃出租 (APCS201810)](https://judge.tcirc.tw/ShowProblem?problemid=d075) + 0/1-knapsack + 價值和容量相等。 + dp表格在王老不夠容量的那欄,其值(最大可退的容量)可能還不夠,往後找第1個超過的值。 ::: #### 6.2.3. 1D1D :::info [d076: P-6-11. Catalan number](https://judge.tcirc.tw/ShowProblem?problemid=d076) ::: :::warning [d084: Q-6-12. 楊鐵心做 1 休 K](https://judge.tcirc.tw/ShowProblem?problemid=d084) + P-6-2 的推廣 ::: :::warning [d077: P-6-13. 周伯通的基地台 (@@)](https://judge.tcirc.tw/ShowProblem?problemid=d077) + P-6-3 的推廣型 ::: :::warning [d085: Q-6-14. K 次買賣 (106 高中全國賽 subtask)](https://judge.tcirc.tw/ShowProblem?problemid=d085) + P-4-12 的推廣型 ::: :::info [d078: P-6-15. 一覽衆山小](https://judge.tcirc.tw/ShowProblem?problemid=d078) + LIS(longest Increasing subsequence,最長遞增子序列),1D1D經典題 + [演算法筆記-LIS](http://web.ntnu.edu.tw/~algo/Subsequence.html) ::: :::warning P-6-16. 山寨華山論劍 + P-4-4 加權版本 + weighted activity selection problem 經典題 ::: #### 6.2.4. 2D1D與其他 :::info [d079: P-6-17. 切棍子](https://judge.tcirc.tw/ShowProblem?problemid=d079) ::: :::warning [d086: Q-6-18. 矩陣乘法鏈](https://judge.tcirc.tw/ShowProblem?problemid=d086) ::: ### 6.3. 進階題(*) <br/> ## 七、基本圖論演算法 ### 7.1. 基本觀念與名詞 ### 7.2. 資料結構與基本演算法 #### 7.2.1. 資料結構 #### 7.2.2. BFS :::info [d090: P-7-1. 探索距離](https://judge.tcirc.tw/ShowProblem?problemid=d090) ::: :::warning [d093: P-7-4. 方格棋盤的最少轉彎數路線](https://judge.tcirc.tw/ShowProblem?problemid=d093) ::: :::warning [d094: Q-7-5. 闖關路線 (APCS201910)](https://judge.tcirc.tw/ShowProblem?problemid=d094) + [解題參考](https://yuihuang.com/nuts-apcs1081026-3/) ::: #### 7.2.3. DFS :::info [d091: P-7-2. 開車蒐集寶物](https://judge.tcirc.tw/ShowProblem?problemid=d091) ::: :::warning [d092: P-7-3. 機器人走棋盤 (APCS 201906)](https://judge.tcirc.tw/ShowProblem?problemid=d092) + DFS ::: :::warning [d100: Q-7-8. 小寶的著色問題](https://judge.tcirc.tw/ShowProblem?problemid=d100) + DFS 或 BFS + [二分圖判斷(1)](https://www.itread01.com/content/1545440778.html)、[(2)](https://www.itread01.com/content/1536499328.html) + 圖可能不連通,每個點都要遍歷 + C++ IO加速 ::: #### 7.2.4. DAG與topological sort :::warning [d095: P-7-6. DAG 的最長與最短路徑](https://judge.tcirc.tw/ShowProblem?problemid=d095) ::: :::warning [d099: Q-7-7. AOV 最早完工時間](https://judge.tcirc.tw/ShowProblem?problemid=d099) ::: ### 7.4. 補充教材(*) #### 7.4.1. Dijkstra演算法 #### 7.4.2. 併查集(Union and Find) #### 7.4.3. 最小生成樹 <br/> ## 八、樹上演算法 ### 8.1. 基本觀念與名詞 ### 8.2. 樹的儲存與基本演算法 #### 8.2.1. 儲存樹的資料結構 #### 8.2.2. DFS :::info [d102: P-8-1. 樹上的推銷員](https://judge.tcirc.tw/ShowProblem?problemid=d102) ::: :::warning [d103: P-8-2. 物流派送系統](https://judge.tcirc.tw/ShowProblem?problemid=d103) + 因為樹沒有環,樹上找距離也可以用DFS(遞迴),程式會更簡潔。 ::: :::info [d025: 例題 P-3-1. 樹的高度與根 (bottom-up) (APCS201710)](https://judge.tcirc.tw/ShowProblem?problemid=d025) + 子節點因數量不定,可用vector諸存 vector<int> child[100000]; + [vector二維陣列1](https://ramihaha.tw/c-program-container-vector-array-linklist/) + [vector二維陣列2](http://f74461036.pixnet.net/blog/post/274951462-c%2b%2b-vector二維陣列) + memset ::: :::warning [d106: P-8-7. 寶石的顏色 (108 全國高中賽)](https://judge.tcirc.tw/ShowProblem?problemid=d106) + 寶石的顏色號碼不超過10^9^,記錄每一顏色的寶石數用陣列會太大,離散化可以用 [STL map](http://larry850806.github.io/2016/06/06/STL1/#map)。 ::: :::warning [d111: P-8-14. 血緣關係 (APCS201603)](https://judge.tcirc.tw/ShowProblem?problemid=d025) + 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) ::: #### 8.2.3. BFS #### 8.2.4. 由下而上的走訪 :::warning [d104: P-8-3. 購物中心選位置](https://judge.tcirc.tw/ShowProblem?problemid=d104) + 計算每個節點孩子的數量,找子節點數量>=n/2者。 ::: :::warning [d108: Q-8-6. 樹狀圖的距離總和](https://judge.tcirc.tw/ShowProblem?problemid=d108) + 需要O(n)的算法,參考 P-8-3 計算median到所有點的距離和的方法。 ::: ### 8.3. 例題與習題 #### 二元樹 :::warning [d105: P-8-5. 自動分裝 (APCS202002)](https://judge.tcirc.tw/ShowProblem?problemid=d105) + 二元樹 + [解題參考](https://yuihuang.com/nuts-apcs1090105-4/) (一邊走就要一邊調整節點重點才不會TLE) ::: #### 樹的最大獨立集 :::warning [d107: P-8-8. 樹的最大獨立集](https://judge.tcirc.tw/ShowProblem?problemid=d107) + greedy ::: :::warning [d109: P-8-11. 公司派對 (NCPC)](https://judge.tcirc.tw/ShowProblem?problemid=d109) + 最大權重獨立集 + DP :::