[蓝桥杯 2022 省 A] 求和

题目描述

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

S=a1⋅a2+a1⋅a3+⋯+a1⋅an+a2⋅a3+⋯+an−2⋅an−1+an−2⋅an+an−1⋅anS=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} S=a1​⋅a2​+a1​⋅a3​+⋯+a1​⋅an​+a2​⋅a3​+⋯+an−2​⋅an−1​+an−2​⋅an​+an−1​⋅an​

输入格式

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

第二行包含 $n$ 个整数 a1,a2,⋯ana_{1}, a_{2}, \\cdots a_{n}a1​,a2​,⋯an​ 。

输出格式

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

样例 #1

样例输入 #1

4
1 3 6 9

样例输出 #1

117

提示

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

对于所有评测用例, 1≤n≤2×105,1≤ai≤10001 \\leq n \\leq 2\\times10^5,1 \\leq a_{i} \\leq 10001≤n≤2×105,1≤ai​≤1000 。

蓝桥杯 2022 省赛 A 组 C 题。

所需变量

int n;//代表n个数

int i;//循环变量

int arr[200005];//用于存储那每个数

long long sum = 0;//代表总合

long long ans = 0;//代表目前每个数加起来的和

思路：我们拿到这个题我们可以两个for循环结束这个题！不过我们可以思考更深层次的东西！比如将有规律的几组乘积合并！仔细看就能发现每个数都是乘上以他为某一个乘数的乘上以他开始的后面所有数的总和，因此我们可以每次算哪个数的总乘积，可以先把它减掉，然后在乘起来！完整代码如下（编译器是dev，语言是C语言）：

#include<iostream>
using namespace std;
int main(){int n,i,arr[200005];long long sum = 0,ans = 0;cin>>n;for(i = 0;i<n;i++){cin>>arr[i];ans +=arr[i]; }for(i = 0;i<n-1;i++){ans -= arr[i];sum += arr[i]*ans;}cout<<sum<<endl;return 0;
}