Q4 是給一個 N x N map, 每一格有高度
現在由起點出發, 經過所有 checkpoint(s) 並回到起點。目標是最小化沿途中 最高點 與 最低點 之差
N ≤ 50
雖然是 path, 但其實不用真的找條 "path" 出來, 只要想成找一棵 spanning tree
先枚舉 path 上允許的最低點, O(N2)
然後二分 path 上允許的最高點, O(lg N)
做 flood fill 檢查可行性, O(N2)
Q5 given 一個有向圖, 每個頂點的 out degree 不大於 1
然後有 Q 個操作, 每次可以
remove(x): 移除 x 的 outgoing edge
query(x): 問由 x 開始走, 最終會到達邊個 vertex, 如果是 cycle 就 report 有 cycle
看下去十分像 disjoint set, 但 disjoint set 不支援 delete, 不過支援就是 dynamic tree 了
個 trick 就是可以倒著做, 那 delete 就變成了 union
所以先把所有 operation 讀入, delete 的照 delete
然後以 operation 倒序 process, 就變成一般的 disjoint set 了
No comments:
Post a Comment