第十三届蓝桥杯省赛C++组、Java组真题—— 求和 (AC)

1.求和

1.题目描述

给定 $n$ 个整数 $a_1,a_2,\cdot \cdot \cdot ,a_n$，求它们两两相乘再相加的和，即：

$S=a_1\cdot a_2+a_1\cdot a_3+\cdots +a_1\cdot a_n+a_2\cdot a_3+\cdots +a_{n-2}\cdot a_{n-1}+a_{n-2}\cdot a_n+a_{n-1}\cdot a_n$

2.输入格式

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

第二行包含 $n$ 个整数 $a_1,a_2,\cdots ,a_n$ 。

3.输入格式

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

第二行包含 $n$ 个整数 $a_1,a_2,\cdots ,a_n$

4.输出格式

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

5.样例输入

4
1 3 6 9

6.样例输出

117

7.数据范围

$1\le n\le 200000,1\le a_i\le 1000$

8.原题链接

link

2.解题思路

如果暴力获取答案的复杂度将会是$O(n^2)$级别，会超时。仔细不难发现，对于任意一个 $a_i$，它只会主动和下标比它大的数相乘。即我们可以提公因式子：$$a_i\cdot a_{i+1}+a_i\cdot a_{i+2}+......+a_i\cdot a_n=(a_{i+1}+a_{i+2}+......+a_n)\cdot a_i$$

对于右边式子不难发现可以利用前缀和在$O(1)$时间内求出，即预处理前缀和数组后我们可以在$O(n)$的时间复杂度内得到答案。

3.Ac_code

#include
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;


int n;
LL a[N];
LL s[N];
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    LL ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += s[i - 1] * a[i];
    }
    cout << ans << '\n';
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41