题目大意

给定元素数量

\le

30 的集合，求解所有元素子集之和

思路

暴力解（仅 60pts）

通过递归求解，对于每一个元素有选与不选两种选择进行递归，但观察数据量元素数量

\le

30，总时间复杂度 = 递归调用总次数 × 每次调用的操作成本,即 O(

2^n

)

\times

O(1)=O( $2^n$ )。

2^{30}

\approx

10^9

，大与

10^8

，超时，因次得想想其他方式入手。

正解

方才的分析中我们有每一个元素有选与不选两种选择，如果能够想到这一点，接下来变简单了。对于每一个元素，便具有

2^{n-1}

种组合方式（除本元素外的其他元素的两种选择组合）。所以，集合所有子集元素之和 =

\sum_{i = 1}^{n} a_{i}

\times

2^{n-1}

代码

具体细节见代码注释。

CPP

#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;//这个应该不会有人忘吧
}

P2415 集合求和

文章操作

题目大意

思路

暴力解（仅 60pts）

正解

代码

相关推荐

评论

P2415 集合求和