题解 P6187 【[NOI Online 提高组]最小环（民间数据）】

> Ran：@dengyaotriangle @LiM_817 @Elegia 你们仨分别写个T1-T3题解吧 被 迫 营 业 /cy 乘积最大化不够直观，我个人更喜欢改成 $2(\sum a_i^2 - Ans) = \sum (a_i - a_j)^2$，也就是说这道题是要最小化相邻位置的差平方和。 首先第一个值得注意的点是本质不同的图只有 $d(n)$ 种，这是因为考虑相邻关系 $i, (i+k)\bmod n, (i + 2k)\bmod n, \cdots$，这个东西走到一个环会需要 $n/\gcd(n, k)$ 次，也就是说得到了 $\gcd(n, k)$ 个相同大小的环。 首先我们讨论 $k=1$ 的答案。~~这个都[出烂](https://loj.ac/problem/520)了。~~ 将 $a$ 排序后，假设 $n\ge 2$，考虑将 $i$ 和 $i+2$ 连边，然后将 $1\rightarrow 2, (n-1)\rightarrow n$ 连边，这样是一个环，也容易发现它是最优的。这个东西为何是个下界呢？我们考虑把乘积看成面积，那么第 $i$ 个点就在 $(a_i, a_i)$ 上，我们要最小化所有走路扫过的以端点形成的正方形面积之和。容易分析得到通过直线 $x=a_i$ 和 $y=a_j$ 切出来的每一个小矩形被经过的次数都达到了下界。 接下来考虑每个环长度为 $g$ 的情况，容易猜到我们将 $a_1 \sim a_g$ 放到第一个环里，$a_{g+1} \sim a_{2g}$ 放到第二个，以此类推。接下来简单证明一下： 1. 注意到对于这个构造，如果加入一个 $\min \sim \max$ 之间的数，答案只会变小。 2. 如果将 $\min$ 或者 $\max$ 删去，答案也会变小。 3. 如果两个环的取值是交叉关系，设它们的值域是 $[l_1, r_1], [l_2, r_2]$，满足 $l_1 < l_2 < r_1 < r_2$，那么交换 $l_1, r_2$ 所属的值，显然每个环都加入了一个新的值，并去掉了极值。因此答案变小。 3. 如果两个环的取值是包含关系，设值域是 $l_1 \le l_2 \le r_2 \le r_1$，那么这个方案甚至不如将这些数排在一个环里，因此这个方案必然不优。 根据以上四条，环必然是按顺序放置的。 我们对每个 $g|n$ 进行计算，复杂度为 $\Theta(nd(n))$，在 $n\le 2\times 10^5$ 时 $nd(n)$ 大概是 3e7，可以通过此题。 事实上还有更快的方法，我们考虑一个方案和 $k=1$ 的方案的差值，只有两个相邻的环之间的地方有修改，因此我们实际上可以在 $\Theta(n/g)$ 的时间内计算出 $g$ 对应的答案。这一方法的复杂度 $\le nH_n = \Theta(n\log n)$。 综上，本题可以在 $\Theta(nd(n))$ 或 $\Theta(n\log n)$ 的时间内通过。