KOI 2026 Day 2 - Flying Squirrel 2

Created2026-02-25Updated2026-02-26

連結

題目

有一隻飛鼠，一開始她所在的高度為 00。對於所有 i=0,1,…,N−1i = 0, 1, \ldots, N - 1，她會依序進行以下事情：

  • 選擇花費 A[i]A[i] 點能量與 B[i]B[i] 塊錢把高度增加 11，或是選擇不做任何事情且高度保持不變。
  • 選擇完後，飛鼠的高度必須介於 L[i]L[i] 與 R[i]R[i] 之間。

結束後飛鼠的高度必須為 HH。現在對於所有 0≤k≤H0 \leq k \leq H，輸出花費恰 kk 塊錢的情況下最少需要花多少能量。

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 0≤B[i]≤10 \leq B[i] \leq 1

解法

Subtask

有三個維度太多了，先看看 B[i]=0B[i] = 0 要怎麼做。很簡單可以列出這個 O(n2)O(n^2) DP：

dp[i][j]={min⁡(dp[i−1][j],dp[i−1][j−1]+A[i])if L[i]≤j≤R[i]∞otherwisedp[i][j] = \begin{cases} \min(dp[i - 1][j], dp[i - 1][j - 1] + A[i]) & \text{if } L[i] \leq j \leq R[i] \\ \infty & \text{otherwise} \end{cases}

最後答案會是 dp[N][H]dp[N][H]，而這個形式很明顯就是個 slope trick。具體來說，如果今天沒有 L[i],R[i]L[i], R[i] 的範圍限制，那你的 dp[i][∗]dp[i][*] 可以用數歸證明他會是凸函數，也就是符合 dp[i][j]−dp[i][j−1]≤dp[i][j+1]−dp[i][j]dp[i][j] - dp[i][j - 1] \leq dp[i][j + 1] - dp[i][j]。那這樣你要維護 dp 值你就只要存下 dp[i][j]−dp[i][j−1]dp[i][j] - dp[i][j - 1] 就好了，而要轉移也相當簡單：將 A[i]A[i] 加進去差分序列裡面即可。

至於有 L[i],R[i]L[i], R[i] 的話，想像現在 dp 值我們只存非 ∞\infty 的值，也就是只存 j∈[L[i],R[i]]j \in [L[i], R[i]] 的 dp[i][j]dp[i][j]。可以發現這也會是凸函數，而轉移一樣在差分序列上面做事的話，會需要算出 dp[i][L[i]]dp[i][L[i]] 的實際值以及把太大的差分砍掉，總之開個 multiset 就可以好好維護了。總複雜度 O(Nlog⁡N)O(N \log N)。

滿分

如果今天只要算一個 kk 的答案的話那很自然會想到要 aliens 二分搜。具體來說，想像今天位置 ii 的花費變成 A[i]+B[i]×CA[i] + B[i] \times C，那當 CC 很小時我會想要花儘量多錢，CC 很大時我會想要花儘量少錢，然後就可以嘗試對 kk 去二分搜去找答案。aliens 二分搜要答案函數是凸/凹函數才會是對的，但這部份很好猜所以這裡先略過證明。

然而今天我們需要對每個 kk 都算答案，這樣太慢了，那既然要對每個都二分搜很自然的會想要整體二分搜。整體二分搜的一個重點是要好好的在遞迴的時候丟掉一些事件，避免一個事件同時被推進左邊與右邊來讓複雜度壞掉。那假如現在我們找到了 C=mC = m 的最優解，判點 case 我們可以得出：

  • 若一個 B[i]=0B[i] = 0 的位置在最優解內，那當 CC 變大時我依然選它一定不虧，所以我只要在 CC 變小的時候重新考慮它。
  • 若一個 B[i]=1B[i] = 1 的位置在最優解內，那當 CC 變小時我依然選它一定不虧，所以我只要在 CC 變大的時候重新考慮它。
  • 若一個 B[i]=0B[i] = 0 的位置不在最優解內，那當 CC 變小時我只會更不想選它，所以我只要在 CC 變大的時候重新考慮它。
  • 若一個 B[i]=1B[i] = 1 的位置不在最優解內，那當 CC 變大時我只會更不想選它，所以我只要在 CC 變小的時候重新考慮它。

這樣一來每一個位置都會有一邊確定要不要選，另一邊不確定，但這樣就足夠了，只要我每次找最優解的複雜度與「目前還不確定要不要選的位置數量」相關的話，那整體複雜度就是好的。至於這樣怎麼做呢？一定不會選的位置直接丟掉就好了，一定要選的話我可以直接把它的花費加進答案裡，並把它的後綴的所有位置的 L,RL, R 都減 1，然後雖然我中間跳過了「考慮這個位置要不要選」這件事，但 L,RL, R 的範圍限制還是要考慮的，而這部份也相當單純：只要會詢問 L,RL, R 的區間最大值與最小值就行了。

整體來說，我會需要一棵區間加/減值、區間最小/最大值的線段樹，這樣一來找最優解可以在 O(mlog⁡N)O(m \log N) 做完，其中 mm 為目前還不確定要不要選的位置數量。這樣套整體二分複雜度會是 O(Nlog⁡Nlog⁡C)O(N \log N \log C)，其中 CC 是值域。是可以通過的但可能會有點緊（時限 5 秒我沒管常數的解要跑 4.5 秒）。

後話

前陣子換電腦發現有些套件版本問題懶得處理所以就直接重新架了一遍 blog，為了確認一切是好的就亂挑個最近寫的題寫個題解。

當時在打 Open Contest 的時候其實沒有預期這個解可以滿分，主要是看到倒數第二筆 Subtask 是 N≤65000N \leq 65000 然後會有 81 分感覺很多才寫的。

事實上這題存在純模擬費用流的解，而且複雜度為 O(Nlog⁡N)O(N \log N)，比上面提出的解好。另外這種題目的凸/凹性的一種常見證明方法就是想辦法建出一個費用流的模型，然後根據費用流的演算法就可以直接得出有凸/凹性。