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?
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).
It is guaranteed that there exists at least one solution. And if there are different solutions, print the lexicographic minimum one.
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]$
1008 Rikka with Subset
签到题，大致的思想就是反过来的背包。
如果 Bi 是 B 数组中除了 B0 以外第一个值不为 0 的位置，那么显然 i 就是 A 中的最小数。
现在需要求出删掉 i 后的 B 数组，过程大概是反向的背包，即从小到大让 Bj-=B(j−i)。
时间复杂度 O(nm)。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<string>
#include<map>
#include<vector>
using namespace std; int b[];//最终结果b
int bb[];//目前得出的b
int a[]; int main()
{
int T,n,m,ans;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
scanf("%d",&b[i]);
memset(a,,sizeof(a));
memset(bb,,sizeof(bb));
bb[]=;
for(int i=;i<=m;i++)
{
a[i]=b[i]-bb[i];
for(int j=;j<=a[i];j++)//对bb进行更新
{
for(int k=m;k>=i;k--)//反着来避免已经加到结果里的数字再加一遍
bb[k]+=bb[k-i];
}
}
int flag=;
for(int i=;i<=m;i++)
for(int j=;j<=a[i];j++)
{
if(flag++) printf(" ");
printf("%d",i);
}
printf("\n");
}
return ;
}