2019.8.13签到

得到了一道有趣的题目,在此珍藏起来。

题意:平面上有N[1,40]个点,每个点有一个整数坐标(X[-1e9,1e9],Y[-1e9,1e9]),这些点成为“收割点”。从原点出发,到一个不是收割点的坐标,设为圆心。你可以到达的收割点的范围必须在这个已知半径R[1,100]的圆内。从圆心出发,要求恰好经过M[1,1e4]次收割点后回到圆心,每次经过的收割点必须异于上一次经过的收割点,求从原点开始到圆心结束的最小路程。(中括号里是数据范围)

题解:当圆心固定时,对范围内的点做M-1遍类似Floyd算法的算法,为了保证恰好M个点,f[i][j]=min(f[i][j],f[i][k]+f[k][j])的第一个f[i][j]要开一个新的数组作为中转站。又因为动态转移方程符合矩阵乘法的形式,所以用矩阵加速来优化M-1遍循环,使其降为logM。得到的f[i][j]表示i到j恰好经过M个点的最短路。枚举起点和终点,比较这两点到圆心的距离与最短路距离之和,取最小值。

但圆心并不固定。我们发现圆心不固定的情况下,包含的点集合可能相同,如果不相同,只能重新计算f数组了。如果点集合相同,变化的就只有圆心的位置,即起点到圆心、终点到圆心、原点到圆心的距离之和。在起点、终点、原点组成的三角形中,同一个y坐标,x坐标增大的过程中,距离之和先变小后变大,符合单峰函数,我们用枚举y坐标、三分x坐标的方法做。由于最优的圆心可能跑到不包含当前点集合的某个点的位置(也是因为这个原因,费马点不好用),所以我们在程序最开始就要预处理出同一个点集合的圆心坐标集合,这里对于每一个y坐标,保存x坐标的区间会方便一些。预处理帮助我们确定三分的范围。

做完了大优化,我们还可以做一些小优化。比如,某一个点集合的点数为1,直接舍弃。点数为2,用简单的四则运算和比大小就能求出答案。还有,点集合之间距离隔太远,代码不好实现,可以离散化坐标。

一个题目竟然包含了四种算法,妙不可言!

发表评论

电子邮件地址不会被公开。 必填项已用*标注