P2415 集合求和

Err0r_C · 2025-07-26 15:12:34 · 题解

题目大意

给定元素数量 \le30 的集合，求解所有元素子集之和

思路

暴力解（仅 60pts）

通过递归求解，对于每一个元素有选与不选两种选择进行递归，但观察数据量 元素数量 \le30，总时间复杂度 = 递归调用总次数 × 每次调用的操作成本,即 O(2^n)\timesO(1)=O(2^n)。 2^{30} \approx 10^9，大与 10^8，超时，因次得想想其他方式入手。

正解

方才的分析中我们有每一个元素有选与不选两种选择，如果能够想到这一点，接下来变简单了。对于每一个元素，便具有 2^{n-1} 种组合方式（除本元素外的其他元素的两种选择组合）。所以，集合所有子集元素之和 = \sum_{i = 1}^{n} a_{i} \times 2^{n-1}

代码

具体细节见代码注释。

#include<iostream>
#include<cstdio>
#include<cmath> 
using namespace std;
int a[31],n=0,j;
long long ans=0;//务必开long long
int main(){
    // 读取元素并累加总和
    while(scanf("%d",&a[++n]) == 1){
    //==1判断读入是否有效
        ans += a[n];
    }
    n--;//减去无效读入 
    ans*=pow(2,n-1);//使用cmath库中的pow计算2的n-1次方 
    printf("%lld",ans);
    return 0;//这个应该不会有人忘吧
}