noip2012普及组复赛

NOIP2012普及组初赛及答案(C++)

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

（普及组C++语言试题）

竞赛时间：2012年10月13日14:30~16:30

选手注意：

试题纸共有10页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上一律无效。 不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料 一、单项选择题（共20题，每题1.5分，共计30分；每题且仅有一个正确选项） 1．计算机如果缺少（ ），将无法正常启动。 A．内存 B．鼠标 C． U盘

D． 摄像头

2．（ ）是一种先进先出的线性表。 A．栈 B．队列 C．哈希表（散列表）

D．二叉树

3．目前计算机芯片（集成电路）制造的主要原料是（ ），它是一种可以在沙子中提炼出的物质。 A．硅 B．铜 C．锗 D．铝 4．十六进制数9A在（ ）进制下是232。 A．四 B．八 C．十 5．（ ）不属于操作系统。 A．Windows B．DOS

D．十二

C．Photoshop D．NOI Linux

6．如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（ ）。 A．ABC

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

PASCAL复习4

1. 字符序列(文件名 ZFXL.PAS)

任意输入三个字母，由程序判断其中是否有字母表中的相邻字母。如果是，输出TRUE，否则输出FALSE。例如，输入字母为”gpf”，其中g和f是字母表中的相邻字母，此时输出TRUE。 【输入】：输入只有一行，是一个字符序列，三个字母。 【输出】：输出共一行，TRUE或FALSE 输入输出样例：

输入：XGY 输入：kym

输出：TRUE 输出：FALSE

2．圆圈填空（文件名YQTK.PAS）

:图中有10个小圆圈，其中6个已填入数字，这6个数字的特点是：相邻两数的平方和等于直径另一端相邻两数的平方和。如492+222=472+262，222+192=262+132。要求填入余下的4个空格（小于20的数），使其符合规律。 输入输出样例：

2 14 14 2 2 16 14 8 2 19 14 13 8 14 16 2 8 16 16 8 8 19 16 13 13 14 19 2 13 16 19 8 13 19 19 13

3. 友素数（文件名YSS.PAS）

若两个自然连续数乘积减1

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．【问题描述

陶陶很喜欢数学 ，尤其喜欢奇怪的数。一天，他突然发现，有的整数拥有的因子数是很有个性的，决定找到一个具有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．数字反转(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

NOIP2014普及组复赛试题解答

3. 螺旋矩阵 【问题描述】

一个n 行n列的螺旋矩阵可由如下方法生成：

从矩阵的左上角（第1行第1列）出发，初始时向右移动：如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入1，2，3，…，n2，便构成了一个螺旋矩阵。

现给出矩阵大小n以及i和j,请你求出该矩阵中第i行第j列的数是多少。 【分析】

这是个蛇形填数问题。 如果采用先枚举二维数组再找对应的元素方法，由于1 ≤ n ≤ 30,000，需要建立一个 30,000× 30,000的二维数组，结果会发生数据溢出且超出运行内存上限（128M)。

我们可以采用类似贪吃蛇的方法，让它在N×N个方格内自外向内逐格移动，控制其向右转的方向，并计算其长度。

解法一

#include using namespace std; bool pd(int,int) ; int i,j; bool p; int main() {

int n,x,y,u,d,l,r,tot=0; // U为上边界，D为下边界 ，L为左边界，R为右边界；

freopen(\freopen(\scanf(\

d=n;r

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

给出用等号连接的两个整数，如“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;