Rikka with SubsetTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) 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]$ Source Recommend Statistic | Submit | Discuss | Note 思路:动态规划+思维 因为已知了集合B要求集合A的序列,显然空集与全集的数量都为1,所以B0和Bm都为1 集合A中1的数量就等于B1,那么B2便可以由B1推出(排列组合的思想),B3可有B2推出,以此类推,采用01背包为题解决
|