NOIP2007 提高组 复赛试题

全国信息学奥林匹克联赛（NOIP2007）复赛提高组题目一览（2007年11月17日 3小时完成）说明：1.文件名（程序名和输入输出文件名）必须使用小写2.C/C++中函数main()的返回值必须是int，程序正常结束时返回值必须是0。

3.全国统一评测时采用的机器参考配置为：CPU 2.0GHz，内存256M。

1.统计数字（count.pas/c/cpp）【问题描述】某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。

已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

【输入】输入文件count.in包含n+1行；第一行是整数n，表示自然数的个数；第2~n+1每行一个自然数。

【输出】输出文件count.out包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。

每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

【输入输出样例】【限制】40%的数据满足：1<=n<=100080%的数据满足：1<=n<=50000100%的数据满足：1<=n<=200000，每个数均不超过1500 000 000（1.5*109）2.字符串的展开（expand.pas/c/cpp）【问题描述】在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于“d-h”或者“4-8”的字串，我们就把它当作一种简写，输出时，用连续递增的字母H 或数字串替代其中的减号，即，将上面两个子串分别输出为“defgh”和“45678”。

在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。

具体约定如下：(1) 遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号“-”，减号两侧同为小写字母或同为数字，且按照ASCII码的顺序，减号右边的字符严格大于左边的字符。

第十七届全国青少年信息学奥林匹克联赛初赛试题（提高组 Pascal语言两小时完成）●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分。

共计30分。

每题有且仅有一个正确选项。

）1．在二进制下，1100011 +（）= 1110000。

A．1011 B．1101 C．1010 D．11112．字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（）。

A．66 B．5A C．50 D．视具体的计算机而定3．右图是一棵二叉树，它的先序遍历是（）。

A．ABDEFC B．DBEFAC C．DFEBCA D．ABCDEF4．寄存器是（）的重要组成部分。

A．硬盘B．高速缓存C．内存D．中央处理器（CPU）5．广度优先搜索时，需要用到的数据结构是（）。

A．链表B．队列C．栈D．散列表6．在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（）。

A．程序运行时理论上所占的内存空间B．程序运行时理论上所占的数组空间C．程序运行时理论上所占的硬盘空间D．程序源文件理论上所占的硬盘空间7．应用快速排序的分治思想，可以实现一个求第K大数的程序。

假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。

A．O(n2)B．O(n log n)C．O(n) D．O(1)8．为解决Web应用中的不兼容问题，保障信息的顺利流通，（）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。

A．微软 B．美国计算机协会（ACM） C．联台国教科文组织D．万维网联盟（W3C）9．体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。

每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。

这种站队的方法类似于（）算法。

A．快速排序B．插入排序C．冒泡排序D．归并排序10．1956年（）授予肖克利（William Shockley）、巴丁（John Bardeen）和布拉顿（Walter Brattain)，以表彰他们对半导体的研究和晶体管效应的发现。

NOI’ 95“同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛复赛试题（高中组）（上机编程，完成时间：210 分钟）<1>编码问题：设有一个数组A:ARRAY[0..N-1] OF INTEGER；数组中存放的元素为0～N-1 之间的整数，且A[i]≠ A[j]（当i≠ j时）。

例如： N=6 时，有：此时，数组 A 的编码定义如下：A[0] 的编码为0；A[i] 的编码为：在A[0] ，A[1]∴上面数组 A 的编码为：A= （ 4，3， 0， 5，1， 2），， A[i-1] 中比 A[i] 的值小的个数（B= （0， 0，0，3，1， 2）i=1 ，2，， N-1 ）程序要求解决以下问题：①给出数组 A 后，求出其编码。

②给出数组 A 的编码后，求出 A 中的原数据。

<2> 灯的排列问题：设在一排上有 N 个格子（ N≤ 20），若在格子中放置有不同颜色的灯，每种灯的个数记为 N 1， N2， N k（ k 表示不同颜色灯的个数）。

放灯时要遵守下列规则：①同一种颜色的灯不能分开；②不同颜色的灯之间至少要有一个空位置。

例如： N=8 （格子数）R=2 （红灯数）B=3 （蓝灯数）放置的方法有：R-B 顺序R R B B BR R B B BR R B B BR R B B BR R B B BR R B B BB-R顺序B B B BBBBBBBBBBBBBBR RRRBRRRRRRRR放置的总数为12 种。

数据输入的方式为：NP1（颜色，为一个字母）P2N1（灯的数量）N2Q（结束标记， Q 本身不是灯的颜色）程序要求：求出一种顺序的排列方案及排列总数。

<3> 设有一个四层的积木块，1～ 4 层积木块的数量依次为：5， 6，7， 8如下图所示放置：815851691423414326其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计算出来的。

全国信息学奥林匹克联赛（NOIP2007）复赛普及组题目一览(2007年11月17日3小时完成)说明：1. 文件名（程序名和输入输出文件名）必须使用小写2. C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。

3. 全国统一评测时采用的机器参考配置为：CPU 2.0GHz，内存256M。

1．奖学金(scholar.pas/c/cpp)【问题描述】某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。

期末，每个学生都有3门课的成绩：语文、数学、英语。

先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前5名学生的学号和总分。

注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。

例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分）是：7 2795 279这两行数据的含义是：总分最高的两个同学的学号依次是7号、5号。

这两名同学的总分都是279（总分等于输入的语文、数学、英语三科成绩之和），但学号为7的学生语文成绩更高一些。

如果你的前两名的输出数据是：5 2797 279则按输出错误处理，不能得分。

【输入】输入文件scholar.in包含n+1行：第1行为一个正整数n，表示该校参加评选的学生人数。

第2到n+1行，每行有3个用空格隔开的数字，每个数字都在0到100之间。

第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。

每个学生的学号按照输入顺序编号为1~n （恰好是输入数据的行号减1）。

所给的数据都是正确的，不必检验。

【输出】输出文件scholar.out共有5行，每行是两个用空格隔开的正整数, 依次表示前5名学生的学号和总分。

Day1铺地毯【问题描述】为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。

一共有n 张地毯，编号从1 到n。

现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。

地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。

注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

【输入】输入文件名为 carpet.in。

输入共 n+2 行。

第一行，一个整数 n，表示总共有n 张地毯。

接下来的 n 行中，第i+1 行表示编号i 的地毯的信息，包含四个正整数a，b，g，k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在x轴和y 轴方向的长度。

第 n+2 行包含两个正整数x 和y，表示所求的地面的点的坐标（x，y）。

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

输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。

【输入输出样例 1】【输入输出样例说明】如下图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，覆盖点（2，2）的最上面一张地毯是3 号地毯。

【输入输出样例 2】【输入输出样例说明】如上图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，点（4，5）没有被地毯覆盖，所以输出-1。

【数据范围】对于 30%的数据，有n≤2；对于 50%的数据，0≤a, b, g, k≤100；对于 100%的数据，有0≤n≤10,000，0≤a, b, g, k≤100,000。

【一句话题意】给定n个按顺序覆盖的矩形，求某个点最上方的矩形编号。

【考察知识点】枚举【思路】好吧我承认看到图片的一瞬间想到过二维树状数组和二维线段树。

置答案ans=-1，按顺序枚举所有矩形，如果点在矩形内则更新ans。

注意题中给出的不是对角坐标，实际上是(a,b)与(a+g,b+k)。

第十三届全国青少年信息学奥林匹克联赛初赛试题（提高组Pascal 语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共 10 题，每题 1.5 分，共计 15 分。

每题有且仅有一个正确答案.）。

1. 在以下各项中。

（）不是 CPU 的组成部分。

A. 控制器B. 运算器C. 寄存器D. 主板E. 算术逻辑单元(ALU)2. 在关系数据库中, 存放在数据库中的数据的逻辑结构以( )为主。

A. 二叉树B. 多叉树C. 哈希表D. B+树E. 二维表3.在下列各项中，只有（）不是计算机存储容量的常用单位。

A. ByteB. KBC. MBD. UBE. TB4．ASCII码的含义是（）。

A. 二—十进制转换码B. 美国信息交换标准代码C. 数字的二进制数码D. 计算机可处理字符的唯一编码E. 常用字符的二进制编码5．在 Pascal 语言中，表达式 (23 or 2 xor 5)的值是（）A. 18B.1 C.23 D.32 E.246．在 Pascal 语言中，判断整数a 等于 0 或b等于 0或c等于0 的正确的条件表达式是（）A. not ((a<>0) or (b<>0) or (c<>0))B. not ((a<>0) and (b<>0) and (c<>0))C. not ((a=0) and (b=0)) or (c=0)D.(a=0) and (b=0) and (c=0)E. not ((a=0) or (b=0) or (c=0))7. 地面上有标号为A、B、C的3根细柱, 在A柱上放有10个直径相同中间有孔的圆盘, 从上到下次依次编号为1, 2, 3, ……，将A柱上的部分盘子经过B柱移入C柱, 也可以在B 柱上暂存。

如果B柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。

第一题：count 统计数字输入一个数n(n<=200000)和n个自然数（每个数都不超过1.5*10^9），请统计出这些自然数各自出现的次数，按顺序从小到大输出。

输入数据保证不相同的数不超过10000个。

样例输入：8242451002100样例输出：2 34 25 1100 2第一题program scholar(input,output);var a,b,c,id,s:array[1..300]of integer;v:array[0..0]of boolean;i,j,k,t,m,n,x,y:integer;beginassign(input,'scholar.in');assign(output,'scholar.out');reset(input);rewrite(output);readln(n);for i:=1 to n dobegin readln(a[i],b[i],c[i]);id[i]:=i;end;for i:=1 to n dos[i]:=a[i]+b[i]+c[i];for i:=1 to n-1 dofor j:=i to n dobeginif s[i]<s[j]thenbegint:=s[i];s[i]:=s[j];s[j]:=t;t:=a[i];a[i]:=a[j];a[j]:=t;t:=b[i];b[i]:=b[j];b[j]:=t;t:=c[i];c[i]:=c[j];c[j]:=t;t:=id[i];id[i]:=id[j];id[j]:=t;end;if s[i]=s[j]thenif a[i]<a[j] thenbegint:=s[i];s[i]:=s[j];s[j]:=t;t:=a[i];a[i]:=a[j];a[j]:=t;t:=b[i];b[i]:=b[j];b[j]:=t;t:=c[i];c[i]:=c[j];c[j]:=t;t:=id[i];id[i]:=id[j];id[j]:=t;endend;for i:=1 to 5 dowriteln(id[i],' ',a[i]+b[i]+c[i]);close(input);close(output);end.第二题：expand 字符串的展开我们可以用减号对连续字母或数字进行缩写，于是字符串a-dha3-68就可以展开为abcdha34568。