---
# System prepended metadata

title: Algo 題單
tags: [Algo, 考研]

---

:::info
📢 **README**
- 本題單的目的是涵蓋大學演算法課程內容，主要會以 CLRS 作為參考，另佐以各校演算法課程的補充內容。
- 若無特別標註，第一題為和課程內容最為相近的原題，隨後是一些變形題，隱藏的額外題目部分為進階題目，但使用該主題內的知識與技巧便可解出。
- 目前僅 DP 部分較為完整，其餘隨緣更新。
:::

:::warning
📌 除了 LeetCode 的題目外，都可以註冊帳號號在 vjudge 上提交，並可以在 vjudge 上透過搜尋題號和我的帳號 `usaya` 找到我的提交紀錄，但若需要在 vjudge 上提交 Luogu 題目，則需要綁定自己的帳號。
:::

[ToC]

---

## 資料結構 Data Structures

### Basic

- [LC 225\. Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/)
- [LC 232\. Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/)

### Queue

:::spoiler 額外題目
- [ABC389C - Snake Queue](https://vjudge.net/problem/AtCoder-abc389_c)
:::

### Deque

### Heap

- [LC 703\. Kth Largest Element in a Stream](https://leetcode.com/problems/kth-largest-element-in-a-stream/) `[112台大]`
    經典題。
- [LC 295\. Find Median from Data Stream](https://leetcode.com/problems/find-median-from-data-stream/) `[112台大]`
    經典題。注意是 Data Stream。

:::spoiler 額外題目
- [ABC376E - Max × Sum](https://atcoder.jp/contests/abc376/tasks/abc376_e)
    :::spoiler 💡Hint
    排序後，枚舉右端點的 A ，並維護左端點最小的 K 個 B 的和
    :::
:::

### Ch19. Disjoint Sets

- [LC 684. Redundant Connection](https://leetcode.com/problems/redundant-connection/)
- [UVA-793 Network Connections](https://vjudge.net/problem/UVA-793)

:::spoiler 額外題目
- [1631. Path With Minimum Effort](https://leetcode.com/problems/path-with-minimum-effort/) `[107 台大]`
    本題也有最短路、二分答案求最大化最小值做法。
    :::spoiler 💡Hint
    將每條邊排序後，將 w 從小到大排序後，依次將每條邊的兩個端點 u, v 連通，直到起點和終點在一個連通分量中結束。
    :::
- [ABC380E - 1D Bucket Tool](https://vjudge.net/problem/AtCoder-abc380_e)
    :::spoiler 💡Hint
    - 在一般的 Disjoint Set 外額外維護每個 conneted component 的顏色以及每個顏色的數量，供操作 2 使用。
    - 但合併時改成依照每個 component 的左端點合併，即 $x$ 所屬區間的左端點為 $f_x = find(x)$，由於 component 是連續的區間，可以得右端點為 $f_x + sz[fx] - 1$。
    - 故更改顏色後檢查 $f_x - 1$ 和 $f_x + sz[f_x]$ 是否需要和 $f_x$ 合併即可。由於先合併 $f_x - 1$ 可能會導致 $f_x$ 改變，因此需要重新取一次 $f_x$ 或 先合併右再合併左。

    📗 [解題紀錄](https://gdst.dev/posts/ATC_ABC380/#%F0%9F%94%97-E-1D-Bucket-Tool-abc380-E)
    :::
:::

### Trie

> NCKU DS

:::danger
📌 今年成大資料結構更換授課老師，出題老師是否更換尚且未知，請自行衡量是否需要準備舊老師的授課內容。
:::

- [LC 208\. Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/)


:::spoiler 額外題目
- [Luogu P1481 魔族密码](https://www.luogu.com.cn/problem/P1481)
    :::spoiler 💡Hint
    維護字典樹上該條路徑上出現的單字數量即可。
    :::
- [ABC377G - Edit to Match](https://vjudge.net/problem/AtCoder-abc377_g)
    :::spoiler 💡Hint
    在 Trie 中維護每個節點往下走到最近的單字結尾的距離，則在查詢時，對於 $S_k$ 的每個位置 $i$，只需要將目前位置需要的刪除數量 $n - 1 - i$ 與前述維護的距離相加即可。
    :::
:::

## 分治法 Divide and Conquer

### Tower of Hanoi

> NTU ADA

- [CSES-2165 Tower of Hanoi](https://vjudge.net/problem/CSES-2165)
- [Luogu P1096 Hanoi 双塔问题](https://www.luogu.com.cn/problem/P1096)
    圓盤的數量為 $2n$，但這題的難點其實在高精度上，只想推公式的話直接用 Python 提交就好
- [UVA-10254 The Priest Mathematician](https://vjudge.net/problem/UVA-10254)
    增加一個中間柱，可以寫出遞迴式後觀察規律，同樣有高精度的要求，只想推公式的話同樣可以使用 Python 提交就好

### Closest Pair Problem

> NTU ADA, NYCU Algorithm

- [UVA-10245 The Closest Pair Problem](https://vjudge.net/problem/UVA-10245)

### Maximum Subarray Sum

> NTU ADA, NCKU Algorithm

- [LC 53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/) `[113 中興]` `[107 中央]`
  - 教科書和課程中介紹的都是 combine 需要 $O(n)$ 的解法，總時間複雜度為 $O(n \log n)$，但其實透過維護其他性質，combine 可以做到 $O(1)$，總時間複雜度為 $O(n)$。
  - 另外本題也有前綴和和動態規劃解法。📗 [解題紀錄](https://gdst.dev/posts/LC-53/)

## 貪心/貪婪 Greedy

### Activity Selection Problem

> NTU ADA, NYCU Algo

- [LC 646. Maximum Length of Pair Chain](https://leetcode.com/problems/maximum-length-of-pair-chain/)
- [LC 435. Non-overlapping Intervals](https://leetcode.com/problems/non-overlapping-intervals/)
- [LC 452. Minimum Number of Arrows to Burst Balloons](https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/)

### Breakpoint Selection Problem

:::warning
🧩 暫時找不到比較貼近的題目，這裡放的是也是加油的另一種貪心問題。(反悔貪心)
:::

- [LC 871\. Minimum Number of Refueling Stops](https://leetcode.com/problems/minimum-number-of-refueling-stops/)

:::spoiler 額外題目
- [Luogu P2949 [USACO09OPEN] Work Scheduling G](https://www.luogu.com.cn/problem/P2949)
    :::spoiler 💡Hint
    按照 deadline 分組，並按照時間做所有任務，遇到目前做了太多任務時，則反悔，選擇前面收益最小的放棄。
    :::
- [AIsing2020E - Camel Train](https://atcoder.jp/contests/aising2020/tasks/aising2020_e)
    :::spoiler 💡Hint
    類似 Luogu P2949，但需要根據擺在左邊還是右邊哪邊的收益比較高先進行一次分組，再對兩組分別做反悔貪心，注意方向已經允許的大小。
    :::
:::

## 動態規劃 Dynamic Programming (DP)

### 14.1 Rod cutting (線性DP)

- [Gym-270304F Rod Cutting](https://vjudge.net/problem/Gym-270304F)

### Maximum Subarray Sum (Kadane's Algorithm)

- [LC 53\. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/) `[113 中興]` `[107 中央]`
   - 可以考慮空間優化，另有前綴和以及 $O(n)$ 的分治作法。📗 [解題紀錄](https://gdst.dev/posts/LC-53/)
- [LC 152\. Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/)
    LC 53 延伸，可以考慮多維護一個值。
- [LC 1749\. Maximum Absolute Sum of Any Subarray](https://leetcode.com/problems/maximum-absolute-sum-of-any-subarray/)
- [LC 2606\. Find the Substring With Maximum Cost](https://leetcode.com/problems/find-the-substring-with-maximum-cost/)


:::spoiler 額外題目
- [LC 2272. Substring With Largest Variance](https://leetcode.com/problems/substring-with-largest-variance/)
    :::spoiler 💡Hint
    - 若已知在答案中出現次數最多和最少的字母分別為 $a$ 和 $b$，則可以將 $a$ 視為 $1$，$b$ 視為 $-1$，其他字母視為 $0$，如此題目所求即為對其求 Maximum Subarray Sum。
    - 由於 $b$ 一定要出現，因此需要額外維護一個狀態紀錄 $b$ 是否出現過。
    - 雖然 $(a, b)$ 是未知的，但所有可能只有 $P^{26}_2 = 650$ 種，可以枚舉所有可能。
    - 若枚舉的 $a^{\prime}$ 並不是真正的 $a$，或若枚舉的 $b^{\prime}$ 並不是真正的 $b$，則最大子陣列和都會變小，不會影響答案。
    :::
:::

### 14.2 Matrix-Chain Multiplication (區間DP)

- [Aizu-ALDS1_10_B Matrix Chain Multiplication](https://vjudge.net/problem/Aizu-ALDS1_10_B)
- [UVA-348 Optimal Array Multiplication Sequence](https://vjudge.net/problem/UVA-348)
    需要構建結果
- [LC 312. Burst Balloons](https://leetcode.com/problems/burst-balloons/)
    變形，但不要被 Hard 嚇到了，只需要做一些處理即可，可以想想這題為甚麼會被分到這裡 XD

### Optimal Polygon Triangulation (區間DP)

> NYCU Algorithm

:::success
📝 三角形的價值可以是邊的權重和、點的權重和、面積。
:::

:::warning
💡 除了最大或最小化三角分割多邊形價值外，那要如何求凸多邊形的分割方法數呢？提示：離散與組合數學。

:::spoiler 答案
==**卡塔蘭數 (Catalan number)**==
- 🔗 [卡特兰数 - OI Wiki](https://oi-wiki.org/math/combinatorics/catalan/)
- 🎞️ [算法讲解147【扩展】卡特兰数题型详解和取模处理](https://www.bilibili.com/video/BV1BACUY7EzN/)
:::

- [LC 1039. Minimum Score Triangulation of Polygon](https://leetcode.com/problems/minimum-score-triangulation-of-polygon/)
- [CF 1140D. Minimum Triangulation](https://vjudge.net/problem/CodeForces-1140D)
    因為 $n = 500$，所以可以用 $O(n^3)$ 的DP解法，此外也有 $O(n)$ 的貪心解法

:::spoiler 額外題目
- [UVA-1331 Minimax Triangulation](https://vjudge.net/problem/UVA-1331)
    注意和上面的題目不同，此題沒有保證是凸邊形，故轉移時需要判斷是否合法，且定義的價值是面積，可以使用海龍公式。 
:::
    
### 14.4 Longest Common Subsequence (區間DP)

- [UVA-10405 Longest Common Subsequence](https://vjudge.net/problem/UVA-10405)
- [LC 583\. Delete Operation for Two Strings](https://leetcode.com/problems/delete-operation-for-two-strings/)
    變形，但不多
- [LC 712\. Minimum ASCII Delete Sum for Two Strings](https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/)
    變形

### 14.5 Optimal binary search trees (區間DP)

- [Aizu-ALDS1_10_D Optimal Binary Search Tree](https://vjudge.net/problem/Aizu-ALDS1_10_D)
- [Luogu P2308 添加括号](https://www.luogu.com.cn/problem/P2308) `108 交大`
    變形，注意是合併只能發生在相鄰兩項間，因此不能貪心。且需要重建結果。此外定義和 OBST 略有不同，邊界條件為 $f(i, i) = 0$，且轉移的 cost 為 $\displaystyle \sum_{k=i}^{j} nums[k]$。
- [Luogu P1880 [NOI1995] 石子合并](https://www.luogu.com.cn/problem/P1880)
    變形，和 P2308 類似，但本題要同時求最大和最小值。

### P14-2 Longest Palindrome Subsequence (區間DP)
- [LC 516. Longest Palindromic Subsequence](https://leetcode.com/problems/longest-palindromic-subsequence/)
- [UVA-11151 Longest Palindrome](https://vjudge.net/problem/UVA-11151)
    測資中有空行，且需要對空行計算 LPS 長度

### P14.4-5&6 Longest Increasing Subsequence
- [LC 300\. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)
    求長度
- [1671\. Minimum Number of Removals to Make Mountain Array](https://leetcode.com/problems/minimum-number-of-removals-to-make-mountain-array/) `113交大`
    - 前後綴分解，類似113交大手寫，只有求答案的部分不同。📗 [解題紀錄](https://gdst.dev/posts/LC-1671/)
    
#### 二維 LIS

- [UVA-437 The Tower of Babylon](https://vjudge.net/problem/UVA-437)
- [LC 354\. Russian Doll Envelopes](https://leetcode.com/problems/russian-doll-envelopes/)
    這題現在 $O(n^2)$ 的 DP 會 TLE ，一定要 $O(n \log n)$ 的貪心才能AC，但還是可以參考原本的 [官方題解](https://leetcode.cn/problems/russian-doll-envelopes/solutions/633231/e-luo-si-tao-wa-xin-feng-wen-ti-by-leetc-wj68)

:::spoiler 額外題目
- [Luogu P1233 木棍加工](https://www.luogu.com.cn/problem/P1233)
	這題的結論上是一維非遞增(>=)、另一維遞增(<)。在推出結論的過程會用到 Dilworth's theorem ，其通俗解釋是把一個序列劃分成 **最少** 個非遞增子序列的數目，等於這個序列的最長遞增子序列的長度(LIS)，怎麼推出這個結論的對考研來說不是很重要。
:::
    
### P14-4 Edit Distance (區間DP)
- [CSES-1639 Edit Distance](https://vjudge.net/problem/CSES-1639)

### P15-1 Coin changing (背包DP)
- [CSES-1634 Minimizing Coins](https://vjudge.net/problem/CSES-1634)
    問最少硬幣數量，同 [LC 322\. Coin Change](https://leetcode.com/problems/coin-change/)
- [CSES-1635 Coin Combinations I](https://vjudge.net/problem/CSES-1635)
    問排列數
- [CSES-1636 Coin Combinations II](https://vjudge.net/problem/CSES-1636)
    問組合數，同 [LC 518\. Coin Change II](https://leetcode.com/problems/coin-change-ii/)
- [UVA-11407 Squares](https://vjudge.net/problem/UVA-11407)
    變形，同 [LC 279\. Perfect Squares](https://leetcode.com/problems/perfect-squares/)
- [CSES-1633 Dice Combinations](https://vjudge.net/problem/CSES-1633)
    變形，分組背包
- [LC 1155\. Number of Dice Rolls With Target Sum](https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/)
    變形，分組背包，骰子點數增加

### Weighted Interval Scheduling / Weighted Job Scheduling (劃分DP)

> NTU ADA

:::success
💡 可以關注如何要找到第一個兼容的區間
:::

- [LC 2830\. Maximize the Profit as the Salesman](https://leetcode.cn/problems/maximize-the-profit-as-the-salesman/)
- [LC 2008\. Maximum Earnings From Taxi](https://leetcode.com/problems/maximum-earnings-from-taxi/)

## 二分搜尋 Binary Search

### 最小化最大值

### 最大化最小值

- [1631. Path With Minimum Effort](https://leetcode.com/problems/path-with-minimum-effort/) `[107 台大]`
    本題有最短路、二分答案求最大化最小值、Disjoint Set 做法。

## 圖論演算法 Graph Algorithms

:::info
🔗 [【题单】图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
](https://leetcode.cn/circle/discuss/01LUak/)
:::

### DFS

:::spoiler 額外題目
- [ABC378F - Add One Edge 2](https://vjudge.net/problem/AtCoder-abc378_f)
    :::spoiler 💡Hint
    對於一個==度數皆為 $3$ 的連通分量==，可以計算他相鄰的點中度數為 $2$ 的點的數量 $cnt$，在這些度數為 $2$ 的點中，任選兩個配對，即可滿足題目要求，故這個連通分量對答案的貢獻為 $\frac{cnt \times (cnt - 1)}{2}$，也可以用 BFS 求解。
    :::
:::

### BFS

- [UVA-532 Dungeon Master](https://vjudge.net/problem/UVA-532)
    三維空間

### 20.4 Topological sort

- [LC 1462. Course Schedule IV](https://leetcode.com/problems/course-schedule-iv/)
    計算 `ans[u][v]` 時可以在拓樸排序過程中找前面的節點，或是拓樸排序結束後用 Floyd-Warshall 求解。

### Ch21. Minimum Spanning Tree

- [LC 1584\. Min Cost to Connect All Points](https://leetcode.com/problems/min-cost-to-connect-all-points/)
- [Luogu P1547 [USACO05MAR] Out of Hay S](https://www.luogu.com.cn/problem/P1547)

### Ch22. Single-Source Shortest Paths

- [CSES-1671 Shortest Routes I](https://vjudge.net/problem/CSES-1671)
- [LC 743\. Network Delay Time](https://leetcode.com/problems/network-delay-time/)
- [1631. Path With Minimum Effort](https://leetcode.com/problems/path-with-minimum-effort/) `[107 台大]`
    本題也有二分答案求最大化最小值、Disjoint Set 做法。
- [1368\. Minimum Cost to Make at Least One Valid Path in a Grid](https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/)
- [UVA-10000 Longest Paths](https://vjudge.net/problem/UVA-10000)
    變形，注意給定的是 DAG
- [LC 3341\. Find Minimum Time to Reach Last Room I](https://leetcode.com/problems/find-minimum-time-to-reach-last-room-i/)
    變形

### Ch23. All-Pairs Shortest Paths

- [CSES 1672_Shortest Routes II](https://vjudge.net/problem/CSES-1672)
- [LC 2976\. Minimum Cost to Convert String I](https://leetcode.com/problems/minimum-cost-to-convert-string-i/)
    - 📗 [解題紀錄](https://gdst.dev/posts/LC-2976/)
- [LC 1462. Course Schedule IV](https://leetcode.com/problems/course-schedule-iv/)
    需要拓樸排序。

### Ch24. Maximum Flow

:::success
💡可以參考 OI-WIKI 和 AtCoder Library 中的實現。不過網路流的問題難點其實在如何建圖，但對考研來說應該不用研究如何針對問題建圖。
:::

- [Luogu P3376 【模板】网络最大流](https://www.luogu.com.cn/problem/P3376)

## Misc

### Maximum Gap

> NYCU Algorithm

- [LC 164. Maximum Gap](https://leetcode.com/problems/maximum-gap/)
    做到 $O(n)$

### Next Combination / Permutation

- [LC 31. Next Permutation](https://leetcode.com/problems/next-permutation/)
    > 某校某年的數學題目，知道出處的歡迎留言告知
    - 做到 $O(n)$。📗 [解題紀錄](https://gdst.dev/posts/LC-31/)
- [LC 1286. Iterator for Combination](https://leetcode.com/problems/iterator-for-combination/description/) `106中央`
- [NC286220 同位序列](https://ac.nowcoder.com/acm/problem/286220)
  - 有做過前面 DP 題目的話本題 DP 部分很簡單，主要思考 $g(x)$ 的求法即可。
    :::spoiler 💡Hint
    - 由於 $x$ 和 $g(x)$ 二進位表示中 $1$ 的個數相同，因此可以使用一個陣列儲存 $x$ 的二進位表示，在前面補 $0$ 後對其求下一個排列即可。時間複雜度 $O(\log x)$。
    - 另有 $O(1)$ 的位運算做法。
    :::