给定 n 个整数 a1, a2, · · · , an ，求它们两两相乘再相加的和，即 S = a1 · a2 + a1 · a3 + · · · + a1 · an + a2 · a3 + · · · + an-2 · an-1 + an-2 · an + an-1 · an.

输入的第一行包含一个整数 n 。

第二行包含 n 个整数 a1, a2, · · · an。

输出一个整数 S，表示所求的和。请使用合适的数据类型进行运算。

4
1 3 6 9

117

对于 30% 的数据，1 ≤ n ≤ 1000，1 ≤ ai ≤ 100。

对于所有评测用例，1 ≤ n ≤ 200000，1 ≤ ai ≤ 1000。

题目解析

这道题，给我的第一印象是用前缀和。
如何处理相乘关系？
便输入边计算？时间复杂度在O(n^3)，优化一下可以到n^2
下面是代码。

#include <iostream>
#include "algorithm"
#include "string.h"
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n+1],b[n+1][n+1],c[n+1][n+1];
    memset(a,0,sizeof a);
    memset(b,1,sizeof b);
    memset(c,0,sizeof c);
    for (int i = 1; i <= n; ++i) {
        cin>>a[i];
    }
    for (int i = 1; i <= n; ++i) {
        for(int j=i;j<=n;++j){
            b[i][j]=a[i]*a[j];//b[i][j]表示a[i]*a[j]的积
            c[i][j]=c[i][j-1]+b[i][j];//前缀和
            if(j==i)c[i][j]=c[i-1][n];//当a[i]开始变换时，存储值转移
        }
    }
    cout<<c[n][n];
}

当然，这样子做空间复杂度太大了，我们还可以优化空间复杂度，没错，就是用滚动数组。

#include <iostream>
#include "string.h"
using namespace std;
int a[200005],b[2][200005],c[2][200005];
int main(){
    int n;
    cin>>n;
    memset(a,0,sizeof a);
    memset(b,1,sizeof b);
    memset(c,0,sizeof c);
    for (int i = 1; i <= n; ++i) {
        cin>>a[i];
    }
    for (int i = 1; i <= n; ++i) {
        for(int j=i;j<=n;++j){
            b[i&1][j]=a[i]*a[j];
            c[i&1][j]=c[i&1][j-1]+b[i&1][j];
            if(j==i)c[i&1][j]=c[(i-1)&1][n];
        }
    }
    cout<<c[n&1][n];
}

当然，时间复杂度还是有点大。
我们不难发现，我们每次可以提一个a[i]出来，那么每次计算的都是一个子前缀和，那么这样的话就很好办了，看代码

#include <iostream>
using namespace std;
long long a[200005];
long long b[200005];
int main(){
    int n;
    cin>>n;
    for (int i = 1; i <= n; ++i) {
        cin>>b[i];
        a[i]=a[i-1]+b[i];
    }
    long long sum=0;
    for(int i=1;i<=n;i++){
        sum+=b[i]*(a[n]-a[i]);
    }
    cout<<sum;
}

今日分享 – 【题解】蓝桥杯2022年第十三届省赛（第二场）真题-求和

题目解析