hdu--6092--Rikka with Subset

你的名字 2022-06-10 03:55 104阅读 0赞

# Rikka with Subset #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)  
Total Submission(s): 1291    Accepted Submission(s): 637**

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

题目大意：

n为a数组的元素个数，这个数组的各项和为m。a数组一共有2^n种子串，（由组合公式c\[0\]\[n\]+c\[1\]\[n\]+c\[2\]\[n\]+.....+c\[n\]\[n\]得）。b\[i\] 表示元素和为 i 的子串个数。给你数组b\[i\],大小为m，以及a数组大小n，让你求 a\[\]，

并按照其字典序最小输出。

解题思路：

对于数组b，除了b\[0\]外，第一个值不为零的b\[i\]，在a数组里一定存在，且存在的个数就为b\[i\]个，

因为a的子串包括那些只含有a数组某一个元素的，这些子串的和只有那一个元素的值，往往较小

排在前面，这时候至少可以确定一个a中的元素，现在要做的是把这已经个确定的元素拿出来，

并且对b进行操作，处理成除去  拿出去的那个元素  后，b数组继续满足原先的定义，就像刚开始那个

元素就没有出现过一样。这个时候我们就可以重复上述的步骤，直到取出a数组中的全部元素。

下面的问题就是怎么对b数组进行处理：

和为j的（总）组合数=和为j的组合数（含有i元素）\+和为j的组合数（不含有i元素）

我们的目的就是把各项处理成  和为j的组合数（不含有i元素） 的那种。和为j的（总）组合数为

处理前的状态，已知。下面就是确定和为j的组合数（含有i元素）了，而  和为j的组合数（含有i元素）为 b\[j-i\] 个，因为有几种值为j的情况 可以由（j-i）+i得到，那么就有多少种 和为j的组合数（含有i元素） ，所以为b\[j-i\]个。

有          b\[j\]=b\[j\]-b\[j-i\];这一个等式 就可以了。

代码：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 #include&lt;bits/stdc++.h&gt; 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 int&nbsp;b[ 
 10050]; 
 
 int&nbsp;a[ 
 600]; 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;T,&nbsp;n,&nbsp;m,&nbsp;k; 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;T); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(T--) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d%d",&nbsp;&amp;n,&nbsp;&amp;m); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;=&nbsp;m;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;b[i]); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 1;&nbsp;i&nbsp;&lt;=&nbsp;m;&nbsp;) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(k&nbsp;&gt;=&nbsp;n) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 break; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(i&nbsp;&lt;=&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 continue; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(b[i]&nbsp;!=&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[k++]&nbsp;=&nbsp;i; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;j&nbsp;=&nbsp;i;&nbsp;j&nbsp;&lt;=&nbsp;m;&nbsp;j++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b[j]&nbsp;=&nbsp;b[j]&nbsp;-&nbsp;b[j&nbsp;-&nbsp;i]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i++; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d",&nbsp;a[ 
 0]); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 1;&nbsp;i&nbsp;&lt;&nbsp;k;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "&nbsp;%d",&nbsp;a[i]); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "\n"); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>