CSES Problem Set 2025 更新的題目總結

畢竟 CSES 就是要讓大家學習經典知識及技巧的題庫，所以此次更新的大部分題都還是蠻經典的(或是各種有名的東西)，以下列一些我覺得相對有意思的題目。

CSES3360 Corner Subgrid Check

提示

相關題目： CF333 D. Characteristics of Rectangles
這題的梗出現好久了，以前也有聽過學弟在 Google 面試時被問到這題。

CSES3227 Sliding Window Advertisement

提示

首先當然要會 CSES1142 Advertisement
接著想想李超線段，那這題就沒了。
是說這次新增的題組超多斜率優化、李超線段樹一類的題…就以這題作代表吧

CSES3358 Split into Two Paths

提示

看完這題會直覺地想到最小路徑覆蓋，可是由於他只問是否有兩條 path 的覆蓋，那其實可以使用雙路徑 DP，也就是 dp[x][y] (x>y)代表拓撲排序後位置

$\le x$ 的點都已被兩條路徑覆蓋，那麼必定有一個路徑終點是 x，而另外一條路徑終點是

$y$ 有沒有可能到達，直接這座的話時間複雜度會炸掉，但可以優化成

$O(n+m)$。
這是我寫特別久的其中一題。

CSES3195 Xor Pyramid Row

提示

在我看來這題是超經典的倍增題，可是連 abc 都覺得這題有去的話，我還是列出來好了XD

更多的提示

定義

$d[x][y]$ 代表有下往數數來第

$x$ 排的第

$y$ 個數。
根據 Lucas 定理，可推出公式

$d[x][y]=d[x-2^i][y]xord[x-2^i][y+2^i]$
於是就可以倍增了。

CSES3157 Collecting Numbers Distribution

提示

不會的話就去查 OEIS，但我認為不要查比較好，試著自己想出來 DP 轉移式吧，蓋念期時很剪單。

CSES3400 Raab Game II

提示

想想錯排列的公式

$D_n=(n-1)(D_{n-1}+D_{(}n-2))$證明怎麼套在這題。

K Subset Sums II

提示

這是我出在 AA 競程 TOI 模擬賽初賽 II E 題的簡化版啊！！！
由於這題我印象深刻，所以一下就刷過去了。但仔細檢視這次到底有哪些有趣的題時，想起來這題的做法還是挺有趣的。
請參考題解影片

順帶一提，CSES3108 K Subset Sums I 在 CS ACademy 有一模一樣的題目：Smallest Subsets，且和我曾經出在台大 PK 賽的 Dreamoon and NightMarket 做法也幾乎一樣。

CSES3159 Replace with Difference

提示

原題應該是 Codfeorces 上的題目吧…，不過令我印象深刻的是這題的進階版曾經出在 2022 年的 NPSC 高中組決賽 B. 選巫醫巫醫。
可參考 NPSC 官方影片題目題解

CSES3402 Minimum Cost Pairs

題示

這類的題目在台灣是經典到不能再經典了吧，最早出現是在 2017 全國資訊能力競賽 p6. AI-666 賺多少
今年(2025) TOI 一階二模又出現類似題。
請自行上網搜尋 priority_queue 一類的做法

CSES3401 Stick Difference

提示

這題和我曾經在 Codeforces Div. 1 出過的題目：Dreamoon Loves AA 有相同的設定，只是問的東西不一樣，只要研讀題解裡的性質，就不難想到這題的做法了。雖然這麼說，但我還是卡細節卡了快一個小時XD

CSES3425 Same Sum Subsets

提示

一看就是鴿籠原理相關的題，可是我還是不會做…最後查到 這篇第 16 頁 的做法，覺得非常妙！AC 後看起來人的做法似乎的示二分搜慢慢縮小答案範圍。