今次的題目比上次的還要難..
上次還有2條可以有機會過的, 今次過完做到的就渣灘了..
最後 我+bill+danny 共過了4題.. (onsite champion solve了6題)
題目: http://acmicpc-live-archive.uva.es/nuevoportal/region.php?r=ce&year=2003
A - Easy Task?
data processing, bill 做的
B - Bundling
題目長得很過份.. danny看明後跟我說題目大意, 判定為不想做
C - Shortcut
我的方法是先按 x->y 和 y->x 兩種方法排序..
然後找出每點的四個方向會最先碰到哪點, 用二分的lower bound和upper bound
但由於不懂用stl的, 所以還是寫了4個binary search
雖然similar code可以copy, code length還是爆了100
在戰略上不應做呢題先的..
D - Dice contest
後來大家一起討論.. 得出「局部shortest path」的猜想
不過 code 起上來好像很煩..
E - November rain
看到這類題最先想到segment tree
但發現很多地方唔work
於是想到由左做到右的方法
便可好好利用題目中的 "there are at most 100 segments placed above any point on the ground level"!
解法是先把所有點 sort by x
用一條 list keep 住每點 x 上 segment 的高低順序
每次 maintain (add, delete) 都可以用 linear 的方法去做
可以求出
1. 每條 segment 接收了多少由天來的雨水
2. 每條 segment 會流去邊條 segment
之後便很簡單了
WA 的幾棍都是在 sorting 上有誤
如果 x 值相同, 應該是「先入後出」的
如果同是先入, 則應該由下至上的入
如果同是先出, 則應該由上至下的出
code的時侯便會明白的了..
F - Football
G - Which is next?
H - Hang or not to hang
0 idea..
I - Minimizing Maximizer
一起做的, 我寫 segment tree 的部份, 其餘由 bill 和 danny 完成
No comments:
Post a Comment