题海拾贝：P8772 [蓝桥杯 2022 省 A] 求和

1、题目

2、题解 

        这题其实并不难想，甚至说都不用想，上来直接就for循环嵌套，但这样想都不用想，时间度都干O（N）了他肯定拿不了满分。

        在这我就不写错的那个了，免得误导大家。发现时间度太高了肯定得降，那我们之前说你两个for循环不嵌套的话就是N,那就想办法把for循环拿出来呗，反正你不嵌套你写多少个for他也是O（N）。

        我们试着写出来几个就能发现规律了。假设我们n等于5，a1就乘了个a2,a3,a4,a5，我们根据乘法结合律把它写成a1*(a2+a3+a4+a5)，现在我们只需要提前写个for循环，把ai需要乘的那几个数加和就OK了。但需要注意的是，求和的时候你也不能嵌套for循环，不然咱时间复杂度还是O（n），咱们让第i个数该乘的数的和 等于 第i-1个数该乘的数的和 减去 第i个数就好了。

        还有，就是千万别忘了开辟成long long，注意数据范围。十年 OI 一场空，不开 long long 见祖宗！

#include<iostream>
using namespace std;
long long a[200005] = { 0 };
long long b[200005] = { 0 };
int main()
{
	int n = 0;
	int i = 0;
	cin >> n;
	long long S = 0;
	int j = 0;
	while(i<n)
	{
		cin >> a[i];
		i++;
	}
	for (i = 1;i < n;i++)
	{
		b[0] = b[0] + a[i];
	}
	for (i = 1;i < n;i++)
	{
		b[i] = b[i-1] - a[i];
	}
	for (i = 0;i < n;i++)
	{
		S = S + a[i] * b[i];
	}
	cout << S;
	return 0;
}

        好了，今天的内容就分享到这，我们下期再见！