今年好不容易把每一题写好写满，满分完成比赛 题目列表：http://www.puzzleup.com/2015/archive/ 我也来分享一下我的心得 http://www.puzzleup.com/2015/puzzle/?2 我觉得最有趣的是Q2，我是使用 Pólya enumeration theorem https://en.wikipedia.org/wiki/Pólya_enumeration_theorem 定理的描述有一些代数的术语，但其实用起来不会很难 有空的时候我可以再补详细的说明 另外帮补一下缺的答案 ※ 引述《LPH66 (-6.2598534e+18f)》之铭言： : 这次我自己因为各种原因跳掉了三题，第四题还因为少看一个条件多送一次被扣 20 分 : 所以最终只有 1874 分，连前五十名都没上 (望 : 以下是我的参考答案: : (86%) 1. 7967/1069335 : (85%) 2. 333 : (82%) 3. 985432107 : (90%) 4. 538171062 : (63%) 5. 60 : (97%) 6. 32 (30%) 7. 24 : (86%) 8. 6021 : (取消)9. 1908 : (92%) 10. 64570081 : (92%) 11. 84 : (92%) 12. 2840 (79%) 13. 117649 : (96%) 14. 19 : (80%) 15. 1436 : (83%) 16. 14 : (91%) 17. 23751 : (67%) 18. 9574083 (90%) 19. 294879 : (84%) 20. 5 : Q9 似乎是题意不清的原因所以取消了 : Q7 跟 Q13 两题我没做的原因是因为这两题问的是一类图论难题的特例 : Q7 问的是最小支配点集 (这题型 2014 就出过了: 2014 Q10 #1KB5GXpU) : https://en.wikipedia.org/wiki/Dominating_set http://www.puzzleup.com/2015/puzzle/?7 第7题我也觉得非常难，是靠Google大神的 http://mathoverflow.net/questions/210358/four-dimensional-rook-domination : Q13 问的是最大独立点集 : https://en.wikipedia.org/wiki/Independent_set_(graph_theory) : 之所以是难题的原因是一般来说他们都是 NP 完全 (意思是连用程式都没有捷径) : (关於 NP 完全的简介可以去找看数学版这篇讲踩地雷的我的文章: #1GPBcQPe (Math) ) : 虽然这两题的图都是特别型式的图，不过 (ry http://www.puzzleup.com/2015/puzzle/?13 第13题倒是可以自己推出答案 7^6 ，以下是证明 因为合乎题目条件的集合中，任两个元素的前6位都不能完全相同 (否则最多只差1位) 而前6位就只有7^6个组合，所以不可能有超过 7^6 个元素 接着要构造一个大小7^6且满足原题条件的集合 令A=0,B=1,C=2,D=3,E=4,F=5,G=6 任何一个7-letter code都可以对应到一个值，就是每一位对应的数相加 例如GFEDCBA就是6+5+4+3+2+1+0=21 我们取所有相加是7的倍数的code成一个集合，这个集合大小正是7^6且任两元素不相似 首先，因为前6位乱取有7^6种组合 根据除7的余数，第7位总可以补一个让它总和是7的倍数，所以有7^6个 再来，任两元素都不会只差1位 因为在其他6位相同，只有1位不同的情况下，不可能他们总和余7会相同 故得证 : Q19 单纯只是繁题，那阵子又比较忙所以没时间写程式 (死) : 其他的难题: Q5 我後来找到了了巨人的肩膀站 XD : https://en.wikipedia.org/wiki/Crossing_number_%28graph_theory%29 : 如维基百科所说，现有的理论对这题要问的东西在完全图上只有到 K12 有确定 : 其他都是上界；而这题问的是 K10 所以就直接代结论了 XD http://www.puzzleup.com/2015/puzzle/?5 Q5我也是Google XD : Q18: 这题最後还是 Programup 了，好在简单分析可以确定答案是七位数 : 所以搜起来并没有那麽难就是 http://www.puzzleup.com/2015/puzzle/?18 这次有满多题都是Programup，有点可惜 Q18在改题目前我有手算出答案(原本是any "two" adjacent digits) 改成3位我就不会了，又只好写程式XD 而且以现今CPU的速度，就算不做任何分析，完全暴搜10!的排列也只是秒杀 其他有几题至少还需要例如DP的技巧 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 206.71.243.2 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/puzzle/M.1451665944.A.114.html