蓝桥杯 2022 省赛 A 组 C 题
题目描述
给定 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，表示所求的和。请使用合适的数据类型进行运算。
输入输出样例
输入 #1复制
4
1 3 6 9
输出 #1复制
117
说明/提示
对于 30 \%30% 的数据, 1001≤n≤1000,1≤ai≤100 。
对于所有评测用例, 1≤n≤2×10^5,1≤ai≤1000 。
暴力求解可以获得30%的分数：
#include<cstdio> #include<iostream> using namespace std; typedef long long LL; int main() { LL sum = 0; int n; cin >> n; int g[200020]; for (int i = 0; i < n; i++) { scanf("%d", &g[i]); } for (int i = 0; i < n; i++) { for (int j = 1 + i; j < n; j++) { sum += g[i] * g[j]; } } cout << sum << endl; return 0; }
使用前缀和和差分（不超时代码：
#include<cstdio> #include<iostream> using namespace std; typedef long long LL; int main() { LL sum = 0; int n; cin >> n; int g[200020]; LL s[200020] = { 0 }; for (int i = 1; i <= n; i++) { scanf("%d", &g[i]); s[i] = s[i - 1] + g[i]; } for (int i = 1; i <= n; i++) { sum += g[i] * (s[n] - s[i]); } cout << sum << endl; return 0; }
