洛谷 P8772 [蓝桥杯 2022 省 A] 求和

 题目描述

给定 �n 个整数 �1,�2,⋯ ,��a1​,a2​,⋯,an​, 求它们两两相乘再相加的和，即

�=�1⋅�2+�1⋅�3+⋯+�1⋅��+�2⋅�3+⋯+��−2⋅��−1+��−2⋅��+��−1⋅��S=a1​⋅a2​+a1​⋅a3​+⋯+a1​⋅an​+a2​⋅a3​+⋯+an−2​⋅an−1​+an−2​⋅an​+an−1​⋅an​

输入格式

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

第二行包含 �n 个整数 �1,�2,⋯��a1​,a2​,⋯an​ 。

输出格式

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

输入输出样例

输入 #1复制

4
1 3 6 9

输出 #1复制

117

说明/提示

对于 30%30% 的数据, 1≤�≤1000,1≤��≤1001≤n≤1000,1≤ai​≤100 。

对于所有评测用例, 1≤�≤2×105,1≤��≤10001≤n≤2×105,1≤ai​≤1000 。

蓝桥杯 2022 省赛 A 组 C 题。

分析：

        关于本题，主要难点有两个，一个是long long，一个是前缀和。

        第一个问题，long long，因为int型大约范围是一乘以十的九次方，所以看题目给的数据肯定会超限，所以用long long。我下边写了一个 typedef long long ll,其实就是为了方便把long long的功能赋给了ll，ll就有了long long同样的功能，所以我在后边定义ans和sum的时候用的ll，当然你按部就班的写long long也没问题。(当时第一次见这种写法的时候我也很困扰，但是很方便)

        第二个问题就是前缀和，如果大家没学过前缀和的话先去了解一下，这里就不展开了。

为什么要用呢，我们分析一下这个题的规律：

S=a1​⋅a2​+a1​⋅a3​+⋯+a1​⋅an​+a2​⋅a3​+⋯+an−2​⋅an−1​+an−2​⋅an​+an−1​⋅an​

我们观察一下 a1​⋅a2​+a1​⋅a3​+⋯+a1​⋅an​ 是不是可以提出一个a1来：

a1(a2+a3+...+an）

观察 a2​⋅a3​+⋯其实就是a2*a3+a2*a4+...+a2*an,同理：

a2(a3+...+an)

.....

由此可得整个式子化简的话得到：

S=a1(a2+a3+a4+...+an)+a2(a3+a4+...+an)+...+an-2(an-1+an)+an-1(an);

那么不难发现在括号内的全是前缀和，那么就得到了我们的代码：

(建议先学前缀和再来做本题哦)

代码：

#include<iostream>
using namespace std;
typedef long long ll;//记得要开long long
int n;
ll ans;//最终结果要开long long
int arr[200005];//输入数据
ll sum[200005];//前缀和数组，记得开long long
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
		sum[i] = sum[i - 1] + arr[i];//前缀和
	}
	for (int i = 1; i <= n-1; i++)
		ans += arr[i] * (sum[n] - sum[i]);//利用前缀和思想，套公式
	cout << ans;
	return 0;
}