蓝桥杯大赛软件类省赛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
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<