NOIP2007提高组复赛试题解题报告三

全国信息学奥林匹克联赛(NOIP2007)复赛普及组1.奖学金(scholar.pas/c/cpp)【问题描述】某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。

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

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

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

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

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

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

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

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

第2到n+1行，每行有3个用空格隔开的数字，每个数字都在O到100之间z第1行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。

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

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

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

全国信息学奥林匹克联赛(NOIP2007)复赛普及组【输入输出样例1】【输入输出样例2】【限制】50%的数据满足:各学生的总成绩各不相同 100%的数据满足: 6<=n<=300全国信息学奥林匹克联赛(NOIP2007)复赛普及组2.纪念品分组(group.pas/c/cpp)【题目描述】元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。

NOIP2007提高组解题报告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）【算法分析】由于数的个数比较多，所以不能用选择排序或冒泡排序。

又因为数比较大，所以普通哈希排序法不能奏效。

我这里采用了快速排序，这是一种二分排序算法，速度比较快。

接下来的步骤也很重要，如果处理不当，会浪费时间。

【变量说明】varn,i,t,k:longint;{t：输出时计数}a:array[1..200000] of longint;{排序数组}【程序清单】varn,i,t,k:longint;a:array[1..200000] of longint;procedure qsort(l,r:longint);{快速排序}vari,j,x,t:longint;begini:=l;;j:=r;x:=a[(l+r) div 2];repeatwhile a[i]<x do inc(i);while x<a[j] do dec(j);if i<=j thenbegint:=a[i];a[i]:=a[j];a[j]:=t;inc(i);dec(j);end;until i>j;if l<j then qsort(l,j);if i<r then qsort(i,r);end;beginassign(input,'count.in');reset(input);assign(output,'count.out');rewrite(output);read(n);for i:=1 to n doread(a[i]);qsort(1,n);i:=1;while i<=n do{输出}beginwrite(a[i],' ');t:=0;k:=a[i];while (i<=n)and(a[i]=k) dobegininc(t);inc(i);end;writeln(t);end;close(input);close(output);end.【考察知识点】快速排序。

第十七届全国青少年信息学奥林匹克联赛初赛试题（提高组 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)，以表彰他们对半导体的研究和晶体管效应的发现。

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

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

1. 在以下各项中。

（）不是CPU 的组成部分。

A. 控制器B. 运算器C. 寄存器D. 主板E. 算术逻辑单元(ALU)【答案】D。

CPU组成：控制器、运算器（ALU）、寄存器。

2. 在关系数据库中, 存放在数据库中的数据的逻辑结构以( )为主。

A. 二叉树B. 多叉树C. 哈希表D. B+树E. 二维表【答案】E。

二维表，列表示数据库的字段（栏目）、行表示数据库的记录，类似于Excel。

3.在下列各项中，只有（）不是计算机存储容量的常用单位。

A. ByteB. KBC. MBD. UBE. TB【答案】D。

1Byte=8bit（位）、1KB=1024B（Byte）、1MB=1024KB、1GB=1024MB、1TB=1024GB 4．ASCII码的含义是（）。

A. 二—十进制转换码B. 美国信息交换标准代码C. 数字的二进制数码D. 计算机可处理字符的唯一编码E. 常用字符的二进制编码【答案】B。

5．在Pascal 语言中，表达式(23 or 2 xor 5)的值是（）A. 18B. 1C.23D.32E.24【答案】A。

23=10111)2，2=00010)2，5=00101)2，10111)2or 00010)2=10111)2，10111)2xor 00101)2=10010)2=18)10。

6．在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))【答案】B。

NOIP 2007 普及组解题报告By 江苏省赣榆县实验中学初二参赛选手夏雨( 阿洛.c ) 我仅仅想用本文启发一下NOIP2007普及组的同学们，我也不是什么牛，仅仅是意见交流，另：本文供各位路过的牛们鄙视下。

第一题：奖学金【题目描述】：【解题思路】：这一题有很多种做法，包括排序、模拟等等。

现在，介绍一种最优算法，（其实最烂算法也可以全过，数据规模毕竟很小，呵呵）插排（时间复杂度：平均O(N),最坏O(N2),空间复杂度：O(1)。

）思路：1.开一个结构类型(Pascal里是record，C/C++是struct.)，包含了学号信息，总分成绩，语文成绩。

或者也可以开三个以下标为关联的一维数组，一次表示上述三个参数。

2.读入。

每当读入一行信息，调用过程insert，从前向后依次寻找，直到寻找到某一记录的总分比当前读入总分小，或其总分和当前读入总分相等且语文成绩比当前总分小，则在当前位置插入所读入的数据。

（这个插入可以是将后面的数据依次向后移动一位，也可以是通过链表的方法实现。

）3.输出，从1至5，输出学号和总分即可。

还有一点要注意的是，当总分相等，且语文成绩也相等的时候，就要将学号小的排在前面。

【解题感想】：对于这种送分题，千万不要辜负出卷人的期望，能拿到的分数就一定要拿到。

否则既对不起老师，也对不起出卷人，更对不起自己。

读题目的时候千万要仔细，我同学就是因为这一题的语文处理有点问题而白白掉了3个点。

第二题奖品分组【题目描述】：【解题思路】：这一题乍一看起来，像是动态规划，很多选手被问题的“最”字迷惑了，拿到题目就开始乐呵呵的DP.殊不知，此题如用动归来做，确实是可以实现的，但编程复杂度很高。

下面介绍一种简单易行的方法：简单哈希表+贪心=哈贪（时间复杂度：平均O(N),最坏O(N2),空间复杂度O(1).）思路：1.开一个a[1..200]的数组作为桶，至于类型Integer足够用了，因为即使最坏情况——所有的数据都在一个桶里，也不过是30000个。

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)。

第一题：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。

第十届全国信息学奥林匹克分区联赛（NOIP2004）复赛试题（提高组竞赛用时：3小时）1、津津的储蓄计划(Save.pas／dpr／c／cpp)【问题描述】津津的零花钱一直都是自己管理。

每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20％还给津津。

因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

例如11月初津津手中还有83元，妈妈给了津津300元。

津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。

到了11月月末，津津手中会剩下3元钱。

津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。

有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。

如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。

现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。

如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。

【输入文件】输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。

【输出文件】输出文件save.out包括一行，这一行只包含一个整数。

如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。

【样例输入1】29023028020030017034050908020060【样例输出1】-7【样例输入2】29023028020030017033050908020060【样例输出2】1580【问题描述】在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。