3
20
2015
0

Codeforces Round #206 (Div. 1)

脑洞太小求治疗

A.n个排成一列的物体,每个有一个重量w[i],每次robot可以选择搬左边或者右边的物体,付出l*w[i]或r*w[i]。如果两次搬的方向相同需要额外付出ql或qr。n<=10W

题解:显然左边一段用左边搬,剩下的右边。那我们枚举一下分界点。然后就可以很容易计算了。

C.n个数a[i],要求构造一个新的b[i],使得gcd(b[i])最大。且满足a[i]-b[i]<k。n<=30W k,a[i]<=100W

题解:其实这题需要很好的转化。gcd之类的一般不具备单调性。所以我们考虑一个一个判断是否可行。

    其实只要每个数判断是否a[i]%x<=k就可以了。但这样是n^2的。所以我们考虑调和级数sigma(n/i)=nlnn

    所以对于每个数枚举倍数即可。

 

Category: codeforces | Tags: | Read Count: 364

登录 *


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

| Theme: Aeros 2.0 by TheBuckmaker.com