集合求和

题目描述

给定一个集合 s（集合元素数量 <=30），求出此集合所有子集元素之和。

输入格式

集合中的元素（元素 <=1000）

输出格式

s 所有子集元素之和。

样例 #1

样例输入 #1

2 3

样例输出 #1

10

提示

【样例解释】

子集为：空集, { 2 }, { 3 }, { 2, 3 }，和为 2 + 3 + 2 + 3 = 10。

---

【数据范围】

对于 100% 的数据，1<=|s|<=30，1<=si<=1000，s 所有子集元素之和 <=10^18

我的题解

#include <stdio.h>
#include <math.h>
int main(){
    long long total=0;
    int a[30],i=0;
    while(scanf("%d",&a[i++])!=EOF);
    for (int j=0;j<i-1;j++){
        total+=(pow(2,i-2))*a[j];
    }
    printf("%lld",total);
}

其实这道题是个找规律的题，重点在于找到n个元素的集合的所有子集中各个元素的出现次数，我们可以根据以下生成子集的代码进行找规律

// {0~n-1}的所有子集：增量构造法
#include<cstdio>
using namespace std;
​
void print_subset(int n, int* A, int cur) {
  for(int i = 0; i < cur; i++) printf("%d ", A[i]); // 打印当前集合    
  printf("\n");
  int s = cur ? A[cur-1]+1 : 0; // 确定当前元素的最小可能值
  for(int i = s; i < n; i++) {
    A[cur] = i;
    print_subset(n, A, cur+1); // 递归构造子集
  }
}
​
int A[10];
int main() {
  int n;
  scanf("%d", &n);
  print_subset(n, A, 0);
  return 0;
}

当集合有1个元素时，各个元素出现的次数是1，接下来是几组数据：2-2，3-4，4-8，5-16

很容易看出来是2^(n-1)的规律，这样就好办了