Facebook Hackercup 2012 Round 1

我想不开始搞搞,这个窝只会越来越荒废。晚上打算做做1月29号的这场比赛,一开始看成两点开始的比赛,确实如此,不过持续24小时没看到,幸亏没有爬起来做。29号的时候想了下,然后用了点力,终于搞完了,但愿别挂。好久没有搞题目了,希望一直搞下去,简单说说吧。

 

Squished Status

给定一个字符串和M,问能切成多少种由不带前导0且数字不大于M的数字组成的序列,其中字符串长度小于1000, M<=255。|
最弱一道题,简单的$O(N^2)$的DP即可,dp[i]表示前i个字符的方案数,然后搞。

update : 由于一个傻逼的下标写错,导致挂了!

Checkpoint

实际上已知

  • $C_{x_1 + y_1}^{x_1} \times C_{x_2 + y_2}^{x_2} = S$

  • $x_1+y_1>0, x_2+y_2>0,x_1+x_2>0,y_1+y_2>0$

  • $S<=10^7$

求 $\min x_1+y_1+x_2+y_2$

由于S很小,可以暴力枚举 S = u * v, 下面即求 $u = C_{x_1 + y_1}^{x_1}$ 然后求 $\min x_1+y_1$
我们可以从1到107暴力枚举$C_y^x$,当y确定,随着x的增大,组合数是先增后减的,且是对称的。
对于$C_y^x < C_y^{x-1}$ 我们可以退出,对于$C_y^x < 10^7$ 我们也可以退出,然后用map记录每个u能达到的最小y即可,默认值为u($C_u^1$)。

Recover the Sequence

对1到N的一个排列进行归并排序,给出每次比较的结果(取左边的数则为1,右边的数则为2),要求通过比较结果数列还原原始数列。

这题不错,想法也挺好玩的。因为有了比较结果序列,那么我们可以知道每次归并数列的变化情况,又我们知道最终的数列为[1,2,3, .. n],那么我们可以拿位置数列[1,2,3, .. n]去重放归并的过程, 然后得到一个位置的排列, 他等于 1, 2, 3, ...n 这个排列,映射一下就得到原来的数列了。

 

这次主要是时间比较长,所有有时间做,接下来也得积极参加才行。回头还希望能多写一点技术方面的东西,总结总结才好,共勉。

update 2012.1.30 14:43
由于最简单那题的傻逼错误导致没能晋级了,真悲剧!!

ps: 感觉用tex数学公式编辑看起来有点不相称,暂时不知道怎么搞漂亮些。