[蓝桥杯 2022 省 A] 求和——前缀和，差分

女爷i 2023-09-26 18:16 70阅读 0赞

蓝桥杯 2022 省赛 A 组 C 题

### **题目描述** ###

给定 n 个整数 *a*1,*a*2,⋯,*an*, 求它们两两相乘再相加的和，即

*S*=*a*1⋅*a*2+*a*1⋅*a*3+⋯+*a*1⋅*an*\+*a*2⋅*a*3+⋯+*an*−2⋅*an*−1+*an*−2⋅*an*\+*an*−1⋅*an*

### **输入格式** ###

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

第二行包含 n 个整数 *a*1,*a*2,⋯*an* 。

### **输出格式** ###

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

### **输入输出样例** ###

**输入 \#1**复制

1 3 6 9

**输出 \#1**复制

117

### **说明/提示** ###

对于 30 \\%30% 的数据, 1001≤*n*≤1000,1≤*ai*≤100 。

对于所有评测用例, 1≤*n*≤2×10^5,1≤*ai*≤1000 。

**暴力求解可以获得30%的分数：**

#include<cstdio>
    #include<iostream>
    using namespace std;
    typedef long long LL;
    int main()
    {
        LL sum = 0;
        int n;
        cin >> n;
        int g[200020];
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &g[i]);
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 1 + i; j < n; j++)
            {
                sum += g[i] * g[j];
            }
        }
        cout << sum << endl;
        return 0;
    }

**使用前缀和和差分（不超时代码：**

#include<cstdio>
    #include<iostream>
    using namespace std;
    typedef long long LL;
    int main()
    {
        LL sum = 0;
        int n;
        cin >> n;
        int g[200020];
        LL s[200020] = { 0 };
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &g[i]);
            s[i] = s[i - 1] + g[i];
        }
        for (int i = 1; i <= n; i++)
        {
            sum += g[i] * (s[n] - s[i]);
        }
        cout << sum << endl;
        return 0;
    }