脑洞太小求治疗
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
所以对于每个数枚举倍数即可。
评论 (0)
