HDU 6092 01背包变形
Rikka with Subset
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1846 Accepted Submission(s): 896
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.
2 3
1 1 1 1
3 3
1 3 3 1
1 1 1
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]
#include<bits/stdc++.h>
#define db double
#define ll long long
#define ci(x) scanf("%d",&x)
#define cd(x) scanf("%lf",&x)
#define cl(x) scanf("%lld",&x)
#define pi(x) printf("%d\n",x)
#define pd(x) printf("%f\n",x)
#define pl(x) printf("%lld\n",x)
#define fr(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=1e5+;
const int mod=1e9+;
const int MOD=mod-;
const db eps=1e-;
const int inf = 0x3f3f3f3f;
int b[N],f[N],a[N];
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
int t;
ci(t);
for(int ii=;ii<=t;ii++)
{
int n,m,c=;
ci(n),ci(m);
for(int i=;i<=m;i++) ci(b[i]);
memset(f,,sizeof(f));
f[]=;
for(int i=;i<=m;i++){//我们要加入的数字i
int v=b[i]-f[i];//加入v个i
for(int j=;j<v;j++){
a[++c]=i;
for(int k=m;k>=i;k--){
f[k]+=f[k-i];//更新当前组合的种数
}
}
}
for(int i=;i<=n;i++){
printf("%d%c",a[i],i==n?'\n':' ');
}
}
}
最新文章
- PHPmailer关于Extension missing: openssl报错的解决
- jquery.SuperSlide.js只需要调用一个插件就能实现网页大部分特效--推荐
- Bash注释
- js删除所有子元素
- 二分查找实现(Jon Bentley:90%程序员无法正确实现)
- OK335xS PMIC(TPS65910A3A1RSL) reset
- 50个非常有用的PHP工具
- LeetCode——Add Binary
- 支持wmv、mpg、mov、avi格式的网页视频播放代码
- EL表达式判断不能为空
- CSS3美化网页元素
- JDBC存储和读取二进制数据
- Java中的String,StringBuilder,StringBuffer
- 在vue 里使用腾讯ditu
- exgcd
- .net敏捷开发框架 力软敏捷开发(learun) 让开发变的更简单
- 判断GPS是否开启&;转到设置GPS界面
- 支持-webkit-前缀的浏览器修改滚动条样式
- django外键以及主表和子表的相互查询
- hdu2510 爆搜+打表