注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

2014年04月21日  

2014-04-21 22:02:58|  分类: 母函数 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |


The Balance



Problem Description

Now you are asked to measure a dose of medicine with a
balance and a number of weights. Certainly it is not always achievable. So you
should find out the qualities which cannot be measured from the range [1,S]. S
is the total quality of all the weights.

 


Input

The input consists of multiple test cases, and each
case begins with a single positive integer N (1<=N<=100) on a line by
itself indicating the number of weights you have. Followed by N integers Ai
(1<=i<=N), indicating the quality of each weight where
1<=Ai<=100.

 


Output

For each input set, you should first print a line
specifying the number of qualities which cannot be measured. Then print another
line which consists all the irrealizable qualities if the number is not
zero.

 


Sample Input

3
1 2 4
3
9 2 1

 


Sample Output

0
2
4 5

 


Source


 


Recommend

lcy   |   We have carefully selected several similar
problems for you:  1171 2069 1708 1721 1701 

 


Statistic | Submit | Discuss | Note

The Balance

Time
Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K
(Java/Others)
Total Submission(s): 5300    Accepted Submission(s):
2134








Home | TopHangzhou
Dianzi University Online Judge 3.0
Copyright ? 2005-2014 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang
Rongtao
 LinLe GaoJie GanLu
Total
0.004349(s) query 4, Server time : 2014-04-21 22:00:21, Gzip enabled

Administration



做完这题,有必要重新理解下生成函数的功能及其作用:我们说(1+x+x^2)*(1+x^2+x^4+x^6)*(1+x^3+x^6+x^9+x^12)的运算结果的x^j的系数表示组合成j的组合数,那么想想(1+x+x^2)*(1-x^2-x^4-x^6)这样?如果里面有负号,则代表的有事什么呢?拿这道题来说,每种砝码既可以放在右盘,又可以放在左盘,(若按左物右码来说),放在左盘那就取减号,放在右盘就取加号。当然最终我们将指数看为正数,所有求的的系数要取绝对值!
在生成函数题目里,这是一道相当不错的题目!
#include<stdio.h>
#include<string.h>

int a1[100000],a2[100000];
int num[1000],count[10000] ;
int counts,sum;
int main()
{
int i,j,k,T;
while(scanf("%d",&T)!=EOF)
{
sum=0;
counts=0;
for(i=1;i<=T;i++)
{
scanf("%d",&num[i]);
sum+=num[i];
}
memset(a1,0,sizeof(a1));
memset(a2,0,sizeof(a2));
a1[0]=1;
a1[num[1]]=1;
for(i=2;i<=T;i++)
{
for(j=0;j<=sum;j++)
{
for(k=0;k+j<=sum && k<=num[i];k+=num[i])
{
if(k>=j) a2[k-j]+=a1[j];
else a2[j-k]+=a1[j];
a2[j+k]+=a1[j];
}
}
for(j=0;j<=sum;j++)
{
a1[j]=a2[j];
a2[j]=0;
}

}
for(i=1,j=0;i<=sum;i++)
{
if(a1[i]==0)
{
counts++;
count[j++]=i;
}
}
if(counts==0)
{
printf("0\n");
}
else
{
printf("%d\n",counts);
for(i=0;i<counts-1;i++)
{
printf("%d ",count[i]);
}
printf("%d\n",count[counts-1]);
}
}
return 0;
}



  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017