1. 2023: [蓝桥杯2022初赛] 求和
传送门:http://oj.ecustacm.cn/problem.php?id=2023
1.1. 题意
给定数组,求。
1.2. Tag
前缀和
1.3. 难度
☆☆
1.4. 思路
可以进行如下转换:
对于里面的求和,直接用前缀和优化:
预处理前缀和即可,时间复杂度。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
ll a[maxn], sum[maxn];
int main(){
int n;
ll ans = 0;
cin >> n;
for(int i = 1; i <= n; i++) ///预处理前缀和
cin >> a[i], sum[i] = sum[i - 1] + a[i];
for(int i = 1; i <= n; i++) ///求和即可
ans += a[i] * (sum[n] - sum[i]);
cout<<ans<<endl;
return 0;
}