1.3 求和
给定 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,表示所求的和。
请使用合适的数据类型进行运算。
数据范围
对于 30% 的数据,1≤n≤1000,1≤ai≤100。
对于所有评测用例,1≤n≤200000,1≤ai≤1000。
输入样例:
4
1 3 6 9
输出样例:
117
题解:
这题肯定不能暴力的,有一定的优化公式,那么显然我们可以用一个类似三角形的来判断,ai*(sum-ai),其中这个sum每一次减完不用再加回去。
除外,我刚刚还看到一个通过前缀优化,把空间复杂度降到1的,是一个更先进的思路o( ̄▽ ̄)d
https://www.acwing.com/solution/content/137053/
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int a[N];long long int b[N];
int main()
{
int n;
cin>>n;
long long res=0;long long ans=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
ans+=a[i];
}
b[0]=ans;
for(int i=1;i<=n;i++)
{
b[i]=b[i-1]-a[i];
res+=b[i]*a[i];
}
cout<<res<<endl;
}
大佬蛮烦您看看我的这个代码有什么问题,纯萌新
a = int(input())
if a >= 2 and a <= 1000:
n = a
b = input().split(‘ ‘)
for i in range(1, n):
for j in range(2, n + 1):
sum += a[i] * a[j]
print(sum)
我是蒟蒻,看不懂(⊙︿⊙)