原题链接：蓝桥杯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)
通过调整式子结构，就可以一边求前缀和一边相加了。
0.0分
69 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复