HDU6092 Rikka with Subset

Rikka with Subset

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 403    Accepted Submission(s): 173

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 i s 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 1

   
    
     Hint
    
In 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]$

   
    
        

題目大意：給你一個n和m下一行輸入B數列從B0~Bm，下标為i則Bi的含義為A數列的子集中和為i的子集為Bi個，現在讓你還原A數列，并按照字典順序輸出。

解題思路：B0一定為零不用考慮，那我們現在從B1開始周遊遇到Bi不為零的時候比如B1不為零那麼在A數列中1的個數就為B1個，假如B1=0，B2不為零那麼同理從B2

開始。我們将這Bi個i一個個的拿走每拿走一個就計算一下拿走這一個i後B數列的值為多少，現在這個狀态我們視為一種新的狀态，再進行一次這個操作，知道把A數列全部拿完為止。就是一步步的将A拿出來，這樣也正好是按照的字典順序。

用這個解釋一下樣例，3 3     1 3 3 1

B1=3，即3個1（其實作在就是最後的答案了）那麼我們拿一個1，拿了這一個1對原數列的影響：1 2 1 0即用Bj=Bj-B[j-i],B1-1=2,B2-B1=1,B3-B2=0.現在我們用答案驗證是符合的。這樣一次次的拿将A數列中的數拿完。

AC代碼：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int t,n,m;
long long b[10050]={0};
int a[600]={0};
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		memset(b,0,sizeof(b));
		memset(a,0,sizeof(a));

		scanf("%d%d",&n,&m);
		for(int i=0;i<=m;i++)
		{
			scanf("%lld",&b[i]);
		}
		int k=0;
		for(int i=1;i<=m;i++)
		{
			if(k>=n)
			{
				break;
			}
			if(i<=0)
			{
				continue;
			}
			if(b[i]!=0)
			{
			    a[k]=i;
				k++;
				for(int j=i;j<=m;j++)
				{
					b[j]=b[j]-b[j-i];
				}
				i--;
			}
		}
		printf("%d",a[0]);
		for(int i=1;i<k;i++)
		{
			printf(" %d",a[i]);
		}
		printf("\n");
	}
	return 0;
}