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 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]\)
题意：
给定数组b，保存的数组a中的所有子集和的个数，让找个这个数组a，并且按照字典序输出来。
分析：
b数组里面除了第一个元素b[0]肯定为1之外(表示空集的个数有且仅有一个)，其余的第一次出现的b[i]==j（j!=0），那么就表示i这个数字肯定在a数组中存在，而且为第一个并且为最小的元素，同时将这个数的个数减减（相当于减去单独自己本身一个自己的情况），记录下标i。
这样循环的往后加b数组的元素下标偏移i个单位，如果此时两个数的个数均不为0，也就意味这后面的那个数，可以由前面这个数构成，然后让当前下标的数减去b[i],得到的那个数减去b[i]的个数，（相当于减去这个数可以由b[i]组合而成的个数）剩下的肯定就是这个数字本身的个数
就这样循环着往下找
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxm = 1100002;
int b[maxm];
int m;
int a[maxm];
int main()
{
int t;
scanf( "%d", &t );
while( t-- )
{
int n;
scanf( "%d%d", &n, &m );
for( int i = 0; i <= m; i++ )
{
scanf( "%d", b+i );
}
b[0] = 0;///空集的情况，不用任何的元素构成，将其赋值为0，不影响后面的计算
for( int i = 0; i < n; i++ )///循环得到a数组中的第i个元素
{
int j;
for( j = 0; j <= m; j++ )///找到当前的第一个不为0的
{
if( b[j] ) break;
}
b[j]--;///相当于有一个本身构成的元素
a[i] = j;///那么就肯定有一个这个元素，而且为当前的最小值
for( int k = j; k <= m; k++ )///找后面的所有可以由j组合而成的是数
{
if( k+j <= m && b[k] && b[k+j] )
{
b[k+j] -= b[k];
}
}
}
for( int i = 0; i < n; i++ )
{
i == 0 ? printf( "%d", a[i] ) : printf( " %d", a[i] );
}
printf( "\n" );
}
return 0;
}