hdu 6092 Rikka with Subset (集合计数,01背包)

Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Yuta has

.

It is too difficult for Rikka. Can you help her?

Input

The first line contains a number

Output

For each testcase, print a single line with

.
It is guaranteed that there exists at least one solution. And if there are different solutions, print the lexicographic minimum one.

Sample Input

2 3

1 1 1 1

3 3

1 3 3 1

Sample Output

1 2

1 1 1

假设现在有一个元素个数为n的允许有重复元素的集合a,那么这个a的子集就有2^n个子集,现在给你这2^n个子集的每一个的和(cnt[i]表示子集的和为i的子集个数),让你还原a集合

第2个样例意思为子集的和为0 1 2 3 的子集个数分别有1 3 3 1个,原集合a一共有3个元素

思路: 首先我们发现原集合中0的个数是好求的,2^num[0]=cnt[0].那么怎样求剩下的元素呢?

发现如果我们一个一个从小到大求,开一个数组sum[i]表示求到当前位置之前子集和为i的子集个数.

有 num[i]*sum[0]+sum[i]=cnt[i],也就是说一共和为i的子集个数等于集合中数字i的个数乘和为0的子集个数再加上之前那些由>0&&<i的元素构成的子集中和为i的个数

然后我们每次求出一个num[i]后,用完全背包的思想将这num[i]个i一个一个的加入到集合中,用完全背包的思想更新sum数组就行了

代码如下:

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 const int maxn = 5e5+500;
 6 int n,m;
 7 ll cnt[maxn];
 8 ll sum[maxn];
 9 int num[maxn];
10 int main()
11 {
12     //freopen("de.txt","r",stdin);
13     int T;
14     scanf("%d",&T);
15     while (T--){
16         memset(sum,0,sizeof sum);
17         memset(num,0,sizeof num);
18         scanf("%d%d",&n,&m);
19         for (int i=0;i<=m;++i)
20             scanf("%lld",&cnt[i]);
21         num[0]=0;
22         sum[0]=cnt[0];
23         while((1<<num[0])<cnt[0]) num[0]++;
24         for (int i=1;i<=m;++i){
25             num[i]=(cnt[i]-sum[i])/sum[0];//num[i]*sum[0]+sum[i]=cnt[i]
26             for (int j=1;j<=num[i];++j){//一个一个的加入几个
27                 for (int k=m;k>=i;--k){//完全背包思想更新sum
28                     sum[k]+=sum[k-i];
29                 }
30             }
31         }
32         vector<int> vec;
33         for (int i=0;i<=m;++i){
34             for (int j=0;j<num[i];++j)
35                 vec.push_back(i);
36         }
37         for (int i=0;i<vec.size();++i)
38             printf("%d%c",vec[i],i==(vec.size()-1)?'
':' ');
39     }
40     return 0;
41 }

hdu 6092 Rikka with Subset (集合计数,01背包)

相关推荐