P8772 [蓝桥杯 2022 省 A] 求和

题目描述

给定 $n$ 个整数 $a_{1}, a_{2}, \cdots, a_{n}$, 求它们两两相乘再相加的和，即

$$S=a_{1} \cdot a_{2}+a_{1} \cdot a_{3}+\cdots+a_{1} \cdot a_{n}+a_{2} \cdot a_{3}+\cdots+a_{n-2} \cdot a_{n-1}+a_{n-2} \cdot a_{n}+a_{n-1} \cdot a_{n}$$

输入格式

输入的第一行包含一个整数 $n$ 。

第二行包含 $n$ 个整数 $a_{1}, a_{2}, \cdots a_{n}$ 。

输出格式

输出一个整数 $S$，表示所求的和。请使用合适的数据类型进行运算。

输入输出样例 #1

输入 #1

4
1 3 6 9

输出 #1

117

说明/提示

对于 $30 \%$ 的数据, $1 \leq n \leq 1000,1 \leq a_{i} \leq 100$ 。

对于所有评测用例, $1 \leq n \leq 2\times10^5,1 \leq a_{i} \leq 1000$ 。

蓝桥杯 2022 省赛 A 组 C 题。

题解

方法1（暴力解法）

• 只能得到60%的分数

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        ArrayList<Integer> Arr = new ArrayList<>();
        Arr.add(0,0);

        for (int i=1;i<=n;i++){
            Arr.add(i, sc.nextInt());//输入 a1 ~ an的值
        }

        long sum = 0;
        for(int i=1;i<=n-1;i++){
            for(int j=i+1;j<=n;j++){
                sum += (long) Arr.get(i) * Arr.get(j);
            }
        }
        System.out.println(sum);
    }
}

方法2（前缀和）

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        ArrayList<Integer> arr = new ArrayList<>(); // a1 - an 的值
        ArrayList<Long> prefix_sum = new ArrayList<>(); // 前缀和
        arr.add(0);
        prefix_sum.add(0L);
        for(int i=1;i<=n;i++){
            arr.add(i,sc.nextInt());
            prefix_sum.add(i,prefix_sum.get(i-1)+arr.get(i)); //计算前缀和
        }

        long sum = 0;
        for(int i=1;i<n;i++){
            sum += arr.get(i) * (prefix_sum.get(n)-prefix_sum.get(i));
        }

        System.out.println(sum);

        sc.close();
    }
}