我想不开始搞搞,这个窝只会越来越荒废。晚上打算做做1月29号的这场比赛,一开始看成两点开始的比赛,确实如此,不过持续24小时没看到,幸亏没有爬起来做。29号的时候想了下,然后用了点力,终于搞完了,但愿别挂。好久没有搞题目了,希望一直搞下去,简单说说吧。
Squished Status
给定一个字符串和M,问能切成多少种由不带前导0且数字不大于M的数字组成的序列,其中字符串长度小于1000, M<=255。|
最弱一道题,简单的的DP即可,dp[i]表示前i个字符的方案数,然后搞。
update : 由于一个傻逼的下标写错,导致挂了!
Checkpoint
实际上已知
求 。
由于S很小,可以暴力枚举 S = u * v, 下面即求 然后求 。
我们可以从1到107暴力枚举,当y确定,随着x的增大,组合数是先增后减的,且是对称的。
对于 我们可以退出,对于 我们也可以退出,然后用map记录每个u能达到的最小y即可,默认值为u()。
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数学公式编辑看起来有点不相称,暂时不知道怎么搞漂亮些。