博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
CodeChef Mahesh and his lost array
阅读量:5775 次
发布时间:2019-06-18

本文共 2631 字,大约阅读时间需要 8 分钟。

Mahesh and his lost array

 
Problem code:
ANUMLA
 

All submissions for this problem are available.

Read problems statements in and as well.

Mahesh got a beautiful array named A as a birthday gift from his beautiful girlfriend Namratha. There are N positive integers in that array. Mahesh loved the array so much that he started to spend a lot of time on it everyday. One day, he wrote down all possible subsets of the array. Then for each subset, he calculated the sum of elements in that subset and wrote it down on a paper. Unfortunately, Mahesh lost the beautiful array :(. He still has the paper on which he wrote all subset sums. Your task is to rebuild beautiful array A and help the couple stay happy :)

Input

The first line of the input contains an integer T denoting the number of test cases.

First line of each test case contains one integer N, the number of elements in A.
Second line of each test case contains 2^N integers, the values written on paper

Output

For each test case, output one line with N space separated integers in non-decreasing order.

Constraints

  • 1T50
  • 1N15
  • 0Values on paper10^9
  • All input values are valid. A solution always exists

Example

Input210 1020 1 1 2Output101 1

Explanation

Test case #2

For the array [1,1], possible subsets are {}, {1}, {1}, {1,1}, respective sums are 0, 1, 1, 2.

 

给出序列的所有子集和,还原序列的元素

从小到大枚举删数,然后遇到一个最小的即是序列中的数

#include 
using namespace std;typedef long long LL;const int N = 100010;int n , m , tot , x[N] ;bool vis[N] , tag ;vector
ans;void Output() { for( int i = 0 ; i < ans.size(); ++i ){ cout << ans[i] << ( i == n-1?'\n':' '); }}int find( int num ) { int l = 0 , r = tot-1 , pos = -1 ; if( num > x[r] ) return -1 ; while( l <= r ) { int mid = (l+r)>>1; if( x[mid] == num ) { if( vis[mid] ) l = mid + 1 ; else pos = mid , r = mid - 1 ; } else if( x[mid] < num ) l = mid + 1 ; else r = mid - 1 ; } return pos ;}void Run() { cin >> n ; tot = (1<
> x[i] ; sort( x , x + tot ); for( int i = 1 ; i < tot ; ++i ) if( !vis[i] ) { vis[i] = true; ans.push_back( x[i] ); if( ans.size() == n ) break ; for( int j = 1 ; j < tot ; ++j ) if( vis[j] ) { int pos = find( x[i] + x[j] ); if( pos == -1 || i == j ) continue ; vis[pos] = true ; } } Output();}int main(){// freopen("in.txt","r",stdin); int _ ,cas =1 ; cin >> _ ; while(_--) Run() ;}
View Code

 

转载于:https://www.cnblogs.com/hlmark/p/4297387.html

你可能感兴趣的文章
深入理解计算机系统(第三版) csapp 第三章部分答案
查看>>
Windows 的GUID
查看>>
Git详解之三 Git分支
查看>>
简单工厂
查看>>
编程笔记 2017-08-11
查看>>
paper 20 :color moments
查看>>
paper 101:图像融合算法及视觉艺术应用
查看>>
绘图笔记
查看>>
MySQL replace into 用法(insert into 的增强版)
查看>>
CMP-5013A Architectures and Operating Systems
查看>>
html5,单击文字自动获得焦点
查看>>
Android Volley
查看>>
科技发烧友之单反佳能700d中高端
查看>>
NANDflash和NORflash的区别(设计师在使用闪存时需要慎重选择)
查看>>
直接插入排序算法的学习
查看>>
<记录> PHP监控进程状态,完成掉线自动重启
查看>>
去掉二级页面 tabs 菜单, 修改返回按钮
查看>>
大白话系列之C#委托与事件讲解(二)
查看>>
c# 扩展方法奇思妙用高级篇四:对扩展进行分组管理
查看>>
Dev GridControl GridView常用属性
查看>>