有道难题资格赛心得

好久没写关于自己的东西了。
最近参加了网易的有道难题。上周一共比了5场,2场练习赛+3场资格赛。
虽然是第一次参加有道难题,但是比赛的规则是ACM,甚至用的平台是北大的POJ,还是比较熟悉的。但唯一有一点区别的,也是很奇怪的一点,有道的OJ,注释只能写成/*...*/不能用单行注释,CE了几次。。不过CE不计算罚时,还好还好。
image

有道难题资格赛(1)

有道的资格赛每场比赛3道题,共3场,每场取前400名,共1200名进入复赛。我比了3场,大家应该能猜到,我都没进前400。但还是有收获的,第一场做出了前2题,最后只剩下半个小时做最后一题,在最后2分钟的时候做出来,但是很悲剧地在提交的时候选错了编译器,结果CE了。。虽然后面验证以后,答案也是错的。但还是觉得很遗憾。一看排名,1159。

有道难题资格赛(1) -- 我的排名

有道难题资格赛(1) -- 我的排名


有点难过,还以为做出2道题肯定能出线了呢。然后看了一下排行榜。发现和我一样做出2道题的,排在最前面的是275名,是可以出线的:
有道难题资格赛(1) -- 2道题

有道难题资格赛(1) -- 2道题


但是他们花的时间太短了,我根本不可能这么快做出来的。我这才发现,原来第一题是150分,第二题是300分,前两题加起来才450分,而第三题一道题题就有550分。换句话说,只要做出第三题就能直接出线。而且第一场比赛的第三题是有思路的,而且基本做对了,只是有几个细节问题没处理好,如果再给我半个小时,甚至是一个小时测试,一定能做出来。
image

有道难题资格赛(1) -- 统计

抱着这种想法参加了后面两场资格赛,直接拼最后一题。因为就算我做出了前两题,我的罚时还是不能入围,而且没有时间做第三题。还不如孤注一掷,直接拼第三题。
我记得第二场的第三题很有意思,套用有道的招聘讲了个故事。说的是,今年HR招人用了个新规则,HR先招到一批人,每个人都有各自的特长。部门来要人,派出部门经理。把所有的部门经理和招到的新人随机排成一列。每个部门经理可以从自己的位置开始,向左右开始挑人,但是范围不能超过另一个部门经理。如果选中了一个人,那么这个人,连同之间的人都必须带走。这些人被选中了以后,当然不能被别的部门经理选了。然后每个部门都有自己的指标和需求,得挑某些有特长的人,问一共有几种选法。
看到题目以后,没思路。我的想法是先选出一个部门经理从自己的位置向左右分别开始挑,然后下一个继续挑,再下一个...这是顺着题目的思路做,但没想出可以套用的算法...结果很悲剧,没做出来。
第三场的第三题,也是蛮有趣的题目。说的是用火柴排数字,给你几根火柴,必须全部用上,能派出几种数字组合,当然0不能被排在最前面。问这些组合对给出的数求余以后的数是质数的组合有几种。
看到题目以后,马上有思路了,首先是一个排列组合问题。每一个火柴数字,都有固定的火柴根数,用固定的总根数能排出几种数字组合。首先要解决的是每排一个数字的时候,有几种选择?而没排完一个数字以后,接下来可以选择的数字有可能跟之前会有区别。所以这有不是一个简单的全排列问题。这里面还包含了背包问题,可以想象成,火柴数字是一个货物,而总根数就是背包,必须刚好把背包装满。顺着这个思路,我很快做了出来。可是现在,我才发现,原来这道题不仅仅是这两个问题,还有一个更大的问题。因为最多一共有10000根火柴,如果全部排1的话,可以排5000位的1。这又引出一个大整数问题。还涉及大整数判断质数,必须有除法和求余运算。这下可麻烦了,准备不够充分,没有现成的大整数类可以用,从头写一个肯定来不及。。。结果。。又悲剧了。
唉,特别难过,不过也是一份很宝贵的经历。特此记录。