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的直线,一直往下压所碰到的凸包上的一个点!!!

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

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

Ural 上5道hardest problem的题解。。。 第二弹

。。。纯除草。。貌似都是上个月做的题目。。。最近完全在颓废。。。

Goat in the Garden 4 :二分答案之后,我们只需要判断3种点:到两线距离相等的,到两点距离相等的,到一点一线距离相等的即可。

Time Limit Exceeded :模拟题,认真读请题意即可

 

Goat in the Garden 6:跟4一样,只需要考虑几种边界上的情况,全部列出暴力判断即可。

 

Death Star 2:首先考虑一个向量v,一个包含v的向量空间中离某点T最近的点p,p->T这个向量必然于v垂直(为啥你脑补一下就知道了),这样就能算出最近点,然后列出方程,可以将剩下的问题转化成一个2次多变量函数的最小值,就傻逼了。

 

Space Poker 3:枚举所有可能的community cards情况,之后进行dp即可,dp的状态是每个数量的牌种类各有几个。Java需要常数优化才能过

我以前出的一套CTSC模拟题 已传至BZOJ~~

很久以前跟某校一起集训的时候出的。。

当时就说要放上来。。结果忘了。。

那就发一下吧。。

连接发不上来。。。自己去我的skydrive网盘看吧。。叫problems

标程和题解不发,数据太大了懒得传。。就当娱乐看看吧

 

第三题的条件中不是|a-b|而是a-b才对。。打错了

题目相当水。。比赛的时候大家都有200分以上,有3个人AK了

 

题目已经+到BZOJ上。。大家可以自己去虐

THU集训吐槽

去这个集训打酱油了。。。。。。

跟超哥住一个房间,超哥每天都说啊,考挂了考挂了,然后他就rank2了。。。

wqs每天都屠狗一样的屠题目。。。总分破天际。。4天有3天rank1。。实在太屌了!!!!!!!!然后在王宏教授讲下次IOI在Italy的时候,wqs果断穿着后面标着大大的Italy的衣服,表示他已经被内定了!!!!!!!!

wqs屠了全场之后还去玩PKU的学姐们,我等屌丝只能给高富帅跪了。。。

第一天我考场犯2。。。。第二天我考场犯2。。。。第三天我考场犯2。。。第四天我考场犯2。。。。。

然后我就回家了。。。。