pas联赛什么级别-pas杯是哪个联赛

谁有NOTP2007信息学奥赛复赛普及组pascal的试题

试题如下：

全国信息学奥林匹克联赛(NOIP2007)复赛 普及组

1.奖学金

(scholar.pas/c/cpp)

问题描述

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数:学号、总分) 是:

7 279

5 279

这两行数据的含义是:总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是:

5 279

7 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名学生的学号和总分。

输入输出样例1

scholar.in

6

90 67 80

87 66 91

78 89 91

88 99 77

67 89 64

78 89 98

scholar.out

6 265

4 264

3 258

2 244

1 237

输入输出样例2

scholar. in

8

80 89 89

88 98 78

90 67 80

87 66 91

78 89 91

88 99 77

67 89 64

78 89 98

scholar. out

8 265

2 264

6 264

1 258

5 258

限制

50%的数据满足:各学生的总成绩各不相同 100%的数据满足: 6<=n<=300

2.纪念品分组

(group.pas/c/cpp)

题目描述

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入

输入文件group.in包含n+2行:

第1行包括一个整数w，为每组纪念品价格之和的上眼= 第2行为一个整数n，表示购来的纪念品的总件数G

第3-n+2行每行包含一个正整数Pi (5 <= Pi <= w3)w表示所对应纪念品的价格。

输出

输出文件group.out仅→行，包含一个整数， ep最少的分组数目合

输入输出样例

group.in

100

9

90

20

20

30

50

60

70

80

90

group. out

6

限制

50%的数据满足: 1 <=n <= 15

100%的数据满足: 1 <= n <= 30000， 80 <= W <= 200

3. 守望者的逃离

(escape.pas/c/cpp)

问题描述

恶魔猎手尤迫安野心勃勃.他背叛了暗夜精灵，率深藏在海底的那加企图叛变：守望者在与尤迪安的交锋中遭遇了围杀.被困在一个荒芜的大岛上。为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去，到那时，刀上的所有人都会遇难：守望者的跑步速度，为17m/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在1s内移动60m，不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s，只有处在原地休息状态时才能恢复。

现在已知守望者的魔法初值M，他所在的初始位置与岛的出口之间的距离S，岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。注意:守望者跑步、闪烁或休息活动均以秒(s)为单位。且每次活动的持续时间为整数秒。距离的单位为米(m)。

输入

输入文件escape.in仅一行，包括空格隔开的三个非负整数M，S，T。

输出

输出文件escape.out包含两行:

第1行为字符串"Yes"或"No" (区分大小写)，即守望者是否能逃离荒岛。

第2行包含一个整数，第一行为"Yes" (区分大小写）时表示守望着逃离荒岛的最短时间

第一行为"No" (区分大小写) 时表示守望者能走的最远距离。

输入输出样例1

escape.in

39 200 4

escape.out

No

1

输入输出样例2

escape.in

36 255 10

escape.out

Yes

6

限制

30%的数据满足: 1 <= T<= 10， 1 <=S<= 100

50%的数据满足: 1 <= T <= 1000， 1 <= S <= 10000

100%的数据满足: 1 <= T <= 300000， 0 <= M<=1000 1 <=S <= 10^8

4.Hanoi双塔问题

hanoi.pas/c/cpp

问题描述

给定A,B,C三根足够长的细柱，在A柱上放有2n个中间有空的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的(下图为n=3的情形）。现要将 这些国盘移到C柱上，在移动过程中可放在B柱上暂存。要求:

(1)每次只能移动一个圆盘；

(2) A、B、C三根细柱上的圆盘都要保持上小下大的顺序；

任务:设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。

输入

输入文件hanoi.in为一个正整数n，表示在A柱上放有2n个圆盘。

输出

输出文件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。

输入输出样例1

hanoi.in

1

hanoi.out

2

输入输出样例2

hanoi.in

2

hanoi.out

6

限制

对于50%的数据， 1<=n<=25

对于100% 数据， 1<=n<=200

提示

设法建立An与An-1的递推关系式

因为网上没有解题报告，我就自己写了一个。请参考：

Noip2007解题报告

——by o0rqy0o（就是我啦~~~~~）

第一题：scholar

这个题没什么特别的，主要考察大家对编程的熟练程度。可用二维数组a的a[1,i]记录下语文成绩，再用a[1,i]、a[3,i]记录总分、编号。因为数据最多就300个，所以排序可以用冒泡。在排序时可以将序号也排序，方便控制下标。

我的程序如下：

program scholar(input,output);

var

n,x,y,z,i,j:integer;

a:array[1..300,1..3] of integer;

procedure swap(var a,b:integer);

var

s:integer;

begin

s:=a;

a:=b;

b:=s;

end;

begin

assign(input,'scholar.in');

assign(output,'scholar.out');

reset(input);

rewrite(output);

readln(n);

for i:=1 to n do

begin

readln(x,y,z);

a[i,1]:=i;

a[i,2]:=x;

a[i,3]:=x+y+z;

end;

for i:=1 to n-1 do

for j:=i+1 to n do

if (a[i,3]<a[j,3]) or ((a[i,3]=a[j,3]) and (a[i,2]<a[j,2])) or ((a[i,1]>a[j,1]) and (a[i,3]=a[j,3]) and (a[i,2]=a[j,2])) then

begin

swap(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 do

writeln(a[i,1],' ',a[i,3]);

close(input);

close(output);

end.

第二题：group

这题也不难，有许多人把它想成了DP，其实就是简单的模拟。先排序（也可用冒泡），然后用2个指针控制下标，每次把第一个（头指针对应数据）和最后一个（尾指针对应数据）相加。若比W大则将计数器加1，同时后移头指针；若比小于等于W，则计数器加1，同时将头指针后移1位，尾指针前移1位。最后输出计数器结果。

程序如下：

program group(input,output);

var

a:array[1..30000] of integer;

w,n,i,j,s:integer;

procedure qsort(h,t:integer);

var

p,i,j:integer;

begin

i:=h;

j:=t;

p:=a;

repeat

while (a[j]>p) and (j>i) do j:=j-1;

if j>i then

begin

a:=a[j];

i:=i+1;

while (a<p) and (i<j) do i:=i+1;

if i<j then

begin

a[j]:=a;

j:=j-1;

end;

end;

until i=j;

a:=p;

i:=i+1;

j:=j-1;

if i<t then qsort(i,t);

if j>h then qsort(h,j);

end;

begin

assign(input,'group.in');

assign(output,'group.out');

reset(input);

rewrite(output);

readln(w);

readln(n);

for i:=1 to n do readln(a);

qsort(1,n);

i:=1;

j:=n;

s:=0;

while i<=j do

begin

if i=j then

begin

s:=s+1;

break;

end;

if a+a[j]<=w then

begin

i:=i+1;

j:=j-1;

s:=s+1;

end;

if a+a[j]>w then

begin

s:=s+1;

j:=j-1;

end;

end;

writeln(s);

close(input);

close(output);

end.

第三题：escape

没必要用什么DP，还是用模拟。因为魔法值每次移动就消耗10，每秒补4，而且每移动一次也要耗1秒（有些人这个没注意）。经过比较得知，用魔法移动比跑步要快，所以我们尽量用魔法，先判断“Yes”和“No”，再求相应数据即可。

程序如下：

program escape(input,output);

var

a,b:array[0..10000]of longint;

m,s,t,i,j:longint;

function max(a,b,c:longint):longint;

var

k:longint;

begin

if a>b then k:=a else k:=b;

if k<c then k:=c;

max:=k;

end;

begin

assign(input,'escape.in');

assign(output,'escape.out');

reset(input);

rewrite(output);

readln(m,s,t);

for i:=0 to 10000 do

begin

a[i]:=0;

b[i]:=0;

end;

for i:=1 to t do

begin

for j:=0 to 9 do

begin

b[j]:=max(a[j]+17,a[j+4],0);

if b[j]>=s then

begin

writeln('Yes');

writeln(i);

close(input);

close(output);

halt;

end;

end;

for j:=10 to m do

begin

b[j]:=max(a[j]+17,a[j+4],a[j-10]+60);

if b[j]>=s then

begin

writeln('Yes');

writeln(i);

close(input);

close(output);

halt;

end;

end;

a:=b;

end;

writeln('No');

writeln(a[m]);

close(input);

close(output);

end.

第四题：hanoi

典型的汉诺塔问题。只不过乘了个2。我们不需要推An与An-1的递推关系式，推An与n的关系就行了。汉诺单塔的关系式是：An=2^n-1。这里乘2，得：An=2*(2^n)-1，化简，得：An=2^(n+1)-2。用个高精度就行了。

程序如下：

program hanoi(input,output);

var

n,i,j:integer;

a:array[1..100] of 0..9;

procedure ppp(k:integer);

var

i,j,w,s:integer;

begin

a[1]:=1;

w:=0;

for i:=1 to k do

for j:=1 to 100 do

begin

s:=a[j]*2+w;

a[j]:=s mod 10;

w:=s div 10;

end;

end;

begin

assign(input,'hanoi.in');

assign(output,'hanoi.out');

reset(input);

rewrite(output);

readln(n);

ppp(n+1);

if a[1]>=2 then

a[1]:=a[1]-2

else

begin

a[1]:=a[1]+8;

a[2]:=a[2]-1;

end;

i:=100;

while a[i]=0 do i:=i-1;

for j:=i downto 1 do write(a[j]);

writeln;

close(input);

close(output);

end.

希腊足球的参赛球队

2015–16年希腊足球参赛队伍共有 16 支。 中文名称 英文名称 所在城市 奥林匹亚科斯 Olympiacos FC 比雷埃夫斯 PAOK塞萨洛尼基 P.A.O.K. FC 塞萨洛尼基 AEK雅典 AEK Athens 雅典 特里波利 Asteras Tripoli FC 特里波利 帕纳辛纳科斯 Panathinaikos FC 雅典 萨丁 Skoda Xanthi FC 克桑西 帕尼奥尼奥斯 Panionios GSS 雅典 卡洛尼 Kalloni FC 米蒂利尼 帕斯基安尼纳Pas Giannina阿尔塔普拉坦亚斯　　Platanias FC干尼亚　　莱瓦贾科斯Levadiakos　　伊拉克里斯Iraklis塞萨洛尼基帕纳多里高斯Panaitolikos Agrinio阿格里尼翁阿特罗米托斯PAE Atromitos佩里斯特里维瑞亚Veria FC韦里亚潘斯拉基科斯Panthrakikos亚历山德鲁波利斯

高中信息学联赛经典题型(pascal)

第八届全国青少年信息学奥林匹克联赛（NOIP2002）初赛试题

（提高组 PASCAL语言 二小时完成）

审定：全国青少年信息学奥林匹克竞赛科学委员会

主管：中国科协、教育部

主办：中国计算机学会

承办：江苏省科协青少年科技中心

●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●

一． 选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，共30分）

1． 微型计算机的问世是由于（ ）的出现。

A）中小规模集成电路 B）晶体管电路 C）（超）大规模集成电路 D）电子管电路

2． 中央处理器（CPU）能访问的最大存储器容量取决于（ ）。

A）地址总线 B）数据总线 C）控制总线 D）实际内存容量

3． 十进制书11/128可用二进制数码序列表示为：（ ）。

A）1011/1000000 B）1011/100000000 C）0.001011 D）0.0001011

4． 算式（2047）10 －（3FF）16 ＋（2000）8的结果是（ ）。

A）（2048）10 B）（2049）10 C）（3746）8 D）（1AF7）16

5． 已知x =（0.1011010）2 ，则[ x / 2 ]补 =（ ）2 。

A）0.1011101 B）11110110 C）0.0101101 D）0.100110

6． IPv4地址是由（ ）位二进制数码表示的。

A）16 B）32 C）24 D）8

7． 计算机传染的必要条件是：（ ）。

A）在内存中运行程序 B）对磁盘进行读写操作

C）在内存中运行含有的可执行的程序 D）复制文件

8． 在磁盘上建立子目录有许多优点，下列描述中不属于建立子目录优点的是（ ）。

A）便于文件管理 B）解决根目录中目录项个数有限问题

C）加快文件查找速度 D）节省磁盘使用空间

9． 在使用E-mail前，需要对Outlook进行设置，其中ISP接收电子邮件的服务器称为（ ）服务器。

A）POP3 B）SMTP C）DNS D）FTP

10．多媒体计算机是指（ ）计算机。

A）专供家庭使用的 B）装有CD-ROM的

C）连接在网络上的高级 D）具有处理文字、图形、声音、影像等信息的

11．微型计算机中，（ ）的存取速度最快。

A）高速缓存 B）外存储器 C）寄存器 D）内存储器

12．管理器的目录前图标中增加“+”号，这个符号的意思是（ ）。

A）该目录下的子目录已经展开 B）该目录下还有子目录未展开

C）该目录下没有子目录 D）该目录为空目录

13．在WORD文档编辑中实现图文混合排版时，关于文本框的下列叙述正确的是（ ）。

A）文本框中的图形没有办法和文档中输入文字叠加在一起，只能在文档的不同位置

B）文本框中的图形不可以衬于文档中输入的文字的下方

C）通过文本框，可以实现图形和文档中输入的文字的叠加，也可以实现文字环绕

D）将图形放入文本框后，文档中输入的文字不能环绕图形

14．一个向量第一个元素的存储地址是100，每个元素的长度是2，则地5个元素的地址是（ ）。

A）110 B）108 C）100 D）109

15．已知A = 35H，A /\ 05H \/ A /\ 30H 的结果是：（ ）。

A）30H B）05H C）35H D）53H

16．设有一个含有13个元素的Hash表（0 ~ 12），Hash函数是：H（key）= key % 13，，其中%是求余数运算。用线性探查法解决冲突，则对于序列（2、8、31、20、19、18、53、27），18应放在第（ ）号格中。

A）5 B）9 C）4 D）0

17．按照二叉数的定义，具有3个结点的二叉树有（ ）种。

A）3 B）4 C）5 D）6

18．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。

A）1/2 B）1 C）2 D）4

19．要使1 ．．．8号格字的访问顺序为：8、2、6、5、7、3、1、4，则下图中的空格中应填入（ ）。

1 2 3 4 5 6 7 8

4 6 1 -1 7 3 2

A）6 B）0 C）5 D）3

20．设栈S和队列Q的初始状态为空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，则栈S的容量至少应该为（ ）。

A）2 B）3 C）4 D）5

二．问题求解：（6 + 8 = 14分）

1． 在书架上放有编号为1 ，2 ，．．．，n的n本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：n = 3时：

原来位置为：1 2 3

放回去时只能为：3 1 2 或 2 3 1 这两种

问题：求当n = 5时满足以上条件的放法共有多少种？（不用列出每种放法）

2． 设有一棵k叉树，其中只有度为0和k两种结点，设n 0 ，n k ，分别表示度为0和度为k的结点个数，试求出n 0 和n k之间的关系（n 0 = 数学表达式，数学表达式仅含n k 、k和数字）。

三．阅读程序，写出正确的程序运行结果：（8 + 9 + 9 = 26分）

1． program Gxp1;

var i , n , jr , jw , jb : integer ;

ch1 : char ;

ch : array[1..20] of char ;

begin

readln(n);

for i:=1 to n do read(ch[i]);

jr:=1; jw:=n; jb:=n;

while (jr<=jw) do

begin

if (ch[jw]=’R’)

then begin

ch1:=ch[jr]; ch[jr]:=ch[jw]; ch[jw]:=ch1; jr:=jr+1;

end

else if ch[jw]=’W’

then jw:=jw-1;

else begin

ch1:=ch[jw]; ch[jw]:=ch[jb]; ch[jb]:=ch1; jw:=jw-1; jb:=jb-1;

end

end;

for i:=1 to n do write(ch[1]);

writeln;

end.

输入：10

RBRBWWRBBR

输出：

2． program Gxp2;

var i , j , s ,sp1 : integer ;

p : boolean ;

a : array[1..10] of integer ;

begin

sp1:=1; a[1]:=2; j:=2;

while sp1<10 do

begin

j:=j+1; p:=true;

for i:=2 to j-1 do

if (j mod i=0) then p:=false;

if p then begin

sp1:=sp1+1; a[sp1]:=j;

end;

end;

j:=2; p:=true;

while p do

begin

s:=1;

for i:=1 to j do s:=s*a[i];

s:=s+1;

for i:=2 to s-1 do

if s mod i=0 then p:=false;

j:=j+1;

end;

writeln(s); writeln;

end.

输出：

3． Program Gxp2

Var d1 , d2 , X , Min : real ;

begin

Min:=10000; X:=3;

while X<15 do

begin

d1:=sqrt(9+(X-3)*(X-3)); d2:=sqrt(36+(15-X)*(15-X));

if(d1+d2)<Min then Min:=d1+d2;

X:=x+0.001;

end;

writeln(Min:10:2);

end.

输出：

四．完善程序：（15 + 15 = 30分）

1． 问题描述：工厂在每天的生产中，需要一定数量的零件，同时也可以知道每天生产一个零件的生产单价。在N天的生产中，当天生产的零件可以满足当天的需要，若当天用不完，可以放到下一天去使用，但要收取每个零件的保管费，不同的天收取的费用也不相同。

问题求解：求得一个N天的生产（即N天中每天应生产零件个数），使总的费用最少。

输入：N（天数 N<=29）

每天的需求量（N个整数）

每天生产零件的单价（N个整数）

每天保管零件的单价（N个整数）

输出：每天的生产零件个数（N个整数）

例如：当N=3时，其需要量与费用如下：

第一天 第二天 第三天

需 要 量 25 15 30

生产单价 20 30 32

保管单价 5 10 0

生产的安排可以有许多方案，如下面的三种：

第一天 第二天 第三天 总的费用

25 15 30 25*20+15*30+30*32=1910

40 0 30 40*20+15*5+30*32=1835

70 0 0 70*20+45*5+30*10=1925

程序说明：

b[n]：存放每天的需求量

c[n]：每天生产零件的单价

d[n]：每天保管零件的单价

e[n]：生产

程序：

program exp5;

var

i,j,n,yu,j0,j1,s : integer ;

b,c,d,e : array[0..30] of integer ;

begin

readln(n);

for i:=1 to n do readln(b[i],c[i],d[i]);

for i:=1 to n do e[i]:=0;

①__________:=10000; c[n+2]=0; b[n+1]:=0 j0:=1;

while (j0<=n) do

begin

yu:=c[j0]; j1:=j0; s:=b[j0];

while ②__________ do

begin

③__________ j1:=j1+1; s:=s+b[j1];

end;

④__________ j0:=j1+1;

end;

for i:=1 to n do ⑤__________

readln;

end.

二．问题描述：有n种基本物质（n≤10），分别记为P1，P2，……，Pn，用n种基本物质构造物质，这些物品使用在k个不同地区（k≤20），每个地区对物品提出自己的要求，这些要求用一个n位的数表示：a1a2……a n，其中：

ai = 1表示所需物质中必须有第i种基本物质

= -1表示所需物质中必须不能有第i种基本物质

= 0无所谓

问题求解：当k个不同要求给出之后，给出一种方案，指出哪些物质被使用，哪些物质不被使用。

程序说明：数组 b[1],b[2]……b[n] 表示某种物质

a[1..k,1..n] 记录k个地区对物品的要求，其中：

a[i,j]=1 表示第i个地区对第j种物品是需要的

a[i,j]=0 表示第i个地区对第j种物品是无所谓的

a[i,j]= -1 表示第i个地区对第j种物品是不需要的

程序：

program gxp2;

var

i,j,k,n : integer ;

p : boolean ;

b : array[0..20] of 0..1 ;

a : array[1..20,1..10] of integer ;

begin

readln(n,k);

for i:=1 to k do

begin

for j:=1 to n do read(a[i,j]);

readln;

end;

for i:=0 to n do b[i]:=0;

p:=true;

while ①__________ do

begin

j:=n;

while b[j]=1 do j:=j-1;

②__________

for i:=j+1 to n do b[i]:=0;

③__________

for i:=1 to k do

for j:=1 to n do

if (a[i,j]=1) and (b[j]=0) or ④__________

then p:=true;

end;

if ⑤__________

then writeln(‘找不到！’)

else for i:=1 to n do

if (b[i]=1) then writeln(‘物质’,i,’需要’)

else writeln(‘物质’,i,’不需要’);

end.

NOIP2010（Pascal提高组）复赛

全国信息学奥林匹克联赛（NOIP2010）复赛 提高组

第 1 页 共 7 页

全国信息学奥林匹克联赛（NOIP2010）复赛

提高组（请选手务必仔细阅读本页内容）

一．题目概况

中文题目名称 机器翻译 乌龟棋 关押罪犯 引水入城

英文题目与子目录名 translate tortoise prison flow

可执行文件名 translate tortoise prison flow

输入文件名 translate.in tortoise.in prison.in flow.in

输出文件名 translate.out tortoise.out prison.out flow.out

每个测试点时限 1秒 1秒 1秒 1秒

测试点数目 10 10 10 10

每个测试点分值 10 10 10 10

附加样例文件 有 有 有 有

结果比较方式 全文比较（过滤行末空格及文末回车）

题目类型 传统 传统 传统 传统

二．提交源程序文件名

对于pascal语言 translate.pas tortoise.pas prison.pas flow.pas

对于C语言 translate.c tortoise.c prison.c flow.c

对于C++语言 translate.cpp tortoise.cpp prison.cpp flow.cpp

三．编译命令（不包含任何优化开关）

对于pascal语言 fpc translate.pasfpc tortoise.pasfpc prison.pas fpc flow.pas

对于C语言

gcc -o translate

translate.c -lm

gcc -o tortoise

tortoise.c -lm

gcc -o prison

prison.c -lm

gcc -o flow

flow.c -lm

对于C++语言 g++ -o translate

translate.cpp -lm

g++ -o tortoise

tortoise.cpp -lm

g++ -o prison

prison.cpp -lm

g++ -o flow

flow.cpp -lm

四．运行内存限制内存上限 128M 128M 128M 128M

注意事项：

1、文件名（程序名和输入输出文件名）必须使用英文小写。

2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。

3、全国统一评测时用的机器配置为：CPU P4 3.0GHz，内存1G，上述时限以此配置为准。

各省在自测时可根据具体配置调整时限。

换页

全国信息学奥林匹克联赛（NOIP2010）复赛 提高组

第 2 页 共 7 页

1．机器翻译

(translate.pas/c/cpp)

问题描述

小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。

这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义

来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，

软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中

文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。

设内存中有M个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入

内存前，如果当前内存中已存入的单词数不超过M?1，软件会将新单词存入一个未使用的

内存单元；若内存中已存入M个单词，软件会清空最早进入内存的那个单词，腾出单元来，

存放新单词。

设一篇英语文章的长度为N个单词。给定这篇待译文章，翻译软件需要去外存查找多

少次词典？设在翻译开始前，内存中没有任何单词。

输入

输入文件名为translate.in，输入文件共2行。每行中两个数之间用一个空格隔开。

第一行为两个正整数M和N，代表内存容量和文章的长度。

第二行为N个非负整数，按照文章的顺序，每个数（大小不超过1000）代表一个英文

单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。

输出输出文件translate.out共1行，包含一个整数，为软件需要查词典的次数。

输入输出样例1

translate.in translate.out

3 7

1 2 1 5 4 4 1

5

输入输出样例1说明

整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：

空：内存初始状态为空。

1． 1：查找单词1并调入内存。

2． 1 2：查找单词2并调入内存。

3． 1 2：在内存中找到单词1。

4． 1 2 5：查找单词5并调入内存。

5． 2 5 4：查找单词4并调入内存替代单词1。

6． 2 5 4：在内存中找到单词4。

7． 5 4 1：查找单词1并调入内存替代单词2。

共计查了5次词典。

换页

全国信息学奥林匹克联赛（NOIP2010）复赛 提高组

第 3 页 共 7 页

输入输出样例2

translate.in translate.out

2 10

8 824 11 78 11 78 11 78 8 264

6

数据范围

对于10%的数据有M=1，N≤5。

对于100%的数据有0≤100，0≤1000。

2．乌龟棋

(tortoise.pas/c/cpp)

问题描述

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。

乌龟棋的棋盘是一行N个格子，每个格子上一个分数（非负整数）。棋盘第1格是唯一

的起点，第N格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

……

1 2 3 4 5 ……N

乌龟棋中M张爬行卡片，分成4种不同的类型（M张卡片中不一定包含所有4种类型

的卡片，见样例），每种类型的卡片上分别标有1、2、3、4四个数字之一，表示使用这种卡

片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择

一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。

游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到

该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的

分数总和。

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡

片使用顺序使得最终游戏得分最多。

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到

多少分吗？

输入

输入文件名tortoise.in。输入文件的每行中两个数之间用一个空格隔开。

第1行2个正整数N和M，分别表示棋盘格子数和爬行卡片数。

第2行N个非负整数，a1a2

……aN

，其中ai表示棋盘第i个格子上的分数。第3行M个整数，b1b2

……bM

，表示M张爬行卡片上的数字。

输入数据保证到达终点时刚好用光M张爬行卡片，即N?1=∑

M

ib

1

输出

输出文件名tortoise.out。

换页

全国信息学奥林匹克联赛（NOIP2010）复赛 提高组

第 4 页 共 7 页

输出只有1行，1个整数，表示小明最多能得到的分数。

输入输出样例1

tortoise.in tortoise.out

9 5

6 10 14 2 8 8 18 5 17

1 3 1 2 1

73

输入输出样例1说明

小明使用爬行卡片顺序为1，1，3，1，2，得到的分数为6+10+14+8+18+17=73。注意，

由于起点是1，所以自动获得第1格的分数6。

输入输出样例2

tortoise.in tortoise.out

13 8

4 96 10 64 55 13 94 53 5 24 89 8 30

1 1 1 1 1 2 4 1

455

数据范围

对于30%的数据有1

≤

N

≤

30，1

≤

M

≤

12。

对于50%的数据有1≤N≤120，1

≤

M

≤

50，且4种爬行卡片，每种卡片的张数不会超

过20。

对于100%的数据有1≤N≤350，1≤M≤120，且4种爬行卡片，每种卡片的张数不会

超过40；0≤ai≤100，1≤i≤N；1≤bi≤4，1≤i≤M。输入数据保证N?1=

∑

M

ib

1

3．关押罪犯

(prison.pas/c/cpp)

问题描述

S城现有两座监狱，一共关押着N名罪犯，编号分别为1~N。他们之间的关系自然也极

不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨

气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之

间的积怨越多。如果两名怨气值为c的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并

造成影响力为c的冲突。

每年年末，警察局会将本年内监狱中的所有冲突按影响力从大到小排成一个列表，

然后上报到S城Z那里。公务繁忙的Z只会去看列表中的第一个的影响力，

如果影响很坏，他就会考虑撤换警察局长。

在详细考察了N名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在

两座监狱内重新分配，以求产生的冲突影响力都较小，从而保住自己的乌纱帽。设只

要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那

么，应如何分配罪犯，才能使Z看到的那个冲突的影响力最小？这个最小值是多

换页

全国信息学奥林匹克联赛（NOIP2010）复赛 提高组

第 5 页 共 7 页

少？

输入

输入文件名为prison.in。输入文件的每行中两个数之间用一个空格隔开。

第一行为两个正整数N和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。

接下来的M行每行为三个正整数aj，bj，cj，表示aj号和bj号罪犯之间存在仇恨，其怨

气值为cj。数据保证Nba

jj

≤1，0000000001

0≤

jc

，且每对罪犯组合只出现一

次。

输出

输出文件prison.out共1行，为Z看到的那个冲突的影响力。如果本年内监狱

中未发生任何冲突，请输出0。

输入输出样例

prison.in prison.out

4 6

1 4 2534

2 3 3512

1 2 28351

1 3 6618

2 4 1805

3 4 12884

3512

输入输出样例说明

罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，看到的冲突

影响力是3512（由2号和3号罪犯引发）。其他任何分法都不会比这个分法更优。

数据范围

对于30%的数据有N≤15。

对于70%的数据有N≤2000，M≤50000。

对于100%的数据有N≤20000，M≤100000。

2 1

3 4

1805 6618

2534 3512

12884

28351 2 1

3 4

2534 3512

换页

全国信息学奥林匹克联赛（NOIP2010）复赛 提高组

第 6 页 共 7 页

4.引水入城

(flow.pas/c/cpp)

问题描述

湖泊

沙漠

在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政

区划十分特殊，刚好构成一个N行M列的矩形，如上图所示，其中每个格子都代表一座城

市，每座城市都有一个海拔高度。

为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施

有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的

蓄水池中。因此，只有与湖泊毗邻的第1行的城市可以建造蓄水厂。而输水站的功能则是通

过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是

存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。

由于第N行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利

设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干

旱区中不可能建有水利设施的城市数目。

输入

输入文件名为flow.in。输入文件的每行中两个数之间用一个空格隔开。

输入的第一行是两个正整数N和M，表示矩形的规模。

接下来N行，每行M个正整数，依次代表每座城市的海拔高度。

输出

输出文件名为flow.out。

输出有两行。如果能满足要求，输出的第一行是整数1，第二行是一个整数，代表最少

建造几个蓄水厂；如果不能满足要求，输出的第一行是整数0，第二行是一个整数，代表有

几座干旱区中的城市不可能建有水利设施。

输入输出样例1

flow.in flow.out

2 5

9 1 5 4 3

8 7 6 1 2

11

换页

全国信息学奥林匹克联赛（NOIP2010）复赛 提高组

第 7 页 共 7 页

样例1说明

只需要在海拔为9的那座城市中建造蓄水厂，即可满足要求。

输入输出样例2

flow.in flow.out

3 6

8 4 5 6 4 4

7 3 4 3 3 3

3 2 2 1 1 2

13

样例2说明

湖泊

8 4 5 6 4 4

7 3 4 3 3 3

3 2 2 1 1 2

沙漠

上图中，在3个粗线框出的城市中建造蓄水厂，可以满足要求。以这3个蓄水厂为源头

在干旱区中建造的输水站分别用3种颜色标出。当然，建造方法可能不唯一。

数据范围

本题共有10个测试数据，每个数据的范围如下表所示：

测试数据编号 能否满足要求 N M

1 不能 ≤ 10 ≤ 10

2 不能 ≤ 100 ≤ 100

3 不能 ≤ 500 ≤ 500

4 能 = 1 ≤ 10

5 能 ≤ 10 ≤ 10

6 能 ≤ 100 ≤ 20

7 能 ≤ 100 ≤ 50

8 能 ≤ 100 ≤ 100

9 能 ≤ 200 ≤ 200

10 能 ≤ 500 ≤ 500

对于所有的10个数据，每座城市的海拔高度都不超过10

6

换页