Facebook Hackercup 2012 Round 1

code6 posted @ 2012年1月30日 10:30 in algorithm , 1677 阅读

我想不开始搞搞，这个窝只会越来越荒废。晚上打算做做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数学公式编辑看起来有点不相称，暂时不知道怎么搞漂亮些。

Small_feed 评论 (5)
1
[回复]
lazycat 说:
2012年1月30日 11:20

肿么都是数学题，，求python或者各种脚本技术贴

2
[回复]
How to Cancel Netfli 说:
2022年8月09日 15:08

Netflix has become one of the world’s largest streaming services. It is an absolute beast when it comes to providing some of the best streaming TV series and movies online. The reason it has become such a huge trend and hype is due to growth in the modern gadgets and better Internet all across the world. How to Cancel Netflix But at the same time people have made a change in their mindset so as to seek comfort and entertainment from their homes, phones or laptop without the hassle of going to movies which has become a boon for some people.

3
[回复]
SEBA 7th Class Boo 说:
2023年7月27日 17:47

SEBA Follows CBSE Curriculum These Textbooks are Updated as per the Syllabus Prescribed by Assam Board. Students of Assam Class Should follow Prescribed Textbooks while Preparing for Exam. Our Team Refer to the Respective Subject Textbook while Preparing the Final Important questions. Students Best Practice Study Materiel about Assam 6th Textbooks 2024 are the Fact that they are so Comprehensible that SEBA 7th Class Books 2024 it does not require the aid of a Subject Literate.Board of Secondary Education, Assam commonly known as SEBA Regular organization High School Education, Assam State Textbook Production and Publication Corporation

4
[回复]
civaget 说:
2024年1月11日 23:06

not everyone would need a nose job but my girlfriend really needs some rhinoplasty coz her nose is kind of crooked` how do i make google docs dark mode

5
[回复]
civaget 说:
2024年1月18日 02:56

opga's versatility allows you to choose your preferred experience, whether it's a therapeutic massage or an intimate journey in a Kiss Room.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter