# CSES Problem Set 2025 更新的題目總結

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

## [CSES3360 Corner Subgrid Check](https://cses.fi/problemset/task/3360)

:::spoiler 提示
相關題目： [CF333 D. Characteristics of Rectangles](https://codeforces.com/problemset/problem/333/D)
這題的梗出現好久了，以前也有聽過學弟在 Google 面試時被問到這題。
:::

## [CSES3227 Sliding Window Advertisement](https://cses.fi/problemset/task/3227)
:::spoiler 提示
首先當然要會 [CSES1142 Advertisement](https://cses.fi/problemset/task/1142)
接著想想李超線段，那這題就沒了。
是說這次新增的題組超多斜率優化、李超線段樹一類的題...就以這題作代表吧
:::

## [CSES3358 Split into Two Paths](https://cses.fi/problemset/task/3358)
:::spoiler 提示
看完這題會直覺地想到最小路徑覆蓋，可是由於他只問是否有兩條 path 的覆蓋，那其實可以使用雙路徑 DP，也就是 dp[x][y] (x>y)代表拓撲排序後位置 $\le x$ 的點都已被兩條路徑覆蓋，那麼必定有一個路徑終點是 x，而另外一條路徑終點是 $y$ 有沒有可能到達，直接這座的話時間複雜度會炸掉，但可以優化成 $O(n+m)$。
這是我寫特別久的其中一題。
:::

## [CSES3195 Xor Pyramid Row](https://cses.fi/problemset/task/3195)
:::spoiler 提示
在我看來這題是超經典的倍增題，可是連 abc 都覺得這題有去的話，我還是列出來好了XD
:::spoiler 更多的提示
定義 $d[x][y]$ 代表有下往數數來第 $x$ 排的第 $y$ 個數。
根據 Lucas 定理，可推出公式 $d[x][y] = d[x-2^i][y]\ xor\ d[x-2^i][y+2^i]$
於是就可以倍增了。
:::

## [CSES3157 Collecting Numbers Distribution](https://cses.fi/problemset/task/3157)
:::spoiler 提示
不會的話就去查 OEIS，但我認為不要查比較好，試著自己想出來 DP 轉移式吧，概念期時很簡單。
:::

## [CSES3400 Raab Game II](https://cses.fi/problemset/task/3400)
:::spoiler 提示
想想錯排列的公式 $D_n=(n-1)(D_{n-1}+D_(n-2))$證明怎麼套在這題。
:::

## [K Subset Sums II](https://cses.fi/problemset/task/3109)
:::spoiler 提示
這是我出在 **AA 競程 TOI 模擬賽初賽 II E 題**的簡化版啊！！！
由於這題我印象深刻，所以一下就刷過去了。但仔細檢視這次到底有哪些有趣的題時，想起來這題的做法還是挺有趣的。
請參考[題解影片](https://www.youtube.com/watch?v=VlNrmHf9zow)

順帶一提，[CSES3108 K Subset Sums I](https://cses.fi/problemset/task/3108) 在 CS ACademy 有一模一樣的題目：[Smallest Subsets](https://csacademy.com/contest/round-79/task/smallest-subsets/)，且和我曾經出在台大 PK 賽的 [Dreamoon and NightMarket](https://codeforces.com/group/UsV3Jf8Bc1/contest/292261/problem/I) 做法也幾乎一樣。
:::

## [CSES3159 Replace with Difference](https://cses.fi/problemset/task/3159)
:::spoiler 提示
原題應該是 Codfeorces 上的題目吧...，不過令我印象深刻的是這題的進階版曾經出在 [2022 年的 NPSC 高中組決賽 B. 選巫醫巫醫](https://tioj.ck.tp.edu.tw/problems/2306)。
可參考 [NPSC 官方影片題目題解](https://www.youtube.com/watch?v=MSqf9_uezfs&list=PLjXPYRCTSLlThPuS1rybUKLNobnJvKHoy&index=8)
:::

## [CSES3402 Minimum Cost Pairs](https://cses.fi/problemset/task/3402)
:::spoiler 題示
這類的題目在台灣是經典到不能再經典了吧，最早出現是在 [2017 全國資訊能力競賽 p6. AI-666 賺多少](https://tioj.ck.tp.edu.tw/problems/2039)
今年(2025) TOI 一階二模又出現類似題。
請自行上網搜尋 priority_queue 一類的做法
:::
## [CSES3401 Stick Difference](https://cses.fi/problemset/task/3401)
:::spoiler 提示
這題和我曾經在 Codeforces Div. 1 出過的題目：[Dreamoon Loves AA](https://codeforces.com/problemset/problem/1329/E) 有相同的設定，只是問的東西不一樣，只要研讀題解裡的性質，就不難想到這題的做法了。雖然這麼說，但我還是卡細節卡了快一個小時XD
:::

## [CSES3425 Same Sum Subsets](https://cses.fi/problemset/task/3425)
:::spoiler 提示
一看就是鴿籠原理相關的題，可是我還是不會做...最後查到 [這篇第 16 頁](https://drops.dagstuhl.de/storage/00lipics/lipics-vol244-esa2022/LIPIcs.ESA.2022.6/LIPIcs.ESA.2022.6.pdf) 的做法，覺得非常妙！AC 後看起來人的做法似乎的示二分搜慢慢縮小答案範圍。
:::