自动搬运

查看原文

来自洛谷，原作者为

	fjzzq2002 **

搬运于2025-08-24 21:51:30，当前版本为作者最后更新于2017-03-19 22:06:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道常规的提交答案题，连checker都给出了，是不是非常良心啊，C++选手连计算几何都不用写，直接拷一波checker都行。

1：我们可以看出圆心全在矿工的西南方向，直接进行两次135°的抓取即可。

2：这个点只有一个圆，直接对准圆心瞄准就行。

3：这个点有两个圆，一个圆是负权的，一个圆是正权的，我们要想办法躲过负权圆进行射击，大致方式是移动后作负权圆的切线。我们可以发现这个移动需要的时间是个单峰函数，三分一下就可以求出极值点了。

4：这个点看起来就不是很随机，而且人不能移动。看起来x坐标呈下降趋势，y坐标呈上升趋势。画个图可以发现矿工到任何圆上任意一点的连线都是不交的，那么这就是一个简单的背包问题。容量可能为小数，那么我们随便乘一个大数取整跑背包即可。注意乘完大数不能四舍五入，而应该下取整，如果跑出来的结果没有取整之前没有爆容量就说明大数是足够大的，证明略。

5、6：这两个点看起来奥妙重重，人仍然不能移动。根据出题人的智商我们可以猜到这仍然是一个背包问题，画个图可以发现矿工对每个圆的两条切线，有很多是重合的，将重合的分为一组，那么不同组间矿工到圆上的连线仍然不交。我们发现同一组的一定要一个一个打，那么这就是一个分组背包问题，同样乘一个大整数跑背包。注意第六个点可能会卡精度，乘的数可能要大一些。

7、8、9、10：这些点全是随机的。第7个点相对小适宜手玩，8、9、10三个点就看大家的乱搞水平了，模拟退火、爬山、遗传等算法应该都能拿到相当高的分数，标解似乎也不是特别优，应该十分容易艹掉。

这里讲一下标程的傻逼做法，对于每个圆在圆周上取21个点，加上圆心一个点，把每个点存成pair(坐标,编号)，然后对于一个这样的顶点序列依次打过去，如果第二关键字编号的圆已经被打过了，那么就忽略，否则考虑打。直接打显得很蠢，浪费了移动功能，那么我们可以类似3号点三分移动到的位置然后打。开始我们把这个顶点序列随机打乱，然后每次随机若干对交换，如果比原来答案优（价值或剩余时间高）则接受。虽然这样不是特别优，但是本着给大家送分的精神主要是懒就只写了这个做法，更优秀的做法大概还要保留若干种群进行随机交配，艹标解的同学估计就是这样做的。