求子集元素之和(洛谷P2415题题解,Java语言描述)

题目要求

P2415题目链接

求子集元素之和(洛谷P2415题题解,Java语言描述)

分析

这题我觉得……当个数学题做就好了嘛。

  • 有一个数N的情况:result = 1 * N
  • 有两个数N1、N2的情况:result = 2 * (N1+N2)
  • 有三个数N1、N2、N3的情况:result = 4 * (N1+N2+N3)
  • ……

其实不难推的,比如说三个数的情况:
N1, N2, N3, N1N2, N1N3, N2N3, N1N2N3

……

找规律嘛……

定义一下sum = sum(N1, N2, …, Nn)
其实结果就是result = sum * 2n-1

于是只需算一下数就好啦!

说明:java.math.BigInteger里有一个静态属性是TWO,可直接用,但洛谷不识别,所以我就改成new BigInteger(“2”)了。

AC代码(Java语言描述)

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] array = scanner.nextLine().trim().split("\\s+");
        long sum = 0;
        for (String s : array) {
            sum += Long.parseLong(s);
        }
        System.out.println(new BigInteger("2").pow(array.length-1).multiply(new BigInteger(Long.toString(sum))));
        scanner.close();
    }
}

猜你喜欢