精选文档宁波2014小学程序解题分析

宁波市第29届中小学生计算机程序设计竞赛复赛试题（小学组）比赛时间：2014年3月29日下午1:30—4:00题目一览试题名称小李数星星小李打台球小李发奖金小李打怪兽英文代号starballmoneymonster程序名star.cpp/pas/cball.cpp/pas/cmoney.cpp/pas/cmonster.cpp/pas/c输入文件名star.inball.inmoney.inmonster.in输出文件名star.outball.outmoney.outmonster.out内存限制128MB128MB128MB128MB时限1S1S1S1S注意：一、关于竞赛中编程语言使用的规定参照中国计算机学会公布的《关于NOI系列赛编程语言使用限制的规定》。二、评测环境为windows。小李数星星【题目描述】小李在农村长大，那时候大家喜欢晚饭过后在院子里纳凉，听不懂大人在说什么的小李喜欢抬头看天空，尤其是夏天的夜晚，天上的星星又多又亮。长大后小李进城打工，每当想家的时他还是喜欢抬头看看天，寻找另一边故乡的记忆。可是大城市里空气质量太差了，雾靈天气横行，天上能看到的星星也越来越少了。小李每次用一个正方形去覆盖自己所能看到的星星，随着日子的推移，这个正方形越来越小了，悲伤的小李希望你能告诉他这个正方形的面积。为了让问题变得筒单，小李毎次只会使用水平放置的正方形来覆盖（不会旋转），具体参照样例解释。【输入】第一行一个整数n，表示星星的数量。接下来共n行，每行2个正整数(a,b),表示该星星到X轴距离为b，到Y轴距离为a，这些星星只会位于X轴的上方，Y轴的右方。输入数据保证存在一个合法的正方形(面积非零)去覆盖这些星星【输出】一个整数，表示能覆盖所有星星的最小正方形的面积。【样例输入】3112122【样例输出】1【样例说明】【数据规模】80%的数据，3<=n<=20,1<=x<=100,1<=y<=100100%的数据，3<=n<=1000,1<=x<=100000,1<=y<=100000解题思路：首先找到X轴上最大的一个坐标跟最小的一个坐标，我们可以用max1和min1表示，然后找到Y轴上最大的一个坐标跟最小的一个坐标，我们可以用max2和min2表示，用max1-min1表示X轴上的边长aa，用max2-min2表示Y轴上的边长bb,比较aa跟bb的长度，因为是正方形，所以用较长的计算面积，这样可以覆盖整个星星的区域。注意：由于数据比较大，所以我们采用int64的数据类型，不然就会出现超范围的错误提示。源程序如下：varn,a,b,aa,bb,max1,min1,max2,min2:int64;i:longint;beginassign(input,'star.in');reset(input);assign(output,'star.out');rewrite(output);readln(n);max1:=0;min1:=maxlongint;max2:=0;min2:=maxlongint;fori:=1tondobeginreadln(a,b);ifa>max1thenmax1:=a;ifa<min1thenmin1:=a;ifb>max2thenmax2:=b;ifb<min2thenmin2:=b;end;aa:=max1-min1;bb:=max2-min2;ifaa>bbthenwrite(aa*aa)elsewrite(bb*bb);close(input);close(output);end.小李打台球【题目描述】在异乡打拼的小李同志迷上了一款叫诺斯克的台球游戏，而且随着练习的深入，他总是能在某些神奇的时刻开启外挂模式，此时小李将指哪打哪，直至无球可打。现在小李想让你帮他计算下当他开启外挂模式的时候最多可以取得多少分数。注意：台面上的球数经常会异于传统斯诺克。斯诺克比赛的基本规则如下：一、彩球共分8种颜色，红（1分）、黄（2分）、绿（3分）、掠（4分）、蓝（5分）、粉（6分）、黑（7分）、白（主球，控制白球来打其余球二、当台面上有红球的时候你必须先击打一个红球，然后能且只能击打一个彩球（不包括红球），此时落袋的彩球将会被放回桌面，一直重复该过程。三、当打完规则二的彩球（不包括红球）发现己经没有红球时，按照彩球的分值从低到高将其依次击入袋中。【输入】输入仅有一行，共7个用空格隔开的整数，分别为当前台面上红、黄、绿、掠、蓝、粉、黑球的数目。【输出】输出仅有一行，共1个整数，表示小李可以得到的最高分。【样例输入】2 010302【样例输出】48【样例说明】台面上共有红球2个、绿球1个、蓝球3个、黑球2个，获得最高分的打法是红-黑-红-黑-绿-蓝-蓝-蓝-黑-黑，共可以获得48分。【数据规模】保证最后得分不会超过231-1。解题思路：这题主要是模拟取球得分的过程，总共七种球，如果有红色球，那么红色的个数乘以有其他颜色球的最高分得出结果，再把除红色球外的其他颜色球按球的数量乘以分值累加就可以完成。我们在读入数据完成后可以把七种颜色球中没有的球排除掉，统计出球桌上有几种颜色的存在，如果桌面上只有红色球，那分数只能得1分。源程序如下：vars,t,i:longint;a:array[1..7]oflongint;beginassign(input,'ball.in');reset(input);assign(output,'ball.out');rewrite(output);fori:=1to7doread(a[i]);t:=7;whilea[t]=0dodec(t);ift=1thens:=1elses:=s+t*a[1]+a[1];fori:=2to7dos:=s+i*a[i];write(s);close(input);close(output);end.

小李发奖金【题目描述】当然打台球只是小李的休闲娱乐活动，对待他的本职工作，他还是非常兢兢业业的。但是小李的老板是个周机皮，每次都想克扣小李的工资和奖金，甚至制定出非常奇葩的规则。又到了每年发年终奖的时候了，今年老板的规则是这样的：给你n个数,每次你可以对任意一个数加1,直到所有的数都不相等为止，每加一次都要花费一定数额的费用。为了小李的幸福生活，聪明的你可否帮助小李，让他尽量少扣钱。【输入】第一行n,表示共有n个数。第二行共n个用空格隔开的非负整数ai。【输出】仅一个整数，表示加到让每个数都不相等的最少次数。【样例输入】41132【样例输出】3【样例说明】让1+1+1+1=4,给定的数字变成4,1,3,2。【数据规模】30%的数据，1<=n<=1060%的数据,1<=n<=100080%的数据,1<=n<=30000,ai<=1000,100%的数据,1<=n<=30000,ai<=1000000。解题思路：首先我们要了解n个数要变成不一样并且要自动加1的话进行变化的话，先要对n个数进行从小到大的排序，因为数据比较大，我们可以选择用快排或者桶排的方法进行排序（注意，不能用选择跟冒泡排序，因为这两种排序数据大会产生超时），我这里用的是桶排序，在排序的同时找到数据的最大值跟最小值，作用是不用从1开始，也不用到最后结束，只要在最小值跟最大值之间（只有桶排序的情况可以这样）。接下来就是自动加1的过程了，如果数据只有一个或没有，那就不用加1了，如果大于1的，我们就要进行自动加1的过程了，加的过程统计加的次数。源程序如下：vari,a,p,n,q,ans,lmt:longint;f:array[1..1100001]oflongint;beginassign(input,'money.in');reset(input);assign(output,'money.out');rewrite(output);read(n);fori:=1tondobeginread(a);f[a]:=f[a]+1;ifa<pthenp:=a;ifa>lmtthenlmt:=a;end;fori:=ptolmtdobeginifq<=ithenq:=i+1;if(f[i]=1)or(f[i]=0)thencontinue;whilef[i]>1dobeginwhilef[q]<>0doq:=q+1;f[q]:=1;ans:=ans+q-i;f[i]:=f[i]-1;end;end;write(ans);close(input);close(output);end.小李打怪兽【题目描述】小李对故乡的思念全部化作了对雾靈天气的怨念，这引起了掌控雾靈的邪神的极大不满，邪神派去了一只小怪兽去对付小李，由于这只怪兽拥有极高的IQ,它觉得直接消灭小李太没有难度了，它决定要和小李在智力水平上一较高下。我们可否帮助小李来战胜强大的怪兽呢？问题是这样的：给定一堆正整数，要求你分成两堆，两堆数的和分别为S1和S2,谁分的方案使得S1*S1-S2*S2的结果小（规定S1>=S2),谁就将获得胜利。注：S2可以等于0。【输入】第一行n，表示共有n个数第二行共n个用空格隔开的正整数ai，表示给定的一堆正整数。【输出】输出就一个整数，表示S1*S1-S2*S2的最小值。【样例输入】41234【样例输出】0【样例说明】1和4一堆，2和3—堆，5*5-5*5=0【数据规模】60%的数据，1<=n<=2080%的数据，1<=n<=50，ai<=20100%的数据，1<=n<=100，ai<=100解题分析：这首题就是很典型的0/1背包问题，我们可以用DP(动态规划)的方法来做，本问题的数学模型如下：设f(x)表示取的数不超过x的最大数，则f(x)=max{f(x-w[i])+v[i]}

最后要两堆数相乘后再相减，sqr(f[x])-sqr(s-f[x])源程序如下：vari,x,n,m,s:longint;f:array[0..10000]oflongint;w,v:array[1..10000]oflongint;beginassign(input,'monster.in');reset(input);assign(output,'monster.out');rewrite(output);fillchar(f,sizeof(f),0);readln(n);//读入数量fori:=1tondobeginread(w[i]);v[i]:=w[i];s:=s+w[i];end;ifodd(s)thenm:=sdiv2+1//总数是奇数，一半+1elsem:=sdiv2;//偶数