2022年ACM程序设计与竞赛作业要点

A C M程序设计与竞赛作业1.采药2.金字塔问题3.毛毛虫问题4.Hamming Problem5.字符串正反连接6.去掉空格7.成绩转换8.金块问题9.工资问题io.“水仙花数”问题11.大小写转换12.取数游戏13.整除问题14.警察抓小偷15.n!16.汉诺塔问题17.猴子吃桃问题(递归)18.A+B for Input-Output Practice 19.A+B for Input-Output Practice(II)20.A+B for Input-Output Practice(III)21.A+B for Input-Output Practice(TV)22.埃及分数23.完数24.Fibbonacci Number _Hdu 207025.Pakets26.不要 62_Hdu20891 问 题 B:采药时间限制：1 S ec内存限制:128 MB提交:8 7 处理:72D U U题目描述辰辰是个很有潜能、天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一种难题。医师把他带到个到处都是草药日勺山洞里对他说：“孩子，这个山洞里有某些不一样日勺草药，采每一株都需要某些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到某些草药。假如你是一种聪颖的孩子，你应当可以让采到的草药的总价值最大。”假如你是辰辰，你能完毕这个任务吗？输入输入的第一行有两个整数T(1 T 1 0 0 0)和 M(1M 100),T 代表总共可以用来采药的时间，M 代表山洞里的草药口勺数目。接下来的M 行每行包括两个在1 到100之 间(包 括 1 和 100)日勺整数，分别表达采摘某株草药的时间和这株草药的价值。输出输出只包括一行，这一行只包括一种整数，表达在规定的时间内，可以采到日勺草药的最大总价值。样例输入70 371 10069 11 2样例输出3#include stdio.hvoid main。int a1021002=0;int t,tl,m 1 ,mJ j 1 ,k=1;scanf(%d%d,&t,&m);scanf(%d%d,&tlfor(il=l;il=tl)akil=ml;)k+;for(i=2;i=m;i+)scanf(%d%d,&tlfor(il=l;il=t;il+)(if(ilml+ak-l il-tl)akil=ak-lil;/采完总价值下降else值得采的状况;|k+;printf(n%dn,am t);)心得：这是一种动态规划的题目，首先定义一种二维数组，根据草药的性价比，优先采用较高的草药，假如时间不够，则减少性价比继续采用草药，直至时间结束，根据采集的草药计算它的最大值，这题通过比较算出也许采的状况，和不能采的状况，假如能采，那再判断值不值得采，得出最优解。2问 题A:金字塔问题时间限制：1 S e c内存限制:128 MB提交:5 4处理:32D D D题目描述)2、片1c?一)I o e I J幺合一种金字塔，如上图所示，请你求出一种从塔顶到塔底的途径，规定途径通过的点的数字和最小。例如上图所示日勺金字塔的最小途径为：40输入输入第一行是一种整数n1000;接下来是n行，第一行一种数；第二行两个数；o o o第 n 行 n 个数；数之间用空格分开。数的链接方式如图所示。输出一种数，就是从塔顶到塔底的途径的最小距离。样例输入5912 1510 6 83 189 519 7 104 16样例输出40#includevoid mainQint i,j,n;int a100100;定义一种二维数组；scanf(H%dH,&n);for(i=l;i=n;i+)f o r(j=l;j =l ;i-)f o r(j=l;j a i+l j j+l )e l s ea i j =a i j +a口 求 得 每 次 途 径 最 小 值;)p r i n t f C%d ,a l l );)心得：这个题目重要运用了动态规划的思想，定义一种二维数组，把所输入的数据存入进去，然后从它的第一行处理，比较相邻位置数的大小，取最小日勺途径和上一行对应的数相加，获得最小途径，进行循环，直到求出数组中祖 山,即所求的成果。3问 题B:毛毛虫问题时间限制：1 Sec内存限制：128 M B提交:3 2处理:16n n n题目描述Mary在她家门口水平种了一排苹果树，共有N棵。忽然Mary发目前左起第P棵树上（从1开始计数）有一条毛毛虫。为了看到毛毛虫变蝴蝶的过程，Lelc在苹果树旁观测了很久。虽然没有看到蝴蝶，但Lele发现了一种规律：每过1分钟，毛毛虫会随机从一棵树爬到相邻的一棵树上。例如刚开始毛毛虫在第2棵树上，过1分钟后，毛毛虫也许会在第1棵树上或者第3棵树上。假如刚开始时毛毛虫在第1棵树上，过1分钟后来，毛毛虫一定会在第2棵树上。目前告诉你苹果树日勺数目N,以及毛毛刚开始所在的位置P,请问，在M分钟后，毛毛虫抵达第T棵树，一共有多少种行走方案数。输入输入四个整数N P M T。输出输出一种整数，就是行走的方案数。样例输入7444样例输出6#includevoid mainQ（int i,j;int p,m,n,t;inta100100=0;定义一种二维数组;scanf(H%d%d%d%dn,&n,&p,&m,&t);a同=1；毛毛虫刚开始在数组中的位置；for(i=l;i=m;i+)(for(j=l;j=n;j+)a 叫产 ai-lj-l+ai-lj+l;每一步的方案数；|)printf(%dn,amt);M分钟后到T 棵树行走的方案数;)心得：这一题运用了动态规划的思想，毛毛虫日勺每一步都会影响下一步的成果，因此首先按照一般状况找出规律及其其公式，进而算出方案数。首先定义一种二维数组，初始化毛毛虫的起始位置，然后通过两个循环，求出毛毛虫走每一步的方案数,存在二维数组中，然后求出第M 分钟到T 棵树行走的方案数。4 问题 A:Hamming Problem时间限制：1 S ec内存限制:128 MB提交:6 1 处理:23nirn题目描述For each three prime numbers pl,p2 and p3,lets define Hamming sequence Hi(pl,p2,p3),i=l?.as containing in increasing order all the natural numbers whose only prime divisors arepl,p2 or p3.For example,H(2,3,5)=2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,.So H5(2,3,5)=6.输入In the single line of input file there are space-separated integers pl p2 p3 i.输出The output file must contain the single integer-Hi(pl,p2,p3).All numbers in input andoutput are less than 10八18.样例输入2 3 5 5样例输出6#include stdio.hint minx(int pl,int p2,int p3)/定义有参函数 minx；int min=pl;if(p2min)min=p2;if(p3min)min=p3;return min;/求 pi,p2,p3 W g 最小值；int mainQint pl,p2,p3,t,i;int a,b,c;char num10000;scanf(%)d%d%d%d,&pl,&p2,&p3,&t);a=b=c=0;num0=l;for(i=l;iv=t;i+)numi=minx(pl*numa,p2*numb,p3*mimc);/调用 minx 函数;if(num i=pl*num a)a+;if(num i=p2*num b)b+;if(num i=p3*num c)c+;求所有的能被pl,p2,p3整除的数；printf(%dn,numt);return 0;心得：运用动态规划的思想，定义一种一维数组，把所有符合条件的数按次序存进一维数组中，这个编程运用了函数调用的措施求三个数的最小值，然后把这个最小值存进一维数组中，每次存进一种数，下次都会用存进去口勺这个数求解下一种数，进行循环。5问 题B:字符串正反连接时间限制：1 S ec内存限制：128 MB提交:6 8处理:42n n n题目描述所给字符串正序和反序连接，形成新串并输出输入任 意 字 符 串（长度=50）输出字符串正序和反序连接所成的新字符串样例输入123abc样例输出123abccba321#include#includevoid mainQchar a50;/定义一种字符串；int i?f;while(scanf(%s,&a)!=EOF)实现多行实例输入；f=strlen(a);/把字符串口勺长度值赋给f;for(i=O;i=0;i-)(printf，%c,ai);/把字符串反序输出；printf(n);)心得：定义一种字符串，运用strlenO函数获取字符串的长度值f,首先用for循环，把这个字符串正序输出，然后再用for循环对这个字符串进行反序输出，这里重要考察了输入输出。6问 题C:去掉空格时间限制：1 S ec内存限制:128 MB提交:2 7 处理:4n n n题目描述读入某些字符串，将其中的空格去掉。输入输入为多行，每行为一种字符串，字符串只由字母、数字和空格构成，长度不超过80o 输入以End of file结束。输出对于每行输入，输出转换后日勺字符串。样例输入Hello World123Nice to meet youabc样例输出HeUoWorld123Nicetomeetyouabc提醒用scanf是不能读入一行有空格口勺字符串日勺，用gets吧。用“gets(str)!=NULL”可以判断输入与否结束，假如此条件为假(即gets(str)二 二NULL),则表达输入结束(对于本题)。#include#includevoid mainQ(int i,f;char a90;/定义一种字符串；while(gets(a)!=NULL)(f=strlen(a);/把字符串的长度值赋给f;fbr(i=O;if;i+)(if(a炉=1)printf(%c”,ai+l);/去掉空格；i=i+1;)elseprintf(c,ai);没有空格，直接输出;)printf(n);)心得：这里也是重要考察输入输出问题，首先也是定义了一种字符串，用strlenO函数获得字符串的长度K进行f次循环，判断这个字符串与否有空格？假如有把数组中日勺每个数往后进一位，即去点空格，假如没有直接输出。7问题D:成绩转换时间限制：1 S ec内存限制：128 MB提交:7 8处理:30nnn题目描述输入一种百分制口勺成绩t,将其转换成对应口勺等级，详细转换规则如下:90 100 为 A;8089为B;7079为C;60-69 为 D;059为E;输入输入数据有多组，每组占一行，由一种整数构成。输出对于每组输入数据，输出一行。假如输入数据不在。10。范围内，请输出一行：“Scoreis error!o样例输入5667100123样例输出EDAScore is error!提醒#includeint mainQint x;while(scanf(%d,&x)!=EOF)/实现多行实例输入;(if(x60)printf(En);else if(x70)printf(Dn);else if(x80)printf(Cn);else if(x90)printf(Bn);else if(x=2),最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，但愿用至