HDu 6092 Rikka with Subset(母関数+思考)
4453 ワード
Rikka with Subset
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1445 Accepted Submission(s): 726
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
n positive
A1−An and their sum is
m. Then for each subset
S of
A, Yuta calculates the sum of
S.
Now, Yuta has got
2n numbers between
[0,m]. For each
i∈[0,m], he counts the number of
is he got as
Bi.
Yuta shows Rikka the array
Bi and he wants Rikka to restore
A1−An.
It is too difficult for Rikka. Can you help her?
Input
The first line contains a number
t(1≤t≤70), the number of the testcases.
For each testcase, the first line contains two numbers
n,m(1≤n≤50,1≤m≤104).
The second line contains
m+1 numbers
B0−Bm(0≤Bi≤2n).
Output
For each testcase, print a single line with
n numbers
A1−An.
It is guaranteed that there exists at least one solution. And if there are different solutions, print the lexicographic minimum one.
Sample Input
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1445 Accepted Submission(s): 726
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
n positive
A1−An and their sum is
m. Then for each subset
S of
A, Yuta calculates the sum of
S.
Now, Yuta has got
2n numbers between
[0,m]. For each
i∈[0,m], he counts the number of
is he got as
Bi.
Yuta shows Rikka the array
Bi and he wants Rikka to restore
A1−An.
It is too difficult for Rikka. Can you help her?
Input
The first line contains a number
t(1≤t≤70), the number of the testcases.
For each testcase, the first line contains two numbers
n,m(1≤n≤50,1≤m≤104).
The second line contains
m+1 numbers
B0−Bm(0≤Bi≤2n).
Output
For each testcase, print a single line with
n numbers
A1−An.
It is guaranteed that there exists at least one solution. And if there are different solutions, print the lexicographic minimum one.
Sample Input
2 2 3 1 1 1 1 3 3 1 3 3 1
Sample Output
1 2 1 1 1HintIn the first sample, $A$ is $[1,2]$. $A$ has four subsets $[],[1],[2],[1,2]$ and the sums of each subset are $0,1,2,3$. So $B=[1,1,1,1]$
Source
2017 Multi-University Training Contest - Team 5
题目大意：有一正数数组a[n]，数组中任意多个（0~n）元素的和（相当于子集但允许大小相等的元素）为k的个数为b[k]个，根据b数组求a[n]数组。
解题思路：经过观察，不难发现数组b中b[0]=b[0]-1后序号最小的非零数就是数组a中最小值的个数，最小值为下标。根据这个结果我们就可以想到，我们可以求出已知数组a部分元素的所有子集（可以包含相等的值）的和为k的个数b'[k]，找出b[i]-b'[i]中序号最小的非零元素就能找到数组a中未知元素中最小的元素及其个数，这样就可以依次求出数组a了。求数组b'时利用母函数，每次加上找到的新元素求出新的数组b'。
代码如下：
#include
using namespace std;
long long a[55],b[10005],tmp1[10005],tmp2[10005];
void init(int m)
{
tmp1[0]=1;
for(int i=1;i<=m;i++)
{
tmp1[i]=0;
}
}
void mf(int p,int m,int p0)
{
int i,j;
for(i=p0;i=a[i];j--)
{
tmp1[j]+=tmp1[j-a[i]];
}
}
}
int f(int p,int m)
{
int i;
for(i=0;i<=m;i++)
{
tmp2[i]=b[i]-tmp1[i];
}
for(i=0;i<=m;i++)
{
if(tmp2[i]!=0)
break;
}
while(tmp2[i]--)
{
a[p++]=i;
}
return p;
}
int main()
{
std::ios::sync_with_stdio(false);
int T,n,m;
int p0,p,i;
cin>>T;
while(T--)
{
cin>>n>>m;
for(i=0;i<=m;i++)
{
cin>>b[i];
}
p=0;
p0=0;
init(m);
while(p