2017杭电多校第五场Rikka with Subset
2024-09-30 21:27:03
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背包为题解决
|
最新文章
- Oracle Blob 字段的模糊查询
- u-boot board_uart_init流程
- jquery Ajax应用总结
- java工作流bpm开发ERP实例
- map,zip,reduce函数
- spring boot MySQL极简封装
- socket(套接字)初使用
- bootstrap table表格前台分页,点击tab选项,重新刷新表格
- 【Java并发编程】21、线程池ThreadPoolExecutor源码解析
- GitHub安装教程
- sscanf的字符串格式化用法
- pandas apply()函数参数 args
- 浏览器实现PDF预览
- Prometheus Node_exporter 之 Network Traffic Detail
- iOS 项目一直在后台执行
- 使用sphinx创建和查看文档
- NS3 fifth.cc 拥塞窗口实例
- linux命令新建文件
- 说一说activity
- streamsets 包管理