Andrew Stankevich』s Contest #3

Overview:

。。#3 的構造題都是比較簡單的啦。。(C, E, H 。。。
.. 另外有兩道很經典的圖論 (B, D 。。。
… 當然最推薦的還是 A 題。。。

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

Problem A. Areas:
… 平面內給定 n 條直線,求封閉區域的個數以及它們的面積。
。。( n <= 80 .. 。。。 ———————— 。。。先求交點,之後對相鄰的交點連邊。(被同一條線段覆蓋。。且中間沒有其他交點隔開。。。。 。。那麼封閉區域等價於平面圖中的環。。那麼以逆時針為軸。。為了分割出最小的封閉區域, 。。我們只要從任意邊開始,每次往最里側的位置旋轉即可。。O(m) 時間即可解決這個問題。。。 。。。所以總的複雜度是建圖的複雜度。。O(n^2logn)。。 。計算幾何。。(80ms。。。
(注意代碼這裡我禁止向順時針方向轉移,如果允許。。那麼會順時針方向會多分割出一個包含所有這些極小封閉區域的大封閉區域。。

————————
(。。補充說明一下精度問題。。這個真是折磨死人了。。當然最可靠方法還是是用分數的形式保存每個 double。。。。
。。這樣的話中間對每個算式除的地方都乘上來。。這樣雖然安全有效但是改累死了。。。
。。。後來發現其實別的地方有 bug 而已。。總之生卡精度的題其實還是沒有的吧?。。。WA 的話可能還是別的其他的地方寫疵了。。

(。。刪去第721行可 AC。。(???。。。

Problem B. Beloved Sons:
匈牙利演算法(120ms +-..

Problem C. Strange Counter:
。。構造 -> 不變式。。

Problem D. Data Transmission:
貪心初始流 + Dinitz() (0.8s +- 。。

Problem E. Strong Defence:
構造 -> bfs()..。

Problem F. Weird Dissimilarity:
dp()..

Problem G. PL/Cool
Tags: 解釋器、表達式求值、並查集、字元串 Hash

。。。

Problem H. Royal Federation:
一個國家有 n 個城市,且城市之間的道路形成一棵樹,現在要求劃分出若干個省,使得每個省的城市數目屬於 [B, 3B]。
並為每個省指定一個省會,使得屬於該省的所有城市,都可以在該省內部的範圍內到達省會。
(省會不要求不在省內。。)

遞歸構造,滿足條件的方案一定存在。設 dfs() 中若訪問到點 u 時,其子樹的 size 都不超過 B,
那麼把它們合併成若干 [B, 2B] 之間的點集,並以 u 點作為省會。剩下來的點集數目+上 u 點自己一定不超過 B。

最後會剩下與根節點相連的不超過 B 個點的集合,任選一個與該集合相鄰的集合與之合併即可。
這樣除了與根結點相連的這個點集外,其他點集的大小都是 [B, 2B] 之間。。

。。。

Problem I. Two Cylinders
$latex V = 8\int_0^{Min(r_1, r_2)} \sqrt{(r_1^2-x^2)(r_2^2-x^2)}dx&s=4$
。。。積分我完全不會。。移步這裡。。。)。。
http://blog.watashi.ws/970/andrew-stankevich-3-solution/

。。。樸素(。設置塊數。。分段黎曼近似。。。

External link:

http://acm.zju.edu.cn/onlinejudge/searchProblem.do?contestId=1&titlefrom=0&authorfrom=0&sourcefrom=0&query=Andrew+Stankevich%27s+Contest+%233