提交答案YYDS！

hz20210123 · 2023-08-30 13:01:47 · 题解

咳咳，众所周知，给了 checker 就照着模拟吧。

题目传送门

题意简述

• 矿工先生位于坐标轴上原点与点 (2s,0) 的线段上移动，向 x 轴下方发出采矿装置（近似看成以矿工为端点的射线），抓取和这条射线最早相交的圆。同时，若这条射线不与任何圆相交，则视为无效操作。
• 移动与抓取都需要时间：移动 1 个单位距离需要花 k1 的时间，将一次有效抓取的距离定义为抓取到的圆与射线较近的交点与矿工的距离，有效抓取每1单位距离需要花费 k2 的时间（无效抓取将会被忽略）。
• 无论此次抓取是否有效，矿工都只会进行 2n 次操作，多余操作自动忽略。

题目分析

根据对应的测试点选择策略！

Task 1 ~ 2

对准圆心瞄准即可。

Task 3

这个点在 Task 2 的基础上增加了一个价值小于 0 的圆，做法可以为查找与负权圆相切并经过正权圆的路线。

Task 4

在这个测试点中，由于矿工不能移动，所以只考虑如何使获得的价值最大。可以画出图形。不难发现，所有从矿工到任意圆的射线都不经过其它圆。于是就成了受限制的 01 背包问题，按模板即可。

Task 5 ~ 6

矿工仍然不可以移动。与 Task 4 的区别在于，矿工到大部分圆的射线都与其它圆相交。做法为将相交的圆依次分组，然后进行 01 背包操作。

Task 7 ~ 10

这些就要动用真本事了，因为完全随机了！就照标签来吧，我用的模拟退火做的，遗传应该也能过但我没试（怎么会告诉你我不会呢qwq）。

看楼上提到了标解，但本蒟蒻觉得标解不算优因此没写，望见谅哟。代码写出来其实也挺不容易的，为了避免那些不诚信者，就不贴代码啦。