《最新ACM程序设计与竞赛作业要点.doc》由会员分享，可在线阅读，更多相关《最新ACM程序设计与竞赛作业要点.doc（130页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-dateACM程序设计与竞赛作业要点主页ACM程序设计与竞赛作业1. 采药2. 金字塔问题3. 毛毛虫问题4. Hamming Problem5. 字符串正反连接6. 去掉空格7. 成绩转换8. 金块问题9. 工资问题10.“水仙花数”问题11.大小写转换12.取数游戏13.整除问题14.警察抓小偷15.n！16.汉诺塔问题17.猴子吃桃问题（递归）18. A+B for I
2、nput-Output Practice (I)19. A+B for Input-Output Practice (II)20. A+B for Input-Output Practice (III)21. A+B for Input-Output Practice (IV)22.埃及分数23.完数24. Fibbonacci Number _Hdu 207025. Pakets26. 不要62 _Hdu 20891问题 B: 采药时间限制:1 Sec内存限制:128 MB提交:87解决:72提交状态讨论版题目描述辰辰是个很有潜能、天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想
3、拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是辰辰，你能完成这个任务吗？输入输入的第一行有两个整数T（1 T 1000）和M（1M 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。输出输出只包括一行，这一
4、行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。样例输入70 371 10069 11 2 样例输出3#include stdio.hvoid main() int a1021002=0; int t,t1,m1,m,i,i1,k=1; scanf(%d%d,&t,&m); scanf(%d%d,&t1,&m1); for(i1=1;i1=t1) aki1=m1; k+; for(i=2;i=m;i+) scanf(%d%d,&t1,&m1); for(i1=1;i1=t;i1+) if(i1m1+ak-1i1-t1) aki1=ak-1i1; /采完总价值下降 else a
5、ki1=m1+ak-1i1-t1;/值得采的情况； k+; printf(%d,amt);心得：这是一个动态规划的题目，首先定义一个二维数组，根据草药的性价比，优先采取较高的草药，如果时间不够，则降低性价比继续采取草药，直至时间结束，根据采集的草药计算它的最大值，这题通过比较算出可能采的情况，和不能采的情况，如果能采，那再判断值不值得采，得出最优解。2问题 A: 金字塔问题时间限制:1 Sec内存限制:128 MB提交:54解决:32提交状态讨论版题目描述給一个金字塔，如上图所示，请你求出一个从塔顶到塔底的路径，要求路径经过的点的数字和最小。例如上图所示的金字塔的最小路径为：40输入输入第一行
6、是一个整数n1000；接下来是n行，第一行一个数；第二行两个数；。第n行n个数；数之间用空格分开。数的链接方式如图所示。输出一个数，就是从塔顶到塔底的路径的最小距离。样例输入5912 1510 6 83 18 9 519 7 10 4 16样例输出40#includevoid main() int i,j,n; int a100100;定义一个二维数组； scanf(%d,&n); for(i=1;i=n;i+) for(j=1;j=1;i-) for(j=1;jai+1j+1) aij=aij+ai+1j+1; else aij=aij+ai+1j; /求得每次路径最小值； printf(%
7、d,a11); 心得：这个题目主要运用了动态规划的思想，定义一个二维数组，把所输入的数据存入进去，然后从它的第一行处理，比较相邻位置数的大小，取最小的路径和上一行对应的数相加，取得最小路径，进行循环，直到求出数组中a11,即所求的结果。3问题 B: 毛毛虫问题时间限制:1 Sec内存限制:128 MB提交:32解决:16提交状态讨论版题目描述Mary在她家门口水平种了一排苹果树，共有N棵。突然Mary发现在左起第P棵树上(从1开始计数)有一条毛毛虫。为了看到毛毛虫变蝴蝶的过程，Lele在苹果树旁观察了很久。虽然没有看到蝴蝶，但Lele发现了一个规律：每过1分钟，毛毛虫会随机从一棵树爬到相邻的一
8、棵树上。比如刚开始毛毛虫在第2棵树上，过1分钟后，毛毛虫可能会在第1棵树上或者第3棵树上。如果刚开始时毛毛虫在第1棵树上，过1分钟以后，毛毛虫一定会在第2棵树上。现在告诉你苹果树的数目N，以及毛毛刚开始所在的位置P，请问，在M分钟后，毛毛虫到达第T棵树，一共有多少种行走方案数。输入输入四个整数N P M T。输出输出一个整数，就是行走的方案数。样例输入7 4 4 4样例输出6#includevoid main() int i,j; int p,m,n,t; int a100100=0;/定义一个二维数组； scanf(%d%d%d%d,&n,&p,&m,&t); a0p=1;毛毛虫刚开始在数组
9、中的位置； for(i=1;i=m;i+) for(j=1;j=n;j+) aij=ai-1j-1+ai-1j+1;/每一步的方案数； printf(%dn,amt);M分钟后到T棵树行走的方案数；心得：这一题运用了动态规划的思想，毛毛虫的每一步都会影响下一步的结果，所以首先按照普通情况找出规律及其其公式，进而算出方案数。首先定义一个二维数组，初始化毛毛虫的起始位置，然后通过两个循环，求出毛毛虫走每一步的方案数，存在二维数组中，然后求出第M分钟到T棵树行走的方案数。4问题 A: Hamming Problem时间限制:1 Sec内存限制:128 MB提交:61解决:23提交状态讨论版题目描述F
10、or each three prime numbers p1, p2 and p3, lets define Hamming sequence Hi(p1, p2, p3), i=1, . as containing in increasing order all the natural numbers whose only prime divisors are p1, 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.输入I
11、n the single line of input file there are space-separated integers p1 p2 p3 i.输出The output file must contain the single integer - Hi(p1, p2, p3). All numbers in input and output are less than 1018.样例输入2 3 5 5样例输出6#include stdio.hint minx(int p1,int p2,int p3)/ 定义有参函数minx； int min=p1; if(p2min) min=p
12、2; if(p3min) min=p3; return min;/求p1,p2,p3的最小值；int main() int p1,p2,p3,t,i; int a,b,c; char num10000; scanf(%d%d%d%d,&p1,&p2,&p3,&t); a=b=c=0; num0=1; for(i=1;i=t;i+) numi=minx(p1*numa,p2*numb,p3*numc);/调用minx函数； if(numi=p1*numa) a+; if(numi=p2*numb) b+; if(numi=p3*numc) c+; 求所有的能被p1,p2,p3整除的数； prin
13、tf(%dn,numt); return 0; 心得：运用动态规划的思想，定义一个一维数组，把所有符合条件的数按顺序存进一维数组中，这个编程运用了函数调用的方法求三个数的最小值，然后把这个最小值存进一维数组中，每次存进一个数，下次都会用存进去的这个数求解下一个数，进行循环。5问题 B:字符串正反连接时间限制:1 Sec内存限制:128 MB提交:68解决:42提交状态讨论版题目描述所给字符串正序和反序连接，形成新串并输出输入任意字符串（长度=50）输出字符串正序和反序连接所成的新字符串样例输入123abc样例输出123abccba321#include#includevoid main()ch
14、ar a50;/定义一个字符串；int i,f;while(scanf(%s,&a)!=EOF)/实现多行实例输入； f=strlen(a);/把字符串的长度值赋给f; for(i=0;i=0;i-) printf(%c,ai);/把字符串反序输出； printf(n);心得：定义一个字符串，运用strlen()函数获取字符串的长度值f，首先用for循环，把这个字符串正序输出，然后再用for循环对这个字符串进行反序输出，这里主要考察了输入输出。6问题 C: 去掉空格时间限制:1 Sec内存限制:128 MB提交:27解决:4提交状态讨论版题目描述读入一些字符串，将其中的空格去掉。输入输入为多行
15、，每行为一个字符串，字符串只由字母、数字和空格组成，长度不超过80。输入以“End of file”结束。输出对于每行输入，输出转换后的字符串。样例输入Hello World1 2 3Nice to meet youabc样例输出HelloWorld123Nicetomeetyouabc提示用scanf是不能读入一行有空格的字符串的，用gets吧。 用“gets(str) != NULL”可以判断输入是否结束，如果此条件为假（即gets(str) = NULL），则表示输入结束（对于本题）。#include#includevoid main()int i,f;char a90;/定义一个字符串
16、；while(gets(a)!=NULL)f=strlen(a);/把字符串的长度值赋给f; for(i=0;if;i+) if(ai= )printf(%c,ai+1);/去掉空格；i=i+1;elseprintf(%c,ai);/没有空格，直接输出； printf(n);心得：这里也是主要考察输入输出问题，首先也是定义了一个字符串，用strlen()函数获得字符串的长度f，进行f次循环，判断这个字符串是否有空格？如果有把数组中的每个数往后进一位，即去点空格，如果没有直接输出。7问题 D: 成绩转换时间限制:1 Sec内存限制:128 MB提交:78解决:30提交状态讨论版题目描述输入一个百
17、分制的成绩t，将其转换成对应的等级，具体转换规则如下：90100为A;8089为B;7079为C;6069为D;059为E;输入输入数据有多组，每组占一行，由一个整数组成。输出对于每组输入数据，输出一行。如果输入数据不在0100范围内，请输出一行：“Score is error!”。样例输入5667100123样例输出EDAScore is error!提示#includeint main()int x;while(scanf(%d,&x)!=EOF)/实现多行实例输入；if(x60)printf(En);else if(x70)printf(Dn);else if(x80)printf(Cn
18、);else if(x90)printf(Bn);else if(x=2),最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。输入输入共两行，第一行输入金块的数量N100000;第二行N金块的重量，用空格间隔。输出两个数用空格分开，最重金块 最轻金块样例输入53 7 9 6 4样例输出9 3#includeint main()int n,a100000;int max,min,i;while(scanf(%d,&n)!=EOF)/实现多行实例输入；for(i=0;in;i+)scanf(%d,&ai);max=mi
19、n=a0;/把数组a0的值赋给max和min；for(i=1;imax)max=ai;/求最最重的金块；for(i=1;in;i+)if(aimin)min=ai;/求最轻的金块；printf(%d %dn,max,min);return 0;心得：这题主要运用分治算法的思想，把一个大问题分成一个个小的子问题去求解，这个题目是典型的二分法问题，把这个题分成两个小问题，即求最重的和求最轻的金块，首先定义了一个一维数组，把所有金块的质量存入其中，把数组的初始值赋给最重的和最轻的金块，然后运用循环对数组中每个金块的质量与金块的初始值进行比较，求的最重和最轻的金块，然后输出。9问题 B: 工资问题时间
20、限制:1 Sec内存限制:128 MB提交:121解决:74提交状态讨论版题目描述某单位给每个职工发工资（精确到元），为了保证不要临时兑换零钱，且取款的张数最少，取工资前要统计出所有职工的工资所需各种 币值（100，50，20，10，5，2，1元共7种）的张数，请编程完成。输入输入一个工资数10000元输出输出各个币种的张数，没有的用0代替，中间用空格分开样例输入173样例输出1 1 1 0 0 1 1#includeint main()int j,z,a;int b7=100,50,20,10,5,2,1;/把所有币值按从从大到小的顺序存到一位数组中；int s7=0;/定义一个一位数组，元
21、素值全为0；scanf(%d,&z); for(j=0;j7;j+) a=z/bj; sj=a;z=z-a*bj; /求需要各个币值的个数； printf(%d,s0); for(j=1;j7;j+) printf( %d,sj);/输出需要各个币值的个数；return 0;心得：这个题主要运用贪婪算法的方法，利用可行的策略，求出可行解的一个解元素由所有解元素合成问题的一个可行解。要想取得的张数最少，可以先考虑币值最大的进行分发，然后再取更小钞票的币值。依次取之。首先定义一个一维数组，把币值从大到小存进去，运用一循环，把每次算的钱数的结果，依次对数组的币值进行取整。然后依次存入数组输出。10问
22、题 C: 水仙花数问题1时间限制:1 Sec内存限制:128 MB提交:138解决:75提交状态讨论版题目描述判断一个数是否为水仙花数，所谓水仙花数是指这样的一人数：其各位数字的立方和等于该数本身。例如：371是一个水仙花数，371=33+73+13.输入一个三位数输出1或者0(1代表此数为水仙花数,0代表此数不是水仙花数)样例输入371样例输出1#includevoid main() int n,x,y,z; scanf(%d,&n); x=n/100;/求三位数的百位数字； z=n%10;/求三位数的个位数字； y=(n-(x*100+z)/10;/求三位数的十位数字； if(n=x*x*
23、x+y*y*y+z*z*z) printf(%d,1); else printf(%d,0);/判断这个三位数是否为水仙花数，是输出1，否输出2；心得：首先，输入一个三位数，运用对这个数取整，取余，运用数学公式，分别算出它的百位，十位，和个位的数字，然后判断这三个数字的平方和是否等于这个三位数，如果是，输出1，如果不是输出0.11问题 E: 大小写转换时间限制:1000 Sec内存限制:65536 MB提交:182解决:116提交状态讨论版题目描述读入一些字符串，将其中的小写字母转成大写字母（其他字符不变）。输入输入为多行，每行为一个字符串，字符串只由字母和数字组成，长度不超过80。输入以“E
24、nd of file”结束。输出对于每行输入，输出转换后的字符串。样例输入HelloICPC200412345abcde样例输出HELLOICPC200412345ABCDE#include#includevoid main()int j;char string80;/定义一个字符串； while(scanf(%s,&string)!=EOF)/实现多行实例输入；for(j=0;j=a)&(stringj=z) stringj=stringj-32;/实现字母大小写转换； printf(%sn,string);心得：这个题目主要考察输入输出，还有大小写转换问题，首先还是定义一个字符串，用whi
25、le(scanf(%s,&string)!=EOF)语句实现多行实例输入，对这个字符串进行循环，如果这个字符串有大写的话，转化成小写的，如果有小写的话，那么转化成大写的。12问题 B: 取数游戏时间限制:1 Sec内存限制:128 MB提交:46解决:39提交状态讨论版题目描述有2个人轮流取2n个数中的n个数，所取数之和大者为胜，请编写算法，让先取数者胜，模拟取数过程。输入输入两行，第一行一个整数N100000；第二行N个数，用空格分开。输出输出取胜人取数和。失败人取数的和，空格分开。样例输入61 2 3 4 5 6样例输出12 9#includeint main()int n,i,sum1,
26、sum2,a100000;while(scanf(%d,&n)!=EOF)/实现多行实例输入；sum1=sum2=0;for(i=0;in;i+)scanf(%d,&ai);for(i=0;in;i=i+2)sum1=sum1+ai;for(i=1;isum2)printf(%d %dn,sum1,sum2);elseprintf(%d %dn,sum2,sum1);/顺序输出取胜人取数和。失败人取数和；return 0;心得;这题主要运用贪心算法的思想，要想先取数人获胜，就得让这个人每一步都尽可能取得最大的数，这样他取数的和才会总体大于后取数的那个人的取数和。首先定义一个一维数组，把要取得数
27、从小到大的顺序放在里面，然后一个人从第一个按照隔一个数取，求和sum1;另一个人从第二个按照隔一个人取,求和sum2，比较sum1和sum2的最大值，输出。13问题 C: 整除问题时间限制:1 Sec内存限制:128 MB提交:70解决:44提交状态讨论版题目描述编写算法对输入的一个整数，判断它能否被3，5，7整除，并输出以下信息之一：能同时被3，5，7整除；能被其中两个数（要指出哪两个）整除；能被其中一个数（要指出那一个）整除；不能被3，5，7任一个整除；输入输入一个整数100000;输出如果都能整除输出“all如果都不能整除输出nonel如果能被3和5整除则输出“3 5”。中间有一个空格，
28、注意按由小到大输出。样例输入35样例输出5 7#includevoid main()long n; int k;scanf(%d,&n);k=(n%3=0)+(n%5=0)*2+(n%7=0)*4);/判断整数是否能被2,3,5整除；switch(k)case 7:printf(all);break;case 6:printf(5 7);break;case 5:printf(3 7);break;case 4:printf(4);break;case 3:printf(3 5);break;case 2:printf(5);break;case 1:printf(3);break;case
29、0:printf(none);break;/用switch语句输出结果；心得：这题主要考察输入输出问题，首先输入一个整数，运用语句k=(n%3=0)+(n%5=0)*2+(n%7=0)*4)，判断这个数能否被2,3,5整除，用switch语句输出所有可能发生的结果，然后输出题目中所要求输出的结果，其中用switch语句起到了优化算法的作用。14问题A警察抓小偷时间限制:1 Sec内存限制:128 MB提交:115解决:88提交状态讨论版题目描述警察局抓了a,b,c,d,4名小偷嫌疑犯，其中只有一个人是小偷，审问中，a说：我不是小偷，b说：c是小偷，c说：小偷肯定是d，d说：c在冤枉人。 现在已
30、经知道4个人中3人说的是真话，一人说的是假话，问到底谁是小偷。输入输出小偷是c样例输入样例输出小偷是c#includevoid main()int x;for(x=1;x=4;x+)/执行4次循环；if(x!=1)+(x=3)+(x=4)+(x!=4)=3)/判断是否有三个人说真话的情况；printf(%c,64+x);心得：这个题目主要考察把文字信息转化为数字信息，即信息数字化，把A，B，C，D看成1，2，3，4；x定义为小偷，然后把A，B，C，D四人所说的话变成数字语言，判断当他们四个人有三个人说真话的情况，然后以把数字变成字母输出。15问题 B: n!时间限制:1 Sec内存限制:128
31、 MB提交:262解决:162提交状态讨论版题目描述输入一个整数N，输出它的阶乘。输入输入一个整数20;输出输出它的阶乘样例输入5样例输出120提示#includeint main()int add(int m);/对add函数进行声明；int n,sum;scanf(%d,&n);sum=add(n);printf(%dn,sum);return 0;int add(int n)/定义add函数int f; if (n=0|n=1)f=1;/判断当n等于0和1这两种情况；else f=n*add(n-1);/调用add函数求值；return f;心得：这里主要运用函数的递归调用，首先用if对
32、输入的数进行判断，看是否为1和0，如果是，那么输出其阶乘等于1，如果不是那么调用函数f=n*add(n-1)进行求值，add函数总共被调用了n次，求得最后的结果，输出。16汉诺塔问题时间限制:1 Sec内存限制:128 MB提交:224解决:138提交状态讨论版题目描述把N个盘子从A柱子借助B柱子移到C柱子，要求每次只能移动一个盘子，并且小盘子不能放到大盘子上。问如何移动。输入输入盘子的个数N（=10)输出输出移动的次数。样例输入3样例输出7提示#includeint main() int i,j,n,sum; scanf(%d,&n); j=1; if(n!=1)/去除盘子的个数为1的情况；
33、for(i=1;i=n;i+) j=j*2; sum=j-1;/求盘子移动的次数； else sum=1; printf(%d,sum); return 0; 心得：这题主要考察循环与递归问题，先假设盘子的个数，取几个特殊值，找出移动盘子次数的规律。这个编程首先判断盘子个数，如果是1，则输出1次，如果不是1，执行n次循环，求得j,然后求出移动盘子的次数j-1，输出。17问题 D: 猴子吃桃子问题（递归）时间限制:1 Sec内存限制:128 MB提交:98解决:87提交状态讨论版题目描述一只猴子摘了若干桃子，每天吃现有桃子的一半多一个，到第10天时就只有一个桃子了，求原来有多少个桃。输入输出输出
34、原来的桃子数样例输入样例输出提示#includeint main()int i,x=1;for(i=9;i0;i-)/执行9次循环；x=(x+1)*2;/求每天桃子的个数；printf(%dn,x);return 1;心得：这个题目运用数学中倒推的方法求得，先求出第10天桃子的个数，然后再求出前一天桃子的个数，直到求出第1天桃子的个数，找出其规律。设桃子的个数为x，则每天剩余桃子的个数满足公式x=(x+1)*2，再用一个for循环求出原来的桃子数。18问题 A: A+B for Input-Output Practice (I)时间限制:1 Sec内存限制:128 MB提交:402解决:183
35、提交状态讨论版题目描述Your task is to Calculate a + b.Too easy?! Of course! I specially designed the problem for acm beginners.You must have found that some problems have the same titles with this one, yes, all these problems were designed for the same aim.输入The input will consist of a series of pairs of integ
36、ers a and b, separated by a space, one pair of integers per line.输出For each pair of input integers a and b you should output the sum of a and b in one line, and with one line of output for each line in input.样例输入1 510 20样例输出630提示#includevoid main()int a,b,s;while(scanf(%d%d,&a,&b)!=EOF)/实现多行实例输入；s=a+b;/求a和b的和；printf(%dn,s); 心得：这个题主要考察了输入和输出问题，目的是计算整数a和b的和，首先用while(scanf(%d%d,&a,&b)!=EOF)语句实现多行实例输入，然后求出a和b的和，输出。19A+B for Input-Output Practice (II)时间限制:1 Sec内存