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

给定 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;
}

正文完