题解 P3723 【[AH2017/HNOI2017]礼物】

2018-12-30 16:16:22


显然两个手环增加非负整数亮度,等于其中一个增加一个整数亮度。

那么只让一个手环改变亮度即可。设亮度改变了 $c$ ,新的差异值为 $\large\sum\limits_{i=1}^n(a_i-b_i+c)$ 。

拆开容易得到 $\large\sum\limits_{i=1}^na_i^2+\sum\limits_{i=1}^nb_i^2+nc^2+2c\left[\sum\limits_{i=1}^n(a_i-b_i)\right]-2\sum\limits_{i=1}^na_ib_i$ 。

前面两项是定值;带 $c$ 的两项是关于 $c$ 的二次函数,而且因为 $n>0$ ,所以有最小值,可以直接算出来。

现在的问题是最后一项,我们要求 $\large\sum\limits_{i=1}^na_ib_i$ 的最大值。

这个形式和卷积很像。将 $a$ 倍长(因为是个环),将 $b$ 翻转,然后用 $\mathrm{FFT}$ 求出 $g=a*b$ ,要求的那个最大值就是 $g$ 的第 $n+1$ 项到 $2n$ 项中的最大值。

代码见blog