【题解】[牛客网NOIP赛前集训营-提高组（第二场）]A.方差 前缀和

题目链接

我们把方差公式进行化简。记 $sum_1$sum1​ 为每个数的前缀和，$sum_2$sum2​ 为每个数平方后的前缀和
$\frac{1}{m}\sum_{i=1}^m(b_i-\overline{b})^2\\=\frac{1}{m}\sum_{i=1}^m(b_i^2-2*b_i*\overline{b}+\overline{b}^2)\\=\frac{1}{m}(sum_2-2*\overline{b}*sum_1+m*\overline{b}^2)\\=\frac{1}{m}(sum_2-2*\frac{sum_1^2}{m}+\frac{sum_1^2}{m})\\=\frac{sum_2}{m}-\frac{sum_1^2}{m^2}$m1​i=1∑m​(bi​−b)2=m1​i=1∑m​(bi2​−2∗bi​∗b+b2)=m1​(sum2​−2∗b∗sum1​+m∗b2)=m1​(sum2​−2∗msum12​​+msum12​​)=msum2​​−m2sum12​​
于是我们要求的答案为
$(n-1)*(sum_2-a_i^2)-(sum_1-a_i)^2$(n−1)∗(sum2​−ai2​)−(sum1​−ai​)2
$O(n)$O(n) 求出前缀和后每一步可以 $O(1)$O(1) 求出解

#include<cstdio>
typedef long long ll;
const int N=1e5+10;
int n,a[N];
ll sum2,sum1;
int main()
{
	//freopen("in.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	    scanf("%d",&a[i]),sum1+=a[i],sum2+=a[i]*a[i];
	for(int i=1;i<=n;i++)
	    printf("%lld ",(n-1)*(sum2-a[i]*a[i])-(sum1-a[i])*(sum1-a[i]));
	return 0;
}

总结

主考公式化简