P8772 [蓝桥杯 2022 省 A] 求和

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int N=200005;
4. int  a[N];
5. int num[N];
6. int main(){
7.         int n;
8.         cin>>n;
9.         for(int i=1;i<=n;i++)
10.         {
11.                
12.                 cin>>a[i];
13.                 if(i==n)
14.                         num[i]=a[i];
15.         }
17.         for(int j=n-1;j>=2;j--)
18.         {       
19.                 num[j]=num[j+1]+a[j];
20.                
21.         }
22.        
23.        
24.         long long sum=0;
25.         for(int i=1;i<n;i++){
26.                 sum+=a[i]*num[i+1];
27.         }
28.         cout<<sum;
29.         return 0;
30.        
31.        
32. }

复制代码

简朴ac这题两重循环的话会爆，不够时间，用前缀和可以优化到n的一次方，题目中求和的各个项可以提出a1到an这n个公共项，那么剩下的就是a2到an，至an的前缀和，先求出a2到an的前缀和，反面的就是n次运算了，不过存储前缀和的数组要用long以上的整型不然会超出空间，数据每个最大是1000，a2到an个数最多是200000，最大的话应该是200000000去到了10的八次方，看到大的数据值，最好就用大一点的整形，空间一般是够的。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。