#C++2664——蓝桥杯2022年第十三届省赛真题-求和

解题思路:

************************************************************************************************

按题目模拟会TLE①②；

加法->加法

减法->取反，加法

乘法->移位，逻辑判断，累加

除法->移位（试错），逻辑判断，累减

具体原理数电里有提到，尽量避免运算复杂，耗时的步骤。

①ans= a1 · a2 + a1 · a3 + · · · + a1 · an + a2 · a3 + · · · + an-2 · an-1 + an-2 · an + an-1 · an.

②=>ans=a1+a2*a1+a3*a2*a1+a4*a3*a2*a1+...+an*an-1*...a3*a2*a1;(累乘再求和)

③=>ans=a1*(a2+a3+a4...+an-1+an)+a2*(a3+a4+a5..+an-1+an)+....an-1*(an);(前缀和相乘再求和)

③简化了运算过程，化大量的乘法运算为加法运算（即：前缀和），以避免TLE；

参考代码:

③--------AC

#include <iostream>
using namespace std;
long long arr[200005];
int main()
{
	int n;
	long long ans=0,sum=0;
	scanf("%lld",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%lld",&arr[i]);
		sum+=arr[i]; 
	}
	for(int i=0;i<n;i++)
	{
		sum-=arr[i];//减去当前即为前缀和
		ans+=arr[i]*sum;
	}
	printf("%lld",ans);
	return 0;
}

②--------73分（其余样例TLE）

#include <iostream>
using namespace std;
long long arr[200005];
int main()
{
	int n;
	long long ans=0;
	scanf("%lld",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%lld",&arr[i]);
		for(int j=0;j<i;j++)//乘上之前的 
		{
			ans+=arr[i]*arr[j];
		}
	}
	printf("%lld",ans);
	return 0;
}