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

2020-03-07 13:42:40


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)$ 的时间内通过。