Luogu 🟢 P1950 长方形
逐列轉成柱狀圖後,每列答案就是區間最小值總和;可用單調棧邊界計數或單調棧優化 DP 線性求解。
AtCoder 🟣 ABC434F Concat (2nd)
給定 N 個字串,求出所有排列組成的字串中字典序第二小的字串。透過自定義排序規則與局部交換獲得答案。
AtCoder 🟢 ABC434E Distribute Bunnies
將兔子的兩種跳躍終點視為圖上的節點,每隻兔子視為邊,問題轉換為計算各連通分量中最多能覆蓋的點數(取點數與邊數的最小值)。
AtCoder 🟡 ABC434D Clouds
利用二維差分求出重疊次數,再對恰好覆蓋一次的格子做二維前綴和以極速查詢區間總量。
AtCoder 🟡 ABC434C Flapping Takahashi
高橋以速度 ≤1 飛行且高度 > 0,判斷能否滿足所有區間目標。利用可行區間傳播與交集判定。
AtCoder 🔵 ABC428F Pyramid Alignment
運用區間始終保持巢狀的性質,轉換對齊操作為延遲標記,並以線段樹上二分搜 max_right 找出覆蓋點的區間後綴。
AtCoder 🟢 ABC428E Farthest Vertex
給定 N 頂點的樹,對每個頂點求最遠頂點(同距取最大編號);利用樹直徑端點性質,三次 BFS 即可求解。
AtCoder 🟡 ABC428D 183184
給定 C, D,計算有多少 x ∈ [1,D] 使得 f(C, C+x)(數字串接)為完全平方數;按 C+x 的位數分段,轉化為區間內完全平方數計數。
AtCoder 🟠 ABC428C Brackets Stack Query
用兩個堆疊分別追蹤括號平衡值與前綴最小值,支援撤銷操作,每次查詢判斷是否為合法括號序列。
Codeforces 🟣 CF1788F XOR, Tree, and Queries
將路徑約束轉為點標籤,帶權併查集維護約束並利用奇度數節點區塊最小化總異或和。
Luogu 🟣 P3631 [APIO2011] 方格染色
找出 2x2 子矩陣中特定狀態的數量規律,將約束轉化為異或方程組,並使用帶權並查集維護節點間的關係。
AtCoder 🌈 AWC0022C Road Pothole Survey
給定損壞磁磚位置與多筆行經區間,利用前綴和快速統計區間內損壞數量,判斷是否達到維修門檻。
AtCoder 🌈 AWC0022D Simultaneous Control of Light Bulb Panels
從左到右貪心處理燈泡狀態,遇到暗燈即翻轉長度 K 的區間,並用差分陣列維護翻轉奇偶性以線性判斷最少操作數。
AtCoder 🌈 AWC0022E Delivery Driver's Route
先用 Floyd-Warshall 求所有城鎮間最短距離,再以狀壓 DP 求從起點出發、訪問所有城鎮並返回的最短路程。
LeetCode 🟡 3857. Minimum Cost to Split into Ones
將問題轉換為完全圖的邊斷開過程,任何拆分方式的總代價均恆為 n(n-1)/2。





![Luogu 🟣 P3631 [APIO2011] 方格染色](https://i.gdst.dev/cover/P3631.webp)





