※ 引述《smartboy (小光光)》之銘言：
: ※ 引述《JonathanWang (小尹)》之銘言：
: : 題目是 2000 中歐的題目
: : http://contest.felk.cvut.cz/00cerc/solved/index.html
: : (附測資)
: 網站上有各題的參考解答, 也能找到當時比賽各隊的送的 code
: 建議大家可以再想想練習賽沒做出來的題目,
: 或是看看參考解答.
: 參考解答有 C 跟 Pascal 兩種版本, 各是不同人寫的
: 有些題也許看 Pascal 版本比較好懂.
: A
: B 這題其實並不難. 對 xy 方向的平面看, 計算其下方的面積, 朝上加朝下減.
: C,Pascal 兩個差不多, Pascal 寫得比較簡潔
: C 使用階差法(還是怎麼稱呼?)即可, 因此程式碼滿短的
是階差數列沒錯,一般在數學競賽會用來解難解的遞迴解
: D
這一題我題目看很久,弄懂了卻不想寫,煩人CG+BFS
: E C 版先 parse build tree, 再 traverse 一遍印出來.
: Pascal 版則直接在計算式中找成對的括號, 再把多餘的去掉
: F
: G 對每一位數遞迴可能的答案, 若 white/black 過多或太少則 cut
: 不過我還沒想通這樣會不會有可能跑很久,
: 有沒有誰可以給個簡單的證明或計算量的 upper bound?
一般這種題目有兩類,一種只有唯一解,可以巧算出答案
一種是很多解,一定要用搜的,至於upper bound的算法應該不好算,
出題想出worst case出來除非規模很小,否則是不太可能的,至於random
生的測資想亂槍打鳥中worst case的機率根本微乎其微
: H
: I 用 DP 做, 想看參考解答的話建議看 Pascal 版的
: 順便問, 若舉辦讀書會讀"算法藝術與信息學競賽", 有人有興趣嗎?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.250.175