信息学奥赛历年试题及答案_21世纪教育网-二一教育

资源简介

NOI’95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛
分区联赛复赛测试数据（初中组）
正确算式如下：8分
809 ① 打印格式占4%
9709　　　　 ② 算式不对不给分
96
109
108
1
本题18分（4%+6%+8%）
① 输入N=1 （4%） ② 输入N=3 （6%）
结果：结果：
7 8 1
6 9 2
5 4 3
③ 输入N=10（8%）
结果： 28 29 30 31 32 33 34 35 36 1
27 58 59 60 61 62 63 64 37 2
26 57 80 81 82 83 84 65 38 3
25 56 79 94 95 96 85 66 39 4
24 55 78 93 100 97 86 67 40 5
23 54 77 92 99 98 87 68 41 6
22 53 76 91 90 89 88 69 42 7
21 52 75 74 73 72 71 70 43 8
20 51 50 49 48 47 46 45 44 9
18 17 16 15 14 13 12 11 10
本题14分
输出结果为： A类=538 B类=462
本题30分（15%+15%）
由数组求编码：共15分（5%+5%+5%）
a 输入：N=6 A=（0，1，2，3，4，5）
输出： B=（0，1，2，3，4，5）
b 输入：N=6 A=（5，4，3，2，1，0）
输出： B=（0，0，0，0，0，0）
c 输入：N=8 A=（1，0，3，2，5，4，7，6）
输出： B=（0，0，2，2，4，4，6，6）
由编码求原数组：共15分（5%+5%+5%）
a 输入：N=5 B=（0，0，0，0，0）
输出： A=（4，3，2，1，0）
b 输入：N=10 B=（0，1，2，3，4，5，6，7，8，9）
输出： A=（0，1，2，3，4，5，6，7，8，9）
c 输入：N=7 B=（0，0，0，0，4，5，6）
输出： A=（3，2，1，0，4，5，6）
本题共30分（10%+10%+10%）
数据输入： N=6
P1=R N1=1
Q
数据输入：N=6
P1=R N1=2
P2=Y N2=1
Q
数据输入：N=12
P1=R N1= 3
P2=B N2=2
P3=Y N3=1
Q
12）
R
R
R
R
R
R
排列方案：
排列总数=6
R R Y
R R Y
R R Y
R R Y
R R Y
R R Y
排列方案：
排列总数=12
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
R R R B B Y
排列方案：
排列总数：
105×2=210
1
3第十一届全国青少年信息学奥林匹克联赛初赛试题
（普及组pascal&C 语言二小时完成）
●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●
由OIFans（www.）整理 ( http: / / www. )
一．选择一个正确答案代码（A/B/C/D/E）,填入每题的括号内(每题1.5分, 共30分)
1. 在字符串“ababacbabcbdecced”中出现次数最多的字母出现了（）次。
A. 6 B. 5 C. 4 D. 3 E. 2
2. 设全集I = {a, b, c, d, e, f, g, h}，集合A = {a, b, c, d, e, f}，B = {c, d, e}，C = {a, d}，那
么集合C B A ~ 为（）。
A. {c, e} B. {d, e} C. {e} D. {c, d, e} E. {d, f}
3. 和十进制数23的值相等的二进制数是（）。
A. 10110 B. 11011 C. 11011 D. 10111 E. 10011
4. 完全二叉树的结点个数为11，则它的叶结点个数为（）。
A. 4 B.3 C.5 D. 2 E. 6
5. 平面上有五个点A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以这五点作为完全图G 的顶点，
每两点之间的直线距离是图G 中对应边的权值。以下哪条边不是图G 的最小生成树中
的边（）。
A. AD B. BD C. CD D. DE E. EA
6. Intel的首颗16 位处理器是（）。
A. 8088 B. 80386 C. 80486 D. 8086 E. Pentium
7. 处理器A 每秒处理的指令数是处理器B 的2 倍。某一特定程序P 分别编译为处理器A
和处理器B 的指令，编译结果处理器A 的指令数是处理器B 的4 倍。已知程序P 在处
理器A 上执行需要1 个小时，那么在输入相同的情况下，程序P 在处理器B 上执行需
要（）小时。
A. 4 B. 2 C. 1 D. 1 / 2 E. 1 / 4
8. 以下哪个不是计算机的输出设备（）。
A. 音箱B. 显示器C. 打印机D. 扫描仪E. 绘图仪
9. 下列活动中不属于信息学奥赛的系列活动的是（）。
A. NOIP B. NOI C. IOI D. 冬令营E. 程序员等级考试
10. 以下断电之后仍能保存数据的是（）。
A. 硬盘B. 寄存器C. 显存D. 内存E. 高速缓存
11. 以下哪个软件不是即时通信软件（）。
A. 网易泡泡B. MSN Messenger C. Google Talk D. 3DS Max E. QQ
12. 下列关于高级语言的说法错误的是（）。
A. Fortran是历史上的第一个面向科学计算的高级语言
B. Pascal和C都是编译执行的高级语言
C. C++是历史上的第一个支持面向对象的语言
D. 编译器将高级语言程序转变为目标代码
E. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上
13. 下列设备不具有计算功能的是（）。
A. 笔记本电脑B. 掌上电脑C. 智能手机
D. 电子计算器E. 液晶显示器
14. 常见的邮件传输服务器使用（）协议接收邮件。
A. HTTP B. SMTP C. TCP D. FTP E. POP3
15. 下列浏览器中，由微软公司开发的浏览器是（）。
A. Internet Explore B. Netscape C. Opera D. Firefox E. Mozilla
16. 一位艺术史学家有20000 幅真彩色图像，每幅图像约占3M空间。如果将这些图像以位
图形式保存在CD 光盘上（一张CD 光盘的容量按600M计算），大约需要（）张CD
光盘。
A. 1 B. 10 C. 100 D. 1000 E. 10000
17. 设A = true，B = false，C = false，D = true，以下逻辑运算表达式值为真的是（）。
A. (A B ∧ )∨(C D ∧ ) B. ((A B ∧ ) C ∨ ) D ∧ C. A∧((B C ∨ ) D ∧ )
D. (A∧(B C ∨ )) D ∨ E. (A B ∨ )∧(C D ∧ )
18. (3725)8 + (B)16的运算结果是（）。
A. (3736)8 B. (2016)10 C. (1111110000)2 D. (3006)10 E. (7B0)16
19. 二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D 是G 的
父结点，F 是I 的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知F
的父结点是（）。
A. 无法确定B. B C. C D. D E. E
20. 设栈S的初始状态为空，元素a, b, c, d, e, f, g依次入栈，以下出栈序列不可能出现的是
（）。
A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, d, c, b, f, g
D. d, c, f, e, b, a, g E. g, e, f, d, c, b, a
二．问题求解（请在空格处填上答案，每空5分，共10分）
1. 将数组{32, 74, 25, 53, 28, 43, 86, 47}中的元素按从小到大的顺序排列，每次可以交换任
意两个元素，最少需要交换次。
2. 有3 个课外小组：物理组，化学组和生物组。今有张、王、李、赵、陈5 名同学，已知
张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员。如果要在
3 个小组中分别选出3 位组长，一位同学最多只能担任一个小组的组长，共有种
选择方案。
三．阅读程序（共4题，每题8分，共计32 分）
==================PASCAL语言==================
1． var
a, b : integer;
begin
read(a);
b := (a * (a * a)) + 1;
if b mod 3 = 0 then b := b div 3;
if b mod 5 = 0 then b := b div 5;
if b mod 7 = 0 then b := b div 7;
if b mod 9 = 0 then b := b div 9;
if b mod 11 = 0 then b := b div 11;
if b mod 13 = 0 then b := b div 13;
if b mod 15 = 0 then b := b div 15;
writeln((100 * a - b) div 2);
end.
输入：10
输出：
2. var
str : string;
i : integer;
begin
str := 'Today-is-terrible!';
for i := 7 to 11 do
if str = '-' then str[i - 1] := 'x';
for i := 13 downto 1 do
if str = 't' then str[i + 1] := 'e';
writeln(str);
end.
输出：
3． var
a, b, c, p, q : integer;
r : array[0..2] of integer;
begin
read(a, b, c);
p := a div b div c;
q := b - c + a + p;
r[0] := a * p div q * q;
r[1] := r[0] * (r[0] - 300);
if (3 * q - p mod 3 <= r[0]) and (r[2] = r[2]) then
r[1] := r[r[0] div p mod 2]
else r[1] := q mod p;
writeln(r[0] - r[1]);
end.
输入：100 7 3
输出：
4． var
str : string;
len, i, j : integer;
nchr : array [0..25] of integer;
mmin : char;
begin
mmin := 'z';
readln(str); len := length(str);
i := len;
while i >= 2 do begin
if str[i - 1] < str then break; dec(i);
end;
if i = 1 then begin
writeln('No result!'); exit;
end;
for j := 1 to i - 2 do write(str[j]);
fillchar(nchr, sizeof(nchr), 0);
for j := i to len do begin
if (str[j] > str[i - 1]) and (str[j] < mmin) then
mmin := str[j];
inc(nchr[ord(str[j]) - ord('a')]);
end;
dec(nchr[ord(mmin) - ord('a')]);
inc(nchr[ord(str[i - 1]) - ord('a')]);
write(mmin);
for i := 0 to 25 do
for j := 1 to nchr do
write(chr(i + ord('a')));
writeln;
end.
输入：zzyzcccbbbaaa
输出：
==================C语言==================
1． #include
int main() {
int a, b;
scanf(“%d”, &a);
b = (a * (a * a)) + 1;
if (b%3 == 0) b = b / 3;
if (b%5 == 0) b = b / 5;
if (b%7 == 0) b = b / 7;
if (b%9 == 0) b = b / 9;
if (b%11 == 0) b = b / 11;
if (b%13 == 0) b = b / 13;
if (b%15 == 0) b = b / 15;
printf(“%d \n”, (100 * a – b) / 2);
return 0;
}
输入：10
输出：
2． #include
int main() {
char str[20] = “Today-is-terrible!”;
int i;
for (i = 6; i <= 10; i++)
if (str == ‘-‘) str[i – 1] = ‘x‘;
for (i = 12; i >= 0; i--)
if (str == ‘t’) str[i + 1] = ‘e’;
printf(“%s\n”, str);
return 0;
}
输出：
3． #include
int main() {
int a, b, c, p, q, r[3];
scanf(“%d%d%d”, &a, &b, &c);
p = a / b / c;
q = b – c + a + p;
r[0] = a * p / q * q;
r[1] = r[0] * (r[0] – 300);
if (3 * q – p % 3 <= r[0] && r[2] == r[2])
r[1] = r[r[0] / p % 2];
else
r[1] = q % p;
printf(“%d\n”, r[0] – r[1]);
return 0;
}
输入：100 7 3
输出：
4． #include
#include
int main(){
char str[60];
int len, i, j, chr[26];
char mmin = 'z';
scanf("%s", str);
len = strlen(str);
for (i = len - 1; i >= 1; i--)
if (str[i - 1] < str) break;
if (i == 0) {
printf("No result!\n"); return 0;
}
for (j = 0; j < i - 1; j++) putchar(str[j]);
memset(chr, 0, sizeof(chr));
for (j = i; j < len; j++) {
if (str[j] > str[i - 1] && str[j] < mmin)
mmin = str[j];
chr[str[j] - 'a']++;
}
chr[mmin - 'a']--;
chr[str[i - 1] - 'a']++;
putchar(mmin);
for(i = 0; i < 26; i++)
for(j = 0; j < chr; j++)
putchar(i + 'a');
putchar('\n');
return 0;
}
输入：zzyzcccbbbaaa
输出：
　
四．完善程序(前4空，每空2分，后5空，每空4分，共28分)
==================PASCAL语言==================
1．判断质数
题目描述:
给出一个正整数，判断这个数是否是质数。
输入:
一个正整数n(1 ≤ n ≤ 10000)。
输出:
如果n是质数，输出”YES”；否则，输出”NO”。
输入样例:
10
输出样例:
NO
程序：
var
① : integer;
begin
read(n);
if n = 2 then writeln( ② )
else if ( ③ ) or (n mod 2 = 0) then writeln('NO')
else begin
i := 3;
while i * i <= n do begin
if ④ then begin
writeln('NO'); exit;
end;
i := i + 2;
end;
writeln('YES');
end;
end.
2．木材加工
题目描述:
木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有
剩余），需要得到的小段的数目是给定的。当然，我们希望得到的小段越长越好，你的任务
是计算能够得到的小段木头的最大长度。木头长度的单位是cm。原木的长度都是正整数，
我们要求切割得到的小段木头的长度也是正整数。
输入:
第一行是两个正整数N和K(1 ≤ N ≤ 10000，1 ≤ K ≤ 10000)，N是原木的数目，
K是需要得到的小段的数目。
接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。
输出:
输出能够切割得到的小段的最大长度。如果连1cm长的小段都切不出来，输出”0”。
输入样例:
3 7
232
124
456
输出样例:
114
程序：
var
n, k : integer;
len : array [1..10000] of integer;
i, left, right, mid : integer;
function isok(t : integer) : boolean;
var
num, i : integer;
begin
num := 0;
for i := 1 to n do begin
if num >= k then break;
num := ① ;
end;
if ② then isok := true
else isok := false;
end;
begin
readln(n, k);
right := 0;
for i := 1 to n do begin
readln(len);
if right < len then right := len;
end;
inc(right); ③ ;
while ④ < right do begin
mid := (left + right) div 2;
if ⑤ then right := mid
else left := mid;
end;
writeln(left);
end.
==================C语言==================
1．判断质数
题目描述:
给出一个正整数，判断这个数是否是质数。
输入:
一个正整数n(1 ≤ n ≤ 10000)。
输出:
如果n是质数，输出”YES”；否则，输出”NO”。
输入样例:
10
输出样例:
NO
程序：
#include
int main() {
int ① ;
scanf("%d", &n);
if (n == 2) puts( ② );
else if ( ③ || n % 2 == 0) puts("NO");
else {
i = 3;
while (i * i <= n) {
if ( ④ ) {
puts("NO"); return 0;
}
i = i + 2;
}
puts("YES");
}
return 0;
}
2．木材加工
题目描述:
木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小
段的数目是给定的。当然，我们希望得到的小段越长越好，你的任务是计算能够得到的小段
木头的最大长度。
木头长度的单位是cm。原木的长度都是正整数，我们要求切割得到的小段木头的长度
也是正整数。
输入:
第一行是两个正整数N和K(1 ≤ N ≤ 10000，1 ≤ K ≤ 10000)，N是原木的数目，
K是需要得到的小段的数目。
接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。
输出:
输出能够切割得到的小段的最大长度。如果连1cm长的小段都切不出来，输出”0”。
输入样例:
3 7
232
124
456
输出样例:
114
程序：
#include
int n, k, len[10000];
int isok(int t) {
int num = 0, i;
for (i = 0; i < n; i++) {
if (num >= k) break;
num = ① ;
}
if ( ② ) return 1;
else return 0;
}
int main() {
int i, left, right, mid;
scanf("%d%d", &n, &k);
right = 0;
for (i = 0; i < n; i++) {
scanf("%d", &(len));
if (right < len) right = len;
}
right++;
③ ;
while ( ④ < right) {
mid = (left + right) / 2;
if ( ⑤ ) right = mid;
else left = mid;
}
printf ("%d\n", left);
return 0;
第十一届全国青少年信息学奥林匹克联赛初赛试题普及组(P&C)参考答案
由OIFans（www.）整理 ( http: / / www. )
一. 选择一个正确答案代码（A/B/C/D/E）,填入每题的括号内 (每题1.5分,多选无分, 共30 分)题号 1 2 ３ 4 5 6 7 8 9 10选择BA DED D D D E A题号 11 12 13 14 15 16 17 18 19 20选择 D C E E A C D B C E　二．问题解答（每题5分，共10分） 1. 答： 5 2. 答： 11 三. 阅读程序，并写出程序的正确运行结果：（每题8分，共32分）(1) 程序的运行结果是: 499(2) 程序的运行结果是: Today-ix-terrible!(3) 程序的运行结果是: -7452(4) 程序的运行结果是: zzzaaabbbcccy 四.根据题意, 将程序补充完整 (前4空，每空2分，后5空，每空4分，共28分) pascal 语言＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 1. ① n, i （或者 i, n） ② 'YES' ③ n = 1 (或者 n – 1 = 0) 　　　 ④ n mod i = 0 　　　　　　　　　 2. ① num + len[i] div t 　 ② 　 num >= k　　　　　 ③ 　 left := 0　④ left + 1　⑤ not isok(mid) （或者 isok(mid) = false）　　　 C 语言＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 1. ① n, i （或者 i, n） ② 'YES' ③ n == 1 (或者 n – 1 == 0) 　　　 ④ n % i == 0 （或者 !n % i）　　　　　　　　　 2. ① num + len[i] / t 　 ② 　 num >= k 　　　　　 ③ 　 left = 0 　 ④ left + 1 　　 ⑤ !isok(mid) （或者 isok(mid) == 0）NOI’95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛
分区联赛复赛试题（高中组）
（上机编程，完成时间：210分钟）
编码问题：
设有一个数组A:ARRAY[0..N-1] OF INTEGER；
数组中存放的元素为0～N-1之间的整数，且A[i]≠A[j]（当i≠j时）。
例如：N=6时，有： A=（4，3，0，5，1，2）
此时，数组A的编码定义如下：
A[0]的编码为0；
A[i]的编码为：在A[0]，A[1]，…，A[i-1]中比A[i]的值小的个数（i=1，2，…，N-1）
∴ 上面数组A的编码为： B=（0，0，0，3，1，2）
程序要求解决以下问题：
给出数组A后，求出其编码。
给出数组A的编码后，求出A中的原数据。
灯的排列问题：
设在一排上有N个格子（N≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为N1，N2，……Nk（k表示不同颜色灯的个数）。
放灯时要遵守下列规则：
同一种颜色的灯不能分开；
不同颜色的灯之间至少要有一个空位置。
例如：N=8（格子数）
R=2（红灯数）
B=3（蓝灯数）
放置的方法有：
R-B顺序
R R B B B
R R B B B
R R B B B
R R B B B
R R B B B
R R B B B
B-R顺序
B B B R R
B B B R R
B B B R R
B B B R R
B B B R R
B B B R R
放置的总数为12种。
数据输入的方式为：
N
P1（颜色，为一个字母） N1（灯的数量）
P2 N2
……
Q（结束标记，Q本身不是灯的颜色）
程序要求：求出一种顺序的排列方案及排列总数。
<3> 设有一个四层的积木块，1～4层积木块的数量依次为：5，6，7，8
如下图所示放置：
8 15 8 5 16 9 14
2 3 4 1 4 3 2 6
其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计算出来的。
计算的方法是：第三层的某个数据A是由第四层相邻的两个数据B，C经过某种计算后产生的：
A
B C
计算所用到的计算符为：+，-，，且无优先级之分（自左向右计算），运算符最多为2个。
如：3+45=35 54+3=23
可以看出，上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的：
A=BC+B
也就是：8=23+2，15=34+3，……14=26+2
程序要求：
给出第四层与第三层的数据后，将第一、二层的每块积木标上相应的数据，并输出整个完整的积木图及计算公式。
输入数据不存在出错的情况，同时也不会超过整数的范围。
计算时可允许出现以下情况：
A=B （即可理解为运算符的个数为零）
A=BB +B （即全部由B产生）
1
1第二届全国青少年信息学（计算机）奥林匹克分区联赛
复赛参考答案（高中组）
赛区学校
题号输入输出实际输出得分
1．1 n=1 <1>1-2
1．2 n=2 <1>1-2，3-4<2>1-3，2-4<3>1-4，2-3
1．3 n=3 <1>1-2，3-4，5-6，7-8<2>1-3，2-4，5-7，6-8<3>1-4，2-3，5-8，6-7<4>1-5，2-6，3-7，4-8<5>1-6，2-5，3-8，4-7<6>1-7，2-8，3-5，4-6<7>1-8，2-7，3-6，4-5
1．4 n=4 <1>1-2，3-4，5-6，7-8，9-10， 11-12，13-14，15-16<2>1-3，2-4，5-7，6-8，9-11， 10-12，13-15，14-16<3>1-4，2-3，5-8，6-7，9-12， 10-11，13-16，14-15<4>1-5，2-6，3-7，4-8，9-13， 10-14，11-15，12-16<5>1-6，2-5，3-8，4-7，9-14， 10-13，11-16，12-15<6>1-7，2-8，3-5，4-6，9-15， 10-16，11-13，12-14<7>1-8，2-7，3-6，4-5，9-16， 10-15，11-14，12-13<8>1-9，2-10，3-11，4-12， 5-13， 6-14，7-15，8-16<9>1-10，2-9，3-12，4-11，5-14， 6-13，7-16，8-15<10>1-11，2-12，3-9，4-10，5-15， 6-16，7-13，8-14<11>1-12，2-11，3-10，4-9，5-16， 6-15，7-14，8-13<12>1-13，2-14，3-15，4-16，5-9， 6-10，7-11，8-12<13>1-14，2-13，3-16，4-15，5-10， 6-9，7-12,8-11<14>1-15，2-16，3-13，4-14，5-11， 6-12，7-9，8-10<15>1-16，2-15，3-14，4-13，5-12， 6-11，7-10，8-9
总计=2+3+8+7=20分
题号输入输出实际输出得分
2．1 101<2>10 101<2>=5<10>
2．2 1101<10>2 1101<10>=10001001101<2>
2．3 3704<8>10 3704<8>=1988<10>
2．4 73<10>8 73<10>=111<8>
2．5 44<7>8 44<7>=40<8>
2．6 62<8>5 62<8>=200<5>
2．7 934<10>7 934<10>=2503<7>
2．8 221<9>6 221<9>=501<6>
2．9 443<5>7 443<5>=234<7>
2．10 61<8>3 61<8>=1211<3>
总计：（每空2分）×10=20分
题号输入输出实际输出得分
3．1 n=3w1=10,w2=20,w3=50 1 0 2MAX=20
3．2 n=3w1=5,w2=10,w3=51 1 0 1-2-3MAX=20
3．3 n=6w1=5,w2=10,w3=20w4=5,w5=4,w6=51 0 1 0 0 0 1 0 0 1 0 0 1 1 1 3-4-2-1MAX=40
3．4 n=6w1=10,w2=15,w3=20w4=15,w5=5, w6=100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3MAX=20
3．5 n=11w1=10,w2=20,w3=30w4=15,w5=40, w6=10w7=20,w8=40, w9=10w10=5,w11=2001 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 11-10-9-7-8-6-2-5-4-3-1MAX=400
总计=4+5+6+7+8=30分
题号输入输出实际输出得分
4．1 1 1 0 0 0 0 Total=3
4．2 2 2 0 0 0 0 Total=6
4．3 1 0 3 0 0 0 Total=7
4．4 3 4 0 5 0 0 Total=36
4．5 2 2 2 2 2 2 Total=82
4．6 0 3 2 7 4 5 Total=185
4．7 0 6 3 4 2 1 Total=79
4．8 1 2 3 4 5 6 Total=204
4．8 6 5 4 3 2 1 Total=83
4．10 10 10 10 10 1 1 Total=140
总计：（每空3分）×10分=30分
1
2NOIP2004 第十届全国青少年信息学奥林匹克联赛复赛试题（普及组三小时完成）
一、不高兴的津津(unhappy.pas/dpr/c/cpp)
【问题描述】
津津上初中了。妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；如果会的话，哪天最不高兴。
【输入文件】
输入文件unhappy.in包括七行数据，分别表示周一到周日的日程安排。每行包括两个小于10的非负整数，用空格隔开，分别表示津津在学校上课的时间和妈妈安排她上课的时间。
【输出文件】
输出文件unhappy.out包括一行，这一行只包含一个数字。如果不会不高兴则输出0，如果会则输出最不高兴的是周几（用1, 2, 3, 4, 5, 6, 7分别表示周一，周二，周三，周四，周五，周六，周日）。如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。
【样例输入】
5 3
6 2
7 2
5 3
5 4
0 4
0 6
【样例输出】
3
二、花生采摘(peanuts.pas/dpr/c/cpp)
【问题描述】
鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。
鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”
我们假定多多在每个单位时间内，可以做下列四件事情中的一件：
1) 从路边跳到最靠近路边（即第一行）的某棵花生植株；
2) 从一棵植株跳到前后左右与之相邻的另一棵植株；
3) 采摘一棵植株下的花生；
4) 从最靠近路边（即第一行）的某棵花生植株跳回路边。
现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。
例如在图2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为13, 7, 15, 9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。
【输入文件】
输入文件peanuts.in的第一行包括三个整数，M, N和K，用空格隔开；表示花生田的大小为M * N（1 <= M, N <= 20），多多采花生的限定时间为K（0 <= K <= 1000）个单位时间。接下来的M行，每行包括N个非负整数，也用空格隔开；第i + 1行的第j个整数Pij（0 <= Pij <= 500）表示花生田里植株(i, j)下花生的数目，0表示该植株下没有花生。
【输出文件】
输出文件peanuts.out包括一行，这一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。
【样例输入1】
6 7 21
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
【样例输出1】
37
【样例输入2】
6 7 20
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
【样例输出2】
28
三、FBI树(fbi.pas/dpr/c/cpp)
【问题描述】
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树[1]，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
1) T的根结点为R，其类型与串S的类型相同；
2) 若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。
现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历[2]序列。
【输入文件】
输入文件fbi.in的第一行是一个整数N（0 <= N <= 10），第二行是一个长度为2N的“01”串。
【输出文件】
输出文件fbi.out包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。
【样例输入】
3
10001011
【样例输出】
IBFBBBFIBFIIIFF
【数据规模】
对于40%的数据，N <= 2；
对于全部的数据，N <= 10。
四、火星人(martian.pas/dpr/c/cpp)
【问题描述】
人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。
火星人用一种非常简单的方式来表示数字——掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为1，2，3……。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。
一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指——拇指、食指、中指、无名指和小指分别编号为1，2，3，4和5，当它们按正常顺序排列时，形成了5位数12345，当你交换无名指和小指的位置时，会形成5位数12354，当你把五个手指的顺序完全颠倒时，会形成54321，在所有能够形成的120个5位数中，12345最小，它表示1；12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指时能够形成的6个3位数和它们代表的数字：
三进制数
123
132
213
231
312
321
代表的数字
1
2
3
4
5
6
现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。
【输入文件】
输入文件martian.in包括三行，第一行有一个正整数N，表示火星人手指的数目（1 <= N <= 10000）。第二行是一个正整数M，表示要加上去的小整数（1 <= M <= 100）。下一行是1到N这N个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。
【输出文件】
输出文件martian.out只有一行，这一行含有N个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。
【样例输入】
5
3
1 2 3 4 5
【样例输出】
1 2 4 5 3
【数据规模】
对于30%的数据，N<=15；对于60%的数据，N<=50；对于全部的数据，N<=10000；
--------------------------------------------------------------------------------
[1] 二叉树：二叉树是结点的有限集合，这个集合或为空集，或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。
[2] 后序遍历：后序遍历是深度优先遍历二叉树的一种方法，它的递归定义是：先后序遍历左子树，再后序遍历右子树，最后访问根。
NOIP普及组复赛参考程序-NOIP2004普及组解题参考
　第一题：不高兴的津津
方法：枚举
程序：
program unhappy; {writen by lxq 2004.11.20}
var a,i,x,y,d,max : byte;
begin
assign(input,'unhappy.in'); reset(input);
assign(output,'unhappy.out'); rewrite(output);
d := 0; max :=8;
for i := 1 to 7 do begin
readln(x,y);
a := x+y;
if a>max then
begin
max :=a; d := i;
end;
end;
writeln(d);
close(input); close(output);
end.
第二题：花生采摘
方法：排个序，然后迭代递推
程序：
program peanuts; {writen by lxq 2004.11.20}
type mytype=record
x,y,d:integer;
end;
var time,all,num,i,j,m,n,k,u,v,z:integer;
q:array[1..400] of mytype;
t:mytype;
begin
all:=0;
assign(input,'peanuts.in');
reset(input);
readln(m,n,k);
for i:=1 to m do
begin
for j:=1 to n do
begin
read(u);
if u>0 then
begin
inc(all);
q[all].x:=i;q[all].y:=j;q[all].d:=u;
if all>1 then
begin
v:=1;
while q[v].d>u do inc(v);
t:=q[all];
for z:=all downto v+1 do q[z]:=q[z-1];
q[v]:=t;
end;
end;
end;
readln;
end;
close(input);
num:=0;time:=0;u:=0;v:=q[1].y;
for i:=1 to all do
begin
if time+abs(q[ i ].x-u)+abs(q[ i ].y-v)+1+q[ i ].x<=k
then begin
inc(num,q[ i ].d);
time:=time+abs(q[ i ].x-u)+abs(q[ i ].y-v)+1;
u:=q[ i ].x;v:=q[ i ].y;
end
else break;
end;
assign(output,'peanuts.out');
rewrite(output);
writeln(num);
close(output);
end.
第三题 FBI树
方法：递归即可，按后序遍历直接边生成边打印。
程序：
program fbi; {writen by lxq 2004.11.20}
var f:array[1..1024] of char;
i,k,n:integer;
c:char;
function lastorder(i,j,n:integer):char;
var lc,rc:char;
begin
if n=0 then lastorder:=f[ i ]
else begin
lc:=lastorder(i,(i+j) div 2,n-1);
write(lc);
rc:=lastorder((i+j) div 2+1,j,n-1);
write(rc);
if lc=rc then lastorder:=lc else lastorder:='F';
end;
end;
begin
assign(input,'fbi.in');
reset(input);
readln(n);
k:=1;
for i:=1 to n do k:=k*2;
for i:=1 to k do
begin
read(c);
if c='0' then f[ i ]:='B' else f[ i ]:='I'
end;
readln;
close(input);
assign(output,'fbi.out');
rewrite(output);
writeln(lastorder(1,k,n));
close(output);
end.
第四题火星人
方法：排列生成法，直接从指定序列用排列产生方法顺序生成到后面M个。
程序：
program martian; {writen by lxq 2004.11.20}
const maxn=10000;
var a:array[1..maxn+1] of integer;
b:array[1..maxn+1] of boolean;
n,m,i,p,k:integer;
begin
assign(input,'martian.in');
reset(input);
readln(n);
readln(m);
fillchar(b,sizeof(b),false);
for i:=1 to n do begin read(a[ i ]);b[a[ i >:=true end;p:=n+1;
k:=-1;
while true do
begin
if p>n then begin
dec(p);
inc(k);
b[a[ i >:=false;
if k=m then break;
end;
repeat inc(a[ i ] ); until not b[a[ i ] ]; b[a[ i ] ]:=true;
if a[ i ] >n then
begin b[a[ i ] ]:=false;dec(p);b[a[ i >:=false end
else
begin inc(p); a[ i ] :=0 end;
end;
assign(output,'martian.out');
rewrite(output);
for i:=1 to n-1 do write(a[ i ],' ');writeln(a[n]);
close(output)
end.
　第十五届全国青少年信息学奥林匹克联赛初赛试题
（提高组 Pascal 语言二小时完成）
○○ 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ○○
一、单项选择题（共10题，每题1.5分，共计15分，每题有且仅有一个正确答案。）
1、关于图灵机下面的说法哪个是正确的：
A）图灵机是世界上最早的电子计算机。
B）由于大量使用磁带操作，图灵机运行速度很慢。
C）图灵机只是一个理论上的计算模型。
D）图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
2、关于BIOS下面的说法哪个是正确的：
A）BIOS是计算机基本输入输出系统软件的简称。
B）BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。
C）BIOS一般由操作系统厂商来开发完成。
D）BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。
3、已知大写字母A的ASCII编码为65（十进制），则大写字母J的十六进制ASCII编码为：
A）48 B）49 C）50 D）以上都不是
4、在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111111111101101。其对应的十进制整数应该是：
A）19 B）-19 C）18 D）-18
5、一个包含n个分支结点（非叶结点）的非空满k叉树，k>=1，它的叶结点数目为：
A）nk+1 B）nk-1 C）(k+1)n-1 D）(k-1)n+1
6、表达式a*(b+c)-d的后缀表达式是：
A）abcd*+- B）abc+*d- C）abc*+d- D）-+*abcd
7、最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码：
A）（00，01，10，11）
B）（0，1，00，11）
C）（0，10，110，111）
D）（1，01，000，001）
8、快速排序平均情况和最坏情况下的算法时间复杂度分别为：
A）平均情况O(nlog(2,n))，最坏情况O(n^2)
B）平均情况O(n)，最坏情况O(n^2)
C）平均情况O(n)，最坏情况O(nlog(2,n))
D）平均情况O(log(2,n))，最坏情况O(n^2)
9、左图给出了一个加权无向图，从顶点V0开始用prim算法求最小生成树。则依次加入最小生成树的顶点集合的顶点序列为： A）V0，V1，V2，V3，V5，V4
B）V0，V1，V5，V4，V3，V3
C）V1，V2，V3，V0，V5，V4
D）V1，V2，V3，V0，V4，V510、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国信息学奥林匹克官方网站的网址是：
A）http://www./ ( http: / / www. / " \t "_blank )
B）http://www.noi.org/ ( http: / / www.noi.org / " \t "_blank )
C）http://www./ ( http: / / www. / " \t "_blank )
D）http://www./ ( http: / / www. / " \t "_blank )
二.不定项选择题（共10题，每题1.5分，共计15分，每题正确答案的个数不少于1。多选或少选均不得分）。
1、关于CPU下面哪些说法是正确的：
A）CPU全称为中央处理器（或中央处理单元）。
B）CPU能直接运行机器语言。
C）CPU最早是由Intel公司发明的。
D）同样主频下，32位的CPU比16位的CPU运行速度快一倍。
2、关于计算机内存下面的说法哪些是正确的：
A）随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。
B）一般的个人计算机在同一时刻只能存/取一个特定的内存单元。
C）计算机内存严格来说包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。
D）1MB内存通常是指1024*1024字节大小的内存。
3、关于操作系统下面说法哪些是正确的：
A.多任务操作系统专用于多核心或多个CPU架构的计算机系统的管理。
B.在操作系统的管理下，一个完整的程序在运行过程中可以被部分存放在内存中。
C.分时系统让多个用户可以共享一台主机的运算能力，为保证每个用户都得到及时的响应通常会采用时间片轮转调度的策略。
D.为了方便上层应用程序的开发，操作系统都是免费开源的。
4、关于计算机网络，下面的说法哪些是正确的：
A）网络协议之所以有很多层主要是由于新技术需要兼容过去老的实现方案。
B）新一代互联网使用的IPv6标准是IPv5标准的升级与补充。
C）TCP/IP是互联网的基础协议簇，包含有TCP和IP等网络与传输层的通讯协议。
D）互联网上每一台入网主机通常都需要使用一个唯一的IP地址，否则就必须注册一个固定的域名来标明其地址。
5、关于HTML下面哪些说法是正确的：
A）HTML全称超文本标记语言，实现了文本、图形、声音、乃至视频信息的统一编码。
B）HTML不单包含有网页内容信息的描述，同时也包含对网页格式信息的定义。
C）网页上的超链接只能指向外部的网络资源，本网站网页间的联系通过设置标签来实现。
D）点击网页上的超链接从本质上就是按照该链接所隐含的统一资源定位符（URL）请求网络资源或者网络服务。
6、若3个顶点的无权图G的邻接矩阵用数组存储为{{0，1，1}{1，0，1}{0，1，0}}，假定在具体存储中顶点依次为：v1，v2，v3 关于该图，下面的说法哪些是正确的：
A）该图是有向图。
B）该图是强联通的。
C）该图所有顶点的入度之和减所有顶点的出度之和等于1。
D）从v1开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的。
7、在带尾指针（链表指针clist指向尾结点）的非空循环单链表中每个结点都以next字段的指针指向下一个节点。假定其中已经有了2个以上的结点。下面哪些说法是正确的：
A）如果p指向一个待插入的新结点，在头部插入一个元素的语句序列为：
p^.next:=clist^.next;clist^.next:=p;
B）如果p指向一个待插入的新结点，在尾部插入一个元素的语句序列为：
p^.next:=clist;clist^.next:=p;
C）在头部删除一个结点的语句序列为：
p:=clist^.next;clist^.next:=clist^.next^.next;dispose(p);
D）在尾部删除一个结点的语句序列为：
p:=clist;clist:=clist^.next;dispose(p);
8、散列表的地址区间为0-10，散列函数为H(K)=K mod 11。采用开地址法的线性探查法处理冲突，并将关键字序列26，25，72，38，8，18，59存储到散列表中，这些元素存入散列表的顺序并不确定。假定之前散列表为空，则元素59存放在散列表中的可能地址有：
A）5 B）7 C）9 D）109、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪些排序算法是稳定的：
A）插入排序 B）基数排序 C）归并排序 D）冒泡排序
10、在参加NOI系列竞赛过程中，下面哪些行为是被严格禁止的：
A）携带书写工具，手表和不具有通讯功能的电子词典进入赛场。
B）在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。
C）通过互联网搜索取得解题思路。
D）在提交的程序中启动多个进程以提高程序的执行效率。三.问题求解（共2题，每空5分，共计10分）
1.拓扑排序是指将有向无环图G中的所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若∈E(G)，则u在线性序列中出现在v之前，这样的线性序列成为拓扑序列。如下的有向无环图，对其顶点做拓扑排序，则所有可能的拓扑序列的个数为______。2、某个国家的钱币面值有1，7，7^2，7^3共计四种，如果要用现金付清10015元的货物，假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通______张钱币。四.阅读程序写结果（共4题，每题8分，共计32分）
1.
var
a,b:integer;
function work(a,b:integer):integer;
begin
if a mod b <> 0 then
work := work(b,a mod b)
else
work := b;
end;
begin
read(a,b);
writeln(work(a,b));
end.
输入：123 321
输出：______2.
var
a,b:array[0..3]of integer;
i,j,tmp:integer;
begin
for i := 0 to 3 do
read(b[i]);
for i := 0 ti 3 do
begin
a[i] := 0;
for j := 0 to i do
begin
inc(a[i],b[j]);
inc(b[a[i] mod 4],a[j]);
end;
end;
tmp:=1;
for i := 0 to 3 do
begin
a[i] := a[i] mod 10;
b[i] := b[i] mod 10;
tmp := tmp * (a[i] + b[i]);
end;
writeln(tmp);
end.
输入：2 3 5 7
输出：______3.
const
y = 2009;
maxn = 50;
var
n,i,j,s:longint;
c:array[0..maxn,0..maxn]of longint;
begin
s := 0;
read(n);
c[0,0] := 1;
for i := 1 to n do
begin
c[i,0] := 1;
for j := 1 to i - 1 do
c[i,j] := c[i-1,j-1] + c[i-1,j];
c[i,i] := 1;
end;
for i := 0 to n do
s := (s + c[n,i]) mod y;
write(s);
end.
输入：17
输出：______4.
var
n,m,i,j,k,p:integer;
a,b:array[0..100]of integer;
begin
read(n,m);
a[0] := n;
i := 0;
p := 0;
k := 0;
repeat
for j := 0 to i - 1 do
if a[i] = a[j] then
begin
p := i;
k := j;
break;
end;
if p <> 0 then
break;
b[i] := a[i] div m;
a[i+1] := (a[i] mod m) * 10;
inc(i);
until a[i] = 0;
write(b[0],'.');
for j := 1 to k - 1 do
write(b[j]);
if p <> 0 then
write('(');
for j := k to i - 1 do
write(b[j]);
if p <> 0 then
write(')');
writeln;
end.
输入：5 13
输出：______五.完善程序（前5空，每空2分，后6空，每空3分，共28分）
1.（最大连续子段和）给出一个数列（元素个数不多于100），数列元素均为负整数、正整数、0。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。例如数列为 4，-5，3，2，4时，输出9和3；数列为1 2 3 -5 0 7 8时，输出16和7。var
a:array[1..100] of integer;
n,i,ans,len,tmp,beg:integer;
begin
read(n);
for i := 1 to n do
read(a[i]);
tmp := 0;
ans := 0;
len := 0;
beg :=__①__;
for i := 1 to n do
begin
if tmp + a[i] > ans then
begin
ans := tmp + a[i];
len := i - beg;
end
else if (__②__) and (i - beg > len) then
len := i - beg;
if tmp + a[i] __③__ then
begin
beg := __④__;
tmp := 0;
end
else
__⑤__;
end;
writeln(ans,' ',len);
end.2.（寻找等差数列）有一些长度相等的等差数列（数列中每个数都为0~59的整数），设长度均为L，将等差数列中的所有数打乱顺序放在一起。现在给你这些打乱后的数，问原先，L最大可能为多大？先读入一个数n（1<=n<=60），再读入n个数，代表打乱后的数。输出等差数列最大可能长度L。var
hash:array[0..60]of integer;
n,x,ans,maxnum,i:integer;
function work(now:integer):boolean;
var
ok:boolean;
first,second,delta,i:integer;
begin
while ((__①__) and (hash[now]=0)) do
inc(now);
if now > maxnum then
begin
work := true;
exit;
end;
first := now;
for second := first to maxnum do
if hash[second] > 0 then
begin
delta :=__②__;
if first + delta * __③__ > maxnum then
break;
if delta = 0 then
ok := (__④__)
else
begin
ok := true;
for i := 0 to ans - 1 do
ok :=__⑤__ and (hash[first+delta*i]>0);
end;
if ok then
begin
for i := 0 to ans - 1 do
dec(hash[first+delta*i]);
if work(first) then
begin
work := true;
exit;
end;
for i := 0 to ans - 1 do
inc(hash[first+delta*i]);
end;
end;
work := false;
end;
begin
fillchar(hash,sizeof(hash),0);
read(n);
maxnum := 0;
for i := 1 to n do
begin
read(x);
inc(hash[x]);
if x > maxnum then
maxnum := x;
end;
for ans := n downto 1 do
if (n mod ans = 0) and __⑥__ then
begin
writeln(ans);
break;
end;
end.第二届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题
（高中组）
（PASCAL 语言竞赛用时：2小时）
●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●
一、基础知识部分：（39分）
已知A盘上的目录和文件组织如下:（2+3=5分）
其中TP、TB、DOS、D11、D31都是子目录名。
设当前命令提示符为 A:＼TB> ,请写出完成如下操作的DOS 命令：
① 在DOS运行中，没有执行过PATH命令，现要用DOS子目录中的FORMAT命令，对插入在B驱动器（5.25英寸高密）中的360KB软盘进行格式化工作,请写出相应的操作命令。
② 交换F2.TXT与F3.DOC两个文件的内容。
2．请用等号或不等号联接表示下列不同进位制数值的大小。（3分）
例如：（3）10 <(4)10 =(100)2 < ( A )16
其中圆括号外右下角的下标，表示圆括号内数的进位制。
（98.375）10 (142.3)8 (58.5)16 (1011000.0101)2
3．阅读下列程序段，写出程序运行后数组元素A1，A2，…，A11中的值。（6分）
A[1]：=1； A[2]：=1 ； K：=1 ；
REPEAT
A[K+2]：=1 ；
FOR I：=K+1 DOWNTO 2 DO
A[I]：=A[I] +A[I-1 ] ；
K：=K+1 ；
UNTIL K>=10 ；
4．已知：ACK（M，N）函数的计算公式如下：（4%）
N+1 M=0
ACK（M，N）= ACK（M-1，1） N=0
ACK（M-1，ACK（M，N-1） M≠0 且N≠0
请计算：ACK（1，3）、ACK（2，4）、ACK（3，3）、ACK（3，4）
5．有N×N个数据组成如下方阵：（5分）
A11 A12 A13 …… A1N
A21 A22 A23 …… A2N
A31 A32 A33 …… A3N
…………
AN1 AN2 AN3 …… ANN
并已知： Aij = Aji
现将A11 ，A21，A22 ，A31 ，A32 ，A33 ，…存储在一维数组A[1]，A[2]，…，A[（N*（N+1））/2] 中。
试问：任给i，j怎样求出K来，使得A[K]的值正好是Aij，请写出由i，j计算K值的表达式。
6．已知：A1，A2，……，A81 共有81个数，其中只有一个数比其它数大，要用最少的比较运算次数，把这个值大的数找出来（假设两个数比较一次能决定出大于、小于或等于这三种情况）请将以下算法补充完整：（9分）
第一步： S1 = A1 + A2 + …… + A27
S2 = A28 + A29 +……+ A54
第一次比较（S1，S2）：
S1 > S2 取 K=0
S1 < S2 取 K=27
S1 = S2 取 K=54
第二步： S1 = AK+1 + AK+2 + …… + AK+9
S2 = AK+10 + AK+11 +……+ AK+18
第二次比较（S1，S2）：
S1 > S2 取 K=
S1 < S2 取 K=
S1 = S2 取 K=
第三步： S1 = AK+1 + AK+2 + AK+3
S2 = AK+4 + AK+5 + AK+6
第三次比较（S1，S2）：
S1 > S2 取 K=
S1 < S2 取 K=
S1 = S2 取 K=
第四步： S1 = AK+1
S2 = AK+2
第四次比较（S1，S2）：
S1 > S2 为最大数
S1 < S2 为最大数，
S1 = S2 为最大数。
7．下面是一个利用完全二叉树特性，用顺序表来存储的一棵二叉树，结点数据为字符型（结点层次号从小到大，同一层从左到右顺序存储，#表示空结点，@表示存储数据结束）。
现要求画出对应该存储结构的二叉树示意图。（7分）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C # # D E # # # # # G F @
二、根据题目要求，完善程序：（61分）
1．[题目] 21分（3+4+3+3+4+4）
积木游戏：设有n 个小木块排成一排，如下图：
……
游戏开始时，每个小木块向下的一面涂有红、黄、蓝三种颜色之中的一种（约定：0表示红色，1表示黄色，2表示兰色）。要求通过翻看与交换方式对小木块重新排列（翻看的规则为每个小木快只能看一次），最终成为下面的形状：
…… …… ……
红蓝黄
即相同颜色的木块排列在一起，设计一个翻看与交换的方案，使得用最少的交换次数实现上面的要求。
[算法描述] 翻看小木块时，可以从两端进行。例如，设中间状态如下：
…… A …… B …… C ……
红未翻过蓝黄
此时，可以从两个方向看，即从A或B处开始：
（1）若看A则有三种可能性：
为红色，则不用交换
为兰色，交换一次，即A与B交换
为黄色，交换两次，即C与B交换一次，然后A与C再交换一次
此时，平均交换次数为1。
（2）若看B，也有三种可能性：
为兰色，则不用交换
为红色，交换一次，即B与A交换。
为黄色，交换一次，即B与C交换。
此时，平均交换次数为2/3。
由此可见，从B处翻看直到游戏结束，次数最少符合题目要求。
[程序]
PROGRAM EXP1(INPUT,OUTPUT)
Const n=20;
Var i,tem,r,b,y:integer;
a :array[1..n] of 0..2;
Begin
For i:=1 to n do read(a[i]); r:=1; ① ; y:=n;
while ② do
if ③ then begin
tem:=a[r]; a[r]:=a[b];
a[b]:=tem; r:=r+1
end
else if ④ then begin
tem:=a[b]; a[b]:=a[y];
a[y]:=tem; ⑤ ; ⑥ ;
end
else b:=b-1
for I:=1 to n do write(a[I]:3)
end.
2．[题目] （20分，每空4分）
4色问题。设有下列形状的图形：（N=8），其编号为1，2，……，N。
图形之间的相邻关系用下面的邻接矩阵表示：
1 2 3 4 5 6 7 8
1 0 1 0 0 0 0 1 1
2 1 0 1 0 0 1 1 0
3 0 1 0 1 0 1 0 0
4 0 0 1 0 1 1 0 0
5 0 0 0 1 0 1 0 0
6 0 1 1 1 1 0 1 0
7 1 1 0 0 0 1 0 1
8 1 0 0 0 0 0 1 0
其中：1——相邻，0——不相邻。
[程序要求] 将上面图形的每一个部分涂上红（1），黄（2），蓝（3），绿（4）四种颜色之一，要求相邻的部分有不同颜色。
输入方式：邻接矩阵。
输出方式：区域、颜色。
…………
[算法描述] 用数组R:ARRAY[1..N,1..N] OF 0..1表示相邻关系，S:ARRAY[1..N] OF INTEGER 表示颜色。
采用回溯的方法，首先给第一个图形涂上红色（1），然后在下面的图形中依次涂上其他颜色，当有矛盾时回溯解决。
［程序］
program exp2(inpuT,output);
Const n=8;
Var I,j,k:integer;
R:Array[1..n,1..n] of 0..1;
S:Array[1..n] of integer;
Begin
For I:=1 to n do
Begin
For j:=1 to n do read(R[I,j]); readln
End;
① ；I:=2; j:=1;
while I<=n do
begin
while (j<=4) and (I<=n) do
begin
k:=1;
while ② do
k:=k+1;
if kelse begin
④ ; I:=I+1; j:=1
End
End;
If j>4 then begin
I:=I-1; ⑤
End;
end;
For I:=1 to n do writeln(I,'',s[I])
End.
3．[题　目] （20分，每空4分）
多项式加法运算：一个仅含有x的多项式可以用下列的方式表示：
（系数，指数），（系数，指数），…，（0，0）。
其中（0，0）作为结束标志。
例如：P(x)=4x6-3x3+2x2-1
可表示为：(4,6),(-3,3),(2,2),(-1,0),(0,0)
Q(x)=x4-x+1
可表示为：(1,4),(-1,1),(1,0),(0,0)
当用上面的方式给出2个多项式之后，编制程序对这两个多项式进行加法运算，结果也用上面的方式给出。
例如：上面的P(x)和Q(x)相加的结果为：
4x6+x4-3x3+2x2-x
表示结果为：(4,6),(1,4),(-3,3),(2,2),(-1,1),(0,0)
[算法描述] 多项式可用数组P表示；分别以p1表示P，p2表示Q，p3表示结果。
处理的过程为将P复制到p3，然后逐项检查Q，当发现有相同的方次时，进行系数相加；当发现没有相同方次时，插入到p3中去。
[程序]
PROGRAM EXP3(INPUT,OUTPUT)
Var
x,y,i,i1,j,j1,j2:integer;
P1,P2,P3 :array[1..20,1..2] of integer
Begin
j1:=0; write('Input P(x)='); read(x,y);
while x<>0 do
begin
j1:=j1+1; P1[j1,1]:=x; P1[j1,2]:=y; read(x,y)
end;
j1:=j1+1; P1[j1,1]:=0; P1[j1,2]:=0;
write('Input Q(x)='); read(x,y); j2:=0;
while x<>0 do
begin
j2:=j2+1; P2[j2,1]:=x; P2[j2,2]:=y; read(x,y)
end;
j2:=j2+1; P2[j2,1]:=0; P2[j2,2]:=0;
for i:=1 to j1 do
begin
P3[I,1]:=P1[I,1]; P3[I,2]:=P1[I,2]
End;
I:=1;
While ① do
begin
If ② then
begin
For j:=j1 down to 1 do
begin
P3[j+1,1]:=P3[j,1]; P3[j+1,2]:=P3[j,2]
End;
P3[I,1]:=P2[I,1]; P3[I,2]:=P2[I,2]; j1:=j1+1
End
Else begin
I1:=1;
While P2[I,2]③ ;
If P2[I,2]=P3[i1,2] then
P3[i1,1]:= ④
Else begin
For j:=j1 downto i1 do
begin
P3[j+1,1]:=P3[j,1]; P3[j+1,2]:=P3[j,2]
End;
P3[i1,1]:=P2[I,1]; P3[i1,2]:=P2[I,2];
⑤
End;
END；
I：=I+1
END；
For j:=1 to j1-2 do write ('(',P3[j,1],',',P3[j,2],'),');
Writeln('(',P3[j+1,1],',',P3[j+1,2],')');
End.
PAGE
1NOI分区联赛 - 1997年第四届初中组试题解析
注意：解析和源程序均为OIBH站长刘汝佳所写，疏漏在所难免
一、设有一个N*M方格的棋盘（l<=N<=100,1<=M<=100）(30％)
求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）。
例如：当 N=2, M=3时：
正方形的个数有8个：即边长为1的正方形有6个；
边长为2的正方形有2个。
长方形的个数有10个：
即2*1的长方形有4个：
1*2的长方形有3个：
3*1的长方形有2个：
3*2的长方形有1个：
程序要求：输入：N，M
输出：正方形的个数与长方形的个数
如上例：输入：2 3
输出：8，10
[分析]
题目够简单吧！直接套公式。不知道公式也可以，自己推吧。
根据乘法原理，先确定长方形的长的总个数，再确定宽。
二、把1，2，… 9共9个数排成下列形状的三角形：（30％）
a
b c
d e
f g h i
其中：a～i分别表示1，2，...9中的一个数字，并要求同时满足下列条件：
(1) a（2）b（3）a+b+d+f=f+g+h+i=i+e+c+a=P
程序要求：根据输入的边长之和P，输出所有满足上述条件的三角形的个数及其中的一
种方案。
[分析]
直接枚举就可以了，没有什么问题。注意因为a+b+d+f=P,只需要枚举a,b,d，根据f=P-a-b-d计算出f
三、设有一个N＊M（l<=N<=50，l<=M<=50）的街道（如图一）：（40%）
　　北
５┌─┬─┬─┬─┬─┬─┬─┬─┐B(9,5)
│ │ │ │ │ │ │ │ │
４├─┼─┼─┼─┼─┼─┼─┼─┤
│ │＊│＊│＊│＊│＊│＊│ │ 东
西３├─┼─┼─┼─┼─┼─┼─┼─┤
│ │＊│＊│＊│＊│＊│＊│ │
２├─┼─┼─┼─┼─┼─┼─┼─┤
│ │ │ │ │ │ │ │ │
１└─┴─┴─┴─┴─┴─┴─┴─┘
　　１　２　３　４　５　６　７　８　９
　A(1,1)　　南
（图一）
规定行人从A(1,1)出发，在街道上只能向东或北方向行走。
图二为N＝3，M=3的街道图，从A出发到达B共有6条可供行走的路径：
1. A-A1-A2-A5-B
2. A-A1-A4-A5-B
3. A-A1-A4-A7-B
4. A-A3-A4-A5-B
5. A-A3-A4-A7-B
6. A-A3-A6-A7-B
若在N＊M的街道中，设置一个矩形障碍区域（包括围住该区域的的街道）不让行人通
行，如图一中用“＊”表示的部分。
此矩形障碍区域用2对顶点坐标给出,图一中的2对顶点坐标为:(2，2),(8，4),此时从
A出发到达B的路径仅有两条。
程序要求
任务一：给出N，M后，求出所有从A出发到达B的路径的条数。
任务二：给出N，M，同时再给出此街道中的矩形障碍区域的2对顶点坐标(X1,y1),
（X2，Y2），然后求出此种情况下所有从A出发到达B的路径的条数。
[分析]
注意：N=50,M=50,无障碍时，数目为100!/(50!*50!)>10^29,连extended都不行了，需要用高精度计算。
另外，这么大的数也说明了本题不可能用搜索，只能用递推。也就是借助加法原理来计算。
在中间有 t[x,y]=t[x-1,y]+t[x,y-1]，其他地方类似。
有障碍或在边上时把公式变一下，少加一两项就可以了。
Copyright OIBH http://oibh.第六届全国青少年信息学（计算机）奥林匹克分区联赛试题
（普及组 PASCAL语言二小时完成）
●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●●
一、选择一个正确答案代码（A/B/C/D），填入每题的括号内 (每题1.5分，多选无分，共30分）
1．下列无符号数中，最小的数是（）．
A．（11011001）2 B．（75）10 C．（37）8 D．（2A）16
2．在外部设备中，绘图仪属于（）．
A．输入设备 B．输出设备 C．辅（外）存储器 D．主（内）存储器
3．GB2312-80 规定了一级汉字3755个，二级汉字3008个，其中二级汉字字库中的汉字是以（）为序排列的．
A．以笔划多少 B．以部首 C．以ASCII码 D．以机内码
4．算法是指（）．
A．为解决问题而编制的计算机程序 B．为解决问题而采取的方法与步骤
C．为解决问题而需要采用的计算机语言 D．为解决问题而采用的计算方法
5．RAM 中的信息是（）．
A．生产厂家预先写入的 B．计算机工作时随机写入的
C．防止计算机病毒侵入所使用的 D．专门用于计算机开机时自检用的
6．计算机主机是由CPU 与（）构成的．
A．控制器 B．运算器 C．输入、输出设备 D．内存储器
7．计算机病毒的特点是（）．
A．传播性、潜伏性、易读性与隐蔽性 B．破坏性、传播性、潜伏性与安全性
C．传播性、潜伏性、破坏性与隐蔽性 D．传播性、潜伏性、破坏性与易读性
8．设循环队列中数组的下标范围是1–n，其头尾指针分别为f和r，则其元素个数为（）．
A．r- f B．r- f +1
C．（r- f ） MOD n+1 D．（r- f + n） MOD n
9．在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是（）．
A 堆排序 B 希尔排序 C 冒泡排序 D 快速排序
10．Internet 的规范译名应为（）．
A．英特尔网 B．因特网 C．万维网 D．以太网
11．WINDOWS 9X 是一种（）操作系统．
A．单任务字符方式 B．单任务图形方式
C．多任务字符方式 D．多任务图形方式
12．某种计算机的内存容量是640K, 这里的640K 容量是指( ) 个字节．
A．640 B． 640*1000 C． 640 * 1024 D．640*1024*1024
13．在Windows 9X中，菜单项后带有符号“…”，表示该菜单项( ) ．
A．可以进行开关选择 B．执行时有对话框
C．有若干子命令 D．不能执行
14．某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索(binary search)，在最坏的情況下，需检视( )个单元．
A．1000 B. 10 C. 100 D. 500
15．已知数组A中，每个元素A[I，J]在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。
试问：A[5，8]的起始地址为（）．
A．SA+141 B．SA+180 C．SA+222 D．SA+225
16．大家知道，不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢的排列是（）．
A．快存 / 辅存 / 主存 B．外存 / 主存 / 辅存
C．快存 / 主存 / 辅存 D．主存 / 辅存 / 外存
17．线性表若采用链表存贮结构，要求内存中可用存贮单元地址（）．
A．必须连续 B．部分地址必须连续
C．一定不连续 D．连续不连续均可
18．下列叙述中，正确的是（）．
线性表的线性存贮结构优于链表存贮结构
队列的操作方式是先进后出
栈的操作方式是先进先出
D．二维数组是指它的每个数据元素为一个线性表的线性表
19．电线上停着两种鸟（A，B），可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可分为两类：一类是两端的小鸟相同；另一类则是两端的小鸟不相同．
已知：电线两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是（）．
A．奇数 B．偶数 C．可奇可偶 D．数目固定
20．请仔細閱读下列程序段:
PASCAL语言 BASIC语言
上列程序段的正确輸出是（）．
A．-1 B．-2 C．-3 D．-4
二、问题解答（每题7分，共14分）
1．已知，按中序遍历二叉树的结果为：abc
问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。
2．有2×n的一个长方形方格，用一个1×2的骨牌铺满方格。例如n=3时，为2×3方格。
此时用一个1×2的骨牌铺满方格，共有3种铺法：
试对给出的任意一个n（n>0），求出铺法总数的递推公式。
三、阅读程序，并写出程序正确的运行结果（10+16分，共26分）
1．program noi_002;
var i, j, l, n, k, s, t : integer;
b : array[1..10] of 0..9;
Begin
readln(l,n); s:=l; k:=1; t:=l;
while sbegin k:=k+1; t:=t*l; s:=s+t end;
s:=s-t; n:=n-s-1;
for i:=1 to 10 do b[i]:=0;
j:=11;
while n>0 do
begin j:=j-1; b[j]:=n mod l; n:=n div l end;
for i:=10-k+1 to 10 do write(chr(ord('A')+b[i]));
End.
输入：　4 167
输出：
2．program noi_004;
var　 i, j, j1, j2, p, q : integer;
p1 : boolean;
b,c : array[1..100] of integer;
Begin
readln(q,p); j:=1; p1:=true; b[j]:=q; j1:=0;
while (q>0) and p1 do
begin
j1:=j1+1; c[j1]:=q*10 div p; q:=q*10-c[j1]*p;
if q>0 then begin
j2:=1;
while (b[j2]<>q) and (j2<=j) do j2:=j2+1;
if b[j2]=q then
begin
p1:=false; write('0.');
for i:=1 to j2-1 do write(c[i]:1);
write('{');
for i:=j2 to j1 do write(c[i]:1);
writeln('}')
end
else begin j:=j+1; b[j]:=q end
end
end;
if q=0 then begin
write('0.');
for i:=1 to j1 do write(c[i]:1);
writeln
end; readln
End.
输入　　①　1 8　　　　输出
输入　 ②　2 7　　　　输出
四、完善程序（每题15分，共30分）
将2n个0和2n 个1，排成一圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。
要求给出一种排法，用上面的方法产生出来的2ｎ＋１个二进制数都不相同。
例如，当n=2时, 即２２个0 和２２个1 排成如下一圈：
比如，从A位置开始，逆时针方向取三个数000，然后再从B位置上开始取三个数001，接着从C开始取三个数010，．．．可以得到000，001，010，101，011，111，110，100共8个二进制数且都不相同。
程序说明
以n=4为例，即有16个0，16个1，
数组a用以记录32个0，1的排法，
数组b统计二进制数是否已出现过。
程序清单
Program noi00;
var
a : array[1..36] of 0..1;
b :array[0..31] of integer;
i, j, k, s, p : integer;
Begin
for i:=1 to 36 do a[i]:=0;
for i:=28 to 32 do a[i]:=1;
p:=1; a[6]:=1;
while (p=1) do
begin
j:=27;
while a[j]=1 do j:=j-1;
①
for i:=j+1 to 27 do ②
for i:=0 to 31 do b[i]:=0;
for i:=1 to 32 do
begin
③
for k:=i to i+4 do s:=s*2+a[k];
④
end;
s:=0;
for i:=0 to 31 do s:=s+b[i];
if ⑤ then p:=0
end;
for i:=1 to 32 do FOR J：=I TO I+4 DO write(a[J]);
writeln
End.
2．多项式的乘法。
例如有如下多项式：
P(X)=2X2-X+1, Q(X)=X+1
则：
P(X)·Q(X)=(2X2-X+1)(X+1)=2X3+X2+1
程序说明：
多项式的表示：系数、指数
如上例中： P(X)：系数指数 Q(X) 系数指数
2 2 1 1
-1 1 1 0
1 0 0 0
0 0
PXQ的结果存入C中。其输出格式是：依次用一对括号内的（系数，指数）分别来表示。如上例的输出结果表示为：（2，3）（1，2）（1，0）
程序清单
program noi_007;
var
i, j, k, l , jp, jq, jc, x, y, x1, y1 : integer;
p, q : array[1..10,1..2] of integer;
c : array[1..20,1..2] of integer;
Begin
jp:=0;
readln(x,y);
　　while x<>0 do
begin jp:=jp+1; p[jp,1]:=x; p[jp,2]:=y; readln(x,y) end;
jq:=0;
readln(x,y);
while x<>0 do
begin jq:=jq+1; q[jq,1]:=x; q[jq,2]:=y; readln(x,y) end;
jc:=1; c[jc,1]:=0; c[jc,2]:=-1000;
for i:=1 to jp do
begin
①
　　　　　 y:=p[i,2];
for j:=1 to jq do
begin
②
　　　　　　　y1:=y+q[j,2];
k:=1;
while y1if y1=c[k,2] then ③
else
begin
for l:=jc downto k do
begin
c[l+1,1]:=c[l,1];
　　　　　　　　　　　　　　　　　　　 c[l+1,2]:=c[l,2]
　　　 end;
　　　　　　　　　　 c[k,1]:=x1; c[k,2]:=y1;
　　　　　　　　　　 ④
　　　　　　　　　　　end
　 end
end;
for i:=1 to jc do
if ⑤ then write(‘（’，c[i,1],‘，’，c[i,2],'）');
readln
End.
赛区市学校姓名
========================== 密封线 =======================
第六届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题
普及组答卷纸
阅卷记录
总阅卷人总得分
第一大题得分第二大题得分
题号 1 2 3 4 5 6 7 8 9 10 第三大题得分
得分 (1) (2)
题号 11 12 13 14 15 16 17 18 19 20 第四大题得分
得分 (1) (2)
============================= 以下由考生填写 =============================
答卷部分
选择一个正确答案代码（A/B/C/D），填入每题的括号内 (每题1.5分，多选无分，共30分）
题号 1 2 ３ 4 5 6 7 8 9 10
选择
题号 11 12 13 14 15 16 17 18 19 20
选择
二、问题解答（共14分）
1. 答：有种不同形态的二叉树可以得到这一遍历结果; （2分）
可画出的这些二叉树为: （5分）
2. 对给出的任意一个n（n>0），用F（N）表示其铺法的总数的递推公式为: （7分）
赛区市学校姓名
========================== 密封线 =======================
三、阅读程序，并写出程序的正确运行结果（10+16分，共26分）
程序的运行结果是:
程序的运行结果是:
四、根据题意，将程序补充完整(每个点3分，共30分)
PASCAL语言 BASIC语言
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
题一
①　　　　　　　　 70
②　　　　　　　　　　　　　　　 110　　　　　　　　　　
③　　　　　　　　　　　　　　　　　　 140　　　　　　　　　　　　　　　
④　　　　　　　　　　　　　　　 180　　　　　　　　　　　　　　
⑤　　　　　　　　　　　　　　　　　　 220　　　　　　　　　　　　　　　
题二
①　　　　　　　　　　　 190
②　　　　　　　　　　　　　 240　　　　　　　　　　　
③　　　　　　　　　　　　　　　　　　　 280　　　　　　　　　　　　　　　　
④　　　　　　　　　　　　　　　　　　　　 300　　　　　　　　　　　　　　　　
⑤ 350　　　　　　　　　　　　　　　　
var
a:array[1..3,1..4] of integer;
b:array[1..4,1..3] of integer;
x,y:integer;
begin
for x:=1 to 3 do
for y:=1 to 4 do
a[x,y]:=x-y;
for x:=4 downto 1 do
for y:=1 to 3 do
b[x,y]:=a[y,x];
writeln(b[3,2]);
end.
DIM A(3,4), B(4,3)
FOR X=1 TO 3
FOR Y=1 TO 4
A(X,Y)=X-Y
NEXT Y , X
FOR X=4 TO 1 STEP -1
FOR Y=1 TO 3
B(X,Y)=A(Y,X)
NEXT Y, X
PRINT B(3,2)
END
　A
　0
　Ｂ　0　　　　　　 1　Ｈ
Ｃ　0　　　　　　　　 1Ｇ
　Ｄ　1　　　　　　 1　Ｆ
　0
　　　　　　Ｅ
PAGE
8第九届分区普及组初赛参考答案
一、选择一个正确答案代码（A/B/C/D/E），填入每题的括号内（每题1.5分，多选无分，共30分）
题号 1 2 3 4 5 6 7 8 9 10
选择 B D B E A A A E B B
题号 11 12 13 14 15 16 17 18 19 20
选择 B A B D A B B C D C
二．问题解答（每题5分，共10分）
　　1．答： 2.04
　　2．答： 11
三．阅读程序，并写出程序的正确运行结果： (每题8分，共32分)
　　（1）程序的运行结果是：-1
　　（2）程序的运行结果是；mo
　　（3）程序的运行结果是：8910
　　（4）程序的运行结果是：Can't be divided　　Can be divided　　Can't be divided
四．根据题意，将程序补充完整(第1空2分，其余每空3分共28分)
PASCAL语言
=================
　　题一
　　① m>0
　　② (-l*b+sqrt(m))／(2*a)；
　　③ 3
　　④ ABS（M）＜0.0001
　　⑤ -1*b/(2*a):0:3
　　题二
　　① 2
　　② i*m
　　③ t=2*m
　　④ (t*2)mod d
　　⑤ solve(m)第三届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题
（高中组竞赛用时：3小时）
1．在N*N的棋盘上（1≤N≤10），填入1，2，…，N*N共N*N个数，使得任意两个相邻的数之和为素数。（30%）
例如：当N=2时，有：
1 2
4 3
当N=4时，一种可以填写的方案如下：
1 2 11 12
16 15 8 5
13 4 9 14
6 7 10 3
在这里我们约定：左上角的格子里必须填数字1。
程序要求：
输入：N；
输出：如有多种解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出“NO！”。
2．代数表达式的定义如下：

例如，下面的式子是合法的代数表达式：
a；
a+b*(a+c);
a*a/(b+c)
下面的式子是不合法的代数表达式：
ab;
a+a*/(b+c);
程序要求：
输入：输入一个字符串，以“；”结束，“；”本身不是代数表达式中字符，仅作为结束）；
输出：若表达式正确，则输出“OK”；若表达式不正确，则输出“ERROR”，及错误类型。
错误类型约定：
式了中出现不允许的字符；
括号不配对；
其它错误。
例如：输入：a+(b); 输出：OK
例如：输入：a+(b+c*a; 输出：ERROR 2
3．骑士游历：
设有一个n*m的棋盘（2≤n≤50，2≤m≤50），如下图，在棋盘上左下角有一个中国象棋马。
（n,m）
(1,1)
马走的规则为：
马走日字；
马只能向右走
即如下图如示：
任务1：当n,m输入之后，找出一条从左下角到右上角的路径。
例如，输入：n=4，m=4
输出：路径的格式：(1,1)→(2,3)→(4,4)。若不存在路径，则输出‘NO’
任务2：当n，m给出之后，同时给出马起点的位置和终点的位置，试找出从起点到终点的所有路径的数目。
例如：（n=10,m=10），（1，5）（起点），（3，5）（终点）
输出：2（即由（1，5）到（3，5）共有2条路径）
输入格式：n,m,x1,y1,x2,y2 (分别表示n,m,起点坐标，终点坐标)
输出格式：路径数目（若不存在从起点到终点的路径，输出0）
其相邻数的和为素数的有：
1+2，1+4，4+3，2+3
a
c
b
字母
马
(4,4)
(1,1)
10
9
8
7
6
5
4
3
2
1
1 2 3 4 5 6 7 8 9 10
1
2NOI’95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛
分区联赛初赛试题（初中组）试题参考答案
基础题：共34分
本题共4分
显示结果不相同，③和④比①多出一个文件目录。
<2> 本题共5分
所表示的公式是：
E=1+X/1！+ X2/2！+ X3/3！+……+ X10/10！
<3> 本题共7分
列出的算法是：
K：=0
FOR i：=0 TO 10 DO
K：=K+（50-I*5） DIV 2+1；
ENDFOR；
<4> 本题共10分
k和i，j之间的关系表示为：4%
k:=(i-1)*i/2+j
给定k值后，决定相应的i,j值的算法为：6%
j:=k;
i:=1;
While j>i do
j:=j-I;
i:=i+1;
Endwhile;
<5> 本题共8分
四色球在盒子中放置的情况为：4%
1 2 3 4
黑红白黄
推理过程是：4%
假定：黑为1√ 黄为2×
　　　黑为2× 白为3√
　　　　　红为2√ 白为4×
　　　　　黄为4√
二、根据题日要求，补充完善以下伪代码程序：（共66分）
共10分（每空二分）
for i:=10 to 99 do
x:=i mod 10;
y:=i div 10;
If (i+j)<100
if k mod 6=0
共12分（每空三分）
s:=0;
s:=s+a[j];
a[i]:=s+1
t:=t+a[i]; 或t:=t*2+1
共24分（每空四分）
for i:=2 to num-1 do 或for i:=2 to sqrt(num)do
if b[i] <>0
if b[i]<>0
for i1:=i+1 to num do
delta:=i1-i; 或delta=b[i1]-b[i]
while (i1+k0 do
共20分（每空四分）
c[j1]=0 and j1<3*n
c[j2]=0 and j2>j1
s:=0;
c[j]:=0;
c[i+j-1]:=c[i+j-1]+b[j]
PAGE
1第二届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题
（高中组竞赛用时：3小时）
1．比赛安排（20分）
设有有2 n（n<=6）个球队进行单循环比赛，计划在2 n – 1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2 n – 1天内每个队都与不同的对手比赛。
例如n=2时的比赛安排：
队 1 2 3 4
比赛 1==2 3==4 一天
1==3 2==4 二天
1==4 2==3 三天
2．数制转换（20分）
设有一个字符串A$的结构为： A$=’mp’
其中m为数字串（长度<=20），而n,p均为1或2位的数字串（其中所表达的内容在2-10之间）。
程序要求：从键盘上读入A$后（不用正确性检查），将A$中的数字串m(n进制)，以p进制的形式输出。
例如：A$=’48<10>8’
其意义为：将10进制数48，转换成8进制数输出。
输出结果为：48<10>=60<8>
4．挖地雷（30分）
在一个地图上有N个地窖（N<=20），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。
V1 V 2 V3 V4 V5
例如：
[题目要求]
当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。
输入格式： N：（表示地窖的个数）
　　　Ｗ1，W2，W3，……WN （表示每个地窖中埋藏的地雷数量）
A12…………… . A1N
A23…………..A2N
……..
AN-1 N
输出格式：
K1--K2--……….KV （挖地雷的顺序）
MAX （挖地雷的数量）
例如：
　　　　⑩--------⑧ ④-----⑦-------⑥
其输入格式为：输出：
5 1 –3 -4 -5
10，8，4，7，6 max=27
1 1 1 0
0 0 0
1 1
1
4．砝码称重（30分）
设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），
要求：
输入方式：a1 a2 a3 a4 a5 a6
（表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个）
输出方式：Total=N
（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）
如输入：1_1_0_0_0_0 （注：下划线表示空格）
输出：TOTAL=3 表示可以称出1g，2g，3g三种不同的重量。
地窖之间连接路径（其中Ａij=1表示地窖i,j之间是否有通路：通Aij=1,不通Aij==0）
1
22002年全国青少年信息学（计算机）
奥林匹克分区联赛复赛提高组试题解题报告
题一均分纸牌（存盘名 NOIPG1）
[问题描述]
　　有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。
　　移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
　　现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
　　例如 N=4，4 堆纸牌数分别为：
　　①　9　②　8　③　17　④　6
　　移动3次可达到目的：
　　从 ③ 取 4 张牌放到 ④ （9 8 13 10） -> 从 ③ 取 3 张牌放到 ②（9 11 10 10）-> 从 ② 取 1 张牌放到①（10 10 10 10）。
[输入]：
　　键盘输入文件名。文件格式：
　　N（N 堆纸牌，1 <= N <= 100）
　　A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000）
[输出]：
　　输出至屏幕。格式为：
　　所有堆均达到相等时的最少移动次数。‘
[输入输出样例]
a.in：
　4
　9 8 17 6
屏慕显示：
　3
分析：如果你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，使大家都变成0，那就意味着成功了一半！拿例题来说，平均张数为10,原张数9，8，17，6，变为-1，-2，7，-4，其中没有为0的数，我们从左边出发：要使第1堆的牌数-1变为0，只须将-1张牌移到它的右边（第2堆）-2中；结果是-1变为0，-2变为-3，各堆牌张数变为0，-3，7，-4；同理：要使第2堆变为0，只需将-3移到它的右边（第3堆）中去，各堆牌张数变为0，0，4，-4；要使第3堆变为0，只需将第3堆中的4移到它的右边（第4堆）中去，结果为0，0，0，0，完成任务。每移动1次牌，步数加1。也许你要问，负数张牌怎么移，不违反题意吗？其实从第i堆移动-m张牌到第i+1堆，等价于从第i+1堆移动m张牌到第i堆，步数是一样的。
如果张数中本来就有为0的，怎么办呢？如0，-1，-5，6，还是从左算起（从右算起也完全一样），第1堆是0，无需移牌，余下与上相同；再比如-1，-2，3，10，-4，-6，从左算起，第1次移动的结果为0，-3，3，10，-4，-6；第2次移动的结果为0，0，0，10，-4，-6，现在第3堆已经变为0了，可节省1步，余下继续。
程序清单
program NOIPG1;
const maxn=100;
var i,j,n,step:integer;ave:longint;
a:array[1..maxn]of integer;
f:text;filename:string;
begin
write('Input filename:');readln(filename);
assign(f,filename);reset(f);
readln(f,n);ave:=0;step:=0;
for i:=1 to n do begin
read(f,a[i]); inc(ave,a[i]);
end;
ave:=ave div i;
for i:=1 to n do a[i]:=a[i]-ave;
i:=1;j:=n;
while a[i]=0 do inc(i);{过滤左边的0}
while a[j]=0 do dec(j);{过滤右边的0}
while (iinc(a[i+1],a[i]);{将第i堆牌移到第i+1堆中去}
a[i]:=0;{第i堆牌移走后变为0}
inc(step);{移牌步数计数}
inc(i);{对下一堆牌进行循环操作}
while a[i]=0 do inc(i);{过滤移牌过程中产生的0}
end;
writeln(step);
end.
点评：基本题（较易）本题有3点比较关键：一是善于将每堆牌数减去平均数，简化了问题；二是要过滤掉0（不是所有的0，如-2，3，0，-1中的0是不能过滤的）；三是负数张牌也可以移动，这是辩证法（关键中的关键）。
题二字串变换（存盘名: NOIPG2）
[问题描述]:
　　已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）:
　　　　　A1$ -> B1$
　　　　　A2$ -> B2$
　　规则的含义为：在 A$中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ …。
　　　　例如：A$＝'abcd'　B$＝'xyz'
　　变换规则为：
　　　　‘abc’->‘xu’　‘ud’->‘y’　‘y’->‘yz’
　　则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：
　　　‘abcd’->‘xud’->‘xy’->‘xyz’
　　共进行了三次变换，使得 A$ 变换为B$。
[输入]:
　　键盘输人文件名。文件格式如下：
　　　A$ B$
　　　A1$ B1$ \
　　　A2$ B2$ |-> 变换规则
　　　... ... /
　　所有字符串长度的上限为 20。
[输出]:
　　输出至屏幕。格式如下：
　　若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出"NO ANSWER!"
[输入输出样例]
b.in:
　abcd xyz
　abc xu
　ud y
　y yz
屏幕显示：
　3
分析：本题是典型的广度优先搜索的例子，但如果只采用正向搜索，某些情况下计算量过大，速度过慢，故采取双向搜索且判重并适当剪枝，效果较好。
程序清单
{$A-,B-,D-,E-,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-,Y-}
{$M 8192,0,655360}
program NOIPG2;
const maxn=2300;
type
node=record{定义节点数据类型}
str:string[115];dep:byte;
end; {str表示字串，其长度不会超过115（长度超过115的字串
不可能通过变换成为目标字串，因为题目限定变换10次之内，且串长
不超过20，即起始串最多可经过5次变换时增长，中间串的最大长度
为20+5*19=115，否则经过余下的步数不可能变为长度不超过20的
目标串），dep表示深度}
ctype=array[1..maxn]of ^node;
bin=0..1;
var
maxk:byte;c:array [0..1]of ctype;
x0:array[0..6,0..1]of string[20];
filename:string;
open,closed:array [0..1] of integer;
procedure Init;{读取数据，初始化}
var f:text;temp:string;i,j:integer;
begin
for i:=0 to 1 do
for j:=1 to maxn do new(c[i,j]);
write('Input filename:');readln(filename);
assign(f,filename);reset(f);i:=0;
while not eof(f) and (i<=6) do begin
readln(f,temp);
x0[i,0]:=copy(temp,1,pos(' ',temp)-1);
x0[i,1]:=copy(temp,pos(' ',temp)+1,length(temp));
inc(i);
end;
maxk:=i-1;close(f);
end;
procedure calc;
var i,j,k:integer;st:bin;
d:string;f:text;
procedure bool(st:bin);{判断是否到达目标状态或双向搜索相遇}
var i:integer;
begin
if x0[0,1-st]=c[st,closed[st]]^.str then begin
{如果到达目标状态，则输出结果，退出}
writeln(c[st,closed[st]]^.dep);
halt;
end;
for i:=1 to closed[1-st] do
if c[st,closed[st]]^.str=c[1-st,i]^.str then begin
{如果双向搜索相遇（即得到同一节点），
则输出结果（2个方向搜索的步数之和），退出}
writeln(c[st,closed[st]]^.dep+c[1-st,i]^.dep);
halt;
end;
end;
procedure checkup(st:bin);{判断节点是否与前面重复}
var i:integer;
begin
for i:=1 to closed[st]-1 do
if c[st,i]^.str=c[st,closed[st]]^.str then begin
dec(closed[st]);exit;{如果节点重复，则删除本节点}
end;
bool(st);{如果节点不重复，再判断是否到达目标状态}
end;
procedure expand(st:bin);{扩展产生新节点}
var i,j,k,lx,ld:integer;
begin
inc(open[st]);d:=c[st,open[st]]^.str;{队首节点出队}
k:=c[st,open[st]]^.dep;ld:=length(d);
for i:=1 to maxk do begin
{从队首节点（父节点）出发产生新节点（子节点）}
lx:=length(x0[i,st]);
for j:=1 to ld do begin
if (copy(d,j,lx)=x0[i,st]) and (length(copy(d,1,j-1)+x0[i,1-st]
+copy(d,j+lx,ld))<=115) then begin
{如果新节点的串长超过115，则不扩展！即剪掉此枝}
if closed[st]>=maxn then exit;{如果队列已满，只好退出}
inc(closed[st]);{新节点入队}
c[st,closed[st]]^.str:=copy(d,1,j-1)+x0[i,1-st]+copy(d,j+lx,ld);
c[st,closed[st]]^.dep:=k+1;{子节点深度=父节点深度+1}
checkup(st);{检查新节点是否重复}
end;
end;
end;
end;
Begin
for st:=0 to 1 do begin{正向(st=0)逆向(st=1)搜索节点队列初始化}
open[st]:=0;closed[st]:=1;
c[st,closed[st]]^.str:=x0[0,st];c[st,closed[st]]^.dep:=0;
bool(st);
end;
repeat
{选择节点数较少且队列未空、未满、深度未达到10的方向先扩展}
if (open[0]<=open[1]) and not ((open[0]>=closed[0]) or
(closed[0]>=maxn) or (c[0,closed[0]]^.dep>10)) then expand(0);
if (open[1]<=open[0]) and not ((open[1]>=closed[1]) or
(closed[1]>=maxn) or (c[1,closed[1]]^.dep>10)) then expand(1);
{如果一方搜索终止，继续另一方的搜索，直到两个方向都终止}
if not ((open[0]>=closed[0]) or (closed[0]>=maxn) or
(c[0,closed[0]]^.dep>10)) then expand(0);
if not ((open[1]>=closed[1]) or (closed[1]>=maxn) or
(c[1,closed[1]]^.dep>10)) then expand(1);
until (open[0]>=closed[0]) or (c[0,closed[0]]^.dep>10) or (closed[0]>=maxn)
and (closed[1]>=maxn) or (open[1]>=closed[1]) or (c[1,closed[1]]^.dep>10);
{终止条件：任一方队空（无解）或搜索深度超过10（10步内无解）
或双方均溢出（可能有解也可能无解，应尽量避免，要尽量把节
点数组开大一点，采用双向搜索，采取剪枝措施等）}
End;
BEGIN
init; calc; writeln('NO ANSWER!')
END.
点评：基本题（较难）考察队列、（双向）广度优先搜索算法及字符串的运算，基本上可以考察出参赛者的数据结构和算法水平。
题三自由落体（存盘名:NOIPG3）
[问题描述]:
　　在高为 H 的天花板上有 n 个小球，体积不计，位置分别为 0，1，2，…．n-1。在地面上有一个小车（长为 L，高为 K，距原点距离为 S1）。已知小球下落距离计算公式为 d＝1/2*g*(t^2)，其中 g=10，t 为下落时间。地面上的小车以速度 V 前进。
　　如下图：
　　小车与所有小球同时开始运动，当小球距小车的距离 <= 0.00001 时，即认为小球被小车接受（小球落到地面后不能被接受）。
　　请你计算出小车能接受到多少个小球。
[输入]：
　　键盘输人：
　　H，S1，V，L，K，n （l<=H，S1，V，L，K，n <=100000）
[输出]：
　　屏幕输出：
　　小车能接受到的小球个数。
[输入输出样例]
　[输入]:
　　　5.0 9.0 5.0 2.5 1.8 5
　[输出]:
　　　1
分析：显然，小车太慢（即V<=Vmin）或太快（V>Vmax）时，一个球也接不到。即在V<=Vmin或V>Vmax时输出为0。下面分别求Vmin和Vmax。当第n-1个小球落地的瞬间，小车在小球的右端离小球尚有e=0.00001的距离，小车的这个极小速度就是Vmin。小车从天花板落到地面的时间t1=,这段时间内小车走了S1-（n-1）-e,所以Vmin=。当第1个小球落到距小车的上表面为e的瞬间，小车在小球的左端离小球距离为e，小车的这个极大速度就是Vmax。小球从天花板落到离小车上表面为e的距离的时间为t2=,小车移动的距离为S1+L+e,所以Vmax=。
那么，当Vmin程序清单
program NOIPG3;
const g=10{重力加速度};e=1E-5;{小车接受小球的极限距离}
var H,s1,v,l,k,t1,t2,Vmin,Vmax:real;
n2,n1,num,n:integer;
begin
readln(h,s1,v,l,k,n);num:=-1;
t1:=sqrt(2*h/g);{小球落地时间}
if h<=k+e then t2:=0 else t2:=sqrt(2*(h-k-e)/g);{小球落到小车上的最短时间}
if s1-v*t2+L+e<0
then num:=0
else n2:=trunc(s1-v*t2+L+e);{小车接受的球的最大编号为n2}
if n2>n-1 then n2:=n-1;{n2取trunc(s1-v*t2+L+e)与n-1的较小值}
if s1-v*t1-e<=0
then n1:=0
else if s1-v*t1-e>n-1
then num:=0
else if (s1-v*t1-e)=trunc(s1-v*t1-e)
then n1:=trunc(s1-v*t1-e){小车接受的球的最小编号为n1}
else n1:=trunc(s1-v*t1-e)+1;
if num=-1 then num:=n2-n1+1;{小车接受的球的个数为num}
writeln(num);
end.
点评：送分题本题“物理味”有余而“信息味”不足，连循环语句都用不上！难见的“送分题”，可物理较差的人也得不到多少分哦！
题四矩形覆盖（存盘名NOIPG4）
[问题描述]:
　　在平面上有 n 个点（n <= 50），每个点用一对整数坐标表示。例如：当 n＝4 时，4个点的坐标分另为：p1（1，1），p2（2，2），p3（3，6），P4（0，7），见图一。
　　这些点可以用 k 个矩形（1<=k<=4）全部覆盖，矩形的边平行于坐标轴。当 k=2 时，可用如图二的两个矩形 sl，s2 覆盖，s1，s2 面积和为 4。问题是当 n 个点坐标和 k 给出后，怎样才能使得覆盖所有点的 k 个矩形的面积之和为最小呢。约定：覆盖一个点的矩形面积为 0；覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开（边线与顶点也都不能重合）。
[输入]:
　　键盘输人文件名。文件格式为
　　　n k
　　　xl y1
　　　x2 y2
　　　... ...
　　　xn yn （0<=xi,yi<=500)
[输出]:
　　输出至屏幕。格式为：
　　一个整数，即满足条件的最小的矩形面积之和。
[输入输出样例]
d.in :
　4 2
　1 1
　2 2
　3 6
　0 7
屏幕显示：
4
分析
1、本题的难度较大。如果你这样认为：即在假定已用i个矩形（面积和满足最小）覆盖所有点的基础上，穷举所有2个矩形合并成1个矩形（条件是：在所有合并方案中使合并后面积最小），从而使矩形个数减少为i-1——那就错了，可是却可以通过前4组测试数据！
正确的做法是对不同的K值分别进行计算，好在K值较小，否则...
讨论：
k=1，只要求出n个点坐标的最大、最小值，就可求得矩形的位置与面积；
k=2，有2个矩形，它们只有2种分布形式：左右式（flag=0），上下式（flag=1）
对于左右式，显然要先将所有点按横坐标升序排列，可将点1~点i-1放入矩形1中，将点i~点n放入矩形2中，求两矩形的面积之和；如果面积和比上一个值小，记下；让i从2循环到n,就可完成左右式的全部搜索；
对于上下式，先将所有点按纵坐标升序排列，依此类推。
k=3，有3个矩形，它们有6种分布形式：
要用两重循环进行搜索：设i,j为循环变量，将点1~i-1放入矩形1中，点i~j-1放入矩形2中，点j~n放入矩形3中；点必须在放入前排好序（均为升序）：对于flag=0,所有点按横坐标排序；对于flag=1,所有点按纵坐标排序；对于flag=2,所有点先按横坐标排序，然后点i~n按纵坐标排序；对于flag=3,所有点先按横坐标排序，然后点1~j-1按纵坐标排序；对于flag=4,所有点先按纵坐标排序，然后点1~j-1按横坐标排序；对于flag=5,所有点先按纵坐标排序，然后点i~n按横坐标排序；
至于k=4,4个矩形有22种分布形式，实在太复杂！幸好测试数据中没有K=4的情形(似乎有意放了一马？)。据说本题全国没有一人全对！（只要求K=1，2，3）
程序清单
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+,Y+}
{$M 65520,0,655360}
program NOIPG4;
const maxn=50;maxk=3;
type rect=record{定义"矩形"数据类型}
l,r,t,b:word;{矩形的左边，右边，下边，上边距坐标轴的距离}
end;
vxy=record{定义"点"数据类型}
x,y:word;{点的横、纵坐标}
end;
var ju:array[1..maxk]of rect;
v:array[1..maxn,0..2] of vxy;v0:vxy;
n,k,i,j,ii,jj:byte;f:text;filename:string;
Smin,temp:longint;
function intersect(jui,juj:rect):boolean;{判断两矩形是否有公共点}
var b1,b2,t1,t2,l1,l2,r1,r2:word;
begin
b1:=jui.b;b2:=juj.b;t1:=jui.t;t2:=juj.t;
l1:=jui.l;l2:=juj.l;r1:=jui.r;r2:=juj.r;
intersect:=((l2<=r1) and (l2>=l1) or (r2<=r1) and (r2>=l1) or (l2<=l1)
and (r2>=r1)) and ((t2<=b1) and (t2>=t1) or (b2<=b1) and (b2>=t1)
or (b2>=b1) and (t2<=t1));
end;
function area(ju:rect):longint;{求矩形的面积}
var temp:longint;
begin
temp:=ju.b-ju.t;area:=temp*(ju.r-ju.l);
{不能直接写成area:=(ju.b-ju.t)*(ju.r-ju.l);因为这样可能会溢出！}
end;
procedure insert(v:vxy;var ju:rect);{将点放入矩形}
begin
if v.xif v.x>ju.r then ju.r:=v.x;
if v.yif v.y>ju.b then ju.b:=v.y;
end;
procedure init;{初始化}
begin
write('Input filename:');readln(filename);
assign(f,filename);reset(f);readln(f,n,k);
for i:=1 to n do begin
read(f,v[i,0].x,v[i,0].y);
v[i,1].x:=v[i,0].x;v[i,1].y:=v[i,0].y;
end;
for i:=1 to n-1 do{按横坐标升序排列各点，存入v[i,0]}
for j:=i+1 to n do
if v[i,0].x>v[j,0].x then begin
v0:=v[i,0];v[i,0]:=v[j,0];v[j,0]:=v0;
end;
for i:=1 to n-1 do{按纵坐标升序排列各点，存入v[i,1]}
for j:=i+1 to n do
if v[i,1].y>v[j,1].y then begin
v0:=v[i,1];v[i,1]:=v[j,1];v[j,1]:=v0;
end;
end;
procedure solve;{核心计算}
begin
smin:=maxlongint;
case k of
1:begin{K=1的情形}
ju[1].b:=v[n,1].y;ju[1].t:=v[1,1].y;
ju[1].r:=v[n,0].x;ju[1].l:=v[1,0].x;
smin:=area(ju[1]);
end;
2:for jj:=0 to 1 do begin{K=2的情形}
{flag=0,1的情形}
ju[1].b:=v[1,jj].y;ju[1].t:=v[1,jj].y;
ju[1].r:=v[1,jj].x;ju[1].l:=v[1,jj].x;
for i:=2 to n do begin
insert(v[i-1,jj],ju[1]);{将第i-1点放入矩形1}
ju[2].b:=v[i,jj].y;ju[2].t:=v[i,jj].y;{将第i至n点放入矩形2}
ju[2].r:=v[i,jj].x;ju[2].l:=v[i,jj].x;
for ii:=i+1 to n do insert(v[ii,jj],ju[2]);
if not intersect(ju[1],ju[2]) then begin{如果两矩形不交叉}
temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]);
if tempend;
end;
end;
3:begin
for jj:=0 to 1 do begin {flag=0,1的情形}
ju[1].b:=v[1,jj].y;ju[1].t:=v[1,jj].y;
ju[1].r:=v[1,jj].x;ju[1].l:=v[1,jj].x;
for i:=2 to n-1 do begin
insert(v[i-1,jj],ju[1]);
ju[2].b:=v[i,jj].y;ju[2].t:=v[i,jj].y;
ju[2].r:=v[i,jj].x;ju[2].l:=v[i,jj].x;
if intersect(ju[1],ju[2]) then continue;
for j:=i+1 to n do begin
insert(v[j-1,jj],ju[2]);
ju[3].b:=v[j,jj].y;ju[3].t:=v[j,jj].y;
ju[3].r:=v[j,jj].x;ju[3].l:=v[j,jj].x;
for ii:=j+1 to n do insert(v[ii,jj],ju[3]);
if intersect(ju[2],ju[3]) then continue;
temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]);
if tempend;
end;
end;
{flag=2的情形:先竖直划分大矩形；再在右矩形中水平划分}
ju[1].b:=v[1,0].y;ju[1].t:=v[1,0].y;
ju[1].r:=v[1,0].x;ju[1].l:=v[1,0].x;
for i:=2 to n-1 do begin
for ii:=1 to n do v[ii,2]:=v[ii,0];{所有点按横坐标升序排列，存入v[i,2]}
for ii:=i to n-1 do{将点i至n按纵坐标升序排列，存入v[i,2]}
for jj:=ii+1 to n do
if v[ii,2].y>v[jj,2].y then begin
v0:=v[ii,2];v[ii,2]:=v[jj,2];v[jj,2]:=v0;
end;{结果：所有点先按横坐标升序排列，然后点i至n按纵坐标升序排列}
insert(v[i-1,2],ju[1]);{将第i-1点放入矩形1}
ju[2].b:=v[i,2].y;ju[2].t:=v[i,2].y;{将第i点放入矩形2}
ju[2].r:=v[i,2].x;ju[2].l:=v[i,2].x;
if intersect(ju[1],ju[2]) then continue;
for j:=i+1 to n do begin
insert(v[j-1,2],ju[2]);{将第j-1点放入矩形2}
ju[3].b:=v[j,2].y;ju[3].t:=v[j,2].y;{将第j至n点放入矩形3}
ju[3].r:=v[j,2].x;ju[3].l:=v[j,2].x;
for ii:=j+1 to n do insert(v[ii,2],ju[3]);
if intersect(ju[2],ju[3]) then continue;
temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]);
if tempend;
end;
{flag=3的情形}
for j:=3 to n do begin
for ii:=1 to n do v[ii,2]:=v[ii,0];
for ii:=1 to j-2 do
for jj:=ii+1 to j-1 do
if v[ii,2].y>v[jj,2].y then begin
v0:=v[ii,2];v[ii,2]:=v[jj,2];v[jj,2]:=v0;
end;
ju[3].b:=v[j,2].y;ju[3].t:=v[j,2].y;
ju[3].r:=v[j,2].x;ju[3].l:=v[j,2].x;
for ii:=j+1 to n do insert(v[ii,2],ju[3]);
for i:=2 to j-1 do begin
ju[2].b:=v[i,2].y;ju[2].t:=v[i,2].y;
ju[2].r:=v[i,2].x;ju[2].l:=v[i,2].x;
for ii:=i+1 to j-1 do insert(v[ii,2],ju[2]);
ju[1].b:=v[1,2].y;ju[1].t:=v[1,2].y;
ju[1].r:=v[1,2].x;ju[1].l:=v[1,2].x;
for ii:=2 to i-1 do insert(v[ii,2],ju[1]);
if intersect(ju[1],ju[2]) or intersect(ju[2],ju[3]) or
intersect(ju[1],ju[3]) then continue;
temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]);
if tempend;
end;
{flag=4的情形}
for j:=3 to n do begin
for ii:=1 to n do v[ii,2]:=v[ii,1];
for ii:=1 to j-2 do
for jj:=ii+1 to j-1 do
if v[ii,2].x>v[jj,2].x then begin
v0:=v[ii,2];v[ii,2]:=v[jj,2];v[jj,2]:=v0;
end;
ju[3].b:=v[j,2].y;ju[3].t:=v[j,2].y;
ju[3].r:=v[j,2].x;ju[3].l:=v[j,2].x;
for ii:=j+1 to n do insert(v[ii,2],ju[3]);
for i:=2 to j-1 do begin
ju[2].b:=v[i,2].y;ju[2].t:=v[i,2].y;
ju[2].r:=v[i,2].x;ju[2].l:=v[i,2].x;
for ii:=i+1 to j-1 do insert(v[ii,2],ju[2]);
ju[1].b:=v[1,2].y;ju[1].t:=v[1,2].y;
ju[1].r:=v[1,2].x;ju[1].l:=v[1,2].x;
for ii:=2 to i-1 do insert(v[ii,2],ju[1]);
if intersect(ju[1],ju[2]) or intersect(ju[2],ju[3]) or
intersect(ju[1],ju[3]) then continue;
temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]);
if tempend;
end;
{flag=5的情形}
ju[1].b:=v[1,1].y;ju[1].t:=v[1,1].y;
ju[1].r:=v[1,1].x;ju[1].l:=v[1,1].x;
for i:=2 to n-1 do begin
for ii:=1 to n do v[ii,2]:=v[ii,1];
for ii:=i to n-1 do
for jj:=ii+1 to n do
if v[ii,2].x>v[jj,2].x then begin
v0:=v[ii,2];v[ii,2]:=v[jj,2];v[jj,2]:=v0;
end;
insert(v[i-1,2],ju[1]);
ju[2].b:=v[i,2].y;ju[2].t:=v[i,2].y;
ju[2].r:=v[i,2].x;ju[2].l:=v[i,2].x;
if intersect(ju[1],ju[2]) then continue;
for j:=i+1 to n do begin
insert(v[j-1,2],ju[2]);
ju[3].b:=v[j,2].y;ju[3].t:=v[j,2].y;
ju[3].r:=v[j,2].x;ju[3].l:=v[j,2].x;
for ii:=j+1 to n do insert(v[ii,2],ju[3]);
if intersect(ju[2],ju[3]) then continue;
temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]);
if tempend;
end;
end;
end;
end;
begin{主程序}
init;
solve;
writeln(smin);
end.
点评：压轴题据说，本次复赛主要是前三题的竞争，可见本题能得分的人相当少，但是K=1应该说是送分的，K=2也是比较容易的。通过测试，发现在K=3的第4、5组测试数据中仅用到了flag=1的情形，也就是说，只要写出flag=1的程序段就OK了（没写flag=0,2,3,4,5的同学偷着乐）。
1
2
flag=0
2
1
flag=1
1
2
3
flag=1
1
2
3
flag=0
3
2
1
flag=2
1
2
3
flag=3
1
2
3
flag=4
1
2
3
flag=5第六届全国青少年信息学（计算机）奥林匹克分区联赛
普及组测试表
第一题：计算器的改良共 18 分
序号一元一次方程输出分值得分
1 20+3x＝－18 3
2 －6＋12x＝0 4
3 47－2＝6y＋3 4
4 －25a＋18－2＝－7a－2 4
5 －a+1a－3=a－3 3
第二题：税收与补贴问题共 20 分
序号输入输出分值得分
1 　　内容见21．IN 5
2 内容见22．IN 5
3 内容见23．IN 5
4 内容见24．IN 5
第三题：乘积最大共26分
序号输入输出分值得分
1 1101010 6
2 4321044105 7
3 322222222 6
4 57777777777 7
第四题：单词接龙共36分
序号输入输出分值得分
1 内容见41．IN 6
2 内容见42．IN 6
3 内容见43．IN 6
4 内容见44．IN 6
5 内容见45．IN 6
6 内容见46．IN 6
选手学校班级邮编：
选手签名：指导教师签名：得分：
赛区主评委签名：评委签名：
普及组复赛试题测试数据
题二．税收与补贴问题 (输入)
题四．单词接龙 (输入)
普及组参考答案
第一题：计算器的改良共１８分
序号一元一次方程输出分值得分
1 20+3x＝－18 x＝－12.667 3
2 －6＋12x＝0 x＝0.500 4
3 47－2＝6y＋3 y＝7.000 4
4 －25a＋18－2＝－7a－2 a＝1.000 4
5 －a+1a－3=a－3 a=0.000 3
第二题：税收与补贴问题共 20 分
序号输入输出分值得分
1 　　内容见21．IN 4 5
2 内容见22．IN －32 5
3 内容见23．IN 9 5
4 内容见24．IN －20 5
第三题：乘积最大共２６分
序号输入输出分值得分
1 1101010 １０１００ 6
2 4321044105 ５１６６０００ 7
3 8 322222222 ２３４２５６ 6
4 10 57777777777 １７２２４９９００９ 7
第四题：单词接龙共3６分
序号输入输出分值得分
1 内容见41．IN 15 6
2 内容见42．IN 19 6
3 内容见43．IN 43 6
4 内容见44．IN 9 6
5 内容见45．IN 31 6
6 内容见46．IN 38 6
23．IN
77
280
266
264
260
239
-1 -1
50
24．IN
4011
1 79990
7999 10
-1 –1
10
22．IN
315
280 1300
300 1200
310 1100
-1 –1
150
21．IN
31
28 130
30 120
31 110
-1 –1
15
43．IN
4
abababc
abababd
abababa
cdababa
a
42．IN
2
abababab
abababc
a
41．IN
1
envelope
e
44．IN
8
no
new
name
never
national
necessary
ever
me
n
46．IN
6
many
youth
this
system
main
navy
m
45．IN
6
act
touch
cheat
choose
tact
sencitive
a
批准:中国科协、教育部主办:中国计算机学会承办:江苏省科协青少年部、广东省计算机学会普委会第四届全国青少年信息学（计算机）奥林匹克分区联赛
复赛参考答案（初中组）
题号输入输出分值得分
1.1 无 192 384 576219 438 657273 546 819327 654 981(共四组) 30分
2.1 N=6 873 5分
2.2 N=10 4,037,913 5分
2.3 N=22 1,177,652 ,997,443 ,428,940 313 10分
2.4 N=48 12,678,163,798,554,051,767,172,643,373,255,731,925,167,694,226,950,680,420,940,313 10分
3.1 73 2(2(2)+2)+2(2+2(0))+2(0) 5分
3.2 136 2(2(2)+2+2(0))+2(2+2(0)) 5分
3.3 255 2(2(2)+2+2(0))+2(2(2)+2)+2(2(2)+2(0))+2(2(2))+2(2+2(0))+2(2)+2+2(0) 10分
3.4 1384 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2)+2(2(2)+2(0))+2(2+2(0)) 10分
3.5 16385 2(2(2+2(0))+2(2)+2)+2(0) 10分
总计=30+30+40=100分
1
1第四届全国青少年信息学（计算机）奥林匹克分区联赛初赛
（高中组）
参考答案
一、选择填空：共23分
1．不属于操作系统的软件是 C {1%}
2、在计算机内部，用来传送、存贮、加工处理的数据或指令（命令）都是以C形式进行的。 {1%}
3．解释正确的是D {2%}
4．最后复制的结果是A。 {2%}
5．表达式的值是 B {2%}
6．等式中的52，19，33，分别为B。 {3%}
7．（1）读过a的人数是 A （2）一本书也没有读过的人数是 B 。 {2%+2%}
8．当x=80时，运行的结果为 E {1%}
当x=5时，运行的结果为 D {1%}
9．①这样表示法的整数a的范围应是A {2%} ②在这样表示法中， D 说法是正确的。{1%}
10．出栈的元素序列是 D 。 {2%}
二、问题求解：共20分
1．当K= 4，a1,a2,…,ak为a1=4, a2=6, a3=4，a4=-1对数列132333,…,n3,…（A）成立。{3%+5%）
2．此二叉树为： {7%}
3．表示该无向图的邻接矩阵为 {6%}
0 1 0 0 0 0 0
1 0 1 1 0 0 0
0 1 0 1 0 0 0
0 1 1 0 1 1 1
0 0 0 1 0 0 1
0 0 0 1 0 0 1
0 0 0 1 1 1 0
三、阅读程序，写出程序的正确运行结果：共39分
1．输出：max=77 {7%}
2．输出结果为：S=1024 {10%}
3．输出结果为：S=252 {10%}
4．输入：10101100 输出：jamp=5 maxswap=2 i=6 j=7 {12%}
四、根据题意，补充完善以下程序：（17%）
PASCAL语言 BASIC语言
① st12<=st11 ； 80 STR2>STR1 {4%}
② t=0 ； 140 T=0 {2%}
③ s=0 ； 150 S=0 {2%}
④ st12+1 ； 180 STR2+1 {3%}
⑤ str1[st12,I+j] ; 250 STR1＄（STR2，I+J） {4%}
⑥ j+1 to n ; 270 J+1 TO N {2%}
A
C
B
D
E
F
G
H
I
1
2第十届全国青少年信息学奥林匹克联赛初赛试题
（普及组 Pascal语言二小时完成）
一、选择一个正确答案代码（A/B/C/D/E）填入每题的挂号内
1．美籍匈牙利数学家冯·诺依曼对计算机科学发展所做出的贡献是：（）
A、提出理想计算机数学模型，成为计算机科学理论基础
B、是世界上第一个编写计算机程序的人
C、提出存储程序工作原理，并设计出第一台具有存储程序功能的计算机EDVAC
D、采用集成电路作为计算机的主要功能部件
E、指出计算机性能将以每两年翻一番的速度向前发展
2．下列哪个不是CPU（中央处理单元）（）
A、Intel Itanium
B、DDR SDRAM
C、AMD Athlon64
D、AMD Opteron
E、IBM Power 5
3、下列网络中常用的名字缩写对应的中文解释错误的是（）
A、WWW(World Wide Web)：万维网
B、URL（Uinform Resource Locator）：统一资源定位器
C、HTTP（Hypertext Transfer Protocol）：超文本传输协议
D、FTP (File Transfer Protocol)：快速传输协议
E、TCP （Transfer Control Protocol）：传输控制协议
4、下面哪个部件对于个人桌面电脑的正常运行不是必需的（）
A、cpu
B、显卡（图形卡）
C、光驱
D、主板
E、内存
5、下列哪个软件属于操作系统软件（）
A、Microsoft Word
B、金山词霸
C、Foxmail
D、WinRAR
E、Red Hat Linux
6、下列哪个不是计算机存储设备（）、
A、文件管理器
B、内存
C、高速缓存
D、硬盘
E、U盘
7、下列说法中错误的是（）
A、CPU的基本功能就是执行指令
B、CPU访问内存的速度快于访问高速缓存的速度
C、CPU的主频是指CPU在1秒内完成的指令周期数
D、在一台计算机内部，一个内存地址编码对应唯一的一个内存单元
E、数据中线的宽度决定了一次传递数据量的大小
8、彩色显示器所显示的五彩斑斓的色彩，是由红色，蓝色和（）色混合而成的
A、紫色 B、白色 C、黑色 D、绿色 E、橙色
9、用静电吸附磨粉后转移到纸张上，是那种输出设备的工作方式（）
A、针式打印机
B、喷墨打印机
C、激光打印机
D、笔式绘图仪
E、喷墨绘图仪
10、一台计算机如果要利用电话线上网，就必须配置能够对数字信号和模拟信号进行互相转换的设备，这种设备是（）
A、调制解调器
B、路由器
C、网卡
D、网关
E、网桥
11、下列哪个不是数据库软件的名称（）
A、MYSQL
B、SQL Sever
C、Oracle
D、金山影霸
E、Foxpro
12、下列哪个程序设计语言不支持面向对象的程序设计方法（）
A、C++
B、Object Pascal
C、C
D、Smalltalk
E、Java
13、由3个a，1个b和2个c构成的所有字符串中，包含子串“abc”的共有（）个
A、20 B、8 C、16 D、12 E、24
14、某车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时该车站站台为空，从这一时刻开始出入记录为：“进出进进出进进进出出进出”。假设车辆入站的顺序为1,2,3……，则车辆出站的顺序为（）
A、1，2，3，4，5
B、1，2，4，5，7
C、1，3，5，4，6
D、1，3，5，6，7
E、1，3，6，5，7
15、二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，其后序遍历序列为
A、4 2 5 7 6 3 1
B、4 2 7 5 6 3 1
C、4 2 7 5 3 6 1
D、4 7 2 3 5 6 1
E、4 5 2 6 3 7 1
16、满二叉树的叶节点为N，则它的节点总数为（）
A、N
B、2N
C、2N-1
D、2N+1
E、2^N-1
17、十进制2004等于八进制数（）
A、3077
B、3724
C、2766
D、4002
E、3755
18、（2004）10 +（32）16的结果是（）
A、（2036）10
B、（2054）16
C、（4006）10
D、（100000000110）2
E、（2036）16
19、在下图，从端点（）出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次
20、某大学计算机专业的必修课及期先修课程如下表所示：
课程代号 C0 C1 C2 C3 C4 C5 C6 C7
课程名称高等数学程序设计语言离散数学数据结构编译技术操作系统普通物理计算机原理
先修课程 C0,C1 C1,C2 C3 C3,C7 C0 C6
请判断下列课程安排哪个是不合理的（）
A、C0,C6,C7,C1,C2,C3,C4,C5
B、C0,C1,C2,C3,C4,C6,C7,C5
C、C0,C1,C6,C7,C2,C3,C4,C5
D、C0,C1,C6,C7,C5,C2,C3,C4
E、C0,C1,C2,C3,C6,C7,C5,C4
二、问题求解（5分一题，共10分）
1、一个家具公司生产桌子和椅子。现有113个单位的木材。每张桌子要使用20个单位的木材，售价是30元；每张椅子要用16个单位的木材，售价是20元。使用已有的木材生产桌椅（不一定要用光木材）做多可以买_____元钱。
2、75名儿童去游乐场玩。他们可以骑旋转木马，坐滑行轨道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中两种。若每玩一样的费用为5元，游乐场总共收入700，可知有_____名儿童没有玩过其中任何一种。
三、阅读程序（8’一题，共32’）
1、-------------------------------------------
program program1;
Var
a,b,c,d,e:integer;
begin
a:=79 ; b:=34; c:=57;d:=0 ; e:=-1;
if (ac) then d:=d+e
else if (d+10else d:=e-a;
writeln(d);
end.
输出：_____________________。
2、-------------------------------------------
program program2;
var
i,j:integer;
str1,str2:string;
begin
str1:='pig-is-stupid';
str2:='clever';
str1[1]:='d'; str1[2]:='o';
i:=8;
for j:=1 to 6 do begin
str1[i]:=str2[j];inc(i);
end;
writeln(str1);
end.
输出：_____________________。
3、-------------------------------------------
program program3;
var
u:array[0..3] of integer;
a,b,c,x,y,z:integer;
begin
read(u[0],u[1],u[2],u[3]);
a:=u[0]+u[1]+u[2]+u[3]-5;
b:=u[0]*(u[1]-u[2] div u[3]+8);
c:=u[0]*u[1] div u[2] * u[3];
x:=(a+b+2)*3-u[(c+3) mod 4];
y:=(c*100-13) div a div (u[b mod 3]*5);
if ((x+y) mod 2=0) then z:=(a+b+c+x+y) div 2;
z:=(a+b+c-x-y)*2;
writeln(x+y-z);
read(a);
end.
输出：_____________________。
4、-------------------------------------------
program program4 ;
var c:array[1..2] of string[200];
s:array[1..10] of integer;
m,n,i:integer ;
procedure numara;
var cod:boolean;
i,j,nr:integer;
begin
for j:=1 to n do begin
nr:=0;cod:=true;
for i:=1 to m do
if c[i,j]='1' then begin
if not cod then begin
cod:=true;inc(s[nr]);nr:=0;
end
end
else begin
if cod then begin
nr:=1;cod:=false ;
end
else inc(nr);
end;
if not cod then inc(s[nr]);
end;
end;
begin
readln(m,n);
for i:=1 to m do readln(c[i]);
numara;
for i:=1 to m do
if s[i] <>0 then write(i,' ',s[i],' ');
read(i);
end.
输出：_____________________。
四、完善程序（共28分）
1、三角形内切圆的面积
题目描述：给出三角形三边的边长，求此三角形内切圆的面积。
输入：三个正实数a、b、c（满足三角形三边关系），表示三角形三边边长。
输出：三角形内切圆的面积，结果四舍五入到小数点后2位
输入样例： 3 4 5
输出样例： 3.14
程序：①②③④⑤
Program program1;
Var
a,b,c,r,s,t:real;
begin
read(a,b,c);
s :=( ① )/2;
t:= ② (s*(s-a)*(s-b)*(s-c));
r:=t/s;
writeln(3.1415927 * r * ③ :0: ④ ;
END.
2..Joseph
题目描述：
原始的Joseph问题的描述如下：有n个人围坐在一个圆桌周围，把这n个人依次编号为1，……，n。从编号是1 的人开始报数，数到m个人出列，然后从出列的下一个人重新开始报数，数到第m个人又出列，……，如此反复直到所有的人全部出列为止。比如当n=6,m=5的时候，出列的顺序依次是5，4，6，2，3，1。
现在的问题是：假设有k个好人和k个坏人。好人的编号是1到k，坏人的编号是k+1到2k。我们希望求出m的最小值，使得最先出列的k个人都是坏人。
输入：
仅有的一个数字是k (0输出：
使得最先出列的k个人都是坏人的m的最小值。
输入样例：
4
输出样例：
30
程序：
program progaram1;
var
i,k,m,start：longint;
find：boolean;
function check（remain:integer）：boolean;
var result：integer;
begin
result：=____(1)____ mod remain;
if ____(2)____ then begin
start：=result; check：=true;
end
else check：=false;
end;
begin
find：=false;
read(k);
m：=k;
while ____(3)____ do begin
find：=true; start；=0；
for i：=0 to k-1 do
if (not check(____(4)____)) then begin
find：=false; break;
end;
inc(m);
end;
writeln(____(5)____);
end.
参考答案
一、1.C 2.B 3.D 4.C 5.E 6.A 7.B 8.D 9.C 10.A
11.D 12.C 13.D 14E 15.B 16.C 17.B 18.D 19.E 20.D
二、1．160元 2．１０人
三、　１．－80　　　　　　　２．Dog-is-clever
3 ． 263 4 ． 1 12588 2 12337 3 12339
四、 1 ． a+b+c SQRT R 2
2 ． start+m-1 result>=k not(find) 2*k-I m-1
C
B
D
E
A
PAGE
1第十二届全国青少年信息学奥林匹克
联赛复赛试题
（NOIP2006提高组）
竞赛时间：2006年11月18日上午8：30—11：30
试题名称 energy budget jsp digital
目录 energy budget jsp digital
输入文件名 energy.in budget.in jsp.in digital.in
输出文件名 energy.out budget.out jsp.out digital.out
试题类型非交互式程序题非交互式程序题非交互式程序题非交互式程序题
附加文件无无无无
时限 1秒 1秒 1秒 1秒
关于竞赛中不同语言使用限制的说明
一．关于使用Pascal语言与编译结果的说明
1．对于Pascal语言的程序，当使用IDE和fpc编译结果不一致时，以fpc的编译结果为准。
2．允许使用数学库(uses math子句)，以及ansistring。但不允许使用编译开关（最后测试时pascal的范围检查开关默认关闭：{$R-,Q-,S-}），也不支持与优化相关的选项。
二．关于C++语言中模板使用的限制说明
1．允许使用的部分：
标准容器中的布尔集合，迭代器，串，流。
相关的头文件：
2．禁止使用的部分：
序列：vector，list，deque
序列适配器：stack, queue, priority_queue
关联容器：map, multimap, set, multiset
拟容器：valarray
散列容器：hash_map, hash_set, hash_multimap, hash_multiset
所有的标准库算法
相关头文件：
　
1．能量项链
(energy.pas/c/cpp)
【问题描述】
在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为（Mars单位），新产生的珠子的头标记为m，尾标记为n。
需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。
例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号表示两颗珠子的聚合操作，(j k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：
(4 1)=10*2*3=60。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
((4 1) 2) 3）=10*2*3+10*3*5+10*5*10=710。
【输入文件】
输入文件energy.in的第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。
至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。
【输出文件】
输出文件energy.out只有一行，是一个正整数E（E≤2.1*109），为一个最优聚合顺序所释放的总能量。
【输入样例】
4
2 3 5 10
【输出样例】
710
2．金明的预算方案
(budget.pas/c/cpp)
【问题描述】
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件附件
电脑打印机，扫描仪
书柜图书
书桌台灯，文具
工作椅无
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：
v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）
请你帮助金明设计一个满足要求的购物单。
【输入文件】
输入文件budget.in 的第1行，为两个正整数，用一个空格隔开：
N m
（其中N（<32000）表示总钱数，m（<60）为希望购买物品的个数。）
从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数
v p q
（其中v表示该物品的价格（v<10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号）
【输出文件】
输出文件budget.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。
【输入样例】
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
【输出样例】
2200
3．作业调度方案
(jsp.pas/c/cpp)
【问题描述】
我们现在要利用m台机器加工n个工件，每个工件都有m道工序，每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。
每个工件的每个工序称为一个操作，我们用记号j-k表示一个操作，其中j为1到n中的某个数字，为工件号；k为1到m中的某个数字，为工序号，例如2-4表示第2个工件第4道工序的这个操作。在本题中，我们还给定对于各操作的一个安排顺序。
例如，当n=3，m=2时，“1-1，1-2，2-1，3-1，3-2，2-2”就是一个给定的安排顺序，即先安排第1个工件的第1个工序，再安排第1个工件的第2个工序，然后再安排第2个工件的第1个工序，等等。
一方面，每个操作的安排都要满足以下的两个约束条件。
(1) 对同一个工件，每道工序必须在它前面的工序完成后才能开始；
(2) 同一时刻每一台机器至多只能加工一个工件。
另一方面，在安排后面的操作时，不能改动前面已安排的操作的工作状态。
由于同一工件都是按工序的顺序安排的，因此，只按原顺序给出工件号，仍可得到同样的安排顺序，于是，在输入数据中，我们将这个安排顺序简写为“1 1 2 3 3 2”。
还要注意，“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时，有可能排在后面的某个操作比前面的某个操作先完成。
例如，取n=3,m=2，已知数据如下：
工件号机器号/加工时间
工序1 工序2
1 1/3 2/2
2 1/2 2/5
3 2/2 1/4
则对于安排顺序“1 1 2 3 3 2”，下图中的两个实施方案都是正确的。但所需要的总时间分别是10与12。
　
当一个操作插入到某台机器的某个空档时（机器上最后的尚未安排操作的部分也可以看作一个空档），可以靠前插入，也可以靠后或居中插入。为了使问题简单一些，我们约定：在保证约束条件（1）（2）的条件下，尽量靠前插入。并且，我们还约定，如果有多个空档可以插入，就在保证约束条件（1）（2）的条件下，插入到最前面的一个空档。于是，在这些约定下，上例中的方案一是正确的，而方案二是不正确的。
显然，在这些约定下，对于给定的安排顺序，符合该安排顺序的实施方案是唯一的，请你计算出该方案完成全部任务所需的总时间。
【输入文件】
输入文件jsp.in 的第1行为两个正整数，用一个空格隔开：
m n
（其中m（<20）表示机器数，n（<20）表示工件数）
第2行：个用空格隔开的数，为给定的安排顺序。
接下来的2n行，每行都是用空格隔开的m个正整数，每个数不超过20。
其中前n行依次表示每个工件的每个工序所使用的机器号，第1个数为第1个工序的机器号，第2个数为第2个工序机器号，等等。
后n行依次表示每个工件的每个工序的加工时间。
可以保证，以上各数据都是正确的，不必检验。
【输出文件】
输出文件jsp.out只有一个正整数，为最少的加工时间。
【输入样例】
2 3
1 1 2 3 3 2
1 2
1 2
2 1
3 2
2 5
2 4
【输出样例】
10
4．2k进制数
（digital.pas/c/cpp）
【问题描述】
设r是个2k 进制数，并满足以下条件：
（1）r至少是个2位的2k 进制数。
（2）作为2k 进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。
（3）将r转换为2进制数q后，则q的总位数不超过w。
在这里，正整数k（1≤k≤9）和w（k≤30000）是事先给定的。
问：满足上述条件的不同的r共有多少个？
我们再从另一角度作些解释：设S是长度为w 的01字符串（即字符串S由w个“0”或“1”组成），S对应于上述条件（3）中的q。将S从右起划分为若干个长度为k 的段，每段对应一位2k进制的数，如果S至少可分成2段，则S所对应的二进制数又可以转换为上述的2k 进制数r。
例：设k=3，w=7。则r是个八进制数（23=8）。由于w=7，长度为7的01字符串按3位一段分，可分为3段（即1，3，3，左边第一段只有一个二进制位），则满足条件的八进制数有：
2位数：高位为1：6个（即12，13，14，15，16，17），高位为2：5个，…，高位为6：1个（即67）。共6+5+…+1=21个。
3位数：高位只能是1，第2位为2：5个（即123，124，125，126，127），第2位为3：4个，…，第2位为6：1个（即167）。共5+4+…+1=15个。
所以，满足要求的r共有36个。
【输入文件】
输入文件digital.in只有1行，为两个正整数，用一个空格隔开：
k W
【输出文件】
输出文件digital.out为1行，是一个正整数，为所求的计算结果，即满足条件的不同的r的个数（用十进制数表示），要求最高位不得为0，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。
（提示：作为结果的正整数可能很大，但不会超过200位）
【输入样例】
3 7
【输出样例】
36第五届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题
（普及组）
（PASCAL 语言竞赛用时：2小时）
●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●
一、选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，共30分）
1．微机内的存储器的地址是以（）编址的。
A．二进制位 B．字长 C．字节 D．微处理器的型号
2．下列诸因素中,对微机工作影响最小的是（）。
A．尘土 B．噪声 C．温度 D．湿度
3．在24*24 点阵的字库中，汉字“一 ”与“编”的字模占用字节数分别是（）。
A．32、32 B．32、72 C．72、72 D．72、32
4．将DOS 系统盘插入A驱动器启动机器，随后使用一批应用软件，在此过程中，DOS 系统盘（）。
A．必须始终插入在A 驱动器中 B．不必再用
C．可能有时要插入 A驱动器中 D．可能有时要插入B 驱动器中
5．以下DOS命令中，有可能在磁盘上建立子目录的是（）
A．type B．dir C．xcopy D．cd
6．在CONFIG.SYS 文件中，装入特定可安装设备驱动程序的命令是（）。
A．buffer B．files C．driver D．device
7．计算机能直接执行的指令包括两部分，它们是（）。
A．源操作数与目标操作数 B．操作码与操作数
C．ASCII码与汉字代码 D．数字与字符
8．在微机中，通用寄存器的位数是（）。
A．8位 B．16位 C．计算机字长 D．32位
9．在计算机中，ASCII码是（）位二进制代码。
A．8 B．7 C．12 D．16
10．计算机的软件系统通常分为（）。
A．系统软件与应用软件 B．高级软件与一般软件
C．军用软件与民用软件 D．管理软件与控制软件
11．执行DOS 命令：c:\ATTRIB A: *.* 的功能是（）。
A．查看A盘上所有文件属性 B．查看A盘上当前目录中所有文件属性
C．查看A盘上所有系统文件属性 D．删去A盘上所有隐含文件的属性
12．执行下列DOS命令，效果等价的是（）组。
A．COPY *.FOR 与 COPY *.FOR CON
B．COPY A: *.* B: 与 XCOPY A: *.* B:
C．COPY FILE1.TXT + FILE2.TXT 与 COPY FILE2.TXT +FILE1.TXT
D．XCOPY A: *.* B :/S 与 DISKCOPY A: B:
13．已知小写字母“m”的十六进制的ASCⅡ码值是6D，则小写字母“c”的十六进制数的ASCII码值是（）。
A．98 B．62 C．99 D．63
14．计算机中的数有浮点与定点数两种，其中用浮点数表示的数，通常由（）这两部分组成。
A．指数与基数 B．尾数与小数 C．阶码与尾数 D．整数与小数
15．下列文件名中，属于DOS 中的保留设备名的为（）。
A．aux B．Com C．Con1 D．prn1
16．启动计算机引导DOS是将操作系统（）。
A．从磁盘调入中央处理器 B．从内存储器调入高速缓冲存储器
C．从软盘调入硬盘 D．从系统盘调入内存储器
17．十进制算术表达式：3*512 + 7*64 + 4*8 + 5的运算结果，用二进制表示为（）。
A．10111100101 B．11111100101 C．11110100101 D．11111101101
18．组成“教授”（jiao shou）,“副教授”（fu jiao shou）与“讲师”(jiang shi)这三个词的汉字，在GB2312-80字符集中都是一级汉字，对这三个词排序的结果是（）。
A．教授、副教授、讲师 B．副教授、教授、讲师
C．讲师、副教授、教授 D．副教授、讲师、教授
19．不同的计算机，其指令系统也不相同，这主要取决于（）。
A．所用的操作系统 B．系统的总体结构
C．所用的 CPU D．所用的程序设计语言
20．对具有隐含属性（H）的当前目录下的文件ab.txt，能成功执行的DOS命令是（）
A．TYPE ab.txt B．COPY ab.txt xy.txt
C．DIR ab.txt D．REN ab.txt xy.txt
二、回答问题（10分）
在磁盘的目录结构中，我们将与某个子目录有关联的目录数称为度。例如下图
该图表达了A盘的目录结构：D1，Dll，…，D2均表示子目录的名字。在这里，根目录的度为2，D1子目录的度为3，D11子目录的度为4，D12，D2，D111，D112，D113的度均为1。不考虑子目录的名字，则可简单的图示为如下所示的树结构：
若知道一个磁盘的目录结构中，度为2的子目录有2个，度为3的子目录有1个，度为4的子目录有3个。
试问：度为1的子目录有几个？
三、公式推导（10分）
根据Nocomachns定理，任何一个正整数n的立方一定可以表示成n个连续的奇数的和。
例如：
13＝ 1
23＝ 3＋ 5
33＝ 7＋ 9 ＋11
43= 13+15+17+19
在这里，若将每一个式中的最小奇数称为X，那么当给出n之后，请写出X与n之间的关系表达式：
四、阅读程序，并写出程序的正确运行结果：（每题15分，共30分）
1．Program excpl;
var
x，y，y1，jk，j1，g，e：Integcr；
a：array[l．．20]of 0．．9；
begin
x：＝3465； y：＝264； jk：＝20；
for j1：= 1 to 20 do a[j1]：＝ 0；
while y＜＞0 do
begin
y1：=y mod 10；
y：= y div 10；
while y1＜＞0 do
begin
g：=x；
for e：＝ Jk downto 1 do
begin
g：＝g＋a[e]；
a[e ]：= g mod 10；
g：= g div 10
end;
y1：＝ y1－ 1
end；
jk：＝jk-1
end；
j1=1；
while a[j1]＝0 do j1：=J1+1；
for Jk：=j1 to 20 do write(a[jk]:4)
WRITELN
End.
程序输出结果为：_________________________________
2．program excp2
var
i，j：integer;；
a ：array[1．．14] of integer；
procedure sw(i1，j1：Integer)；
var k1： Integer；
begin
for k1：= 1 to（j1- i1+1） div 2 do
begin
a[i1＋k1-1]：=a[i1＋ k1－1]＋a[j1－k1+1]；
a[j1－k1＋1]：＝a[i1＋k1－1]－a[j1－k1+1];
a[i1+k1－1]：=a[i1-k1+1]－a[J1－k1+1]；
end；
end；
begin
j：=211；
for i:=1 to 14 do
begin
a[i]:=i; J：=j-i
end；
sw（1,4）； sw（ 5，10）;
Sw（11，14）；sw（1，14）；
For i：=1 to 14 do
begin
If j mod I=1 then write (a[i]:3)；
j：=j－a[i]；
end;
WRITElN
end.
程序运行结果是：________________________________________
五、根据题意，将程序补充完整（20分）
[问题描述]
下面程序的功能是从键盘读取A，B数组的元素，A，B数组均已从小到大排好序（无相同元素），现将A，B合并为数组C，同样要求数组C也是从小到大排好序（有相同元素时只保留一个）。
程序中N表示数组A，B的长度，i，j，k分别表示数组A，B，C的取数或存数的指针。
[程序清单]
program excp3;
const n=8; m=2*n;
type arr1=array[1..n]of integer;
arr2=array[1..m]of integer;
var a,b :arr1; c :arr2; i,j,k :integer;
procedure copy(x:arr1;var y:arr2;var i,j:integer);
begin i:=i+1;y[i]:=x[j];j:=j+1; end;
begin
for i:=1 to n do read(a[i]);readln;
for i:=1 to n do read(b[i]);readln;
i:=1;j:=1;___________①________
while__________②__________do.
if a[i]else if b[j]else begin
copy(a,c,k,i);
__________③__________
end;
while__________④___________do copy(a,c,k,i);
while__________⑤___________do copy(b,c,k,j);
for i:=1 to k do write (c[i]:4);
writeln;
end.
PAGE
5NOIP2004解题报告(普及组)
宝坻区牛道口二中：唐虎
第一题：unhappy；
【算法分析】
此题主要考察选手的编程基本能力。做题时，可先求出七天内每天学校和妈妈安排的学习时间总和存于数组中，然后设置一个循环对数组中的每个值进行处理，若学习时间超过8小时，则说明有不高兴的天，做上标记；若这一天的学习时间超过上一次不高兴的天学习的时间，说明这一天更不高兴，则做上标记。最后若没有不高兴的天，输出“0”，否则输出做上标记的那一天的代码。
【数据结构】
var a:array[1..7]of integer;
【程序清单】
program unhappy;
var a:array[1..7]of integer;
i,x,y,sum,point:integer;
yes:boolean;
f1,f2:text;
begin
assign(f1,'unhappy.in');reset(f1); {输入文件名"unhappy.in"}
assign(f2,'unhappy.out');rewrite(f2); {输出文件名"unhappy.out"}
for i:=1 to 7 do
begin
readln(f1,x,y);
a[i]:=x+y
end; {读入数据，将每天要学习的时间存于数组a中}
yes:=true; {若有不高兴的天，即a中没有超过8的元素，布尔型变量yes置真值}
sum:=0;
for i:=1 to 7 do {求出最不高兴的天数，存于point中}
if (a[i]>8)then
begin
yes:=false;
if a[i]>sum then
begin sum:=a[i];point:=i;end;
end;
if yes then writeln(f2,0)
else writeln(f2,point);
close(f1);
close(f2)
end.
第二题：peanuts；
【算法分析】
乍一看此题，就会发现，穷举、搜索的方法对此题都不适用，因为题目中已明确给出了摘豆子的规则。其实，我们只需要根据题目给出的规则，编程序模拟摘豆子的过程就可以了。首先，定义一个整型的二维数组a存储每个格子中的豆子数目，然后进行摘豆子。
设置一个二层循环求出含有最多豆子的格子的坐标，由数学知识可知，从(x1,y1)到(x2,y2)需要的单位时间为|x1-x2|+|y1-y2|，因此由当前位置（x，y）跳到含有最多豆子的格子（x1，y1）内摘下豆子并回到路边所需的时间为step=|x-x1|+|y-y1|+1+x1，接下来判断step与剩余的时间p的大小关系。若step<=p则说明有足够的时间去摘豆子，则去摘：具体步骤（剩余时间p：=p-|x-x1|+|y-y1|-1；当前点的坐标跳入（x1，y1）；摘下的总豆子数sum：=sum+a[x，y]，a[x，y]：=0；表示此格子内的豆子已被摘没）；若step>p，说明没有足够多的时间跳过去摘下豆子再回到路边，因此只能回到路边而不能去摘豆子了。
重复此摘法即可得出最后结果。
【数据结构】
var a:array[0..20，0..20]of integer; {存每个格子内的豆子数}
【程序清单】
program peanuts;
var a:array[0..20,0..20]of integer; {存每个格子内的豆子数}
m,n,k,step,i,j,x,y,x1,y1,sum:integer;
f1,f2:text;
yes:boolean; {存是否有豆子可摘}
begin
assign(f1,'peanuts.in');reset(f1); {输入文件名"peanuts.in"}
assign(f2,'peanuts.out');rewrite(f2); {输出文件名"peanuts.out"}
readln(f1,m,n,k);
for i:=1 to m do
begin
for j:=1 to n do read(f1,a[i,j]);readln(f1)
end; {读入数据}
x:=0;y:=0;yes:=true;sum:=0; {初始化,x,y存当前结点坐标}
repeat
x1:=0;y1:=0;
for i:=1 to m do
for j:=1 to n do
if a[i,j]>a[x1,y1] then begin x1:=i;y1:=j end; {求出含有最多豆子数的格子坐标}
if y=0 then y:=y1;
step:=abs(x-x1)+abs(y-y1)+x1+1; {求出从原点到含豆子数最多点内摘豆子并回到路边所需单位时间}
if (kif yes then
begin
sum:=sum+a[x1,y1];
k:=k-abs(x-x1)-abs(y-y1)-1;
x:=x1;y:=y1;a[x,y]:=0;
end; {摘豆子}
until yes=false;
writeln(f2,sum);
close(f1);close(f2)
end.
第三题：fbi；
【算法分析】
此题的后序遍历适合用递归算法完成。由题目可知，输入数据给出的字符为所要遍历的fbi树的叶结点代码，又因为字符串的长度为2的整数次幂，故此fbi树为完全二叉树。由于题中明确规定：子符串中的字符都是‘0’，为B串；都是‘1’，为I串；既有‘0’又有‘1’，为F串。即：二叉树的子结点都是B，父结点为B；子结点都是I，父结点为I；既有I又有B，父结点为F。因此，根据树的子结点可以求出父结点。我们要做的是根据子结点后序遍历二叉树。基本算法为：
procedure bianli（x，y：integer）；//遍历过程；x，y：为子结点在数组a中的位置。
begin
if x=y then 输出叶结点 //结束递归条件，结点为一个字符。
else begin
求出父结点；
遍历左子树；
遍历右子树；
输出父结点；
end；
end； //递归算法，详情请参阅程序清单。
【数据结构】
var a:array[1..10000]of '0'..'1';
【程序清单】
program fbi;
var a:array[1..10000]of '0'..'1';
n,i,l:integer;
f1,f2:text;
treeb,treei:boolean;
tree:char;
procedure bianli(x,y:integer); {递归过程，x,y为所要遍历的树的叶结点在数组a中位置}
begin
if x=y then case a[x] of
'0':write(f2,'B');
'1':write(f2,'I');
end {输出叶结点}
else begin
bianli(x,x+(y-x+1) div 2-1); {遍历左子树}
bianli(x+(y-x+1)div 2,y); {遍历右子树}
treei:=false;treeb:=false;
for i:=x to y do if a[i]='0' then treeb:=true else treei:=true; {求出树的父结点}
if treei and treeb then tree:='F'
else begin
if treei then tree:='I';
if treeb then tree:='B' {输出父结点}
end;
write(f2,tree);
end
end;
begin
assign(f1,'fbi.in'); reset(f1); {输入文件名"fbi,in"}
assign(f2,'fbi.out');rewrite(f2); {输出文件名"fbi.out"}
readln(f1,n);l:=1;
for i:=1 to n do l:=l*2;
for i:=1 to l do read(f1,a[i]); {读入数据,l为字符串长度}
bianli(1,l);writeln(f2);
close(f1); close(f2)
end.
第四题：martian;
【算法分析】
此题难度较大。
此题的常规算法为根据题中给出的组合算出其表示的值，加上要加的数m，最后“翻译”成组合。但这种方法会受到时间限制，当数据规模大一些时，会超时或无法得出结果。使用好一点的算法是利用数学中的组合知识计算出所给的组合所表示的数存于高精度数中，再进行处理，但当数据规模达到100甚至10000时，从存储空间上或从时间上来说都是不可能实现的。
这就启发我们寻求更为简洁有效的算法。
我们以n为例，从小到大的组合为：
第n位第n-1位第n-2位 . . . 第x 位 . . . 第1位序列在组合中的位置数
1 2 3 . . . x . . . n 1
1 2 3 . . . . . . . . . n-1 2
1 2 3 . . . . . . . . . n-2 3
.
.
.
n n-1 n- 2 . . . . . . . . . 1 n!
对于给定的整数n，共有n!序列,对应于1打头的序列有（n-1）！个。
对序列中任一位x(x组合中前i位（a[I]、、a[1]）所表示的数=（a[I]在a[1、、I]中的位置-1）×(I-1)!+（a[I-1]在a[1、、I-1]中的位置-1）×(I-2)!+、、+ 1；（后面源程序代码中“前p位”指最低位开始的p位；“x在s中的位置”指的是数s在集合中或某一部分数中排序后的位置，如3在[2，3，4，1，0]中的位置为4。），如：
1 5 3 4 2 前3位表示的数：
（2-1）×2！+（2-1）×1！+（1-1）×0！+1=4
首先，我们求出m使组合数需要变动的最小长度p求出，然后求出组合前p位表示的数s，m：=m+s；若数m仍能用长度为p的组合数表示出，即原组合数+m后所得的新组合数不需要进位，就将a[1]、、a[p]之间的数（包括a[1]，a[p]）构成一个集合，将集合中的p个数重新填入 a[1]、、a[p]，使前p位所表示的数等于m；若m>p！数m不能用长度为p的组合数表示出，即原组合数+m后所得的新组合数需要进位，则求出需要进位的数在数组a中的位置p1，将a[1]、、a[p1]之间的数（包括a[1]，a[p1]）重新构成一个集合。a[p1]：=集合中比它在集合中的位置大1的数，a[p1]出集合，在p1-1、、p+1之间依次填入集合中的最小数，填过的数出集合，m：=m-p！将集合中剩下的p个数重新填入 a[1]、、a[p]，使第p位到第1位所表示的数等于m。新组合数已构成，详情参见程序清单。
求组合第p位到第1位表示的数详细算法：
function jisuan(p:integer):longint;
begin
for i:=p downto 1 do
begin
x:=只变动组合前（p-1）位能表示的最大数；
s:=s+((a[i]在集合中位置)-1)*x;
a[I]出集合；
end;
jisuan:=s+1；
end；
将集合中的数填入a[p]、、a[1]中，使前p位表示的数为m；详细算法：
procedure fill(p:integer;m:longint);
begin
for i:=p downto 2 do
begin
s：=只变动前（p-1）位能表示的最大数；
if m mod s=0 then begin a[i]:=集合中位置为(m div s)的数;m:=s; end
else begin a[i]:=集合中位置为(m div s+1)的数;m:=m mod s end;
a[I]出集合；
end;
a[1]:=集合中最后剩下的数;
end;
【数据结构】
var a:array[1..10000]of 0..10000;//存组合中的数；
b:array[1..10000]of 0..1; //表示集合；
【程序清单】
program martian;
var m,n,p1,p:longint;
i,x,s,max:longint;
yes:boolean;
a:array[1..10000]of 0..10000;
b:array[1..10000]of 0..1;
f1,f2:text;
function jiecheng(p:integer):longint;
var i,s:longint;
begin
s:=1;for i:=1 to p do s:=s*i;jiecheng:=s
end; {计算阶乘函数}
function find1(p:integer):integer;
var i,s:integer;
begin
s:=0;
for i:=1 to p do
if b[i]=1 then inc(s);
find1:=s;
end; {求出数p在集合中位置}
function find2(p:integer):integer;
var i,s:integer;
begin
s:=0;i:=0;
while i

展开更多......

收起↑

请用微信扫码

信息学奥赛历年试题及答案

信息学奥赛历年试题及答案