2664: 蓝桥杯2022年第十三届省赛真题-求和 c++题解

解题思路:

首先想到的是用for循环暴力解决，但即使优化后，时间复杂度O(n²), 对于20万的大小，达到了整整400亿， 所以肯定行不通

由于此处数据范围较大，我们观察到原式等于=a₁(a₂+a₃+...+a_n) + a₂(a₃+a₄+...+a_n) + ... 

所以我们可以添加个变量tmp= a₂ + a₃ + a_n 每次循环后 tmp = tmp - a_{i + 1}

上代码

代码样例：

#include <iostream>
using namespace std;
int a[200200];
unsigned long long tmp; //unsigned long long 是无符号超长整型, 大小为2^64 - 1,对于本题足够了 
//tmp存储
int main() {
    int n;
    unsigned long long s;
    cin >> n;
    for (int i = 1; i <= n; i++) //读入数组
        cin >> a[i];
    for (int i = 2; i <= n; i++) //这里不需要算a1,所以初始值从2开始
        tmp += a[i];
    for (int i = 1; i <= n; i++) {
        s += a[i] * tmp; 
        tmp -= a[i + 1];
    }
    cout << s;
    return 0;
}