蓝桥杯大赛软件类省赛C/C++大学A组-求和

题目

题目描述

给定 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。

分析

数据范围直接采用long long 吧

const int N=200010
long long a[N],b[N]

数组

S = a1 · a2 + a1 · a3 + · · · + a1 · an + a2 · a3 + · · · + an-2 · an-1 + an-2 · an + an-1 · an

本题采用提取公因式和前缀和；

我们提取公因式后可以得到S=a1*(a2+a3+...+an)+a2*(a3+...an)+....an-1*an;

我们将数据读取到a数组中

**重点**

将b数组从n开始循环到1；

b[i]=a[i];
b[i]+=b[i+1];

我们此时就得到了a数组的前缀和

得到的数据b[i+1]直接乘上a[i]再累加即可

代码

#include<iostream>
using namespace std;
const int N=200010;
long long a[N],b[N];
int main(){
  int n;
  long long sum=0;
  cin>>n;
  for(int i=1;i<=n;i++) cin>>a[i];
  for(int i=n;i>=1;i--) b[i]=a[i],b[i]+=b[i+1];
  for(int i=1;i<=n;i++)
    {
      sum+=(a[i]*b[i+1]);
      
    }
  cout<<sum<<endl;
}