[NOIP2021] 方差

WeLikeStudying · 2021-11-25 22:12:50 · 题解

• 多写题解从我做起。
• 勿做斜杠青年从我做起。
• 希望作者不要爆零。

题意

• 题目链接。
• 给定长度为 n 的非严格递增正整数数列，a_1,a_2,\cdots,a_n。
• 每次可以选定一个 1< i< n，把 a_i 变成 a_{i-1}+a_{i+1}-a_i。
• 可以进行无限次操作，求可能的数列方差的最小值乘 n^2 的结果。
• 后面记 a_i 的最大值为 A。

思路

• 看到这么多限制就要想结论。
• 首先有一个被强调千万次的结论：设 \overline{x^2} 为 a_1^2,a_2^2,\cdots ,a_n^2 的平均值，\overline{x} 为 a_1,a_2,\cdots,a_n 的平均值，则 s^2=\overline{x^2}-\overline{x}^2。
• 具体可以在这道题中得到解释。
• 然后容易发现特殊性质：设 a_i' 为变化后的，a_i 为变化前的，则： a_i'-a_{i-1}=a_{i-1}+a_{i+1}-a_i-a_{i-1}=a_{i+1}-a_i a_{i+1}-a_i'=a_{i+1}-(a_{i-1}+a_{i+1}-a_i)=a_i-a_{i-1}
• 也就是本质上相当于交换差分数组，也就是设 b_i=a_{i+1}-a_i，相当于求任意交换 b_i 后还原出 a_i 的方差最小值。
• 有一个 O(n!) 的暴力可以立刻打出来。
• 暴力实现。
• 然后下一步就是思考。
• 忽然想起：方差是和中心偏离的程度，用来衡量一批数据的波动大小。
• 于是我们思考，数据会长什么样子，使得它趋近于某个值。
• 由于数列 a 始终是递增的，情况并不难想。
• 我们发现，当差分数组是这样的时候：（也就是存在 b_i 使得 b_1\ge b_2\ge \cdots b_i 且 b_i\le b_{i+1}\le\cdots\le b_{n-1}）
• 因为这个时候，整个 a 数列长这样（即趋近于中间的某个数）：
• 因为其它情况显然没有这个集中。
• 就是暴力也能弄出一个 O(n\cdot 2^n) 的算法吧。
• 基于性质的暴力实现。
• 不过这道题值域这么小找到性质就可以进行动态规划了。
• 先将差分数组排好序。
• 设 f(i,u,v,S) 为使用 b_1,b_2,\cdots b_i 的差分数组，以中间为 0 计算，左边已经下降到 -u 右边已经上升到 v，总和为 S 的情况下的平方和最小值。
• 有初始状态： f(0,0,0,0)=0。
• 有转移状态： f(i,u,v,S)+(v+b_{i+1})^2\rightarrow f(i+1,u,v+b_{i+1},S+v+b_{i+1}) f(i,u,v,S)+(u+b_{i+1})^2\rightarrow f(i+1,u+b_{i+1},v,S-u-b_{i+1})
• 不过很容易发现这是不好的，比如 S<0，难以维护，发现只要 v-u 相等可以一起算，比较好一点的做法是：
• 设 f(i,j,S) 为使用 b_1,b_2,\cdots b_i 的差分数组，以左侧为 0 计算，右边已经上升到了 j，且数组总和为 S 的数据平方和最小值。
• 有初始状态 f(0,0,0)=0。
• 有转移状态： f(i,j,S)+(j+b_{i+1})^2\rightarrow f(i+1,j+b_{i+1},S+j+b_{i+1}) \rightarrow f(i+1,j+b_{i+1},S+b_{i+1}\times (i+1))
• 然后惊喜地发现第二维可以消掉，设 s(x)=\sum_{i=0}^xb_i，设 f(i,S) 为使用 b_1,b_2,\cdots b_i 的差分数组，以左侧为 0 计算，数据总和为 S 的数据平方和最小值，别笑，我真滴是这样一步步推的。
• 有初始状态：f(0,0)=0。
• 有转移状态： f(i,S)+s^2(i+1)\rightarrow f(i,S+s(i+1)) f(i,S)+2\times b_{i+1}\times S+b_{i+1}^2\times(i+1)\rightarrow f(i,S+b_{i+1}\times (i+1))
• 发现 S\le n\cdot A 恒成立，因此时间复杂度和空间复杂度都是 O(n^2\cdot A) 。
• 而 f(i,S) 中的 S 开到 i\cdot s(i) 即可。
• 代码实现。
• 滚动数组可以优化一维使得空间不太紧张。
• 代码实现。
• 就这么 AC 了，测试数据也太水了……吗？
• 思考一下当 n>A 的时候，b_i 数组的前面会有一大堆 0，实际有效的转移个数不会超过 A。
• 所以更精确的时间复杂度是 O(n\cdot \min(n,A)\cdot A)，空间复杂度是 O(n\cdot A)，可以通过本题。
• 加了这个细节，出题者还算用心。