※ 引述《ledia (contemplation)》之铭言： : F 的 strong king 题则是预期用够好的顺序来穷举 tournament 所有可能组合 : 大部份简单的 heuristic 都会有反例, 测资有为不让 heuristic 解法答对设计过 : 但是出题教授说在出了题目之後他的学生把 close form 解出来了 : 这跟我看到这个题目的第一感其实是蛮符合的 : 只是我求不出 close form (我承认... 我无能... :~) 若不论 close form 的话, 这类需要 heuristic 或 cut 的 search 题目在这几年的比赛满少出现的 这类题目对选手也是个考验 -- 在时间有限的情况下, 该先做其他题, 还是要想不一定有效的 cut... 说不定花时间写 search 其实存在好演算法可解 若是我, 相较之下, 我大概会先写 D 吧, 感觉起来 2*16!/4!/4!/8!=1.8M node 跑起来若超过时间, 应该也在 time limit 的几倍之内 最佳化 D 似乎比较有希望 orz 要不要分享一下你们写这题的经验? (三队解出 D 的队伍, 有两个队名叫 orz ...) 回到 F, 我试了一下, branch&bound 用一些 heuristic 估计 upper bound 大约可以解到 n=30 (random input 几乎大部份都瞬间跑完, 少数要花个几秒) -- "灵感 = 经验 + 尝试 + 快速的计算能力" --- Ledia "灵感, 是实力的累积" --- untitled --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.70.142.187