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

 

T1 方差

根据题目要求将式子先写出来注意下面式子中的 $n$ 全部都是 $n-1$$$\begin{aligned}ans&=n^2\times \frac{1}{n}\times \sum_{i=1}^{n}\left(b_i-\overline{b}\right)^2\\&=n\times \sum_{i=1}^{n}\left({b_i}^2-2b_i\overline{b}+{\overline{b}}^2\right)\\&=n\times \left(\sum_{i=1}^{n}{b_i}^2-2\overline{b}\times \sum_{i=1}^{n}b_i+n\times \overline{b}\right)\\&=n\times \sum_{i=1}^{n}{b_i}^2-n\times 2\overline{b}\times \sum_{i=1}^{n}b_i+n\times n\times \overline{b}\\&=n\times \sum_{i=1}^{n}{b_i}^2-2\times \left(\sum_{i=1}^{n}b_i\right)^2+n\times \sum_{i=1}^{n}b_i\end{aligned}$$上面最后一步化出来的式子就是最简的式子。我们可以通过一些预处理将其 $\text{O}(1)$ 求出来。这样总的时间复杂度是 $\text{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("\n"); } }

 

转载于:https://www.cnblogs.com/bljfy/p/9656352.html