牛客网提高组第二场---solution

T1 方差

根据题目要求将式子先写出来
注意下面式子中的 $n$ 全部都是 $n-1$
$$
egin{aligned}
ans&=n^2 imes frac{1}{n} imes sum_{i=1}^{n}left(b_i-overline{b} ight)^2
\&=n imes sum_{i=1}^{n}left({b_i}^2-2b_ioverline{b}+{overline{b}}^2 ight)
\&=n imes left(sum_{i=1}^{n}{b_i}^2-2overline{b} imes sum_{i=1}^{n}b_i+n imes overline{b} ight)
\&=n imes sum_{i=1}^{n}{b_i}^2-n imes 2overline{b} imes sum_{i=1}^{n}b_i+n imes n imes overline{b}
\&=n imes sum_{i=1}^{n}{b_i}^2-2 imes left(sum_{i=1}^{n}b_i ight)^2+n imes sum_{i=1}^{n}b_i
end{aligned}
$$
上面最后一步化出来的式子就是最简的式子。
我们可以通过一些预处理将其 $ ext{O}(1)$ 求出来。这样总的时间复杂度是 $ ext{O}(n)$ 的，还是很优秀的复杂度。

附上代码

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 1e5+3;
int n;
long long a[maxn], sum, POW, ans;
int main() {
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%lld", &a[i]), sum += a[i], POW += a[i] * a[i];
    for(int i=1; i<=n; i++) {
        long long tmp = sum, ppp = POW;
        tmp -= a[i];
        ppp -= a[i]*a[i];
        ans = ppp*(n-1) - (2*tmp*tmp) + (tmp*tmp);
        printf("%lld", ans);
        if(i != n) printf(" ");
        else printf("
");
    }
}