题解：AT_abc448_f [ABC448F] Authentic Traveling Salesman Problem

· · 题解

前言

赛时想到做法，由于 \dfrac{4\times 10^{14}}{len}+6\times 10^4\times len 中上面算成 10^{28} 了，随便写了个块长没过，然后觉得思路没前途就放弃了，痛失前 200 名。应该没有别人会犯这种错了。

做法

首先考虑按照 x 排序，但是这样的话可能相邻两个点虽然 x 很近但 y 很远。

所以考虑先按照 x 分块，块内按照 y 排序。

分析一下复杂度，如果块长为 len，则共有 \dfrac{2\times 10^7}{len} 个块。每个块内，考虑最劣情况，相邻两个点之间 x 坐标需要跑一整个块长，一共要跑 n 次，总计就是 n\times len。

考虑块间的距离，从一个块到另一个块最劣可能需要跑一整个 y 轴，共 \dfrac{2\times 10^7}{len} 个块，所以这里是 \dfrac{4\times 10^{14}}{len}。

两部分总和就是 \dfrac{4\times 10^{14}}{len}+6\times 10^4\times len，使用均值不等式即可求得最小值为 \sqrt {24\times 10^{18}}<10^{10}，然后取块长为 \dfrac{2\times 10^7}{\sqrt n} 即可。

题目要求说从 1 号点开始，这样走到最后一个块时需要回到第一个块，这一部分是 2\times 10^7。但这一部分在 10^{10} 的尺度下微不足道，忽略即可。

排序时，编号为奇数的块按 y 正序排；编号为偶数的块按 y 逆序排，这样在前一个块中走到头后，可以在下一个块中再走回来。

赛后听同学说才反应过来，其实这个 \vert X_i-X_j\vert+\vert Y_i-Y_j\vert 也可以理解成莫队中操作 (X_i,Y_i) 要移到 (X_j,Y_j) 的过程，所以以上内容同时证明了莫队复杂度。

代码

赛后改了个块长就过了，真绷不住了。

赛后提交记录。