逆向求解

有些問題從起點出發難以前進，從終點逆算過程卻意外的容易。

記得有時倒著做比正著做更容易。

AtCoder abc216_c - Many Balls

https://atcoder.jp/contests/abc216/tasks/abc216_c

如果從

$0$ 出發，很難確定下一步應該

$+1$ 還是該

$\times 2$，畢竟

$\times 2$ 成長雖快，但歪掉時很難修正回來，例如剛好乘進

$\frac{N}{2}$ 再多一些些的地方時。

但反過來從終點就很簡單了：

• 如果它是奇數，那
  $\times 2$ 不可能達成，必然得選
  $+1$；
• 如果它是偶數，那
  $\times 2$ 必然能較快回到
  $0$，故必選
  $\times 2$。

每次的抉擇可以直接由奇偶來決定，只要

$O(1)$ 的計算量；最多

$2$ 次抉擇就會將

$N$ 砍半，因此過程最多

$2\times {\log }_{2}N$ 次，複雜度為

$O(\log N)$。

CSES 1163 - Traffic Lights

https://cses.fi/problemset/task/1163/

直接暴力處理的話，每次加入一個點後，重新計算每一段的長度，需要

$O(N)$ 的計算量來維護，整體

$O(N^2)$。

插入一個新的點會導致大量的資料搬動，且必須維持遞增使得容易找出最接近的兩個位置，以找到該切點所影響的線段；

每次切分會導致原有的線段會變短，要維護當前的最長線段，必須能支援刪除最大值後仍能找到下一個最大值。

以上這些都是必要，但目前所學的資料結構難以應對的部份。具體來說必須做到以下：

• 給一整數
  $k$ 在一個遞增序列
  $A$ 找到位置
  $i$ 使得
  $A_i<k<A_{i+1}$
• 插入一個整數
  $k$ 到一個遞增序列
  $A$ 並維持遞增
• 對序列
  $A$ 增加或刪除元素後，維護其仍能快速找出最大值

以上任一動作都必須執行

$O(N)$ 的次數，因此每個動作都必須在

$O(\log N)$ 等級的計算量完成，否則都有 TLE 的可能。

當然，仰賴目前進度未學過的強大資料結構的話，並不是做不到。只是現在做不到。

考慮一開始先把所有切點放進去，再從最後一個切點開始還原，就變成是把一個一個線段接回去。

維護每個切點的左右鄰居，則和鄰居的距離即為線段的長度，如上圖；刪除切點

$i$ 時左鄰居

$l$ 右側從

$i$ 變成

$r$、右鄰居

$r$ 的左側從

$i$ 變成

$l$，用 linked-list 的概念可以處理。

還原時會產生新線段，長度

$r-l$，直接和當前最長線段比較，即可維護。刪除舊的點維護最長很困難，但加入新的點維護最長很容易。

排序後即可知道所有切點在最後和誰相鄰。

得到做法如下：

1. 對切點序列
   $A$ 加入道路最左端和最右端
2. 複製
   $A$ 並按位置 sort 變成序列
   $B$
3. 對序列
   $B$ 每個切點記錄現在的左鄰居切點和右鄰居切點是誰
4. 逆序窮舉
   $A$ 對每個切點找到
   $B$ 中的位置，將它刪除（讓左鄰居和右鄰居變成相鄰）並更新當前最長

預處理 sort 需要

$O(N\log N)$，計算過程窮舉

$N$ 個點，每個點透過二分搜尋

$O(\log N)$ 找到在

$B$ 中的位置，修改左右鄰居

$O(1)$，總複雜度

$O(N\log N)$。

歡樂練習時間

ZJ f607 - 切割費用

https://zerojudge.tw/ShowProblem?problemid=f607

APCS 2021/01 p3

tags: 競程：二章後半, 競程