蓝桥杯2022省A题C

题目链接：https://www.luogu.com.cn/problem/P8772

我是在洛谷里做到这题的。

因为刚接触算法在练习前缀和，我直接再洛谷上搜索了关于前缀和的题看到这个题。

由于我一开始就知道这题要用前缀和做，所以我做起来就不难了，关键是怎么找到里面运用了前缀和的地方。

题目只给了一个式子，我们首先看不到任何破解之法，就可以带入特定的值，就像题中的案例带入的是4，将4带入后写出完整的式子是

s = a1*a2 + a1*a3 + a1*a4

  + a2*a3 + a2* a4

  +a3*a4

将公因式提取出来就是

s = a1*（a2 + a3 + a4）

+ a2*（a3 + a4）

+a3*a4

可以看到括号内就是一个前缀和的形式，这样就和前缀和联系起来了。

但是说实话，我还是不清楚怎么一看到题目就知道要运用到前缀和，如果有网友知道的话可以在评论区告知一声吗？提前说声谢谢啦。

我用的是java写的，代码如下

import java.util.*;
 
public class Main{
 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
  int[] a = new int[n + 10];
  long[] s = new long[n + 10];
  long sum = 0;
  for(int i = 1; i <= n; i++){
   a[i] = sc.nextInt();
   s[i] = s[i - 1] + a[i];
  }
  for(int i = 1; i <= n; i++){
    sum += a[i] * (s[n] - s[i]);
  }
  System.out.println(sum);
 }
}