第13届蓝桥杯CA省赛 求和

样例:

4

1 3 6 9

输出13+16+19+36+39+69 = 117

一维前缀和(开数组,浪费空间),res += a[i] * s[i - 1]

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
using LL = long long; //开long long 防爆
const int N = 2e5 + 10;
LL a[N],s[N];
int main()
{
    LL n,res = 0;
    cin >> n;
    for(LL i = 1;i<=n;i++)
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i]; //构造前缀和
    }
    for(LL i = n;i>0;i--)
        res += a[i] * s[i - 1];
    cout << res << endl;
    return 0;
}

一维前缀和(不开数组版)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
using LL = long long;
const int N = 2e5 + 10;
int a[N];
int main()
{
    LL n,res = 0, s = 0;
    cin >> n;
    for(int i = 0;i<n;i++)
    {
        cin >> a[i];
        res += a[i] * s;
        s += a[i];
    }
    cout << res;
    return 0;
}