※ 引述《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