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

柔情只为你懂 2023-09-28 23:36 69阅读 0赞

## 1.求和 ##

### 1.题目描述 ###

给定  n n n 个整数  a 1 , a 2 , ⋅ ⋅ ⋅ , a n a\_1, a\_2, · · · , a\_n a1,a2,⋅⋅⋅,an，求它们两两相乘再相加的和，即：

S = a 1 ⋅ a 2 + a 1 ⋅ a 3 + ⋯ + a 1 ⋅ a n + a 2 ⋅ a 3 + ⋯ + a n − 2 ⋅ a n − 1 + a n − 2 ⋅ a n + a n − 1 ⋅ 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\} S=a1⋅a2\+a1⋅a3\+⋯\+a1⋅an\+a2⋅a3\+⋯\+an−2⋅an−1\+an−2⋅an\+an−1⋅an

### 2.输入格式 ###

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

第二行包含  n n n 个整数  a 1 , a 2 , ⋯   , a n a\_1,a\_2,\\cdots, a\_n a1,a2,⋯,an 。

### 3.输入格式 ###

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

第二行包含  n n n 个整数  a 1 , a 2 , ⋯   , a n a\_1,a\_2,\\cdots, a\_n a1,a2,⋯,an

### 4.输出格式 ###

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

### 5.样例输入 ###

4  
1 3 6 9

### 6.样例输出 ###

117

### 7.数据范围 ###

1 ≤ n ≤ 200000 , 1 ≤ a i ≤ 1000 1 \\leq n \\leq 200000,1 \\leq a\_\{i\} \\leq 1000 1≤n≤200000,1≤ai≤1000

### 8.原题链接 ###

[link][]

## 2.解题思路 ##

如果暴力获取答案的复杂度将会是 O ( n 2 ) O(n^2) O(n2)级别，会超时。仔细不难发现，对于任意一个  a i a\_i ai，它只会**主动**和下标比它大的数相乘。即我们可以提公因式子： a i ⋅ a i + 1 + a i ⋅ a i + 2 + . . . . . . + a i ⋅ a n = ( a i + 1 + a i + 2 + . . . . . . + a n ) ⋅ 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 ai⋅ai\+1\+ai⋅ai\+2\+......\+ai⋅an=(ai\+1\+ai\+2\+......\+an)⋅ai

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

## 3.Ac\_code ##

#include<bits/stdc++.h>
    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;
    }

[link]: https://www.lanqiao.cn/problems/2080/learning/