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

题目链接

---

我们把方差公式进行化简。记 $su{m}_1$ 为每个数的前缀和，$su{m}_2$ 为每个数平方后的前缀和 $$\begin{gathered} \frac{1}{m}\sum _{i=1}^m(b_i-\overline{b}{)}^2 \\ =\frac{1}{m}\sum _{i=1}^m(b_i^2-2\ast b_i\ast \overline{b}+{\overline{b}}^2) \\ =\frac{1}{m}(su{m}_2-2\ast \overline{b}\ast su{m}_1+m\ast {\overline{b}}^2) \\ =\frac{1}{m}(su{m}_2-2\ast \frac{su{m}_1^2}{m}+\frac{su{m}_1^2}{m}) \\ =\frac{su{m}_2}{m}-\frac{su{m}_1^2}{m^2} \end{gathered}$$ 于是我们要求的答案为 $$(n-1)\ast (su{m}_2-a_i^2)-(su{m}_1-a_i{)}^2$$ $O(n)$ 求出前缀和后每一步可以 $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; }

总结

主考公式化简