题解 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 的答案。这个都出烂了。

将 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 所属的值，显然每个环都加入了一个新的值，并去掉了极值。因此答案变小。
  4. 如果两个环的取值是包含关系，设值域是 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) 的时间内通过。