All-Ukrainian School Olympiad in Informatics 2011

ACM style, 以下是我做題的順序

E. Points

利用

可以快速計算, O(N) 時間, O(1) 空間

D. Plus and xor

考慮 B 的每一個 bit (由 MSB 到 LSB), 如果是 1, 則 X 和 Y 的那一個 bit 必定有一個是 1 另一個是 0, 那當然把 1 assign 給 X
如果 B 的那個 bit 是 0, 則計算如果 X 和 Y 的那一 bit 均為 0 的話 X+Y 是否能 ≥ A

留意

if (X + Y > A)

會 overflow

A. Gift

一開始以為對 gold 做 ternary search 可行, 但 WA 後便發現很容易作出反例..
之後想想有甚麼必定正確的做法:

首先 sort gold, silver 的可能值
然後用 2 支 pointer, 一支在 gold 的最前, 另一支在 silver 的最尾, 做 sliding
但是由於每次 check connectivity 要 O(E), 整個 algorithm 是 O(E²)

後來想到了 http://poj.org/problem?id=2838, 也就是 maintain 著一棵 tree, 而不是一個 graph
簡單來說, 每次 insert 一條 edge 時, 如果形成環的話, 可以 delete 環上的一條 edge 而不影響連通性
在這條題目中, delete 的便是 silver 最大的那條 edge 了

由於邊的數目最多為 V-1, 每次 check connectivity 只要 O(V), 於是 total time = O(VE)

B. Mice

這條理論上比 A 簡單
首先把只有一個選擇的 mice 所選的 cheese mark 上時間截
然後對於剩下的 mice, 可以 greedy 的決定去左邊還是右邊

F. Tourist

看到這類題目通常都是先把 equation 寫出來, 例如去完 event i 後能去 event j 的話, 必需滿足

T_i ≥ T_j + X_j - X_i (假設 X_j ≥ X_i)

然後移項, i 歸 i, j 歸 j

T_i + X_i ≥ T_j + X_j

然後, 可以證明到, 只要滿足 (1) 和 (2),

Ti + Xi ≥ Tj + Xj    (1)
Ti - Xi ≥ Tj - Xj    (2)

是去完 event i 後能去 event j 的充份條件
之後, 便可把問題轉化為在 2D plane 上找最長不下降線段