Practice : Asia Beijing 2008 / 2009

北京賽區。據說當年五題+不錯的Penalty就可以拿到金獎  雖然不知道金獎怎麼定義XDD                             .

Beijing (China)

 

ID Problem Title Download Hint Ranking 4322 Destroying the bus stations YES 4323 A simple stone game YES 4324 Ugly Windows YES 4325 Tornado YES 4326 Minimal Ratio Tree YES 4327 Parade YES 4328 Priest John's Busiest Day YES 4329 Ping pong YES 4330 Timer YES 4331 Elevator YES

pA 給你一張有向圖(V=50 E=4000)和K，問至少要拔幾個點才使得1->N的最短路大於等於K
(邊權皆為1、1->N沒有直接連邊)

用最大流想法：增廣到該次最短路長度>=K就結束，輸出目前源點流量   不過依然WA

pB給你N和K，兩人輪流取石頭，第一個人第一次只能拿1~N-1顆、
以後每個人每次拿的數量不能超過上衣個人K倍，問先手必勝的第一步？

沒想法，不過應該是經典題

pC給你一張NxM圖片，問你有幾個矩形框在最上層？

模擬，但是注意回字型。

pD有一個龍捲風路徑是一條射線，給你他的速度，還有一個人在兩點之間等速往復運動，問龍捲風到人的最近距離？

沒想法

pE給一張無向有權完全圖，你要輸出一組M個點的生成樹且邊權和/點權和最小，且點排好後的字典序最小。

爆搜，注意一下精度問題。

pF給一張NxM網格(N=100,M=10000)，橫向(M方向)每條路徑都有兩個權重，v跟k。
從最底下任意一點開始，到最上面任意一點。只能往上或左右走，且走過路徑不能再走，
且每層(依照N分層)走過的路徑sum k要小於給定的K，求出整條路徑sum v的最大值。

DP，每層轉移需要Deque，不過我還在WAorz

pG給你很多區間(N=100000)代表婚禮，牧師必須選擇一段連續段來進行證婚。
這段必須要大於區間大小的一半，且牧師只有一個人不能分身，問有沒有可能替所有婚禮證婚？

Greedy (by worm)，還不會

pH給你一個序列ar(長度=100000)，問有幾個三數對A,B,C符合位置A<B<C且ar[B]介於ar[A]和ar[C]之間。

頗裸的Binary Indexed Tree

pI, pJ沒看題目


總體而言打得很失敗orz

不過要感謝suhorng, jurrasickill