全国信息学奥林匹克联赛（NOIP2008）复赛
提高组
一、题目概览
二、提交源程序文件名
三、编译命令（不包含任何优化开关）
四、运行内存限制
注意事项：
1. 文件名（程序名和输入输出文件名）必须使用大写。
2. C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。
3. 全国统一评测时采用的机器配置为：CPU 1.9GHz，内存512M，上述时限以此配置为准。各省在自测时可根据具体配置调整时限。
1. 笨小猴
(word.pas/c/cpp)
【问题描述】
笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！
这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn 是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。
【输入】
输入文件word.in只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。【输出】
输出文件word.out共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”；
第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出0。
【输入输出样例1】
【输入输出样例1解释】
单词error中出现最多的字母r出现了3次，出现次数最少的字母出现了1次，3-1=2，2是质数。
【输入输出样例2】
【输入输出样例2解释】
单词olympic中出现最多的字母i出现了2次，出现次数最少的字母出现了1次，2-1=1，1不是质数。
基本的字符串处理，细心一点应该没问题的，不过判断素数时似乎需要考虑下0和1的情况。var a:array['a'..'z']of integer;
s:string;
l,i,max,min,n:integer;
ch:char;flag:boolean;
begin
assign(input,'word.in');
reset(input);
assign(output,'word.out');
rewrite(output);
readln(s);
l:=length(s);
fillchar(a,sizeof(a),0);
for i:=1 to l do
inc(a[s[i]]);
max:=0;min:=100;
for ch:='a'to 'z' do
if a[ch]>0 then begin
if a[ch]>max then max:=a[ch];
if a[ch] end; n:=max-min; flag:=true; if(n=0) or (n=1) then flag:=false else for i:=2 to trunc(sqrt(n)) do if n mod i =0 then begin flag:=false;break;end; if flag then begin writeln('Lucky Word'); writeln(n);end else begin writeln('No Answer');writeln(0);end; close(output);close(input); end. 2. 火柴棒等式 (matches.pas/c/cpp) 【问题描述】 给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示： 注意： 1. 加号与等号各自需要两根火柴棍 2. 如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0） 3. n根火柴棍必须全部用上 【输入】 输入文件matches.in共一行，又一个整数n（n<=24）。 【输出】 输出文件matches.out共一行，表示能拼成的不同等式的数目。 【输入输出样例1】 【输入输出样例1解释】 2个等式为0+1=1和1+0=1。 【输入输出样例2】 【输入输出样例2解释】 9个等式为： 0+4=4 0+11=11 1+10=11 2+2=4 2+7=9 4+0=4 7+2=9 10+1=11 11+0=11 预处理下，然后枚举、剪枝，范围稍微开大点，弄到2000似乎足够了，剪枝后不会超时的。首先预处理下每个数（0~2000）需要多少个火柴棒，然后枚举A和B，再判断。 参考程序1： program matches; const inp='matches.in'; oup='matches.out'; num:array['0'..'9'] of integer=(6,2,5,5,4,5,6,3,7,6);//0~9需要的火柴棒数 maxn=1000; var f:array[0..maxn*2] of longint; i,j,k,n,ans:longint; s:string; procedure flink; begin assign(input,inp); reset(input); assign(output,oup); rewrite(output); end; procedure fclose; begin close(input); close(output); end; procedure init;//预处理0~2000每个数需要的火柴棒数 var i,j,k:longint; s:string; begin for i:= 0 to maxn*2 do begin str(i,s); f[i]:=0; for j:= 1 to length(s) do inc(f[i],num[s[j]]); end; end; begin flink; readln(n); init; ans:=0; n:=n-4;//总火柴棒数减去'+'和'='所需的火柴棒数 for i:= 0 to maxn do//枚举A begin if f[i]>=n then continue;//剪枝 for j:= 0 to maxn do//枚举B begin if f[i]+f[j]>=n then continue;//剪枝 k:=i+j; if f[i]+f[j]+f[k]=n then inc(ans);//符合条件,总数加一 end; end; write(ans); fclose; end. 参考程序2： program matches; var n:longint; begin assign(input,'matches.in'); reset(input); assign(output,'matches.out'); rewrite(output); read(n); n:=n-4; if n<9 then begin writeln(0); close(output); exit; end; case n of 9:writeln(1); 10:writeln(2); 11:writeln(8); 12:writeln(9); 13:writeln(6); 14:writeln(9); 15:writeln(29); 16:writeln(39); 17:writeln(38); 18:writeln(65); 19:writeln(88); 20:writeln(128); end; close(output); end. 3. 传纸条 (massage.pas/c/cpp) 【问题描述】 小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。 在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。 还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。 【输入】 输入文件message.in的第一行有2个用空格隔开的整数m和n，表示班里有m行n列（1<=m,n<=50）。 接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。 【输出】 输出文件message.out共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。 【输入输出样例】 【限制】 30%的数据满足：1<=m,n<=10 100%的数据满足：1<=m,n<=50 这道题和方格取数是一样的，只是状态的给出不同而已，典型的动态规划，我们可以把一来一回变成2次同时从左上到右下的过程，用f（i1,j1，i2,j2）表示两个同时分别到达（i1,j1）（i2,j2）的最大值，则转移方程为： 设x=max（f【i1-1,j1，i2-1,j2】，f【i1-1,j1，i2,j2-1】，f【i1,j1-1，i2-1,j2】，f【i1,j1-1，i2,j2-1】） f【i1,j1,i2,j2】={ 0 i1=0或j1=0或i2=0 或j2=0 { x+a【i1,j1】i1*i2*j1*j2<>0 且i1=i2,j1=j2 { x+a【i1,j1】+a【i2,j2】 i1*i2*j1*j2<>0 且i1<>i2,j1<>j2代码如下： program message; var f:array[0..51,0..51,0..51,0..51]of longint; map:array[0..100,0..100]of longint; n,m:longint; procedure init ; begin assign(input,'message.in'); assign(output,'message.out'); reset(input); rewrite(output); end; procedure prepare; var i,j:longint; begin readln(n,m); for i:=1 to n do for j:=1 to m do begin read(map[i,j]); end; end; procedure outit; begin close(input) ; close(output); end; procedure main; var i,j,k,l:longint; begin for i:=1 to n do for j:=1 to m do for k:=1 to n do for l:=1 to m do begin if f[i-1,j,k-1,l]>f[i,j,k,l] then f[i,j,k,l]:=f[i-1,j,k-1,l]; if f[i-1,j,k,l-1]>f[i,j,k,l] then f[i,j,k,l]:=f[i-1,j,k,l-1]; if f[i,j-1,k-1,l]>f[i,j,k,l] then f[i,j,k,l]:=f[i,j-1,k-1,l]; if f[i,j-1,k,l-1]>f[i,j,k,l] then f[i,j,k,l]:=f[i,j-1,k,l-1]; f[i,j,k,l]:=f[i,j,k,l]+map[i,j]; if (i<>k)and(j<>l) then f[i,j,k,l]:=f[i,j,k,l]+map[k,l]; end; writeln(f[n,m,n,m]); end; begin init; prepare; main; outit; end. var a:array[1..50,1..50] of integer; f:array[1..100,1..50,1..50]of integer; m,i,j,n,total,k,x1,x2:integer; function max(s1,s2,s3,s4:integer):integer; var s:integer; begin s:=s1; if s2>s then s:=s2; if s3>s then s:=s3; if s4>s then s:=s4; max:=s; end; begin assign(input,'message.in'); reset(input); assign(output,'message.out'); rewrite(output); readln(m,n); for i:=1 to m do for j:=1 to n do read(a[i,j]); fillchar(f,sizeof(f),0); for k:=2 to m+n-2 do for x1:=1 to k do for x2:=1 to x1-1 do begin f[k,x1,x2]:=max(f[k-1,x1,x2],f[k-1,x1,x2-1],f[k-1,x1-1,x2],f[k-1,x1-1,x2-1]); f[k,x1,x2]:=f[k,x1,x2]+a[x1,k+1-x1]+a[x2,k+1-x2]; end; writeln(f[m+n-2,m,m-1]); close(input); close(output); end. 4. 双栈排序 (twostack.pas/c/cpp) 【问题描述】 Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。 操作a 如果输入序列不为空，将第一个元素压入栈S1 操作b 如果栈S1不为空，将S1栈顶元素弹出至输出 序列 操作c 如果输入序列不为空，将第一个元素压入栈S2 操作d 如果栈S2不为空，将S2栈顶元素弹出至输出 序列 如果一个1~n的排列P可以通过一系列操作使 得输出序列为1，2，…，(n-1)，n，Tom就称P是一个“可双栈排序排列”。例如(1,3,2,4)就是一个“可双栈排序序列”，而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列： 当然，这样的操作序列有可能有几个，对于上例(1,3,2,4)， 【输入】 输入文件twostack.in的第一行是一个整数n。 第二行有n个用空格隔开的正整数，构成一个1~n的排列。 【输出】 输出文件twostack.out共一行，如果输入的排列不是“可双栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。 【输入输出样例1】 【输入输出样例2】 【输入输出样例3】 【限制】 30%的数据满足：n<=10 50%的数据满足：n<=50 100%的数据满足：n<=1000 这道题大概可以归结为如下题意: 有两个队列和两个栈,分别命名为队列1(q1),队列2(q2),栈1(s1)和栈2(s2).最初的时候,q2,s1和s2都为空,而q1中有n个数(n<=1000),为1~n的某个排列. 现在支持如下四种操作: a操作,将q1的首元素提取出并加入s1的栈顶. b操作,将s1的栈顶元素弹出并加入q1q2的队列尾. c操作,将q1的首元素提取出并加入s2的栈顶. d操作,将s2的栈顶元素弹出并加入q1q2的队列尾. 请判断,是否可以经过一系列操作之后,使得q2中依次存储着1,2,3,…,n.如果可以,求出字典序最小的一个操作序列. 这道题的错误做法很多,错误做法却能得满分的也很多,这里就不多说了.直接切入正题,就是即将介绍的这个基于二分图的算法. 注意到并没有说基于二分图匹配,因为这个算法和二分图匹配无关.这个算法只是用到了给一个图着色成二分图. 第一步需要解决的问题是,判断是否有解. 考虑对于任意两个数q1[i]和q1[j]来说,它们不能压入同一个栈中的充要条件是什么(注意没有必要使它们同时存在于同一个栈中,只是压入了同一个栈).实际上,这个条件p是:存在一个k,使得i 首先证明充分性,即如果满足条件p,那么这两个数一定不能压入同一个栈.这个结论很显然,使用反证法可证. 假设这两个数压入了同一个栈,那么在压入q1[k]的时候栈内情况如下: …q1[i]…q1[j]… 因为q1[k]比q1[i]和q1[j]都小,所以很显然,当q1[k]没有被弹出的时候,另外两个数也都不能被弹出(否则q2中的数字顺序就不是1,2,3,…,n了). 而之后,无论其它的数字在什么时候被弹出,q1[j]总是会在q1[i]之前弹出.而q1[j]>q1[i],这显然是不正确的. 接下来证明必要性.也就是,如果两个数不可以压入同一个栈,那么它们一定满足条件p.这里我们来证明它的逆否命题,也就是"如果不满足条件p,那么这两个数一定可以压入同一个栈." 不满足条件p有两种情况:一种是对于任意i 第一种情况下,很显然,在q1[k]被压入栈的时候,q1[i]已经被弹出栈.那么,q1[k]不会对q1[j]产生任何影响(这里可能有点乱,因为看起来,当q1[j] 第二种情况下,我们可以发现这其实就是一个降序序列,所以所有数字都可以压入同一个栈. 这样,原命题的逆否命题得证,所以原命题得证. 此时,条件p为q1[i]和q1[j]不能压入同一个栈的充要条件也得证. 这样,我们对所有的数对(i,j)满足1<=i 二分图的两部分看作两个栈,因为二分图的同一部分内不会出现任何连边,也就相当于不能压入同一个栈的所有结点都分到了两个栈中. 此时我们只考虑检查是否有解,所以只要O(n)检查出这个图是不是二分图,就可以得知是否有解. 此时,检查有解的问题已经解决.接下来的问题是,如何找到字典序最小的解. 实际上,可以发现,如果把二分图染成1和2两种颜色,那么结点染色为1对应当前结点被压入s1,为2对应被压入s2.为了字典序尽量小,我们希望让编号小的结点优先压入s1. 又发现二分图的不同连通分量之间的染色是互不影响的,所以可以每次选取一个未染色的编号最小的结点,将它染色为1并从它开始DFS染色,直到所有结点都被染色为止.这样,我们就得到了每个结点应该压入哪个栈中.接下来要做的,只不过是模拟之后输出序列啦~ 还有一点小问题,就是如果对于数对(i,j),都去枚举检查是否存在k使得p1[k] MRain:程序是我自己写的(懒得按照格式输出了),已经过了所有标准数据. var a,b,head,next,point,color:array[0..2001]of longint; s:array[1..2,0..1000]of longint; n,p,i,j,last:longint; procedure badend; begin writeln(0); close(output); halt; end; procedure addedge(a,b:longint); var t:longint; begin inc(p); point[p]:=b; if head[a]=0 then head[a]:=p else begin t:=head[a]; while next[t]<>0 do t:=next[t]; next[t]:=p; end; end; procedure dfs(now:longint); var t:longint; begin t:=head[now]; while t<>0 do begin if color[point[t]]=0 then begin color[point[t]]:=3-color[now]; dfs(point[t]); end; if color[point[t]]=color[now] then badend; t:=next[t]; end; end; begin assign(input,'twostack.in'); reset(input); assign(output,'twostack.out'); rewrite(output); fillchar(s,sizeof(s),0); fillchar(a,sizeof(a),0); readln(n); for i:=1 to n do read(a[i]); b[n+1]:=maxlongint;p:=0; for i:=n downto 1 do begin b[i]:=b[i+1]; if a[i] end; for i:=1 to n do for j:=i+1 to n do if (b[j+1] begin addedge(i,j); addedge(j,i); end; for i:=1 to n do if color[i]=0 then begin color[i]:=1; dfs(i); end; last:=1; for i:=1 to n do begin if color[i]=1 then write('a ') else write('c '); inc(s[color[i],0]); s[color[i],s[color[i],0]]:=a[i]; while (s[1,s[1,0]]=last)or(s[2,s[2,0]]=last) do begin if s[1,s[1,0]]=last then begin write('b '); dec(s[1,0]); end; if s[2,s[2,0]]=last then begin write('d '); dec(s[2,0]); end; inc(last); end; end; close(input); close(output); end. NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案 一、单项选择题（共 15 题，每题 1.5 分，共计 22.5 分；每题有且仅有一个正确选项） 1. 从( )年开始，NOIP 竞赛将不再支持 Pascal 语言。 A. 2020 B. 2021 C. 2022 D. 2023 2.在 8 位二进制补码中，10101011 表示的数是十进制下的( )。 A. 43 B. -85 C. -43 D.-84 3.分辨率为 1600x900、16 位色的位图，存储图像信息所需的空间为( )。 A. 2812.5KB B. 4218.75KB C. 4320KB D. 2880KB 4. 2017年10月1日是星期日，1949年10月1日是( )。 A. 星期三 B. 星期日 C. 星期六 D. 星期二 5. 设 G 是有 n 个结点、m 条边(n ≤m)的连通图，必须删去 G 的( )条边，才能使得 G 变成一棵树。 A.m–n+1 B. m-n C. m+n+1 D.n–m+1 6. 若某算法的计算时间表示为递推关系式： T(N)=2T(N/2)+NlogN T(1)=1 则该算法的时间复杂度为( )。 A.O(N) B.O(NlogN) C.O(N log2N) D.O(N2) 7. 表达式a * (b + c) * d的后缀形式是()。 A. abcd*+* B. abc+*d* C. a*bc+*d D. b+c*a*d 8. 由四个不同的点构成的简单无向连通图的个数是( )。 A. 32 B. 35 C. 38 D. 41 9. 将7个名额分给4个不同的班级，允许有的班级没有名额，有( )种不同的分配方案。 A. 60 B. 84 C. 96 D.120 10. 若f[0]=0, f[1]=1, f[n+1]=(f[n]+f[n-1])/2，则随着i的增大，f[i]将接近与( )。 A. 1/2 B. 2/3 D. 1 11. 设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。 A. n2 B. nlogn C. 2n D.2n-1 12. 在n(n>=3)枚硬币中有一枚质量不合格的硬币（质量过轻或质量过重），如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是找出这枚不合格的硬币的算法。请把 a-c三行代码补全到算法中。 a. A XUY b. A Z c. n |A| 算法Coin(A,n) 1. k n/3 2. 将A中硬币分成X,Y,Z三个集合，使得|X|=|Y|=k, |Z|=n-2k 3. if W(X)≠W(Y) //W(X), W(Y)分别为X或Y的重量 4. then_______ 5. else_______ 6. __________ 7. if n>2 then goto 1 8. if n=2 then 任取A中1枚硬币与拿走硬币比较，若不等，则它不合格；若相等，则A 中剩下的硬币不合格 9. if n=1 then A中硬币不合格 正确的填空顺序是( )。 A. b,c,a B. c,b,a C. c,a,b D.a,b,c 13. 在正实数构成的数字三角形排列形式如图所示，第一行的数为a11；第二行的数从左到右依次为a21,a22;…第n行的数为an1,an2,…，ann。从a11开始，每一行的数aij只有两条边可以分别通向下一行的两个数a(i+1)j和a(i+1)(j+1)。用动态规划算法找出一条从a11向下通到an1,an2,…,ann中某个数的路径，使得该路径上的数之和达到最大。 全国信息学奥林匹克联赛（NOIP2008）复赛 提高组 一、题目概览 二、提交源程序文件名 三、编译命令（不包含任何优化开关） 四、运行内存限制 注意事项： 1. 文件名（程序名和输入输出文件名）必须使用大写。 2. C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3. 全国统一评测时采用的机器配置为：CPU 1.9GHz，内存512M，上述时限以此配置为准。各省在自测时可根据具体配置调整时限。 1. 笨小猴 (word.pas/c/cpp) 【问题描述】 笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！ 这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn 是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。 【输入】 输入文件word.in只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。【输出】 输出文件word.out共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”； 第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出0。 【输入输出样例1】 【输入输出样例1解释】 单词error中出现最多的字母r出现了3次，出现次数最少的字母出现了1次，3-1=2，2是质数。 【输入输出样例2】 【输入输出样例2解释】 单词olympic中出现最多的字母i出现了2次，出现次数最少的字母出现了1次，2-1=1，1不是质数。 基本的字符串处理，细心一点应该没问题的，不过判断素数时似乎需要考虑下0和1的情况。var a:array['a'..'z']of integer; s:string; l,i,max,min,n:integer; ch:char;flag:boolean; begin assign(input,'word.in'); reset(input); assign(output,'word.out'); rewrite(output); readln(s); 1. 话说去年苹果们被陶陶摘下来后都很生气，于是就用最先进的克隆技术把陶陶克隆了好多份>.<然后把他们挂在树上，准备摘取。摘取的规则是，一个苹果只能摘一个陶陶，且只能在它所能摘到的高度以下（即是小于关系）的最高的陶陶，如果摘不到的话只能灰溜溜的走开了>.<给出苹果数目及每个苹果可以够到的高度和各个陶陶的高度，求苹果们都摘完后剩下多少个陶陶…… 【输入格式】第一行为两个数，分别为苹果的数量n和陶陶的数量m（n,m<=2000）以下的n行，分别为各个苹果能够到的最大高度。再接下来的m行，分别为各个陶陶的高度。高度均不高于300。 当然了，摘取的顺序按照输入的“苹果够到的最大高度”的顺序来摘。 【输出格式】输出仅有一个数，是剩下的陶陶的数量 【样例输入】5 5↙9↙10↙2↙3↙1↙6↙7↙8↙9↙10 【样例输出】3 2. 某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。 任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前5名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分）是：7 279 5 279 这两行数据的含义是：总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是279（总分等于输入的语文、数学、英语三科成绩之和），但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是：5 279 7 279则按输出错误处理，不能得分。【输入】输入文件scholar.in包含n+1行： 第1行为一个正整数n，表示该校参加评选的学生人数。 第2到n+1行，每行有3个用空格隔开的数字，每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1~n（恰好是输入数据的行号减1）。 所给的数据都是正确的，不必检验。 【输出】输出文件scholar.out共有5行，每行是两个用空格隔开的正整数, 依次表示前5名学生的学号和总分。 【输入输出样例1】 scholar.in scholar.out 6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98 6 265 4 264 3 258 2 244 1 237 【输入输出样例2】 scholar.in scholar.out 8 80 89 89 8 265 2 264 2.排座椅 （seat.pas/c/cpp） 【问题描述】 上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列，坐在第i行第j列 的同学的位置是（i，j），为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。 请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少。 【输入】 输入文件seat.in的第一行，有5各用空格隔开的整数，分别是M，N，K，L，D（2<=N，M<=1000，0<=K 第十四届全国青少年信息学奥林匹克联赛初赛试题 （普及组Pascal语言二小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一、单项选择题（共20题，每题1.5分。每题有且仅有一个正确答案。） 1．微型计算机中，控制器的基本功能是（）。 A．控制机器各个部件协调工作B．实现算术运算和逻辑运算 C．获取外部信息D．存放程序和数据 2．设A=True，B=False，C=True，D=False，以下逻辑运算表达式值为真的是（）。A．(A∧B)∨(C∧D∨﹁A) B．((﹁A∧B)∨C)∧﹁D C．(B∨C∨D)∧D∧A D．A∧（D∨﹁C）∧B 3．在下列关于图灵奖的说法中，不正确的是（）。 A．图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人 B．图灵奖有“计算机界诺贝尔奖”之称 C．迄今为止，还没有华裔计算机科学家获此殊荣 D．图灵奖的名称取自计算机科学的先驱、英国科学家阿兰·图灵 4．计算机在工作过程中，若突然停电，（）中的信息不会丢失。 A．ROM 和RAM B．CPU C．ROM D．RAM 5．完全二叉树共有2*N-1个结点，则它的叶节点数是（）。 A．N-1 B．N C．2*N D．2N-1 6．在以下各项中，( ）不是操作系统软件。 A．Solaris B．Linux C．Windows Vista D．Sybase 7．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，则栈S的容量至少应该是（）。 A．6 B．5 C．4 D．3 8．与十进制数28.5625相等的四进制数是（）。 A．123.21 B．131.22 C．130.22 D．130.21 9．设字符串S=”Olympic”，S的非字串的数目是（）。 A．28 B．29 C．16 D．17 10．Web2.0 是近年来互联网的热门概念之一，其核心思想是互动与分享。下列网站中，（）是典型的Web 2.0应用。 A．Sina B．Flicker C．Yahoo D．Google 2002年全国青少年信息学（计算机）奥林匹克分区联赛复赛试题 （普及组竞赛用时：3 小时） 题一级数求和（存盘名：NOIPC1） [问题描述]: 已知：Sn= 1＋1／2＋1／3＋…＋1／n。显然对于任意一个整数K，当n足够大的时候，Sn大于K。 现给出一个整数K（1<=k<=15），要求计算出一个最小的n；使得Sn＞K。 [输入] 键盘输入 k [输出] 屏幕输出 n [输入输出样例] 输人：1 输出：2 题二选数（存盘名：NOIPC2） [问题描述]: 已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34。 现在，要求你计算出和为素数共有多少种。 例如上例，只有一种的和为素数：3＋7＋19＝29）。 [输入]： 键盘输入，格式为： n , k （1<=n<=20，k＜n） x1,x2，…,xn （1<=xi<=5000000） [输出]： 屏幕输出，格式为： 一个整数（满足条件的种数）。 [输入输出样例]: 输入： 4 3 3 7 12 19 输出： 1 [问题描述]: 给出一个整数 n（n<10^30) 和 k 个变换规则（k<=15）。 规则： 一位数可变换成另一个一位数： 规则的右部不能为零。 例如：n=234。有规则（k＝2）： 2－> 5 3－> 6 上面的整数 234 经过变换后可能产生出的整数为（包括原数）: 234 534 264 564 共 4 种不同的产生数 问题： 给出一个整数 n 和 k 个规则。 求出： 经过任意次的变换（0次或多次），能产生出多少个不同整数。 仅要求输出个数。 [输入]: 键盘输人，格式为： n k x1 y1 x2 y2 ... ... xn yn [输出]: 屏幕输出，格式为： 一个整数（满足条件的个数）： [输入输出样例]: 输入: 234 2 2 5 3 6 输出： 4 NOIP2017普及组初赛试题及答案 一、单项选择题（共20题，每题1.5分，共计30分；每题有且仅有一个正确选项） 1.在8位二进制补码中，10101011表示的数是十进制下的( )。 A. 43 B. -85 C. -43 D. -84 2.计算机存储数据的基本单位是( )。 A. bit B. Byte C. GB D. KB 3.下列协议中与电子邮件无关的是( )。 A. POP3 B. SMTP C. WTO D. IMAP 4.分辨率为800x600、16位色的位图，存储图像信息所需的空间为( )。 A.937.5KB B. 4218.75KB C.4320KB D. 2880KB 5.计算机应用的最早领域是( )。 A.数值计算 B.人工智能 C.机器人 D.过程控制 6.下列不属于面向对象程序设计语言的是( )。 A. C B. C++ C. Java D. C# 7.NOI的中文意思是( )。 A.中国信息学联赛 B.全国青少年信息学奥林匹克竞赛 C.中国青少年信息学奥林匹克竞赛 D.中国计算机协会 8. 2017年10月1日是星期日，1999年10月1日是( )。 A.星期三 B.星期日 C.星期五 D.星期二 9.甲、乙、丙三位同学选修课程，从4门课程中，甲选修2门，乙、丙各选修3门，则不同的选修方案共有( )种。 A. 36 B. 48 C. 96 D. 192 10.设G是有n个结点、m条边(n ≤m)的连通图，必须删去G的( )条边，才能使得G变成一棵树。 A.m–n+1 B. m-n C. m+n+1 D.n–m+1 11.对于给定的序列{ak}，我们把(i, j)称为逆序对当且仅当i < j且ai> aj。那么 序列1, 7, 2, 3, 5, 4的逆序对数为()个。 A. 4 B. 5 C. 6 D. 7 12.表达式a * (b + c) * d的后缀形式是()。 A. abcd*+* B. abc+*d* C. a*bc+*d D. b+c*a*d 13.向一个栈顶指针为hs的链式栈中插入一个指针s指向的结点时，应执行( )。 第十四届全国青少年信息学奥林匹克联赛初赛试题2008 （普及组 C++语言二小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题分，共计30分。每题有且仅有一个正确答案.）。 1．微型计算机中，控制器的基本功能是（）。 A. 控制机器各个部件协调工作 B. 实现算术运算和逻辑运算 C. 获取外部信息 D. 存放程序和数据 2. 设A=true，B=false，C=true，D=false，以下逻辑运算表达式值为真的是（）。 A. (A∧B)∨(C∧D∨?A) B. ((?A∧B)∨C)∧?D C. (B∨C∨D)∧D∧A D. A∧(D∨?C)∧B 3. 在下列关于图灵奖的说法中，不正确的是（）。 A. 图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人 B. 图灵奖有“计算机界诺贝尔奖”之称 C. 迄今为止，还没有华裔计算机科学家获此殊荣 D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰·图灵 4．计算机在工作过程中，若突然停电，（）中的信息不会丢失。 A. ROM和RAM B. CPU D. RAM 5．完全二叉树共有2*N-1个结点，则它的叶节点数是（）。 A. N-1 B. N C. 2*N D. 2N-1 6. 在以下各项中，（）不是操作系统软件。 A. Solaris B. Linux C. Windows Vista D. Sybase 7．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，则栈S的容量至少应该是（）。 A. 6 B. 5 C. 4 D. 3 8. 与十进制数相等的四进制数是（）。 A. B. 131.22 C. D. 9. 设字符串S=”Olympic”，S的非空子串的数目是（）。 A. 28 B. 29 C. 16 D. 17 10．是近年来互联网的热门概念之一，其核心思想是互动与分享。下列网站中， （）是典型的应用。 A. Sina B. Flickr C. Yahoo D. Google CCF全国信息学奥林匹克联赛（NOIP2015）复赛 普及组 （请选手务必仔细阅读本页内容） 一、题目概况 中文题目名称金币扫雷游戏求和推销员 coin mine sum salesman 英文题目与子目 录名 可执行文件名coin mine sum salesman 输入文件名coin.in mine.in sum.in salesman.in 输出文件名coin.out mine.out sum.out salesman.out 每个测试点时限1秒 测试点数目10 每个测试点分值10 附加样例文件有 结果比较方式全文比较（过滤行末空格及文末回车） 题目类型传统 运行内存上限128M 二、提交源程序文件名 对于C++语言coin.cpp mine.cpp sum.cpp salesman.cpp 对于C语言coin.c mine.c sum.c salesman.c 对于Pascal语言coin.pas mine.pas sum.pas salesman.pas 四、注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm)II x2240processor，2.8GHz，内存4G，上述时限以此配置为准。 4、只提供Linux格式附加样例文件。 5、特别提醒：评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以其为准。 1.金币 (coin.cpp/c/pas) 【问题描述】 国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N+1天里，每天收到N+1枚金币。 请计算在前K天里，骑士一共获得了多少金币。 【输入格式】 输入文件名为coin.in。 输入文件只有1行，包含一个正整数K，表示发放金币的天数。 【输出格式】 输出文件名为coin.out。 输出文件只有1行，包含一个正整数，即骑士收到的金币数。 【输入输出样例1】 coin.in coin.out 614 见选手目录下的coin/coin1.in和coin/coin1.ans。 【输入输出样例1说明】 骑士第一天收到一枚金币；第二天和第三天，每天收到两枚金币；第四、五、六天，每天收到三枚金币。因此一共收到1+2+2+3+3+3=14枚金币。 【输入输出样例2】 coin.in coin.out 100029820 见选手目录下的coin/coin2.in和coin/coin2.ans。 【数据说明】 对于100%的数据，1≤K≤10,000。 noip2017提高组复赛解题报告 定期推送帐号信息学新闻，竞赛自主招生，信息学专业知识，信息学疑难解答，融科教育信息学竞赛培训等诸多优质内容的微信平台，欢迎分享文章给你的朋友或者朋友圈！以下解题思路及代码未经官方评测，仅供参考，复赛成绩以官方（CCF）评测结果为准。 Day1 1.小凯的疑惑(math.cpp/c/pas)【问题描述】小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币?注意:输入数据保证存在小凯无法准确支付的商品。【输入格式】输入文件名为math.in。输入数据仅一行，包含两个正整数a 和b，它们之间用一个空格隔开，表示小凯手中金币的面值。【输出格式】输出文件名为math.out。输出文件仅一行，一个正整数N，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。【输入输出样例1】math.in3 7 math.out11【数据规模与约定】对于30%的数据: 1 ≤a，b ≤50。对于60%的数据: 1 ≤a，b ≤10,000。对于100%的数据:1 ≤a，b ≤1,000,000,000。数学太差只找规律吧。 设：其中一个数为2则：2、3=>1；2、5=>3；2、7=>5；2、11=>9得：2、n=>n-2设：其中一个数为3则：3、5=>7；3、7=>11；3、11=>19；3、13=>23得：3、n=>2n-3设：其中一个数为5则：5、7=>23；5、11=>39；5、13=>47；5、17=>63得：5、n=>4n-5所以：m、n=>(m-1)n-m #includeusing namespace std;int main(){ long long a,m,n; scanf('%lld %lld',&m,&n); a=(m-1)*n-m; printf('%lld',a); return 0;} 2.时间复杂度(complexity.cpp/c/pas)【问题描述】小明正在学习一种新的编程语言A++，刚学会循环语句的他激动地写了好多程序并给出了他自己算出的时间复杂度，可他的编程老师实在不想一个一个检查小明的程序，于是你的机会来啦!下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。A++语言的循环结构如下:其中“F i x y”表示新建变量(i 变量i 不可与未被销毁的变量重名)并初始化为x，然后判断i 和y 的大小关系，若i 小于等于y 则进入循环，否则不进入。每次循环结束后i都会被修改成i +1，一旦i 大于y 终止循环。x和y 可以是正整数(x 和y 的大小关系不定)或变量n。n 是一个表示数据规模的变量，在时间复杂度计算中需保留该变量而不能将其视为常数，该数远大于100。“E”表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。注:本题中为了书写方便，在描述复杂度时，使用大 第十四届全国青少年信息学奥林匹克联赛初赛试题2008 （普及组C++语言二小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一、单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确答案.）。 1．微型计算机中，控制器的基本功能是（）。 A.控制机器各个部件协调工作 B.实现算术运算和逻辑运算 C.获取外部信息 D.存放程序和数据 2.设A=true，B=false，C=true，D=false，以下逻辑运算表达式值为真的是（）。 A.(A∧B)∨(C∧D∨?A) B.((?A∧B)∨C)∧?D C.(B∨C∨D)∧D∧A D.A∧(D∨?C)∧B 3.在下列关于图灵奖的说法中，不正确的是（）。 A.图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人 B.图灵奖有“计算机界诺贝尔奖”之称 C.迄今为止，还没有华裔计算机科学家获此殊荣 D.图灵奖的名称取自计算机科学的先驱、英国科学家阿兰·图灵 4．计算机在工作过程中，若突然停电，（）中的信息不会丢失。 A.ROM和RAM B.CPU C.ROM D.RAM 5．完全二叉树共有2*N-1个结点，则它的叶节点数是（）。 A.N-1 B.N C.2*N D.2N-1 6.在以下各项中，（）不是操作系统软件。 A.Solaris B.Linux C.WindowsVista D.Sybase 7．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，则 栈S的容量至少应该是（）。 A.6 B.5 C.4 D.3 8.与十进制数28.5625相等的四进制数是（）。 A.123.21 B.131.22 C.130.22 D.130.21 9.设字符串S=”Olympic”，S的非空子串的数目是（）。 A.28 B.29 C.16 D.17 10．Web2.0是近年来互联网的热门概念之一，其核心思想是互动与分享。下列网站中，（）是典型的Web2.0应用。 A.Sina B.Flickr C.Yahoo D.Google 11．递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（）的数据结构。 A.队列 B.多维数组 C.线性表 D.栈 12.(2008)10+(5B)16的结果是（）。 A.(833)16 B.(2089)10 C.(4163)8 D.(100001100011)2 13.二叉树T，已知其先根遍历是1243576（数字为结点的编号，以下同），中根遍历是2415736，则该二叉树的后根遍历是（）。 A.4257631 B.4275631 C.7425631 D.4276531 【最新整理，下载后即可编辑】 历年noip普及组初赛试题汇编 芜湖县实验学校NOIP初赛复习资料 第十五届全国青少年信息学奥林匹克联赛初赛试题(2009) （普及组C++语言二小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸 上一律无效●● 一．单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确答案。） 1、关于图灵机下面的说法哪个是正确的： A)图灵机是世界上最早的电子计算机。 B)由于大量使用磁带操作，图灵机运行速度很慢。 C)图灵机是英国人图灵发明的，在二战中为破译德军的密码 发挥了重要作用。 D)图灵机只是一个理论上的计算模型。 2、关于计算机内存下面的说法哪个是正确的： A)随机存储器（RAM）的意思是当程序运行时，每次具体分 配给程序的内存位置是随机而不确定的。 B)1MB内存通常是指1024*1024字节大小的内存。 C)计算机内存严格说来包括主存（memory）、高速缓存（cache） 和寄存器（register）三个部分。 D)一般内存中的数据即使在断电的情况下也能保留2个小时 以上。 3、关于BIOS下面说法哪个是正确的： A)BIOS是计算机基本输入输出系统软件的简称。 B)BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输 入输出设备的驱动程序。 C)BIOS一般由操作系统厂商来开发完成。 D)BIOS能提供各种文件拷贝、复制、删除以及目录维护等文 件管理功能。 4、关于CPU下面哪个说法是正确的： A)CPU全称为中央处理器（或中央处理单元）。 B)CPU可以直接运行汇编语言。 C)同样主频下，32位的CPU比16位的CPU运行速度快一倍。 D)CPU最早是由Intel公司发明的。 5、关于ASCII，下面哪个说法是正确的： A)ASCII码就是键盘上所有键的唯一编码。 B)一个ASCII码使用一个字节的内存空间就能够存放。 C)最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的 编码。 D)ASCII码是英国人主持制定并推广使用的。 6、下列软件中不是计算机操作系统的是： A) Windows B) Linux C) OS/2 D) WPS 7、关于互联网，下面的说法哪一个是正确的： A)新一代互联网使用的IPv6标准是IPv5标准的升级与补充。 B)互联网的入网主机如果有了域名就不再需要IP地址。 C)互联网的基础协议为TCP/IP协议。 D)互联网上所有可下载的软件及数据资源都是可以合法免 费使用的。 8、关于HTML下面哪种说法是正确的： A）HTML实现了文本、图形、声音乃至视频信息的统一编码。 B）HTML全称为超文本标记语言。 C）网上广泛使用的Flash动画都是由HTML编写的。 D）HTML也是一种高级程序设计语言。 CCF 全国信息学奥林匹克联赛（NOIP2017）复赛 提高组 day1 （请选手务必仔细阅读本页内容） 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz， 内存4G，上述时限以此配置为准。 4、只提供Linux 格式附加样例文件。 5、提交的程序代码文件的放置位置请参照各省的具体要求。 6、特别提醒：评测在当前最新公布的NOI Linux 下进行，各语言的编译器版本以其为准。 【问题描述】1．小凯的疑惑 (math.cpp/c/pas) 小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在小凯无法准确支付的商品。 【输入格式】 输入文件名为math.in。 输入数据仅一行，包含两个正整数a 和b，它们之间用一个空格隔开，表示小凯手中金币的面值。 【输出格式】 输出文件名为math.out。 输出文件仅一行，一个正整数N，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。 见选手目录下的math/math1.in 和math/math1.ans。 【输入输出样例1 说明】 小凯手中有面值为3 和7 的金币无数个，在不找零的前提下无法准确支付价值为1、2、4、5、8、11 的物品，其中最贵的物品价值为11，比11 贵的物品都能买到，比如： 12 = 3 * 4 + 7 * 0 13 = 3 * 2 + 7 * 1 14 = 3 * 0 + 7 * 2 15 = 3 * 5 + 7 * 0 …… 【输入输出样例2】 见选手目录下的math/math2.in 和math/math2.ans。 【数据规模与约定】 对于30%的数据： 1 ≤ a，b ≤ 50。 对于60%的数据： 1 ≤ a，b ≤ 10,000。 对于100%的数据：1 ≤ a，b ≤ 1,000,000,000。 PASCAL复习12 1.自然数(文件名ZRS.PAS) 【问题描述】任意给定一个自然数M(M<999999999)，如果它的所有各位数字都是由0或1组成，则输出YES,否则输出NO.例: 输入：100 输出：YES 输入：31 输出: NO Var m,x,a:longint; f:boolean; Begin readln(m); x:=m; f:=true; while (x>0)and f do begin a:=x mod 10; if (a<>0)and(a<>1) then f:=false; x:=x div 10; end; if f then writeln(‘YES’) else writeln(‘NO’); readln; End. 2．字符串(文件名ZFC.PAS) 【问题描述】由键盘输入一个超过10个字符的字符串，已知其中有两个“A”，以回车键结束。请你编个程序实现一下两个功能， 1、打印出第一个“A”所在的位置 2、打印出两个“A”之间的字符以及字符个数。 输入：TEACHERSTUDENTAND 输出：3 CHERSTUDENT 11 V AR T,T1:INTEGER; C:CHAR; BEGIN T:=0;t1:=0; Read(c); Repeat t:=t+1; if c=‘A’then begin writeln(t); read(c); repeat write(c); t1:=t1+1; read(c); until c=‘A’; end; read(c); Until c=chr(13); Writeln; Writeln(t1); END. 3.数位和与积(文件名HWHJ.pas) 【问题描述】试编写程序求出n个自然数的各个数位之和与之积。输入：一个自然数n(n<=5)及n个自然数 输出：各行依次输出每一个自然数n的各个数位之和与之积。例如： 输入: 3 92 23 1024 输出 11 18 5 6 7 0 var i,t,x,y,z:integer; begin readln(t); for i:=1 to t do begin read(x); y:=0; z:=1; while x>0 do begin y:=y+x mod 10; z:=z*(x mod 10); x:=x div 10; end; writeln(y,' ',z); end; readln; readln end. 4. 黑色星期五(文件名HSXQW.PAS) 第八届全国青少年信息学奥林匹克联赛(NOIP2002)试题 (普及组PASCAL语言二小时完成) 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 一.选择一个正确答案代码(A/B/C/D,填入每题的括号内(每题1.5分,多选无分,共30分) 1)微型计算机的问世是由于( ) 的出现。 A) 中小规模集成电路 B) 晶体管电路 C) (超)大规模集成电路 D) 电子管电路 2)下列说法中正确的是( ) 。 A) 计算机体积越大,其功能就越强 B) CPU的主频越高,其运行速度越快 C) 两个显示器屏幕大小相同,则它们的分辨率必定相同 D)点阵打印机的针数越多,则能打印的汉字字体越多 3)Windows98中,通过查找命令查找文件时,若输入F*.? , 则下列文件( ) 可以被查到。 A) F.BAS B) FABC.BAS C) F.C D) EF. 4)CPU处理数据的基本单位是字,一个字的字长( ) 。 A) 为8个二进制位 B) 为16个二进制位 C) 为32个二进制位 D) 与芯片的型号有关 5)资源管理器的目录前图标中增加"+"号,这个符号的意思是( ) 。 A) 该目录下的子目录已经展开 B) 该目录下还有子目录未展开 C) 该目录下没有子目录 D) 该目录为空目录, 6)下列哪一种程序设计语言是解释执行的( ) 。 A) Pascal B) GWBASIC C) C++ D) FORTRAN 7)启动WORD的不正确方法是( ) 。 A) 单击Office工具栏上的Word图标 B) 单击"开始"→"程序"→Word C) 单击"开始"→"运行",并输入Word按回车 D) 双击桌面上的"Word快捷图标" 8)多媒体计算机是指( ) 计算机。 A) 专供家庭使用的 B) 装有CDROM的 C) 连接在网络上的高级 D) 具有处理文字、图形、声音、影像等信息的 9)在树型目录结构中,不允许两个文件名相同主要是指( ) 。 A) 同一个磁盘的不同目录下 B) 不同磁盘的同一个目录下 C) 不同磁盘的不同目录下、 D) 同一个磁盘的同一个目录下 10)用画笔(Paintbrush)绘制图形并存储在文件中,该图形文件的文件名缺省的后缀为( ) 。 A) .jpg B) .bmp C) .gif D).tiff t11)E-ml地址中用户名和邮件所在服务器名之间的分隔符号是( ) 。 E A) # B) @ C) & D) $ 12)(0.5)10=( ) 16. A) 0.1 B) 0.75 C) 0.8 D) 0.25 NOIP2017提高组初赛试题及答案 一、单项选择题（共15 题，每题1.5 分，共计22.5 分；每题有且仅有一个正确选项） 1. 从( )年开始，NOIP 竞赛将不再支持Pascal 语言。C A. 2020 B. 2021 C. 2022 D. 2023 2.在8 位二进制补码中，10101011 表示的数是十进制下的( )。B A. 43 B. -85 C. -43 D.-84 3.分辨率为1600x900、16 位色的位图，存储图像信息所需的空间为( )。A A. 2812.5KB B. 4218.75KB C. 4320KB D. 2880KB 4. 2017年10月1日是星期日，1949年10月1日是( )。C A. 星期三 B. 星期日 C. 星期六 D. 星期二 5. 设G 是有n 个结点、m 条边(n ≤m)的连通图，必须删去G 的( )条边，才能使得G 变成一棵树。A A.m–n+1 B. m-n C. m+n+1 D.n–m+1 6. 若某算法的计算时间表示为递推关系式：T(N)=2T(N/2)+NlogN T(1)=1 则该算法的时间复杂度为( )。C A.O(N) B.O(NlogN) C.O(N log2N) D.O(N2) 7. 表达式a * (b + c) * d的后缀形式是()。B A. abcd*+* B. abc+*d* C. a*bc+*d D. b+c*a*d 8. 由四个不同的点构成的简单无向连通图的个数是( )。C A. 32 B. 35 C. 38D. 41 9. 将7个名额分给4个不同的班级，允许有的班级没有名额，有( )种不同的分配方案。D A. 60 B. 84 C. 96 D.120 10. 若f[0]=0, f[1]=1, f[n+1]=(f[n]+f[n-1])/2，则随着i的增大，f[i]将接近与( )。B A. 1/2 B. 2/3 D. 1 11. 设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。D A. n2 B. Nlogn C. 2n D.2n-1 12. 在n(n>=3)枚硬币中有一枚质量不合格的硬币（质量过轻或质量过重），如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是找出这枚不合格的硬币的算法。请把a-c三行代码补全到算法中。 2. 将A中硬币分成X,Y,Z三个集合，使得|X|=|Y|=k, |Z|=n-2k 3. if W(X)≠W(Y) //W(X), W(Y)分别为X或Y的重量 4. then_______ 5. else_______ 6. __________ 7. if n>2 then goto 1 8. if n=2 then 任取A中1枚硬币与拿走硬币比较，若不等，则它不合格；若相等，则A中剩下的硬币不合格 9. if n=1 then A中硬币不合格 正确的填空顺序是( )。D A. b,c,a B. c,b,a C. c,a,b D.a,b,c 13. 在正实数构成的数字三角形排列形式如图所示，第一行的数为a11；第二行的数从左到右依次为a21,a22;…第n行的数为 an1,an2,…，ann。从a11开始，每一行的数aij只有两条边可以分别通向下一行的两个数a(i+1)j和a(i+1)(j+1)。用动态规划算法找出一条从a11向下通到an1,an2,…,ann中某个数的路径，使得该路径上的数之和达到最大。 令C[i,j]是从a11到aij的路径上的数的最大和，并且C[i,0]=C[0,j]=0，则C[i,j]=( )。A A. max{C[i-1,j-1],C[i-1,j]}+aij B. C[i-1,j-1]+c[i-1,j] C. max{C[i-1,j-1],C[i-1,j]}+1 D. max{C[i,j-1],C[i-1,j]}+aij 14. 小明要去南美洲旅游，一共乘坐三趟航班才能到达目的地，其中第1个航班准点的概率是0.9，第2个航班准点的概率为0.8，第3个航班准点的概率为0.9。如果存在第i个（i=1,2）航班晚点，第i+1个航班准点，则小明将赶不上第i+1个航班，旅行失败；除了这种情况，其他情况下旅行都能成功。请问小明此次旅行成功的概率是( )。DNOIP2017全国青少年信息学奥林匹克联赛提高组初赛试题卷答案解析
NOIP2008提高组复赛试题及题解
noip普及组复赛模拟试题18
2008noip普及组复赛--排座位--代码C++
NOIP2008初赛普及组试题
NOIP2002普及组(复赛)
NOIP2017普及组初赛试题及答案
2019年NOIP2008初赛普及组C题目及答案
NOIP2015普及组复赛试题
noip2017提高组复赛解题报告
NOIP2008初赛普及组C++题目及答案
历年noip初赛普及组试题(完整资料).doc
noip2017提高组试题
noip普及组复赛入门训练12(答案)
NOIP2002普及组初赛试题及答案
NOIP2017提高组初赛试题及答案
相关主题
文本预览