noip2010普及组复赛试题答案

NOIP 2010试题与解题报告

NOIP 2010初赛试题

（ 普及组 C语言 两小时完成 ）

●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●●

一、单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确选项。） 1．2E+03表示（ ）。

A. 2.03 B. 5 C. 8 D. 2000

2．一个字节（byte）由（ ）个二进制位组成。

A. 8 B. 16 C. 32 D. 以上都有可能

3．以下逻辑表达式的值恒为真的是（ ）。

A. P∨(¬P∧Q)∨(¬P∧¬Q) B. Q∨(¬P∧Q)∨(P∧¬Q) C. P∨Q∨(P∧¬Q)∨(¬P∧Q) D. P∨¬Q∨(P∧¬Q)∨(¬P∧¬Q)

4．Linux下可执行文件的默认扩展名为（ ）。

A. exe B. com C. d

第十六届全国青少年信息学奥林匹克联赛初赛试题

（普及组C++语言两小时完成）

● ●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●

一、单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确选项。） 1．2E+03表示（）。 A．2.03B．5C．8D．2000

2．一个字节（byte）由（）个二进制位组成。 A．8B．16C．32D．以上皆有可能 3．以下逻辑表达式的值恒为真的是（）。 A．PV(?PΛQ)V(?PΛQ)B．QV(?PΛQ)V(PΛ?Q) C．PVQV(PΛ?Q)V(?PΛQ)D．PV?QV(PΛ?Q)V(?PΛ?Q) 4．Linux下可执行文件的扩展名为（）。 A．exeB．comC．dllD．以上都不是

5．如果树根算第1层，那么一棵n层的二叉树最多有（）个结点。 A．2n-1B．2nC．2n+1D．2n+1

6．提出“存储程序”的计算机原理的是（）。

A．克劳德·香农B．戈登·摩尔C．查尔斯·巴比奇D．冯·诺依曼

7．设X、Y、Z分别代表三进制下的一位数字，若等式XY+ZX=XYX在三进制下成立，那么同样在三进制下，等式XY*ZX=()也成立。 A．YXZB．ZXYC．XYZD．XZY

8．Pa

陶陶很喜欢数学 ，尤其喜欢奇怪的数。一天，他突然发现，有的整数拥有的因子数是很有个性的，决定找到一个具有n个正因子数的最小的正整数。

例如：n=4，则m=6，因为6有4个不同正整数因子1，2，3，6；而且是最小的有4个因子的整数。 【输入文件】

仅一个数 n（1≤n≤60） 【输出文件】 仅一个数 m 【样例输入】 4

【样例输出】 6

var flag:boolean;x,t,n,i:longint; begin readln(n); x:=0;flag:=false; while not flag do begin x:=x+1;t:=0; for i:=1 to x do

if x mod i=0 then t:=t+1; if t=n then flag:=true; end;

writeln(x); end.

输入 12 输出 60 输入30 输出 720 输入 60 输出 5040 输入 45 输出 3600

2. 由文件给出n个1~30000的无序数正整数，其中1≤N≤10000,同一个正整数可能会出现多次，出现次数最多的整数称为众数，找出其中的众数及它出现的次数。输入格式：输入文件masses.in 第

1. 军方截获的信息由n（n<=30000）个数字组成，因为是敌国的高端秘密，所以一时不能破获。最原始的想法就是对这n个数进行小到大排序，每个数都对应一个序号，然后对第i个是什么数感兴趣，现在要求编程完成。 【输入格式】

第一行n，接着是n个截获的数字，接着一行是数字k，接着是k行要输出数的序号。

【输出格式】

k行序号对应的数字。 【输入样例】Secret.in 5

121 1 126 123 7 3 2 4 3

【输出样例】Secret.out 7 123 121

2. 有一只坏的里程表：它总是跳过数字3和数字8。也就是说，当前显示已走过两公里时，如果车子再向前走一公里，那么将显示4公里，而不是三公里（数字3跳过了）。再比如，当前是15229公里，车子再向前走一公里，显示的是15240公里，而不是15230公里。数字8也同样跳过

现在，给你里程表上显示的数字，请你告诉我车子真正走了多少公里。 输入： 15 输出： 12

3. 硬币游戏：Farmer John的奶牛喜欢玩硬币游戏，因此FJ发明了一种称为“Xoinc”的两人硬币游戏。

初始时，一个有N(5 <= N <= 2,000)枚硬币的堆栈放在地上，从堆顶数起的第I枚硬币的币值为C_i (1 <= C_i <= 100,000)。 开始玩游戏时，第一个玩家可以从堆顶拿走一枚或两枚硬币。如果第一个玩家只拿走堆顶的一枚硬币，那么第二个玩家可以拿走随后的一枚或两枚硬币。如果第一个玩家拿走两枚硬币，则第二个玩家可以拿走1，2，3，或4枚硬币。在每一轮中，当前的玩家至少拿走一枚硬币，至多拿走对手上一次所拿硬币数量的两倍。当没有硬币可拿时，游戏结束。

两个玩家都希望拿到最多钱数的硬币。请问，当游戏结束时，第一个玩家最多能拿多少钱呢？ Input

第1行：1个整数N

第2..N+1行：第i+1行包含1个整数C_i Output

第1行：1个整数表示第1个玩家能拿走的最大钱数。

Sample In

1．数字反转(reverse.cpp/c/pas)【问题描述】给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。【输入】输入文件名为 reverse.in。 输入共 1 行，一个整数N。

【输出】输出文件名为 reverse.out。

输出共 1 行，一个整数，表示反转后的新数。 【输入输出样例 1】reverse.in reverse.out 123 321

【输入输出样例 2】Reverse.in reverse.out -380 -83

【数据范围】-1,000,000,000 ≤ N≤ 1,000,000,000。

var

s3,s1,s2:string; n,i:integer; begin

assign(input,'reverse.in');reset(input);

assign(output,'reverse.out');rewrite(output); read(s1);

n:=length(s1); if s1[1]='-' then begin s2:='-';

f

小华的寒假作业上，有这样一个趣味填空题：

给出用等号连接的两个整数，如“1234＝127”。当然，现在这个等号是不成立的。题目让你在左边的整数中间某个位置插入一个加号，看有没有可能让等号成立。以上面的式子为例，如果写成123+4=127，这就可以了。 请你编写一个程序来解决它。

Input 只有那个不相等的式子。已知，等号两边的整数都不会超过200000000000。

Output 如果存在这样的方案，请输出那个正确的式子。如果不存在解决方案，请输出“Impossible!”（引号中的部分）。 Sample Input 1234=127 Sample Output 123+4=127 program ex1075;

var i,len,p:integer; a1,a2,b:longint;

st,st1,st2,st3:string; begin

readln(st); p:=pos('=',st);

st1:=copy(st,1,p-1); delete(st,1,p); val(st,b,x);

len:=length(st1); for i:=1 to len-1 do beg

【基础】班委确定 【试题描述】

经过紧张而激烈的选拔考试，编程班终于浮出水面，一共有k位同学幸运的入选，这k位同学个个可都是精英，才华横溢，思维敏捷。让谁做班长？让谁做学习委员？让谁做团委书记呢……？这可让班主任老师伤透了脑筋。个个都优秀，个个都能干，实在是没有办法了。抓阄吧！这个抓阄可不是普通的抓阄，老师让这k位同学围成一圈从一号位置开始顺时针报数报到m这个人就出圈（啊？猴子选大王啊！把我们当猴子啦？Of course not），出圈后就反向逆时针从下一个开始报数，报到n再出圈，然后再反向顺时针报到m出圈,反向逆时针报到n出圈……圈里的人越来越少，当还剩下5个人的时候那么这5个人就是编程班的班委。Star很想当班委，为了能够当上班委，他想请你帮忙确定哪些位置是班委的位置。 【输入描述】一行：三个整数k,m和n

【输出描述】 一行：5个数，分别为5个班委位置的号码（号码从大到小排列）。两个号码之间用一个空格隔开，最后一个号码没有空格 【输入样例】 10 3 2 【输出样例】 10 9 8 6 4

【解题提示】 样例说明： 出圈顺序为：3 1 5 2 7 剩下4 6 8 9 10 数据规模：

10%的数据 k,n,m <= 15 40%的数据 k,n,m <= 200 60%的数据 k,n,m <= 500 90%的数据 k,n,m <= 1000

100%的数据 k<=1000 n,m <= 100000 【试题来源】 常州长训班测试 var k,i,h,s,w:integer;t,z,m,n:int64; f:boolean; a:array[1..1000] of 0..1; b:array[1..5] of integer;

beg

图书馆馆长正犯愁呢，原来，有一堆的书要他整理，每本书都有一个书号（<=32767),现在他有一本书，这本书的书号为K（<=32767),现在他要找出一本书号比这本书大的书和书号比这本小的书(但都要最接近图书馆馆长已有的书号），将找到的这两本书的书号加起来，并算出加起来以后的数是否为素数

Input

第一行二个数为N,K，表示几本书以及手中书的书号（<=32767) 第二行开始有N个整数，表示这些书的书号 Output

第一行一个数，表示两本书书号加起来的和 第二行一个字符，表示和是否为素数，若是则输出\否则输出\（引号不打出） Sample Input 6 5

6 4 5 3 1 20 Sample Output 10 F

program ex1148; var n,k,i,x,s:integer;

a:array[0..32767] of integer; f:boolean; begin

readln(n,k);

fillchar(a,sizeof(a),0); for i:=1 to n do begin read(x); a[x]:=1; end; s:=0;

for i:=k+1 to 32767 do

if a[i]<>0 then begin s:=s+i;break; end; for i:=k-1 downto 1 do

if a[i]<>0 then begin s:=s+i;break; end;

1农场主的篱笆：农场主有100块1米的正方形篱笆，他想用这些篱

笆搭一个一面靠墙的长方形圈，想使圈的面积最大应如何搭建？请你邦他编程解决。

2对输入的一句子实现查找且置换的功能。如输入This is a book!↙is(查找的内容) ↙IS(替换的内容)，则输出ThIS IS a book!.

3. 输入一个'.' 结束的字串，从左至右翻译。若下一字符是数字n(0≤n≤9)，表

示后一字符重复n+1次，不论后一字符是否是数字；若下一字符是非数字字符，则表示自己。翻译后以三个字符为1组输出，组与组之间用空格分开。如输入A2B5E34G，则输出ABB BEE EEE E44 44G。

4．求全排列：生成从1到n(n<10)的n个数的全部可能的排列（不一定按升序输出）。例如，输入3，则应该输出（每行输出5个排列）： 123 132 213 231 321 312

5．公园门票每张5角，如果有2n个人排队购票，每人一张，并且其中一半人恰有５角钱，另一半人恰有１元钱，而票房无零钱可找，那么有多少种方法将这2n个人排成一列，顺次购票，使得不至于因票房无零钱可找而耽误时间？ 如输入 3 则输出 000111 001011 001101 010011 010101

6．【问题描述

图书馆馆长正犯愁呢，原来，有一堆的书要他整理，每本书都有一个书号（<=32767),现在他有一本书，这本书的书号为K（<=32767),现在他要找出一本书号比这本书大的书和书号比这本小的书(但都要最接近图书馆馆长已有的书号），将找到的这两本书的书号加起来，并算出加起来以后的数是否为素数

Input

第一行二个数为N,K，表示几本书以及手中书的书号（<=32767) 第二行开始有N个整数，表示这些书的书号 Output

第一行一个数，表示两本书书号加起来的和 第二行一个字符，表示和是否为素数，若是则输出\否则输出\（引号不打出） Sample Input 6 5

6 4 5 3 1 20 Sample Output 10 F

program ex1148; var n,k,i,x,s:integer;

a:array[0..32767] of integer; f:boolean; begin

readln(n,k);

fillchar(a,sizeof(a),0); for i:=1 to n do begin read(x); a[x]:=1; end; s:=0;

for i:=k+1 to 32767 do

if a[i]<>0 then begin s:=s+i;break; end; for i:=k-1 downto 1 do

if a[i]<>0 then begin s:=s+i;break; end;