P8772 [蓝桥杯 2022 省 A] 求和题解前缀和思路

题干

P8772 [蓝桥杯 2022 省 A] 求和

题目描述

给定 $n$ 个整数 $a_{1}, a_{2}, \cdots, a_{n}$, 求它们两两相乘再相加的和，即

$$ S=a_{1} \cdot a_{2}+a_{1} \cdot a_{3}+\cdots+a_{1} \cdot a_{n}+a_{2} \cdot a_{3}+\cdots+a_{n-2} \cdot a_{n-1}+a_{n-2} \cdot a_{n}+a_{n-1} \cdot a_{n} $$

输入格式

输入的第一行包含一个整数 $n$ 。

第二行包含 $n$ 个整数 $a_{1}$, $a_{2}$, $\cdots a_{n}$ 。

输出格式

输出一个整数 $S$，表示所求的和。请使用合适的数据类型进行运算。

输入输出样例 #1

输入 #1

4 1 3 6 9

输出 #1

117

说明/提示

对于 $30 \%$ 的数据, $1 \leq n \leq 1000,1 \leq a_{i} \leq 100$ 。

对于所有评测用例, $1 \leq n \leq 2\times10^5,1 \leq a_{i} \leq 1000$ 。

蓝桥杯 2022 省赛 A 组 C 题。

思路解析

我拿到这道题最先想到的思路是数学优化，将原式进行合并同类项，如下：

$$ 原式= a_1\times{(a_2+a_3+...+a_n)}+a_2\times{(a_3+a_4+...+a_n)}+...+a_{n-1}\times{a_n} $$

我们正常计算是需要 $O(n^2)$ 的复杂度，但数据样例中 $1<=n<=2e5$ ，所以 $1<=n^2<=4e10$ ，这明显是TLE，所以我们就要考虑优化。观察 $a_1$ 、 $a_2$ 、 $a_3$ 、$...$ 、 $a_{n-1}$ 的系数，可整理成通项公式 $(a_{i+1}+a_{i+2}+...+a_n)$ ，可以发现它们都是这个数组中连续的一段的和，所以我们就可以通过前缀和预处理从 $a_1$ 到 $a_i$ 的和（$s_i$），这时从 $a_{i+1}$ 到 $a_n$ 的和就可以表示为 $s_n-s_{i}$ 。那么这道题就可以优化至 $O(n)$ 的复杂度了。

代码

#include <bits/stdc++.h> using namespace std; const int N=2e5+10; int n,a[N],s[N],ans; signed main() { cin>>n; for (int i=1;i<=n;i++) { cin>>a[i],s[i]=s[i-1]+a[i];//预处理计算前缀和 } for (int i=1;i<n;i++) { ans+=(s[n]-s[i])*a[i];//计算每一项的值并累加 } cout<<ans<<endl; return 0; }