ACM-ICPC Regional Asia Beijing 2008

Overview:

。。常規套題。。除了 B 題以外都沒什麼好推薦的。。。。(B 題是非常經典的 Nim-like 問題。。必須總結整理。。。。
A 可以迭代加深搜索、也可以網路流。。
G 可以排序貪心、也可以 2-SAT。。
。另外像是 J 題這樣子的蘑菇題。。處理起來必須要非常小心。。。
。。比賽的時候需要用這類題目來給三妹爭取推 B 和 I 的時間。。。

Analysis:

Problem A. Destroying the bus stations
..有向圖,問最少刪去多少點,使得不存在 s 到 t 的長度 <=k 的路徑。 (。不能刪去 s、t。。不存在 s 直接到 t 的邊。。。n ≤ 50。。。 。。因為 n 比較小所以可以裸搜。。。 。。一般問題可以網路流解決。(有向圖點連通度)。。 。做法是對中間結點拆點。連一條容量為 1 的邊。 。。之後從 s 出發各做一次單源最短路。(得到 d1[]。。。 、從 t 出發在轉置圖中做一次最短路。。(d2[]。。 。檢查每條邊 (u, v, w)。。如果 d1[u] + w + d2[v] <= k 。則連一條 u -> v’ 。。容量為 oo 的邊。。求最小割。。

演算法 1:
迭代加深搜索。。
演算法 2:
最小割。

Problem B. A simple stone game
任何一個正整數都可以分解為某個類 Fibonacci 數列 {ai} 中。。
一個子序列 {aj} 的和。。且滿足 k aj < aj+1 。 證明:(構造 。。。設 ri 為前 i 個 {ai} ,在滿足性質 1 的情況下所能分解出的數字的最大值。 那麼有。。 ai+1 = ri + 1。。(保證每個數字都可以出現。。 ri = ai + rj。。j 滿足 aj * k < ai 且儘可能大。(保證分解方案唯一。。 —————————————————————— 這個題非常 Nice,思維流首先是對 k 做限制, 對於 k = 1、2 的情況不難發現解和數的二進位分解和 Fibonacci 分解有關。。。 關於 Fibonacci 唯一分解這個有必要在 Mark 一下。。 定理:任何一個正整數都可以分解為 Fibonacci 數列中一些不相鄰的數的和,且分解方案唯一。 證明這個定理的方法和前面更一般的構造法類似,且 且 k = 2 恰好是 Fibonacci 數列,只是 k aj < aj+1 這個條件中 k = 2 情況下的特例。。 之後把觀察了一下 k 比較小情況下的 {ai} .. .

1,2,4,8,16,32,64 .. .
1,2,3,5,8,13,21,34 .. .
1,2,3,4,6,8,11,15 .. .
1,2,3,4,5,7,9,12,15,19,24,31,40,52 .. .
1,2,3,4,5,6,7,8,10,12,15,18,22,27,33,41,51,63,78

k = 3 的時候是

A003411A003412 / A003413

對於之後的 k >=3 。。都是從數列的某項開始(哪項?。。
滿足 a[n] = a[n-1] + a[n-k] 。。
(… 而開始前面的地方會偶爾向前震蕩一下。 a[n] = a[n-1] + a[n-k+?]。。。
(… 似乎沒什麼規律。。。

博弈論、斐波那契數列、構造

Problem C. Ugly Windows
模擬。。

Problem D. Tornado
計算幾何。。
固定一點,問題轉換為單點到一組平行線段的最短距離,三分之。。
注意線段退化的情況。。。。

Problem E. Minimal Ratio Tree
暴力枚舉,最小生成樹。

Problem F.
單調隊列,動態規劃。。。

Problem G. Priest John’s Busiest Day
根據中間時刻排序貪心即可。(婚禮必然經過中間時刻。。注意儀式時間嚴格大於婚禮時間的一半。。
排序,貪心。。

Problem H. Ping pong
樹狀數組。。。

Problem I. Timer
二分答案 + 積分 =w=。。。

Problem J. Elevator
1 是如何討論狀態。。。
。。總之分 idle(空閑中)。。 anchor (停泊中) 。。open (開門中) 三種進行討論。。
。。另外對於空閑狀態。。記錄當前移動的方向。。
(正確的討論狀態非常重要。。否則根本無法處理諸如。。先開門進來 3 個人。。這個時候又來了 1 個。。。再進來 1 個。。再關門。。關門的時候又來了一個。。再開門再進來一個這樣的情況。。。)

2 處理請求的優先順序問題。。
。。這裡做了。。__c(), _c(), c0(), c1(), c2(), c3() 一組函數。。。
__c() 判斷某個位置是否有人要上車。。
_c() 在 __c() 的基礎上,再判斷請求方向是否與電梯運行方向一致。
c0(), c1(), c2(), c3() 分別是是否有 上/下 方向的人需要 進/出。。。

。。然後做起來的話就要舒服多了。。
惡模擬。。

External link:

http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=723#overview