TopCoder SRM 526.5 题解

250:

做法很多,我用的是最暴力的一种,考虑一个数x,它如果是完全平方数,那么它下一轮就跪了,否则它下一轮的位置是

x-sqrt(x),sqrt(x)取下整。

由于没删掉的数之间的顺序不会变。

我们显然是要找到一个最大的数,它在变成1之前没有跪,那么我们从n到1暴力判断。。。。

这个速度很慢。。Java会T。。改成C++就能卡过。。。

500:

注意到期望的平方不具有可加性,咋办呢。。

注意到Sum(a1+..an) ^2 = Sum(ai*aj){i in [1,n],j in[1,n]}

那么一个点上的和平方的期望,就等于每对个range在这个点上相遇的期望次数的和

后者是可以通过简单的数学计算得出的。

 

1000:

确保你会做http://community.topcoder.com/stat?c=problem_statement&pm=8587这题

SRM396 1000pt

我们要找出一个最大的,独立的子空间,使得Sum(Red)*Sum(Blue)最小

我们考虑所有这些子空间,它们的(sumRed,sumBlue)组成的点集合。

那么我们可以注意到,答案只可能在这个点集合的凸包上!

那么我们来办法搞出凸包上的所有点就行了。。

打个比方说,我们给一个斜率k,然后把所有信封按red*k+blue排序,然后用SRM396 1000pt的做法

我们就能得到一个最大独立子空间,它的k*sumRed+sumBlue最小

这意味这,它就是斜率k的直线,一直往下压所碰到的凸包上的一个点!!!

根据标程我们只要搞出所有有可能成为答案的斜率,计算即可。。

不过我随机了很多斜率。。也过了。。

9 thoughts on “TopCoder SRM 526.5 题解

  1. 具體說,維護兩個數:一個是次數的期望,一個是分數(次數平方)的期望,設為ec和es。而落到該點概率為p的話,就是ec’ = ec + p; es’ = es + p*((ec+1)^2 – (ec)^2);然後就可以了。

  2. 那道250的题当时连暴力都不会,被憋着找规律,也不知道是不是最简单的,还盼高人指点呀~方法在这里http://larlyii.blog.163.com/blog/static/2013791832011112685156995/ 

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>