2015海曙区中小学生计算机奥赛解题报告

1、2015海曙区中小学生计算机奥赛解题报告1. 抗战阅兵(parade.pas/c/cpp)【问题描述】2015年9月3日，是首个决定放假的抗战胜利纪念日。为隆重纪念中国人民抗日战争暨世界反法西斯战争胜利70周年，在9月3日当天，在天安门广场举行了规模宏大的阅兵仪式。当天全国放假一天，以便全国人民能够观看阅兵仪式的盛况，为我们伟大的祖国喝彩。这一天，小NN终于可以摆脱繁重的课业压力，在家里认真的观看阅兵仪式。他发现，阅兵仪式是由很多个方阵组成（方阵是矩形），长宽一般固定是25*14，外加两个领队的将军。现在，小NN想要知道，如果每个方阵的长宽以及将军的人数不固定的时候，所有方阵的总人数是多少，平

2、均每个方阵有多少人。【输入】第一行一个整数N，表示方阵的个数。接下来N行，每行3个正整数a，b，c，中间用一个空格隔开，a和b分别表示方阵的长和宽，c表示领队的将军数量。【输出】输出有两行，第一行是一个整数，表示所有方阵的总人数，第二行是一个实型（四舍五入到2位小数），表示平均每个方阵的人数。【输入输出样例1】parade.inparade.out23 4 32 5 12613.00【样例1解释】 第一个方阵有3*4+3=15人，第二个方阵有2*5+1=11人。【输入输出样例2】parade.inparade.out210 10 27 8 115979.50【样例2解释】第一个方阵有10*10

3、+2=102人，第二个方阵有7*8+1=57人。【数据范围】 50%的数据，1=a,b=10。100%的数据，N=100，1=a,b=50,1=c=3。Readln(n);For i:=1 to n doBegin Readln(a,b,c); S:=s+a*b+c;End;Writeln(s);Writeln(s/n:0:2);End.2. 摘苹果(apple.pas/c/cpp)【问题描述】秋天到了，小NN所在的学校组织小朋友们去秋游。这次他们去的地方是一个果园，果园里有很多很多的果树。由于小NN和他的小伙伴们总共N个人最喜欢吃苹果，所以他们都跑到了一棵苹果树下，这棵苹果树总共结出了M个苹

4、果，管理果园的叔叔允许小朋友们自己摘苹果吃。但是现在问题来了，每个苹果都有一个固定的高度。每个小朋友每次跳跃高度也都是一个固定值（跳一次花费的体力等于这个高度值），只要他们的跳跃高度大于等于某个苹果的高度的时候，就可以把那个苹果摘下来，跳一次最多只能摘一个苹果。由于小朋友们还小，体力上可能跟不上，所以规定每个小朋友最多只能跳一次。现在小NN和他的小伙伴想要知道最少需要花费多少的体力才能将这些苹果全部摘完，现在请你来帮助他们吧。【输入】第一行两个正整数N和M，分别表示小朋友的数量和苹果的数量。第二行N个正整数，两个整数间用一个空格分开，第i个数Hi表示第i个小朋友的跳跃高度。第三行M个正整数，两

5、个整数间用一个空格分开，第i个数Pi表示第i个苹果的高度。【输出】如果能够摘完所有的苹果，就输出最小的体力花费，如果不能摘完，就输出“Bad luck”（不包括引号）。【输入输出样例1】apple.inapple.out3 25 3 64 611【样例解释】首先让跳跃高度为5的小朋友去摘高度为4的苹果，花费的体力值是5,然后让跳跃高度为6的小朋友去摘高度为6个苹果，花费的体力值是6，所以总共花费体力值11。【输入输出样例2】apple.inapple.out3 34 2 33 3 4Bad luck【样例解释】由于是3个小朋友摘3个苹果，第2个小朋友的跳跃高度不足以摘到任何一个苹果，所以不能摘

6、下所有的苹果。【数据范围】60%的数据，1=N,M=1000，1=Hi,Pi=1000。100%的数据，1=N,M=, 1=Hi,Pi=。贪心 两组数据按照从小到大排序，用最小的人，配最小的树，当然人的高度要大于等于树的高度。最后看2个下标，i爆掉还是j爆掉。满分要快排。核心代码 i:=1; j:=1; while (i=n)and(j=bj then begin ans:=ans+a; inc(i); inc(j); end else inc(i); end; if jm then writeln(ans) else writeln(you lie);end.3. 奇怪排列(sort.pas

7、/c/cpp)【问题描述】小NN是一个活泼好动的小朋友，他特别喜欢上体育课，他喜欢的运动项目有很多，比如跑步、打篮球、踢毽子等等，所以每次上体育课的时候他都特别的开心。班里有N个学生，学生的编号从1-N编号，男生的学号恰好都是偶数，女生的学号恰好都是奇数。体育课一开始，体育老师就让小朋友们把队伍排成一条直线，并且为了防止小朋友们窃窃私语，老师要求男生和女生必须交错排列，既不能同时让两个女生站在一起，也不能同时让两个男生站在一起。由于小NN是一个非常擅于思考的学生，他很想知道这样的排法有多少种，现在请你来帮助他吧。【输入】输入只有一行一个正整数N，表示学生的数量。【输出】输出排列的总数。【输入输

8、出样例1】sort.insort.out22【样例解释】由于只有两个学生，学号1和2，分别是一个女生和一个男生，所以只有两种排法，要么是12，要么是21。【输入输出样例2】sort.insort.out32【样例解释】由于是两个女生一个男生（女生是1和3，男生是2），只能是123或者321。【数据范围】70%的数据，N=10。100%的数据，N=40。70分算法暴力搜索，递归回溯算法，枚举全排列procedure try(c:integer);var i:integer;begin if c=n+1 then begin /相邻位不同奇偶性 inc(ans); exit; end; /回溯 e

9、nd;end;begin readln(n); try(1); writeln(ans);end.另一种70分递推算法男生的全排列*女生的全排列,判断奇偶性，偶数还要乘二100分算法:递推算法的基础上，写个高乘单的高精度乘法。 for i:=1 to b do begin for j:=1 to s0 do begin sj:=sj*i+jw; jw:=sj div 10; sj:=sj mod 10; end; while jw0 do begin inc(s0); ss0:=jw mod 10; jw:=jw div 10; end;4. 画圈圈（初中生做，小学生不做）【输入】第一行一个正

10、整数N，表示圆的数量。第二行有N个正整数，第i个数Xi，表示第i个圆的水平位置。第三行有N个正整数，第i个数Ri，表示第i个圆的半径。【输出】输出剩余圆的最大总面积（结果四舍五入到整数）。【输出输出样例1】circle.incircle.out25 33 328【样例解释】由于两个圆相交了，只能取一个。【输出输出样例2】circle.incircle.out23 1310 1314【样例解释】 由于小圆被大圆遮住了，所以留下大圆是最优选择。【数据范围】60%的数据，N=20。100%的数据，N=1000，1=Xi,Ridi+1,1-di,1 then exit; t:=0; for i:=1 to xb do t:=t+pi*di,2*di,2; if tans then ans:=t; exit; end;满分算法思想：这道题目其实就是codevs的线段覆盖5，只是把数轴上的线段隐射到圆上。区间型的dp无疑。首先需要把所有线段根据右端点升序排序，这样的话，找与第i条线段不重合的线段j，就只需要往前找一个线段j，使得j的右端点小于等于i的左端点坐标，然后开一个数组f进行动规