NOIP2007试题+答案+解析(学生版)

[解题思想2 by peterche1990/2wsx2wsx2wsx/czp] 容易求出所有最长路，以及所有最长路上的点。依 次枚举，复杂度是O(KN^3)，其中K是最长路的条数。 该算法易于实现，但是写得不好会TLE1个点，部分 大牛就是这样没有得400的。
[解题思想3] 引理：如果树有多条直径，则每条直径上都存在一个core。 明：首先，如图，如果ABCD和FBCE都是直径的话，则AB=FB， CD=CE（如果不然，可设AB>FB，则FBCE<ABCE，矛盾！）。 这样，ABCE，FBCD也都是直径。我们给BC起个名字叫“公共 段”。题目中说过，公共段必然存在。 考虑ecc的定义，路径的ecc是指所有的点到路径的距离的最大值。 核指的是直径上长度满足约束的ECC最小的子路经。假如根据直径 ABCE算得的core是GHBI，路径GHBI的ecc就是max{BF,AG,DI,EI}, 这个最大值取到了最小。由于DC=EC，也就是说，如果路径和公 共段有交集，公共段的一端上，不包含CORE的直径是可以任选的。 换言之，此时max{BF,AG,ID}有最小值，此时用AB替换BF，发现必 然有BF=AB>AG，ecc=max{BF,ID}。也就是说，如果路径和公共段 有交集，实际计算max时，只需要计算路径在公共段上的部分的 ecc，然后和公共段两端的路径长取一遍MAX就行了。
第四个题目 core [题目转述] 给出一棵无根树，边上有权。称最长路径为直径， 定义路径的偏心距为：点到路径的上的点的最小值 的距离的最大值，给出一个s，找出直径上的某段长 度不超过s的路径，使得偏心距最小。
[解题思想] 算法是严格立方的。中心理念是不要做重复的工作。算法比较笨 拙。考虑到树的性质，对于任意两点，最短路=联通路=最长路。 首先求出多源最短路，该步可以由类似Tarjan的算法，在O(N^2) 内解决。实际上由于下一步的复杂度高达三次方，这里就直接 floyd了。同时可以求出最长路径上都有哪些点。在NOI2007中， 记录最短路的中间结点是很有用的。设mid[a,b]是a,b之间的联通 路上的一个中间点，。 由于这是一棵树，最短路必然唯一。考虑问题的解，构造一个函 数F(k,a,b)为K到ab间的最短路的长度。则 f(k,a,b)=min{d[k,mid[a,b],f[k,a,mid[a,b]],f[k,mid[a,b],b]} 写出了这 个方程，便不难得出一个三次方的算法。 在实际coding的时候，把k放在最外层枚举，这样内层实际上只 用到了f的后面2维，用2维数组记录即可。

2007普及组复赛C语言答案；1．奖学金；(scholar.pas／c／cpp)；【问题描述】；某小学最近得到了一笔赞助，打算拿出其中一部分为学；任务：先根据输入的3门课的成绩计算总分，然后按上；7279；5279；这两行数据的含义是：总分最高的两个同学的学号依次；7279；则按输出错误处理，不能得分；【输入】；输入文件scholar.in包含行n+1行：；2007普及组复赛C语言答案1．奖学金(scholar.pas／c／cpp)【问题描述】某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。

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

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

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

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

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

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

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

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

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

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

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

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

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

2．将边长为 n 的正三角形每边 n 等分，过每个分点分别做另外两边的平行线，得到若干个 正三角形，我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的 一个小三角形，终点是最下面一行位于中间的小三角形。在通路中，只允许由一个小三角 形走到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能 经过两次或两次以上（图中是 n=5 时一条通路的例子）。设 n=10，则该正三角形的不同的 通路的总数为_____________。 四．阅读程序写结果（共 4 题，每题 8 分，共计 32 分） 1. #include <stdio.h> int main() {int i,u[4],v[4],x,y=10; for(i=0;i<=3;i++) scanf("%d", &u[i]); v[0]=(u[0]+u[1]+u[2]+u[3])/7; v[1]=u[0]/((u[1]-u[2])/u[3]); v[2]=u[0]*u[1]/u[2]*u[3]; v[3]=v[0]*v[1]; x=(v[0]+v[1]+2)-u[(v[3]+3)%4]; if(x>10) y+= (v[2]*100-v[3])/(u[u[0]%3]*5); else y+=20+(v[2]*100-v[3])/(u[v[0]%3]*5); printf("%d,%d\n", x,y); return 0; } /*注：本例中，给定的输入数据可以避免分母为 0 或下标越界。 */ 输入：9 3 9 4 输出：_______________ 2．#include <stdio.h> main() {int i,j,m[]={2,3,5,7,13}; long t; for (i=0;i<=4;i++) {t=1; for(j=1;j<m[i];j++) t*=2; printf("%ld ",(t*2-1)*t); } printf("\n"); } 输出:____________________ 3．#include "stdio.h" #define N 7 int fun1(char s[],char a,int n) {int j; j=n; while(a<s[j] && j>0) j--;

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

2007年NOIP初赛试题一、单项选择题（共 10 题，每题 1.5 分，共计 15 分。

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

1. 在以下各项中。

（）不是 CPU 的组成部分。

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

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

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

A. 二—十进制转换码B. 美国信息交换标准代码C. 数字的二进制数码D. 计算机可处理字符的唯一编码5．一个完整的计算机系统应包括（）A.系统硬件和系统软件B. 硬件系统和软件系统C.主机和外部设备D.主机、键盘、显示器和辅助存储器6．IT的含义是（）A．通信技术 B. 信息技术 C. 网络技术 D. 信息学7. LAN的含义是（）。

A. 因特网B. 局域网C. 广域网D. 城域网8. 冗余数据是指可以由以他数据导出的数据，例如，数据库中已存放了学生的数学、语文、和英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看做冗余数据。

冗余数据往往会造成数据的不一致，例如上面4个数据如果都是输入的，由于操作错误使总分不等于三科成绩之和，就会产生矛盾。

下面关于冗余数据的说法中，正确的是（）。

A. 应该在数据库中消除一切冗余数据B.用高级语言编写的数据处理系统，通常比用关系数据库编写的系统更容易消除冗余数据C. 为了提高查询效率，在数据库中可以适当保留一些冗余数据，但更新时要做相容性检验D. 做相容性检验会降低效率，可以不理睬数据库中的冗余数据9. 在下列各软件中，属于 NOIP 竞赛（复赛）推荐使用的语言环境有（）。

A. gccB. g++C. Turbo CD. free pascal10. 以下断电之后将仍能保存数据的有（）。

A. 硬盘B. 高速缓存C. 显存 D. RAM11. 在下列关于计算机语言的说法中，正确的有（）。

Noip2007普及组复赛答案1——奖学金typeaa=recordy,s,w:integer;end;bb=recordf,h:integer;end;var a:array[1..300]of aa;b:array[1..5]of bb;n,i,j,k,t:integer;f:boolean;beginreadln(n);for i:=1 to 5 dowith b[i] do beginf:=0;h:=0;end;for i:=1 to n do beginwith a[i] do read(y,s,w);j:=1;f:=true;t:=a[i].y+a[i].s+a[i].w;while (j<=5)and f do beginif (t>b[j].f)or((t=b[j].f)and(a[i].y>a[b[j].h].y)) then begin for k:=5 downto j+1 do beginb[k].f:=b[k-1].f;b[k].h:=b[k-1].h;end;b[j].f:=t;b[j].h:=i;f:=false;end else if (t=b[j].f)and(a[i].y=a[b[j].h].y) then beginfor k:=5 downto j+2 do beginb[k].f:=b[k-1].f;b[k].h:=b[k-1].h;end;b[j+1].h:=i;b[j+1].f:=t;f:=false;end;j:=j+1;end;for i:=1 to 5 dowith b[i] do writeln(h,' ',f);end.Noip2007普及组复赛答案2——纪念品var a:array[1..30000]of byte;b:array[1..30000]of boolean;w,n,i,zu,k,ma,t:integer;beginreadln(w);readln(n);for i:=1 to 30000 do b[i]:=true;for i:=1 to n do read(a[i]);zu:=0;for i:=1 to n do beginma:=0;t:=0;if b[i] then for k:=i+1 to n doif (a[i]+a[k]<=w)and(a[i]+a[k]>ma)and b[i] and b[k] then begin ma:=a[i]+a[k];t:=k;end;if t<>0 then beginb[i]:=false;b[t]:=false;zu:=zu+1;end;end;for i:=1 to n do if b[i] then zu:=zu+1;writeln(zu);end.Noip2007普及组复赛答案3——守望者的逃离var maxs,mintime,t,m,s,t1,m1,s1:longint;procedure aa(m1,s1,t1:integer);beginif (s1>0)and(t1>0) then begins1:=s1-m1 div 10*60;t1:=t1-m1 div 10;m1:=m1 mod 10;m1:=m1+4;t1:=t1-1;aa(m1,s1,t1);m1:=m1-4;aa(m1,s1,t1);end else beginif maxs<s-s1 then maxs:=s-s1;if (t1>=0)and(mintime>t-t1) then mintime:=t-t1;end;end;beginreadln(m,s,t);maxs:=0;mintime:=2000000;t1:=t;m1:=m;s1:=s;aa(m1,s1,t1);if maxs<s then beginwriteln('No');writeln(maxs);end else beginwriteln('Yes');writeln(mintime);end;end.(pascal语言)Noip2007普及组复赛答案4——Hanoi双塔问题2007年11月21日星期三18:40var a:array[1..62]of integer;i,j,n:integer;f:boolean;beginreadln(n);for i:=2 to 62 do a[i]:=0;a[1]:=2;for i:=2 to n do beginfor j:=1 to 62 doa[j]:=a[j]*2;a[1]:=a[1]+2;for j:=1 to 62 doif a[j]>9 thenbegina[j+1]:=a[j+1]+1;a[j]:=a[j] mod10;end;end;f:=false;for i:=62 downto 1 dobeginif a[i]<>0 thenf:=true;if f then write(a[i]);end;writeln;end.(pascal语言)Noip2007普及组复赛答案4——Hanoi双塔问题2007年11月21日星期三18:40var a:array[1..62]of integer;i,j,n:integer;f:boolean;beginreadln(n);for i:=2 to 62 do a[i]:=0;a[1]:=2;for i:=2 to n do beginfor j:=1 to 62 doa[j]:=a[j]*2;a[1]:=a[1]+2;for j:=1 to 62 doif a[j]>9 thenbegina[j+1]:=a[j+1]+1;a[j]:=a[j] mod10;end;end;f:=false;for i:=62 downto 1 dobeginif a[i]<>0 thenf:=true;if f then write(a[i]);end;writeln;end.问题转述：给出一个一元多项式各项的次数和系数，按照规定的格式要求输出该多项式。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

【输入输出样例l】scholar.in scholar.out690 67 8087 66 9178 89 9188 99 7778 89 98 6 2654 2643 2582 2441 237【输入输出样例2】scholar.in scholar.out880 89 8988 98 7890 67 8087 66 9178 89 9188 99 7767 89 6478 89 98 8 2652 2646 2641 2585 258【限制】50％的数据满足：各学生的总成绩各不相同100％的数据满足：6<=n<=300【试题分析】简单的排序。

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

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

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

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

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

【输入输出样例】count.in8242451002100count.out2 34 25 1100 2【限制】40%的数据满足：1<=n<=100080%的数据满足：1<=n<=50000100%的数据满足：1<=n<=200000，每个数均不超过1500 000 000（1.5*109）【解题思想1】显然，此题可以用排序的方法来解决，根据n的范围，可以看出，O(nlogn)的算法是可以接受的。

【解题思想2】维护一个二叉树，以数的大小作为节点的权值，以数的重复次数作为节点的附加信息。

之后中序遍历即可。

看起来，树内的节点个数应该不到n，所以可能表现不错，其算法复杂度依然为O(nlogn)【实际数据规模】挺小的，而且也没有传说中的卡Qsort的数据，全部都很温柔。

【分析】这个题目实在不能说是一道TG组的好题。

实际上，个人认为题目最大的意义在于：提供了10个测试排序算法的不怎么特别好的数据。

话说回来，此题是送分题，但是送分题送的这么水，考察的也就只有OIers的细心程度了。

在考试的时候，要相信有简单的题目，要相信有直接的算法。

在我的身边就有几个同学因为这个题目与一等失之交臂，这是最可惜的事情。

var a:array[1..200001] of longint;i,j,k,m,n:longint;procedure qsort(s,t:longint);var i,j,mid,temp:longint;begini:=s;j:=t;mid:=a[(s+t) div 2];while i<=j dobeginwhile a[i]<mid do inc(i);while a[j]>mid do dec(j);if i<=j thenbegintemp:=a[i];a[i]:=a[j];a[j]:=temp;inc(i);dec(j);end;end;if i<t then qsort(i,t);if j>s then qsort(s,j);end;beginreadln(n);for i:=1 to n do readln(a[i]);qsort(1,n);a[n+1]:=maxlongint;k:=1;for i:=2 to n+1 doif a[i]<>a[i-1] thenbegin writeln(a[i-1],' ',k); k:=1;endelse k:=k+1;end.2.字符串的展开（expand.pas/c/cpp）【问题描述】在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于“d-h”或者“4-8”的字串，我们就把它当作一种简写，输出时，用连续递增的字母获数字串替代其中的减号，即，将上面两个子串分别输出为“defgh”和“45678”。

2007年程序设计竞赛小学组试题1、输出1~100之间中能被3整除，且被5除余1的所有整数。

(源程序保存名为xone.pas，编译后的文件名为xone.exe)要求：将结果用文件的方式输出在xone.out中。

2、从文件xtwo.in读入a、b两数，c为a与b差的绝对值（c>0），将c打印到文件xtwo.out中。

(源程序保存名为xtwo.pas，编译后的文件名为xtwo.exe)【输入样例1】2 9【输出样例1】7【输入样例2】8 6【输出样例2】23、从文件xthree.in读入字符串str，判断是否为回文，若为回文结果为yes，否则结果no，将结果打印到输出文件文件xthree.out。

（注：回文字符串即为从左向右读与从右向左读是同一个字符串，如abcdcba，abccba。

源程序保存名为xthree.pas，编译后的文件名为xthree.exe）。

【输入样例1】abcdcba【输出样例1】yes【输入样例2】abcde【输出样例2】no4、从文件xfour.in中读入6个整数，将它们从小到大排序后打印到输出文件xfour.out中，并给出排序后每个元素所对应的原来输入的次序。

（源程序保存名为xfour.pas，编译后的文件名为xfou.exe）【输入样例】27、3、2、28、14、39【输出样例】3 214 525 327 128 439 65、甲乙丙丁戊五个人在运动会上分获百米、二百米、跳高、跳远和铅球冠军，有四个人猜测比赛结果：Ａ说：乙获铅球冠军，丁获跳高冠军。

Ｂ说：甲获百米冠军，戊获跳远冠军。

Ｃ说：丙获跳远冠军，丁获二百米冠军。

Ｄ说：乙获跳高冠军，戊获铅球冠军。

其中每个人都只说对一句，说错一句。

求五人各获哪项冠军。

将五个人获得的冠军项目依次打印在输出文件xfive.out中。

（源程序保存名为xfive.pas，编译后的文件名为xfive.exe）6、从文件xsix.in读入字符串str，统计各字母出现的次数，并按字母出现的多少输出到文件xsix.out中（先输出字母出现多的，次数相同的按字母表顺序输出，不出现的字母不输出）。

矩阵取数游戏(game.pas/c/cpp)【问题描述】帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素a ij均为非负整数。

游戏规则如下：1.每次取数时须从每行各取走一个元素，共n个。

m次后取完矩阵所有元素；2.每次取走的各个元素只能是该元素所在行的行首或行尾；3.每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值*2i，其中i表示第i次取数（从1开始编号）；4.游戏结束总得分为m次取数得分之和。

帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

【输入】输入文件game.in包括n+1行：第1行为两个用空格隔开的整数n和m。

第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。

【输出】输出文件game.out仅包含1行，为一个整数，即输入矩阵取数后的最大得分。

【输入输出样例1】【输入输出样例1解释】第1次：第1行取行首元素，第2行取行尾元素，本次得分为1*21+2*21=6第2次：两行均取行首元素，本次得分为2*22+3*22=20第3次：得分为3*23+4*23=56。

总得分为6+20+56=82】【输入输出样例2【输入输出样例【限制】60%的数据满足：1<=n, m<=30, 答案不超过1016100%的数据满足：1<=n, m<=80, 0<=a ij<=1000分析：此题为区间动归，做了田忌赛马后，此题的动态转移一点也不难，f【i，j】表示区间（i，j）所能取得的最大值，取数时必取i或j 所以，转移方程式为f【i，j】=max（f【i+1，j】+a【i】，f【i，j-1】+a【j】）*2边界为f【i，i】=a【i】*2此题要用高精度，可以只写加法，把乘以二看做两个相加。

还有一个高精度比较大小，为了不超时可把进制设为10000或更大。

注意输出的时候要进行补位。

代码如下：program game;typehp=array[0..10] of longint;vara:array[0..200,0..200]of longint;f:array[0..200,0..200]of hp;n,m:longint;procedure init ;beginassign(input,'game.in');assign(output,'game.out');reset(input);rewrite(output);end;procedure prepare;vari,j:longint;beginread(n,m);for i:=1 to n dofor j:=1 to m doread(a[i,j]);end;procedure jia(a,b:hp; var c:hp);vari,len:longint;beginlen:=0;fillchar(c,sizeof(c),0);if a[0]>b[0] then len:=a[0] else len:=b[0];for i:=1 to len dobegininc(c[i],a[i]+b[i]);if c[i]>100000 thenbegindec(c[i],100000);inc(c[i+1]);end;end;if c[len+1]>0 then inc(len);c[0]:=len;end;procedure outit;beginclose(input) ;close(output);end;{procedure cheng(a:hp; b:longint; var c:hp); vari,len:longint;beginfillchar(c,sizeof(c),0);len:=a[0];for i:=1 to len do begininc(c[i],a[i]*b);inc(c[i+1],(a[i]*b) div 100000);c[i]:=c[i] mod 100000;end;inc(len);while (c[len]>=100000) do beginc[len+1]:=c[len] div 100000;c[len]:=c[len] mod 100000;inc(len);end;while (len>1) and (c[len]=0) do dec(len);c[0]:=len;end; } ////////考试时写的高精度乘法，后来发现可以不用，正确性经过了验证procedure bi(x,y:hp; var z:hp);vari,j,len:longint; ///////////高精度大小比较（有点冗长）beginif x[0]>y[0] thenbeginfor i:=0 to x[0] dobeginz[i]:=x[i];end;exit;end;if x[0]<y[0] thenbeginfor i:=0 to y[0] dobeginz[i]:=y[i];end;exit;end;len:=x[0];for i:=len downto 1 dobeginif x[i]>y[i] thenbeginfor j:=0 to x[0] dobeginz[j]:=x[j];end;exit;end;if x[i]<y[i] thenbeginfor j:=0 to y[0] dobeginz[j]:=y[j];end;exit;end;end;if x[i]<y[i] thenbeginfor j:=0 to y[0] dobeginz[j]:=y[j];end;exit;end;for j:=0 to y[0] dobeginz[j]:=y[j];end;end;procedure main;vari,j,k,l,p:longint;x,y,z,sum:hp;beginfillchar(sum,sizeof(sum),0); for k:=1 to n dobeginfillchar(f,sizeof(f),0);for i:=1 to m dobeginf[i,i,1]:=a[k,i]*2;f[i,i,0]:=1;end;for l:=1 to m-1 dofor i:=1 to m-l dobeginfillchar(y,sizeof(y),0);fillchar(x,sizeof(x),0);fillchar(z,sizeof(z),0);j:=i+l;x[0]:= 1;x[1]:=a[k,j];y[0]:=1;y[1]:=a[k,i];jia(f[i,j-1],x,x);jia(f[i+1,j],y,y);bi(x,y,z);jia(z,z,f[i,j]);end;jia(sum,f[1,m],sum);end;write(sum[sum[0]]);for i:=sum[0]-1 downto 1 dobeginp:=10000;while sum[i]<p dobegin write(0); p:=p div 10; end;write(sum[i]);end;end;begininit;prepare;main;outit;end.。

全国信息学奥林匹克联赛（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行：第1行是整数n，表示自然数的个数。

第2~n+1行每行一个自然数。

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

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

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

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

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

Noip2007解题报告第一题：scholar这个题没什么特别的，主要考察大家对编程的熟练程度。

可用二维数组a的a[1,i]记录下语文成绩，再用a[1,i]、a[3,i]记录总分、编号。

因为数据最多就300个，所以排序可以用冒泡。

在排序时可以将序号也排序，方便控制下标。

我的程序如下：program scholar(input,output);varn,x,y,z,i,j:integer;a:array[1..300,1..3] of integer;procedure swap(var a,b:integer);vars:integer;begins:=a;a:=b;b:=s;end;beginassign(input,'scholar.in');assign(output,'scholar.out');reset(input);rewrite(output);readln(n);for i:=1 to n dobeginreadln(x,y,z);a[i,1]:=i;a[i,2]:=x;a[i,3]:=x+y+z;end;for i:=1 to n-1 dofor j:=i+1 to n doif (a[i,3]a[j,1]) and (a[i,3]=a[j,3]) and (a[i,2]=a[j,2])) thenbeginswap(a[i,1],a[j,1]);swap(a[i,2],a[j,2]);swap(a[i,3],a[j,3]);end;for i:=1 to 5 dowriteln(a[i,1],' ',a[i,3]);close(input);close(output);end.第二题：group这题也不难，有许多人把它想成了DP，其实就是简单的模拟。

先排序（也可用冒泡），然后用2个指针控制下标，每次把第一个（头指针对应数据）和最后一个（尾指针对应数据）相加。

2007年全国高中数学联赛考试时间：上午8：00—9：40）一、选择题（本题满分36分，每小题6分）1. 如图，在正四棱锥P −ABCD 中，∠APC =60°，则二面角A −PB −C 的平面角的余弦值为（ ） A. 71 B. 71- C. 21 D. 21-5. 设圆O 1和圆O 2是两个定圆，动圆P 与这两个定圆都相切，则圆P 的圆心轨迹不可能是（ ）6. 已知A 与B 是集合{1，2，3，…，100}的两个子集，满足：A 与B 的元素个数相同，且为A ∩B 空集。

若n ∈A 时总有2n +2∈B ，则集合A ∪B 的元素个数最多为（ ）A. 62B. 66C. 68D. 74二、填空题（本题满分54分，每小题9分）7. 在平面直角坐标系内，有四个定点A (−3，0)，B (1，−1)，C (0，3)，D (−1，3)及一个动点P ，则|PA |+|PB |+|PC |+|PD |的最小值为__________。

8. 在△ABC 和△AEF 中，B 是EF 的中点，AB =EF =1，BC =6，33=CA ，若2=⋅+⋅AF AC AE AB ，则EF 与BC 的夹角的余弦值等于________。

9. 已知正方体ABCD −A 1B 1C 1D 1的棱长为1，以顶点A 为球心，332为半径作一个球，则球面与正方体的表面相交所得到的曲线的长等于__________。

10. 已知等差数列{a n }的公差d 不为0，等比数列{b n }的公比q 是小于1的正有理数。

若a 1=d ，b 1=d 2，且321232221b b b a a a ++++是正整数，则q 等于________。

11. 已知函数)4541(2)cos()sin()(≤≤+-=x x πx πx x f ，则f (x )的最小值为________。

12. 将2个a 和2个b 共4个字母填在如图所示的16个小方格内，每个小方格内至多填1个字母，若使相同字母既不同行也不同列，则不同的填法共有________种（用数字作答）。

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

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

）1．在以下各项中，（）不是CPU的组成部分。

A．控制器B．运算器C．寄存器D．主板2．在关系数据库中，存放在数据库中的数据的逻辑结构以（）为主。

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

A．Byte B．KB C．UB D．TB4．ASCII码的含义是（）。

A．二→十进制转换码 B．美国信息交换标准代码C．数字的二进制编码D．计算机可处理字符的唯一编码5．一个完整的计算机系统应包括（）。

A．系统硬件和系统软件B．硬件系统和软件系统C．主机和外部设备D．主机、键盘、显示器和辅助存储器6．IT的含义是（）。

A．通信技术B．信息技术C．网络技术D．信息学7．LAN的含义是（）。

A．因特网B．局域网C．广域网D．城域网8．冗余数据是指可以由其它数据导出的数据。

例如，数据库中已存放了学生的数学、语文和英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看作冗余数据。

冗余数据往往会造成数据的不一致。

例如，上面4个数据如果都是输入的，由于操作错误使总分不等于三科成绩之和，就会产生矛盾。

下面关于冗余数据的说法中，正确的是（）。

A．应该在数据库中消除一切冗余数据B．用高级语言编写的数据处理系统，通常比用关系数据库编写的系统更容易消除冗余数据C．为了提高查询效率，在数据库中可以保留一些冗余数据，但更新时要做相容性检验D．做相容性检验会降低效率，可以不理睬数据库中的冗余数据9．在下列各软件，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。

A．gcc B．g++ C．Turbo C D．Free Pascal10．以下断电后仍能保存数据的有（）。

│ 21
二、问题解答
1、（子集划分）将 n 个数{1，2，…，n}划分成 r 个子集。每个数都恰好属于 一个子集，任何两个不同的子集没有共同的数，也没有空集。将不同划分方法 的总数记为 S(n,r)。例如，S(4,2)=7，这 7 种不同的划分方法依次 为{(1),(234)}, {(2),(134)}, {(3),(124)}, {(4),(123)}, {(12),(34)}, {(13),(24)}, {(14),(23)}。当 n=6，r=3 时，S(6,3)=_________ 。 （提示：先固定一个数，对于其余的 5 个数考虑 S(5,3)与 S(5,2)，再分这两种 情况对原固定的数进行分析）。
一、选择题
11. 在下列关于计算机语言的说法中，正确的有（ ）。 A. 高级语言比汇编语言更高级，是因为它的程序的运行效率更高 B. 随着 Pascal、C 等高级语言的出现，机器语言和汇编语言已经退 出了历史舞台 C. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种 计算机上
D. C 是一种面向对象的高级计算机语言
│8
一、选择题
8. 冗余数据是指可以由其他数据导出的数据，例如，数据库中已存放了学生的数学、语文和 英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看作冗余数据。冗余数据往往 会造成数据的不一致，例如，上面 4 个数据如果都是输入的，由于操作错误使总分不等于三 科成绩之和，就会产生矛盾。下面关于冗余数据的说法中，正确的是（ ）。 A. 应该在数据库中消除一切冗余数据 B. 用高级语言编写的数据处理系统，通常比用关系数据库编写的系统更容易消除冗余数据 C. 为了提高查询效率，在数据库中可以适当保留一些冗余数据，但更新时要做相容性检验 D. 做相容性检验会降低效率，可以不理睬数据库中的冗余数据

NOIP2007 初赛试题（提高组C)2008-08-03 15:09分类：默认分类字号：大中小信息学奥赛试题NOIP2007 初赛试题（提高组C）© 中国计算机学会20071第十三届全国青少年信息学奥林匹克联赛初赛试题（提高组C 语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共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．在C 语言中，表达式23|2^5 的值是（）A. 23B. 1C.18D.32E.246．在C 语言中，判断a 等于0 或b 等于0 或c 等于0 的正确的条件表达式是（）A. !((a!=0)||(b!=0)||(c!=0))B. !((a!=0)&&(b!=0)&&(c!=0))C. !(a==0&&b==0)||(c!=0)D. (a=0)&&(b=0)&&(c=0)E. !((a=0)||(b=0)||(c=0))7．地面上有标号为A、B、C 的3 根细柱，在A 柱上放有10 个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3，……，将A 柱上的部分盘子经过B 柱移入C 柱，也可以在B 柱上暂存。

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

y+= (q[1]*100-q[3])/(p[p[4]%3]*5); else
y+=20+(q[2]*100-q[3])/(p[p[4]%3]*5); printf("%d,%d\n", x,y); return 0;
© 中国计算机学会 2007
4
NOIP2007 初赛试题（提高组 C）
} /*注：本例中，给定的输入数据可以避免分母为 0 或数组元素下标越界。 */ 输入：6 6 5 5 3 输出：_______________
NOIP2007 初赛试题（提高组 C）
第十三届全国青少年信息学奥林匹克联赛初赛试题
（ 提高组 C 语言 二小时完成 ）
●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●●
一、 单项选择题 （共 10 题，每题 1.5 分，共计 15 分。每题有且仅有一个正确答案）。
1. 在以下各项中，（ ）不是 CPU 的组成部分。
B．有些编译系统可以检测出死循环 C. 死循环属于语法错误，既然编译系统能检查各种语法错误，当然也应该能检查出死循环 D. 死循环与多进程中出现的“死锁”差不多，而死锁是可以检测的，因而，死循环也是可以检测 的 E. 对于死循环，只能等到发生时做现场处理，没有什么更积极的手段
二、 不定项选择题 （共 10 题，每题 1.5 分，共计 15 分。每题正确答案的个数大于或等于 1。多选 或少选均不得分）。
但这一点还没有得到理论上的证实，也没有被否定 D. 一个问题如果是NP类的，与C有相同的结论
20. 近20年来，许多计算机专家都大力推崇递归算法，认为它是解决较复杂问题的强有力的工具。在下 列关于递归算法的说法中，正确的是（ ）。
© 中国计算机学会 2007