2664: 蓝桥杯2022年第十三届省赛真题-求和

解题思路:

我们观察式子可以发现，可以把每一个数提出来，以a1到a5为例

S=a1*(a2+a3+a4+a5)+a2*(a3+a4+a5)+a3*(a4+a5)+a4*a5

这样很容易想到前缀和，我们可以通过前缀和来得到括号里面的数，这样时间复杂度就降到了O(n)

参考代码:

#include <stdio.h>

long long  p[200007];
long long dp[200007];//开到long long 来存放这些数之和

int main (){
	int i,j;
	int n;
	long long z=0;//注意开到long long
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&p[i]);
		if(i==0)dp[i]=p[i];
		else 	dp[i]=dp[i-1]+p[i];//前缀和数组
	}
	for(i=0;i<n;i++){
		z+=p[i]*(dp[n-1]-dp[i]);//dp[n-1]-dp[i]即为()里的数
	} 
	printf("%lld",z);
	
	return 0;
}

还有另一种算法，时间复杂度是O(n)但是不需要开辟数组。

代码如下：

#include <stdio.h>

int main ()
{
	int i;
	int n,m;
	long long k=0,z=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&m);
		z+=k*m;
		k+=m;
	}
	printf("%lld",z);
	
	return 0;
}

这样的做法就是把式子拆成：

S=a2*a1+a3*(a2+a1)+a4*(a3+a2+a1)+a5*(a4+a3+a2+a1)

通过调整式子结构，就可以一边求前缀和一边相加了。