蓝桥杯备战日志(Python)7-求和(前缀和)

原题

给定 n 个整数  ，求它们两两相乘再相加的和，即：

评测用例规模与约定：

对于  的数据， 。

对于所有评测用例，  。

分析

这种类型的题一般有较明显的数学规律，一种求稳的解题思路是，通过列出前几种数字较小的情况并总结出规律。

不难发现，给定n个整数 ，S = a₁*(a₁的后面n-1项的和)  +  a2*(a2的后面n-2项的和) + a_n-1*a_n。可以使用给定数列的前缀和求解，即计算出给定长度为n的数列的S₁, S_2, S_3, ......, S_n, (S_i为数列前i项和) _。

源码

n = int(input())
# An存放数列，索引从0开始；Sn存放前i项和，索引从1开始
An = list( map(int,input().split()) )

Sn = [0] * (n+1)
for i in range(n):
    Sn[i+1] = An[i] + Sn[i]

res = 0
for i in range(n):
    res += An[i] * (Sn[n]-Sn[i+1])

print(res)

上一篇：​​蓝桥杯备战日志(Python)6-整数分解&数的分解(有“条件”的枚举)​​