枚举与贪心算法例题.docx
- 文档编号:9862132
- 上传时间:2023-05-21
- 格式:DOCX
- 页数:55
- 大小:43.58KB
枚举与贪心算法例题.docx
《枚举与贪心算法例题.docx》由会员分享,可在线阅读,更多相关《枚举与贪心算法例题.docx(55页珍藏版)》请在冰点文库上搜索。
枚举与贪心算法例题
例1:
NameThatNumber命名那个数字
在威斯康辛州牛大农场经营者之中,都习惯于请会计部门用连续数字给母牛打上烙印。
但是,母牛用手机时并没感到这个系统的便利,它们更喜欢用它们喜欢的名字来呼叫它们的同伴,而不是用像这个的语句"C'mon,#4734,getalong."。
请写一个程序来帮助可怜的牧牛工将一只母牛的烙印编号翻译成一个可能的名字。
因为母牛们现在都有手机了,使用那标准的按键的排布来把收到从数目翻译到文字:
(除了"Q"和"Z")
2:
A,B,C5:
J,K,L8:
T,U,V
3:
D,E,F6:
M,N,O9:
W,X,Y
4:
G,H,I7:
P,R,S
可接受的名字都被放在这样一个叫作"dict.txt"的文件中,它包含一连串的少于5,000个可被接受的牛的名字。
(所有的名字都是大写的且已按字典序排列)请读入母牛的编号并返回那些能从编号翻译出来并且在字典中的名字。
举例来说,编号4734能产生的下列各项名字:
GPDGGPDHGPDIGPEGGPEHGPEIGPFGGPFHGPFIGRDGGRDHGRDIGREGGREHGREIGRFGGRFHGRFIGSDGGSDHGSDIGSEGGSEHGSEIGSFGGSFHGSFIHPDGHPDHHPDIHPEGHPEHHPEIHPFGHPFHHPFIHRDGHRDHHRDIHREGHREHHREIHRFGHRFHHRFIHSDGHSDHHSDIHSEGHSEHHSEIHSFGHSFHHSFIIPDGIPDHIPDIIPEGIPEHIPEIIPFGIPFHIPFIIRDGIRDHIRDIIREGIREHIREIIRFGIRFHIRFIISDGISDHISDIISEGISEHISEIISFGISFHISFI
碰巧,81个中只有一个"GREG"是有效的(在字典中)。
写一个程序来对给出的编号打印出所有的有效名字,如果没有则输出NONE。
编号可能有12位数字。
INPUTFORMAT
单独的一行包含一个编号(长度可能从1到12)。
OUTPUTFORMAT
以字典顺序输出一个有效名字的不重复列表,一行一个名字。
SAMPLEINPUT
4734
SAMPLEOUTPUT
GREG
分析:
思路1:
一个数字对应3个字母,如果我们先枚举出数字所代表的所有字符串,就有3^12种,然后再在5000的字典里寻找,可以用二分查找,数据规模是3^12*log5000=6.5e6,空间规模是5000。
其实可以做的更好!
思路2:
一个字母只对应一个数字,从字典中读入一个单词,把它转化成唯一对应的数字,看它是否与给出的数字匹配,时间规模是5000*12=6e4,空间规模是常数,而且编程复杂度较低。
参考代码:
#include
intnum[26]={2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,0,7,7,8,8,8,9,9,9,0};
intname[13];
charles[13];
intmain()
{inti=-1,j=0;
while(scanf("%c",&name[++i])!
=-1&&name[i]!
='\n')
name[i]-='0';
if(name[i]=='\n')name[i]=0;
while(scanf("%s",les)!
=-1)
{i=-1;
while(les[++i]!
=0)
if(num[les[i]-'A']!
=name[i])break;
if(les[i]==0&&name[i]==0)
{printf("%s\n",les);j=1;}
}
if(j==0)printf("NONE\n");
return0;
}
例2:
PalindromicSquares回文平方数
回文数是指从左向右念和从右向左念都一样的数。
如12321就是一个典型的回文数。
给定一个进制B(2<=B<=20,由十进制表示),输出所有的大于等于1小于等于300(十进制下)且它的平方用B进制表示时是回文数的数。
用’A’,’B’……表示10,11等等。
INPUTFORMAT
共一行,一个单独的整数B(B用十进制表示)。
OUTPUTFORMAT
每行两个B进制的符合要求的数字,第二个数是第一个数的平方,且第二个数是回文数。
SAMPLEINPUT
10
SAMPLEOUTPUT
11
24
39
11121
22484
26676
10110201
11112321
12114641
20240804
21244944
26469696
分析:
枚举+进制转换。
穷举1——300的所有平方数,转进制,回文数的判断,OK。
参考代码:
#include
chara[20]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J'};
intmain()
{intb,i,j=0,k,pan,z,c[20]={0},d[20]={0};
longp;
scanf("%d",&b);
for(i=1;i<300;i++)
{memset(c,0,sizeof(c));memset(d,0,sizeof(d));
pan=1;j=0;p=i*i;
while(p!
=0)
{c[j]=p%b;p=p/b;j++;}
for(k=j/2;;k>=1;k--)
if(c[k-1]!
=c[j-k])pan=0;
if(pan==0)continue;
k=0;z=i;
while(z!
=0)
{d[k]=z%b;z=z/b;k++;}
if(pan==1)
{j--;k--;
for(;k>=0;k--)
printf("%c",a[d[k]]);
printf("");
for(;j>=0;j--)
printf("%c",a[c[j]]);
printf("\n");
}
}
return0;
}
例3:
DualPalindromes双重回文数
如果一个数从左往右读和从右往左读都是一样,那么这个数就叫做“回文数”。
例如,12321就是一个回文数,而77778就不是。
当然,回文数的首和尾都应是非零的,因此0220就不是回文数。
事实上,有一些数(如21),在十进制时不是回文数,但在其它进制(如二进制时为10101)时就是回文数。
编一个程序,从文件读入两个十进制数N(1<=N<=15)S(0
本问题的解决方案不需要使用大于32位的整型变量。
INPUTFORMAT
只有一行,用空格隔开的两个数N和S。
OUTPUTFORMAT
N行,每行一个满足上述要求的数,并按从小到大的顺序输出。
SAMPLEINPUT
325
SAMPLEOUTPUT
26
27
28
分析:
枚举。
因为数据很小,所以只需要从s开始枚举每个十进制数然后判断就行了。
参考代码:
#include
intmain()
{intb,i=0,j=0,k,pan,n;
intc[30]={0};
longs,a;
scanf(cin,"%d%ld",&n,&s);
while(i {s++;a=s; for(b=2;b<=10;b++) {j=0;pan=1; memset(c,0,sizeof(c)); while(s! =0) {c[j]=s%b;s=s/b;j++;} for(k=j/2;k>=1;k--) if(c[k-1]! =c[j-k])pan=0; if(pan==0) {s=a;continue;} else {printf("%ld\n",a);i++;s=a;break;} } } return0; } 例4: MixingMilk混合牛奶 牛奶包装是一个如此低利润的生意,以至于尽可能低地控制初级产品(牛奶)的价格变得十分重要。 请帮助Merry的牛奶制造公司(MerryMilkMakers')以尽可能最廉价的方式取得他们所需的牛奶。 Merry的牛奶制造公司从一些农民那购买牛奶,每个农民卖给牛奶制造公司的价格不一定相同。 而且,如一只母牛一天只能生产一定量的牛奶,农民每一天只有一定量的牛奶可以卖。 每天,Merry的牛奶制造公司从每个农民那购买一定量的牛奶,少于或等于农民所能提供的最大值。 给出Merry牛奶制造公司的每日的牛奶需求,连同每个农民的可提供的牛奶量和每加仑的价格,请计算Merry的牛奶制造公司所要付出钱的最小值。 注意: 每天农民生产的牛奶的总数对Merry的牛奶制造公司来说是足够的。 INPUTFORMAT 第1行: 二个整数,N和M。 第一个数值,N,(0<=N<=2,000,000)是Marry的牛奶制造公司的一天需要牛奶的数量。 第二个数值,M,(0<=M<=5,000)是提供牛奶的农民个数。 第2到M+1行: 每行二个整数,Pi和Ai。 Pi(0<=Pi<=1,000)是农民i的牛奶的价格。 Ai(0<=Ai<=2,000,000)是农民i一天能卖给Marry的牛奶制造公司的牛奶数量。 OUTPUTFORMAT 单独的一行包含单独的一个整数,表示Marry的牛奶制造公司拿到所需的牛奶所要的最小费用。 SAMPLEINPUT 1005 520 940 310 880 630 SAMPLEOUTPUT 630 分析: 思路1: 简单的贪心算法。 将所有的牛奶按价格升序排列(用快排),然后从低到高买入,直到买够m为止。 思路2: 最佳解题方法。 因为价格的范围在1..1000之内,所以,我们只要在读入数据的时候把相同价格的合并即可,进行计算时,也只需要fori: =0to1000do进行扫描如果有价格为i的牛奶就收购即可,所以不需要排序。 参考代码: #include #include #include #decineMAXFARMER5000 typedefstructFarmerFarmer; structFarmer{intp;inta;}; intfarmcmp(constvoid*va,constvoid*vb) {return((Farmer*)va)->p-((Farmer*)vb)->p;} intnfarmer; Farmerfarmer[MAXFARMER]; intmain() {inti,n,a,p; scanf("%d%d",&n,&nfarmer); for(i=0;i scanf("%d%d",&farmer[i].p,&farmer[i].a); qsort(farmer,nfarmer,sizeof(farmer[0]),farmcmp); p=0; for(i=0;i {a=farmer[i].a; if(a>n)a=n; p+=a*farmer[i].p; n-=a; } printf(cout,"%d\n",p); return0; } 例5: BarnRepair修理牛棚 在一个月黑风高,下着暴风雨的夜晚,农民约翰的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假,所以牛棚没有住满。 剩下的牛一个紧挨着另一个被排成一行来过夜。 有些牛棚里有牛,有些没有。 所有的牛棚有相同的宽度。 自门遗失以后,农民约翰必须尽快在牛棚之前竖立起新的木板。 他的新木材供应商将会供应他任何他想要的长度,但是供应商只能提供有限数目的木板。 农民约翰想将他购买的木板总长度减到最少。 给出: 可能买到的木板最大的数目M(1<=M<=50);牛棚的总数S(1<=S<=200);牛棚里牛的总数C(1<=C<=S);和牛所在的牛棚的编号stall_number(1<=stall_number<=S),计算拦住所有有牛的牛棚所需木板的最小总长度。 输出所需木板的最小总长度作为答案。 INPUTFORMAT 第1行: M,S和C(用空格分开) 第2到C+1行: 每行包含一个整数,表示牛所占的牛棚的编号。 OUTPUTFORMAT 单独的一行包含一个整数表示所需木板的最小总长度。 SAMPLEINPUT 45018 3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43 SAMPLEOUTPUT 25 分析: 贪心 思路一: 要使木板总长度最少,就要使未盖木板的长度最大。 我们先用一块木板盖住牛棚,然后,每次从盖住的范围内选一个最大的空隙,以空隙为界将木板分成两块,重复直到分成m块或没有空隙。 思路二: 显然,当所有木板均用上时,长度最短(证明....)。 正向思维,初始状态有c块木板,每块木板只盖住一个牛棚。 由c块倒推至m块木板,每次寻找这样的两个牛棚: 其间距在所有未连接的木板中最小。 当这两个牛棚的木板连接时,总木板数减1,总长度增加1。 思路三: 显然,当所有木板均用上时,长度最短。 用上m块木板时有m-1各间隙。 现在的目标是让总间隙最大。 将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的m-1个作为间隙,其余地方用木板盖住即可。 参考代码1: c++ #include #decinemax202 usingnamespacestd; inta[max],b[max],now;//有牛的编号,间隙,最大长度 intm,s,c; intcmp2(constvoid*va,constvoid*vb) {return*(int*)vb-*(int*)va;} intmain() {inti; cin>>m>>s>>c; for(i=0;i qsort(a,c,sizeof(a[0]),cmp2);//编号从大到小 for(i=0;i b[i-1]=a[i]-a[i+1]-1;//所有间隔 qsort(b,c,sizeof(b[0]),cmp2);//所有间隔按从大到小排列 now=a[0]-a[c-1]+1; for(i=0 ;i now=now-b[i];//减去那些间隔从大到小,直到块数等于最大购入量 cout< return0; } 参考代码2: #include #include #include #decineMAXSTALL1000 inthascow[MAXSTALL]; intintcmp(constvoid*va,constvoid*vb) {return*(int*)vb-*(int*)va;} intmain() {intn,m,nstall,ncow,i,j,c,lo,hi,nrun; intrun[MAXSTALL]; scanf("%d%d%d",&m,&nstall,&ncow); for(i=0;i {scanf("%d",&c);hascow[c-1]=1;} n=0; for(i=0;i hascow[i];i++)n++; lo=i; for(i=nstall-1;i>=0&& ! hascow[i];i--)n++; hi=i+1;nrun=0;i=lo; while(i {while(hascow[i]&&i i++; for(j=i;j hascow[j];j++) ; run[nrun++]=j-i; i=j; } qsort(run,nrun,sizeof(run[0]),intcmp); for(i=0;i n+=run[i]; printf(cout,"%d\n",nstall-n); return0; } 参考代码3: c++ #include #include usingnamespacestd; constintMAXS=202; constintMAXM=50; intdis[MAXS];intstn[MAXS]; intmain() {intm,s,c,i,x; cin>>m>>s>>c; if(m>=c){cout< for(i=0;i cin>>stn[i]; sort(stn,stn+c); for(i=0;i dis[i]=stn[i+1]-stn[i]-1; sort(dis,dis+c-1); x=stn[c-1]-stn[0]+1; for(i=0;i x-=dis[c-2-i]; cout< return0; } 例6: Calfflac 据说如果你给无限只母牛和无限台巨型便携式电脑(有非常大的键盘),那么母牛们会制造出世上最棒的回文。 你的工作就是去寻找这些牛制造的奇观(最棒的回文)。 在寻找回文时不用理睬那些标点符号、空格(但应该保留下来以便做为答案输出),只用考虑字母'A'-'Z'和'a'-'z'。 要你寻找的最长的回文的文章是一个不超过20,000个字符的字符串。 我们将保证最长的回文不会超过2,000个字符(在除去标点符号、空格之前)。 输入格式: 输入文件不会超过20,000字符。 这个文件可能一行或多行,但是每行都不超过80个字符(不包括最后的换行符)。 样例输入: Confuciussay: Madam,I'mAdam. 输出格式: 输出的第一行应该包括找到的最长的回文的长度。 下一行或几行应该包括这个回文的原文(没有除去标点符号、空格),把这个回文输出到一行或多行(如果回文中包括换行符)。 如果有多个回文长度都等于最大值,输出最前面出现的那一个。 样例输出: 11 Madam,I'mAdam 分析: 枚举。 枚举中间数(也就是认为它是回文数最中间的字母),然后左右扩展(忽略非字母)至出界和不相等。 最后更新最大值。 要考虑回文是奇数和偶数两种情况。 提示大家在开始扩展之前就判断(很巧妙,大家举几个例子就可以明白了) 输入中的换行符可以维持原样不变。 参考代码: #include #include #include #include charfulltext[21000],text[21000],*pal;intpallen; voidcindpal(void) {char*p,*fwd,*bkwd,*etext; intlen; etext=text+strlen(text); for(p=text;*p;p++) {for(fwd=bkwd=p;bkwd>=text&&fwd bkwd++;len=fwd-bkwd; if(len>pallen) {pal=bkwd;pallen=len;} for(bkwd=p,fwd=p+1;bkwd>=text&&fwd bkwd++;len=fwd-bkwd; if(len>pallen) {pal=bkwd;pallen=len;} } } voidmain(void) {char*p,*q;intc,i,n; p=fulltext;q=text; while((c=getc(cin)) ! =EOF) {if(isalpha(c))*q++=tolower(c); *p++=c; } *p='\0';*q='\0'; cindpal(); printf("%d\n",pallen); n=pal-text; for(i=0,p=fulltext;*p;p++) if(isalpha(*p))if(i++==n)break; for(i=0;i {putc(*p); if(isalpha(*p))i++; } printf("\n"); return0; } 例7: PrimeCryptarithm牛式 下面是一个乘法竖式,如果用我们给定的那n个数字来取代*,可以使式子成立的话,我们就叫这个式子牛式。 *** x** ------- *** *** ------- **** 数字只能取代*,当然第一位不能为0。 注意一下在美
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 枚举 贪心 算法 例题