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

题干P8772 [蓝桥杯 2022 省 A] 求和题目描述给定 $n$ 个整数 $a_{1}, a_{2}, \cdots, a_{n}$, 求它们两两相乘再相加的和即$$ Sa_{1} \cdot a_{2}a_{1} \cdot a_{3}\cdotsa_{1} \cdot a_{n}a_{2} \cdot a_{3}\cdotsa_{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输入 #14 1 3 6 9输出 #1117说明/提示对于 $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_2a_3...a_n)}a_2\times{(a_3a_4...a_n)}...a_{n-1}\times{a_n} $$我们正常计算是需要 $O(n^2)$ 的复杂度但数据样例中 $1n2e5$ 所以 $1n^24e10$ 这明显是TLE所以我们就要考虑优化。观察 $a_1$ 、 $a_2$ 、 $a_3$ 、$...$ 、 $a_{n-1}$ 的系数可整理成通项公式 $(a_{i1}a_{i2}...a_n)$ 可以发现它们都是这个数组中连续的一段的和所以我们就可以通过前缀和预处理从 $a_1$ 到 $a_i$ 的和$s_i$这时从 $a_{i1}$ 到 $a_n$ 的和就可以表示为 $s_n-s_{i}$ 。那么这道题就可以优化至 $O(n)$ 的复杂度了。代码#include bits/stdc.h using namespace std; const int N2e510; int n,a[N],s[N],ans; signed main() { cinn; for (int i1;in;i) { cina[i],s[i]s[i-1]a[i];//预处理计算前缀和 } for (int i1;in;i) { ans(s[n]-s[i])*a[i];//计算每一项的值并累加 } coutansendl; return 0; }