※ 引述《JonathanWang (小尹)》之銘言：
: ※ 引述《JonathanWang (小尹)》之銘言：
: : 下次希望什麼時候? 下週二下午嗎? (8.17)
: 題目是 2000 中歐的題目
: http://contest.felk.cvut.cz/00cerc/solved/index.html
: (附測資)
網站上有各題的參考解答, 也能找到當時比賽各隊的送的 code
建議大家可以再想想練習賽沒做出來的題目,
或是看看參考解答.
參考解答有 C 跟 Pascal 兩種版本, 各是不同人寫的
有些題也許看 Pascal 版本比較好懂.
A
B 這題其實並不難. 對 xy 方向的平面看, 計算其下方的面積, 朝上加朝下減.
C,Pascal 兩個差不多, Pascal 寫得比較簡潔
C 使用階差法(還是怎麼稱呼?)即可, 因此程式碼滿短的
D
E C 版先 parse build tree, 再 traverse 一遍印出來.
Pascal 版則直接在計算式中找成對的括號, 再把多餘的去掉
F
G 對每一位數遞迴可能的答案, 若 white/black 過多或太少則 cut
不過我還沒想通這樣會不會有可能跑很久,
有沒有誰可以給個簡單的證明或計算量的 upper bound?
H
I 用 DP 做, 想看參考解答的話建議看 Pascal 版的
順便問, 若舉辦讀書會讀"算法藝術與信息學競賽", 有人有興趣嗎?
--
"聲音是聲音, icon 是 icon, 用 icon 來表示聲音的結果,
就是不知道哪個是聲音, 哪個是 icon. "
小光光
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.70.142.187