有道难题资格赛心得

好久没写关于自己的东西了。
最近参加了网易的有道难题。上周一共比了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。这又引出一个大整数问题。还涉及大整数判断质数,必须有除法和求余运算。这下可麻烦了,准备不够充分,没有现成的大整数类可以用,从头写一个肯定来不及。。。结果。。又悲剧了。

唉,特别难过,不过也是一份很宝贵的经历。特此记录。

5 comments

  1. 有些连载的漫画是下载不到的,例如:漫点的火影499和500,笨狗漫画的捕杀天使,其他的有些忘记了.
    你的程序做得很好,但bug始终都还是有的,你可以给我看看它的code吗?或教我怎么弄得,我想学你那样编程

    1. @Pandaandrew
      最近实在太忙了,都没时间来维护漫画下载器。。
      我会持续做下去,慢慢把BUG都修复的。
      很抱歉的告诉你,我的软件是免费的,但并没有开源的打算。

  2. 好复杂呢
    关于那个选人的问题 觉得题目稍微有点问题 就是经理可不可以不选?或者说其他人选完之后又谢经理就没有人可以选算不算一种选择方式?还是说经理必须选到人才算一种选择方式?
    画了几个圈圈叉叉 打算弄出个数列的式把a和b代入 不过发现只要上面那个问题不解决我就做不了下一步 还是杯具
    算了 反正我高数也就及格上那么一点点 做不出来顶多遗憾自己笨 不伤心不伤心
    对了 你的漫画软件做的很不错 本来只想踩踩感谢一下 结果变成来算算术的了~哈~~

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">