P8920 『MdOI R5』Variance 题解

· · 题解

题目大意

传送门

分析

其实这差不多是一道数学题。

我们先来看一下什么是方差。网上给的定义是：

方差是在概率论和统计方差衡量随机变量或一组数据时离散程度的度量。其计算方法为，序列中数与它们平均数之差的平方的平均值。

公式表示为：

S^2 = \dfrac{(x_1-\overline{x})^2 + (x_2-\overline{x})^2 + \dots + (x_n-\overline{x})^2}{n}

其中，\overline{x} 为：

\overline{x} = \dfrac{x_1+x_2+\dots+x_n}{n}

根据定义，我们可知要尽量让数据分散。即，小的尽量小，大的尽量大。

再来看看题目所给的条件

很容易可以想到，前半段我们应当全选 a 数组，后半段则应全选 b 数组，这样数据离散程度最大。图像大概是这样的：

问题便成为了：找一个位置 i，使得 a_1 \sim a_2, b_{i+1} \sim b_n 两段组成的序列，方差最大。这样，对于每一个 i，我们逐个进行枚举就行了。但是，为了将每一次计算方差的时间复杂度降到 O(1)，我们还要先对方差公式进行一下变形。

S^2 = \dfrac{(x_1-\overline{x})^2 + (x_2-\overline{x})^2 + \dots + (x_n-\overline{x})^2}{n} S^2 = \dfrac{({x_1}^2+{x_2}^2+\dots+{x_n}^2) - 2*\overline{x}*(x_1+x_2+\dots+x_n) + n*\overline{x}^2}{n} S^2 = \dfrac{({x_1}^2+{x_2}^2+\dots+{x_n}^2) - 2*\dfrac{(x_1+x_2+\dots+x_n)^2}{n} + n*\dfrac{(x_1+x_2+\dots+x_n)^2}{n^2}}{n}

题目要求的是 S^2*n^2，因此可以继续化简：

S^2*n^2 = n*({x_1}^2+{x_2}^2+\dots+{x_n}^2) - 2*(x_1+x_2+\dots+x_n)^2 + (x_1+x_2+\dots+x_n)^2 S^2*n^2 = n*({x_1}^2+{x_2}^2+\dots+{x_n}^2) - (x_1+x_2+\dots+x_n)^2

这也顺带证明了为什么 S^2*n^2 一定为整数。

现在，我们手里只要有数列的平方和以及数列的和的平方就可以求出答案了。

实现

我们预处理四个数组：a 的前缀和、a 平方的前缀和、b 的后缀和（本人杜撰的一个名词，就是从后往前的前缀和）以及 b 平方的后缀和。对于每个 i，我们将位置 i 的前缀以及位置 i+1 的后缀相加便是这个数列的总和，再带进刚才推导的公式计算就可以了。

Coding：

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e6+5;
__int128 ans, qz[MAXN], hz[MAXN], qz2[MAXN], hz2[MAXN];
int n, a[MAXN], b[MAXN];

void print(__int128 x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x < 10){
        putchar(x+48);
        return;
    }
    print(x/10);
    putchar(x%10+48);
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", a+i);
    for(int i=1; i<=n; i++) scanf("%d", b+i);
    for(int i=1; i<=n; i++) qz[i] = qz[i-1]+a[i];       //前缀和
    for(int i=n; i>=1; i--) hz[i] = hz[i+1]+b[i];       //后缀和
    for(int i=1; i<=n; i++){                            //平方的前缀和
        qz2[i] = a[i];
        qz2[i] = qz2[i]*qz2[i]+qz2[i-1];
    }
    for(int i=n; i>=1; i--){                            //平方的后缀和
        hz2[i] = b[i];
        hz2[i] = hz2[i]*hz2[i]+hz2[i+1];
    }
    for(int i=0; i<=n; i++)
        ans = max(ans, (qz2[i]+hz2[i+1])*n-(qz[i]+hz[i+1])*(qz[i]+hz[i+1]));
    print(ans);

    return 0;
}

后记

才开始写题解，请多多包涵。

最后的最后，感谢您的观看！

:)