HackMDtags: 選修
AP325 練習題單
一、遞迴
1.1. 基本觀念與用法
1.2. 實作遞迴定義
- 選每段最接近中點的切割點，會得到最小的切割總成本。
1.3. 以遞迴窮舉暴搜
- 先練習 P-1-9. N-Queen解的個數
二、排序與二分搜
2.1. 排序
- STL set
2.2. 搜尋
- 將原陣列a中的相異元素排序在b陣列中，對於原陣列a中的元素，置換成它在b陣列中的index。
- 在b陣列中找到a[i]可用二分搜加速。
- 或STL map (map 的元素會按 Key 排序)
- 離散化
d024: 例題 P-2-15. 圓環出口 (APCS202007)
- 前綴和(prefix sum)
- 二分搜
- 解題參考
- 因為 qi 不會超過 p 的總和，所以將原序列複製一次再求前綴和，可簡化操作。如果沒有此限制，也只需將 qi 預先 mod p的總和即可。
2.3. 其他相關技巧介紹
快速冪
- x 超過long long，先求 x % p
- 以 string 讀取 x，將每個字元轉成數值的過程，不斷%p。
- 例如 x=123=(1*10+2)10+3，x%p=((((110%p+2)%p)*10)%p+3)%p
模逆元
快速計算費式數列
2.4. 其他例題與習題
d015: 例題 P-2-6. Two-Number problem
- 將A陣列與B陣列分別排序，對A中的每一個元素，在B中以滑動的方式找K-ai。
- 或STL set
d016: 習題 Q-2-7. 互補團隊 (APCS201906)
- 以一個整數表示一個集合，第i個bit設為1代表第i個字母在集合中。兩個互補團隊的數字 xor 後會等於 2m -1。
- 若 a xor b = c 則 a xor c = b
- 只用前綴和，O(n2) 會 TLE。
- set+2分搜尋 O(nlog(n))
d021: 習題 Q-2-12. 最接近的子矩陣和 (108 高中全國賽) (*)
- 只用前綴和會 TLE。
- 利用set儲存已經計算好的矩形區塊和，搜尋會比較快。auto it = st.lower_bound(sum-k);
三、佇列與堆疊
3.1. 基本原理與實作
3.2. 應用例題與習題
堆疊
- 中序式轉後序式
- 以堆疊1記錄運算元(數字)，堆疊2記錄運算子(±*/)。
- 遇到運算元就放入堆疊1。
- 遇到運算子則和堆疊2上端的運算子比較優先權，如果比較小，則堆疊2內的運算子先運算。
- 空的stack執行sk.top()會錯誤
d028: 例題 P-3-4. 最接近的高人 (APCS201902, subtask)
- 維護一個遞減的序列(前->後或後->前)
- 均攤分析(amortized analysis) 經典題。
- for迴圈內有while迴圈，但時間複雜度還是O(n)，不會是O(n2)，因為雖然while可能某次會做很多次的 pop()，但總共只會做 n 次。
d029: 習題 Q-3-5. 帶著板凳排雞排的高人 (APCS201902)
- 最左邊界的無限大高度，初值要超過 2*107
佇列
d030: 例題 P-3-6. 砍樹 (APCS202001)
- 亦有使用堆疊的做法
d036: 習題 Q-3-12. 完美彩帶 (APCS201906)
- 滑動視窗，使用queue或deque，模擬區間由左向右滑，左邊出去一個顏色(front pop)，右邊進來一個顏色(back push)。比對queue內相異顏色數量是不是等於M。
滑動視窗(Sliding window)
- multiset
- 亦可用deque會更快
- 先對 x 座標排序。
- 宣告 deque<int> max_q,min_q; max_q 記錄 L 區間 y 最大值的索引，min_q 記錄 L 區間 y 最小值的索引。
- 當元素要從窗戶右端放入max_q時，先從前端移除超過L的點(離開窗戶)，再從後端移除所有小於它的點(這些點對找最大值沒用，max_q為遞減序列)，然後push_back至max_q內。
- min_q同理從後端移除所有大於它的點。
- 以迴圈讓窗戶的右端逐步往右推，處理完畢後 max_q.front()為窗戶內的最大值的點，min_q.front()為最小值的點。
d034: 例題 P-3-10. 全彩彩帶 (需離散化或字典) (@@)
- 顏色編號可能達到10億，map<int, int>記錄該顏色的數量(key表顏色，value表數量)。(離散化觀念)
- 因為順序不重要，可用unordered_map查詢會更快。
- 以queue儲存最長相異色彩帶，往右的顏色如果重複，將queue中此顏色之前的顏色刪除。
四、貪心演算法與掃瞄線演算法
4.1. 基本原理
4.2. 例題與習題
4.2.1. 單欄位資料排序
- STL sort
- minimum completion time 經典題
4.2.2. 結構資料排序
d045: 例題 P-4-4. 幾場華山論劍(activity selection)
- activity selection problem 經典題
d046: 例題 P-4-5. 嵩山磨劍坊的問題(加權最小完成時間)
- 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)
d047: Q-4-6. 少林寺的自動寄物櫃(APCS201710)
- 假設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處理動態資料(*)
d048: P-4-7. 岳不群的併派問題(Two-way merge) (*)
- priority_queue< LL, deque<LL>, greater<LL> > pq;
- 依輸入序，將其時間與優先佇列中最小值相加後，再放入優先佇列。
4.2.4. 外掛二分搜
- 每次檢測的能量可能 < p[i]。
4.2.5. 掃描線演算法sweep-line
- 配合前綴和，可以做到O(n2)，但還是會TLE。
- 拋棄繼承
- 點的x由小到大序列時，極大點的y是嚴格遞減的。
4.3. 其他習題
- Q-4-8 變化題
- 依工作所需時排序，若相同再依完工時間排序。
- 依完工時間排序。
- 以櫃台數量2分搜，檢查是否可以在時間 D 內完成。
- 檢查方法為假設開 c 個櫃台，使用priority_queue，取佇列中最小值相加後再放入佇列，計算完成時間。
- 先依開始時間排序。
- 以 priority_queue 記錄處理過的時段，在 pq 內優先權的定義為結束時間大->小，移除此時間開始前的時段人數。
五、分治演算法
5.1. 基本原理
5.2. 例題與習題
- ZeroJudge Merge Sort
- 以最小高為中間的切割點，如果每次的最低點都在邊緣，例如輸入高度是遞增或遞減，時間複雜度會高到O(n2)。
六、動態規劃
6.1. 基本原理
6.1.1. 基本思維與步驟
6.1.2. 狀態轉移
6.1.3. 分類與複雜度
6.1.4. Top-down memoization
6.2. 例題與習題
6.2.1. 1D0D
- 設dp[i]是前i個點的最小監控成本(最後一點選在i)。
- dp[i] = c[i] + min(dp[i-1], dp[i-2], dp[i-3]) for i>2
- 每個關卡通過的成本只跟上一關有關(跟更早的無關)，設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]) );
6.2.2. 2D0D
- LCS(Longest Common Subsequence，最長共同子序列)，序列分析的重要問題
- 0/1-knapsack 經典題。
d075: Q-6-10. 置物櫃出租 (APCS201810)
- 0/1-knapsack
- 價值和容量相等。
- dp表格在王老不夠容量的那欄，其值(最大可退的容量)可能還不夠，往後找第1個超過的值。
6.2.3. 1D1D
- P-6-2 的推廣
- 設dp[i] 是前 i 天可以獲得的最大報酬，dp[i]=max(dp[i-k-1]+當天報酬, dp[i-1])。
- dp前k天的初值為當天之前報酬的最大值。
- P-6-3 的推廣型
d085: Q-6-14. K 次買賣 (106 高中全國賽 subtask)
- P-4-12 的推廣型
- LIS(longest Increasing subsequence，最長遞增子序列)，1D1D經典題
- 演算法筆記-LIS
- P-4-4 加權版本
- weighted activity selection problem 經典題
6.2.4. 2D1D與其他
6.3. 進階題(*)
七、基本圖論演算法
7.1. 基本觀念與名詞
7.2. 資料結構與基本演算法
7.2.1. 資料結構
7.2.2. BFS
7.2.3. DFS
7.2.4. DAG與topological sort
7.4. 補充教材(*)
7.4.1. Dijkstra演算法
7.4.2. 併查集(Union and Find)
7.4.3. 最小生成樹
八、樹上演算法
8.1. 基本觀念與名詞
8.2. 樹的儲存與基本演算法
8.2.1. 儲存樹的資料結構
8.2.2. DFS
- 因為樹沒有環，樹上找距離也可以用DFS(遞迴)，程式會更簡潔。
d025: 例題 P-3-1. 樹的高度與根 (bottom-up) (APCS201710)
- 子節點因數量不定，可用vector諸存
vector<int> child[100000]; - vector二維陣列1
- vector二維陣列2
- memset
d106: P-8-7. 寶石的顏色 (108 全國高中賽)
- 寶石的顏色號碼不超過109，記錄每一顏色的寶石數用陣列會太大，離散化可以用 STL map。
8.2.3. BFS
8.2.4. 由下而上的走訪
- 計算每個節點孩子的數量，找子節點數量>=n/2者。
- 需要O(n)的算法，參考 P-8-3 計算median到所有點的距離和的方法。
8.3. 例題與習題
二元樹
d105: P-8-5. 自動分裝 (APCS202002)
- 二元樹
- 解題參考 (一邊走就要一邊調整節點重點才不會TLE)
樹的最大獨立集
- greedy
- 最大權重獨立集
- DP
