首页 > 代码库 > hdu acm 2082 找单词
hdu acm 2082 找单词
找单词
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3722 Accepted Submission(s): 2663
Problem Description
假设有x1个字母A, x2个字母B,..... x26个字母Z,同时假设字母A的价值为1,字母B的价值为2,..... 字母Z的价值为26。那么,对于给定的字母,可以找到多少价值<=50的单词呢?单词的价值就是组成一个单词的所有字母的价值之和,比如,单词ACM的价值是1+3+14=18,单词HDU的价值是8+4+21=33。(组成的单词与排列顺序无关,比如ACM与CMA认为是同一个单词)。
Input
输入首先是一个整数N,代表测试实例的个数。
然后包括N行数据,每行包括26个<=20的整数x1,x2,.....x26.
然后包括N行数据,每行包括26个<=20的整数x1,x2,.....x26.
Output
对于每个测试实例,请输出能找到的总价值<=50的单词数,每个实例的输出占一行。
Sample Input
2 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 2 6 2 10 2 2 5 6 1 0 2 7 0 2 2 7 5 10 6 10 2 10 6 1 9
Sample Output
7 379297
Source
2006/1/15 ACM程序设计期末考试
这是道母函数的经典题,首先读懂题意,虽然始终问题,不过也容易出现歧义。输入的是对应字母的数量,字母的价值是固定的。
然后用母函数求所有小于50价值的组合数,求和即可。
这道题用到了母函数模板,稍微有所变化,能改对这道题,说明对母函数的理解比较深刻了。
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <algorithm> 5 #include <cstring> 6 7 using namespace std; 8 #define maxx 50 9 int ans[maxx+2],temp[maxx+2],v[30]; 10 void init()//母函数打表 11 { 12 int i; 13 memset(ans,0,sizeof(ans)); 14 for(i=1;i<=26;i++)//初始化第一个式子系数 15 { 16 if(v[i]!=0) 17 { 18 for(int j=0;j*i<=maxx&&j<=v[i];j++) 19 { 20 ans[j*i]=1; 21 } 22 break;//用于临时保存每次相乘的结果 23 } 24 } 25 for(i=i+1;i<=26;i++)//循环每一个式子 26 { 27 if(v[i]==0) 28 continue; 29 for(int j=0;j<=maxx;j++)//循环第一个式子各项 30 { if(ans[j]==0) 31 continue; 32 for(int k=0;k+j<=maxx&&k/i<=v[i];k+=i)//下个式子的各项 33 temp[k+j]+=ans[j];//结果保存到temp数组中 34 } 35 36 for(int j=0;j<=maxx;j++)//临时保存的值存入ans数组 37 { 38 ans[j]=temp[j]; 39 // cout<<ans[j]<<‘ ‘; 40 temp[j]=0; 41 } 42 // cout<<endl; 43 } 44 } 45 int main() 46 { 47 48 int T; 49 scanf("%d",&T); 50 while(T--) 51 { 52 for(int i=1;i<=26;i++) 53 scanf("%d",&v[i]); 54 init(); 55 int a=0; 56 for(int i=1;i<=50;i++) 57 a+=ans[i]; 58 cout<<a<<endl; 59 } 60 return 0; 61 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。