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

TIOJ 1516 Problem F. HALLO ☆ GAME [Binary Tree]

3    91671    poao899    18388K    2197MS    G++     3.18K     2010-12-07 01:07:12                                            .


                                              


因為要正名(?)所以就不用Segment Tree這個名詞了XD

其實我覺得叫做Segment Tree也沒什麼不好，這種東西這麼常用總該有個名字吧XD

而且為什麼歪果仁講的就是正確的大陸人講就是亂講(?)


或許我跟這些都不熟上面只是我一廂情願罷了XD


反正以後這種東西在我的部落格上都會紀錄為Binary Tree?



這題操作很多，不過不難寫。

只需要有三個操作：

區間覆蓋、區間詢問、單點求值就好了。



不過這題還是值得推薦的?

因為它有用到存左邊右邊中間再meld的概念還有大陸學生口中的延遲標記(或sb標記?)

還有有些操作不能純用樹來作XD




仔細想了一下，似乎一棵純粹的Splay Tree可以支援所有操作？

因為那個旋轉說實話我搞了一個禮拜xD