第十一届全国青少年信息学奥林匹克联赛复赛提高组解题报告

第十一届全国青少年信息学奥林匹克联赛（NOIP2005）

复赛提高组解题报告

题一 谁拿了最多奖学金

【问题描述】

某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同：

1) 院士奖学金，每人8000元，期末平均成绩高于80分（>80），并且在本学期内发表1篇或

1篇以上论文的学生均可获得；

2) 五四奖学金，每人4000元，期末平均成绩高于85分（>85），并且班级评议成绩高于80

分（>80）的学生均可获得；

3) 成绩优秀奖，每人2000元，期末平均成绩高于90分（>90）的学生均可获得； 4) 西部奖学金，每人1000元，期末平均成绩高于85分（>85）的西部省份学生均可获得； 5) 班级贡献奖，每人850元，班级评议成绩高于80分（>80）的学生干部均可获得；

只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是87分，班级评议成绩82分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是4850元。

现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。 【输入文件】

输入文件scholar.in的第一行是一个整数N（1 <= N <= 100），表示学生的总数。接下来的N行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过20的字符串（不含空格）；期末平均成绩和班级评议成绩都是0到100之间的整数（包括0和100）；是否是学生干部和是否是西部省份学生分别用一个字符表示，Y表示是，N表示不是；发表的论文数是0到10的整数（包括0和10）。每两个相邻数据项之间用一个空格分隔。 【输出文件】

输出文件scholar.out包括三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。第三行是这N个学生获得的奖学金的总数。 【样例输入】 4

YaoLin 87 82 Y N 0 ChenRuiyi 88 78 N Y 1 LiXin 92 88 N N 0

- 1 -

ZhangQin 83 87 Y N 1 【样例输出】 ChenRuiyi 9000 28700 【题目概述】

已知每个学生的个人信息，求出获得奖学金最多的学生姓名、金额，以及全部奖学金金额。 模拟 【算法分析】

其中涉及简单的字符处理，特别要注意数据类型的应用。如：学生姓名可采用char和string相结合的方法处理，奖学金金额用longint较为适宜。 【程序】

program scholar;

var name:array[1..100] of string;

a1,a2,a5:array[1..100] of longint; a3,a4:array[1..100] of char; n,i,max,total,p:longint; maxname:string; ch:char; f:text; begin

assign(f,'scholar.in');reset(f); readln(f,n); for i:=1 to n do begin

read(f,ch);

while ch<>' ' do begin

name[i]:=name[i]+ch; read(f,ch); end;

readln(f,a1[i],a2[i],ch,a3[i],ch,a4[i],ch,a5[i]); end;

close(f);

for i:=1 to n do begin p:=0;

if (a1[i]>80) and (a5[i]>=1) then inc(p,8000); if (a1[i]>85) and (a2[i]>80) then inc(p,4000); if (a1[i]>90) then inc(p,2000);

if (a1[i]>85) and (a4[i]='Y') then inc(p,1000); if (a2[i]>80) and (a3[i]='Y') then inc(p,850); if p>max then begin

- 2 -

max:=p;

maxname:=name[i]; end;

inc(total,p); end;

assign(f,'scholar.out');rewrite(f); writeln(f,maxname); writeln(f,max); writeln(f,total); close(f); end.

题二 过河

【问题描述】

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，??，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。 【输入文件】

输入文件river.in的第一行有一个正整数L（1 <= L <= 10），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。 【输出文件】

输出文件river.out只包括一个整数，表示青蛙过河最少需要踩到的石子数。 【样例输入】 10 2 3 5 2 3 5 6 7 【样例输出】 2

【数据规模】

- 3 -

9

对于30%的数据，L <= 10000； 对于全部的数据，L <= 10。 【题目概述】

在一条长为L数轴上有若干障碍点，每次前进距离为S到T之间的任意正整数（包括S,T），求走过L或大于L的距离，遇到最少的障碍点。 【算法分析】

看到题目首先想到的是时间复杂度为O(L)的递推算法。但是L的上限为10^9，这种算法显然是不行的。仔细思考，可以得到下面的结论：

存在N0，当n> N0时，n可以由若干S到T之间的正整数（包括S,T）组成。

因此，将障碍点按升序排列，当两相邻障碍点之间距离较大时，可适当缩小两障碍点之间距离，但不影响最终结果。

根据上述结论，改进递推算法。由于障碍点之间距离大大缩减，算法的复杂度是可以承受的。 特别地，当S=T时需要单独处理。 【程序】

program river; const max=105;

var a,a1:array[0..101] of longint; b:array[0..100] of boolean; c,d:array[0..10000] of longint; l,s,t,m,ans,low,i,j,k,temp:longint; flag:boolean; f:text; procedure init; begin

assign(f,'river9.in');reset(f); readln(f,l); readln(f,s,t,m);

for i:=1 to m do read(f,a[i]); a[0]:=0;a[m+1]:=l; for i:=1 to m-1 do for j:=i+1 to m do if a[i]>a[j] then begin

temp:=a[i];a[i]:=a[j];a[j]:=temp; end;

close(f); end;

procedure work1; begin

for i:=1 to m do

if a[i] mod s=0 then inc(ans); end;

procedure work2; begin

fillchar(b,sizeof(b),false);

- 4 -

9

b[0]:=true;

for i:=s to t do begin

for j:=0 to 100 do if b[j] then begin

k:=1;

while k*i+j<=100 do begin

b[k*i+j]:=true; inc(k); end; end; end;

for i:=1 to 100 do begin

flag:=true;

for j:=0 to t-1 do

if not b[i+j] then begin flag:=false;break;end; if flag then begin low:=i; break; end; end;

if low

a1[i]:=(a[i]-a[i-1]-low) mod low+a1[i-1]+low; end; a:=a1;

for i:=1 to m do d[a[i]]:=1; l:=a[m+1];

for i:=1 to l+t-1 do c[i]:=max; for i:=1 to l+t-1 do for j:=s to t do

if (i-j>=0) and (c[i]>c[i-j]+d[i]) then c[i]:=c[i-j]+d[i]; ans:=max;

for i:=l to l+t-1 do

if ans>c[i] then ans:=c[i]; end; begin

init;

if s=t then work1 else work2;

- 5 -

assign(f,'river.out');rewrite(f); writeln(f,ans); close(f); end.

题三 篝火晚会

【问题描述】

佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有n个同学，编号从1到n。一开始，同学们按照1，2，??，n的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。

佳佳可向同学们下达命令，每一个命令的形式如下：(b1, b2,... bm -1, bm)

这里m的值是由佳佳决定的，每次命令m的值都可以不同。这个命令的作用是移动编号是b1，b2，?? bm –1，bm的这m个同学的位置。要求b1换到b2的位置上，b2换到b3的位置上，??，要求bm换到b1的位置上。执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置，那么这个命令的代价就是m。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？ 【输入文件】

输入文件fire.in的第一行是一个整数n（3 <= n <= 50000），表示一共有n个同学。其后n行每行包括两个不同的正整数，以一个空格隔开，分别表示编号是1的同学最希望相邻的两个同学的编号，编号是2的同学最希望相邻的两个同学的编号，??，编号是n的同学最希望相邻的两个同学的编号。 【输出文件】

输出文件fire.out包括一行，这一行只包含一个整数，为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望，则输出-1。 【样例输入】 4 3 4 4 3 1 2 1 2

【样例输出】 2

- 6 -

【数据规模】

对于30%的数据，n <= 1000； 对于全部的数据，n <= 50000。 【题目概述】

根据一定的移动规则，将初始圆环转化为满足一定条件的目标圆环。 【算法分析】

从第一个人处断开，将圆环的问题转化为序列的问题。如果可以，求出目标序列。求出目标序列复杂度O(n).

求出目标序列右移0至n-1位置时，不需要移动的人数。将目标序列反转，再求出目标序列右移0至n-1位置时，不需要移动的人数。不需要移动的人数最大等价于需要移动的人数最小。复杂度O(n)。 【程序】

program fire;

var a:array[1..50000] of longint;

b:array[1..50000,1..2] of longint; d:array[1..50000] of longint; w:array[0..50000] of longint; n,ans,i,j,t,max:longint; flag:boolean; f:text; procedure init; begin

assign(f,'fire.in');reset(f); readln(f,n); for i:=1 to n do begin

readln(f,b[i,1],b[i,2]); inc(d[b[i,1]]); inc(d[b[i,2]]); end;

close(f);

for i:=1 to n do

if d[i]<>2 then begin flag:=false;exit;end; end;

procedure circle; begin

a[1]:=1;a[2]:=b[1,1]; for i:=3 to n do

if b[a[i-1],1]<>a[i-2] then a[i]:=b[a[i-1],1] else a[i]:=b[a[i-1],2];

if a[n]<>b[1,2] then flag:=false; end;

procedure min; begin

fillchar(w,sizeof(w),0);

- 7 -

for i:=1 to n do

inc(w[(a[i]-i+n) mod n]); for i:=0 to n-1 do

if max

t:=a[i];a[i]:=a[n+1-i];a[n+1-i]:=t; end;

fillchar(w,sizeof(w),0); for i:=1 to n do

inc(w[(a[i]-i+n) mod n]); for i:=0 to n-1 do

if max

flag:=true; init;

if flag then circle; if flag then min;

assign(f,'fire.out');rewrite(f);

if flag then writeln(f,ans) else writeln(f,-1); close(f); end.

题四 等价表达式

【问题描述】

明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。

这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？

这个选择题中的每个表达式都满足下面的性质：

1． 表达式只可能包含一个变量‘a’。

2． 表达式中出现的数都是正整数，而且都小于10000。

3． 表达式中可以包括四种运算‘+’（加），‘-’（减），‘*’（乘），‘^’（乘幂），

以及小括号‘(’，‘)’。小括号的优先级最高，其次是‘^’，然后是‘*’，最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符‘+’，‘-’，‘*’，‘^’以及小括号‘(’，‘)’都是英文字符）

- 8 -

4． 幂指数只可能是1到10之间的正整数（包括1和10）。 5． 表达式内部，头部或者尾部都可能有一些多余的空格。 下面是一些合理的表达式的例子：

((a^1) ^ 2)^3，a*a+a-a，((a+a))，9999+(a-a)*a，1 + (a -1)^3，1^10^9?? 【输入文件】

输入文件equal.in的第一行给出的是题干中的表达式。第二行是一个整数n（2 <= n <= 26），表示选项的个数。后面n行，每行包括一个选项中的表达式。这n个选项的标号分别是A，B，C，D??

输入中的表达式的长度都不超过50个字符，而且保证选项中总有表达式和题干中的表达式是等价的。 【输出文件】

输出文件equal.out包括一行，这一行包括一系列选项的标号，表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列，而且之间没有空格。 【样例输入】 ( a + 1) ^2 3

(a-1)^2+4*a a + 1+ a

a^2 + 2 * a * 1 + 1^2 + 10 -10 +a -a 【样例输出】 AC

【数据规模】

对于30%的数据，表达式中只可能出现两种运算符‘+’和‘-’；

对于其它的数据，四种运算符‘+’，‘-’，‘*’，‘^’在表达式中都可能出现。 对于全部的数据，表达式中都可能出现小括号‘(’和‘)’。 【题目概述】

判断两表达式是否等价。 【算法分析】

用栈的方法求表达式的值是经典的算法。考虑到多项式的处理比较麻烦，不妨对变量a进行多次赋值以判断表达式是否等价。 值得注意，由于进行数值运算，采用哪种数据类型成为程序是否正确的关键。下面的程序，采取mod m的方法，其中m为任意正整数。当对a多次赋值，且m取不同的较大的正整数时，可以保证算法的正确性。 【程序】

program equal;

const max=maxlongint;

const com:array[1..7,1..7] of char=(('>','>','<','<','<','>','>'), ('>','>','<','<','<','>','>'), ('>','>','>','<','<','>','>'), ('>','>','>','>','<','>','>'), ('<','<','<','<','<','=','X'),

- 9 -

('>','>','>','>','X','>','>'), ('<','<','<','<','<','X','X'));

var there:char;

oped:array[1..1000] of longint; optr:array[1..1000] of char; ned,ntr:int64; a,b:int64; flag:boolean;

s:array[0..26] of string;

value:array[0..26,-4..4] of int64; ans:array[0..26] of boolean; n,i,j,p,q:longint; f:text;

function compare(w1,w2:char):char; var x1,x2:integer; begin

case w1 of

'+':x1:=1; '-':x1:=2; '*':x1:=3; '^':x1:=4; '(':x1:=5; ')':x1:=6; '#':x1:=7; end;

case w2 of

'+':x2:=1; '-':x2:=2; '*':x2:=3; '^':x2:=4; '(':x2:=5; ')':x2:=6; '#':x2:=7; end;

compare:=com[x1,x2]; end;

function operation(a:int64;there:char;b:int64):int64; var i:longint; begin

case there of

'+':operation:=(a+b) mod max; '-':operation:=(a-b) mod max; '*':operation:=(a*b) mod max;

'^':begin operation:=1;for i:=1 to b do

- 10 -

operation:=operation*a mod max;end; end; end;

function exp(s:string;aa:int64):int64; var i:int64; begin

s:=s+'#'; i:=1;

ned:=0;ntr:=1;

fillchar(oped,sizeof(oped),0); optr:='';

optr[1]:='#';flag:=false;

while not ((s[i]='#')and (optr[ntr]='#')) do begin

if s[i] in ['0'..'9'] then begin

if not flag then begin

ned:=ned+1;

oped[ned]:=ord(s[i])-ord('0'); flag:=true; inc(i); end else begin

oped[ned]:=oped[ned]*10+ord(s[i])-ord('0'); inc(i); end; end else

if s[i]='a' then begin

inc(ned);

oped[ned]:=aa; inc(i); end

else if s[i]=' ' then inc(i) else begin

flag:=false;

case compare(optr[ntr],s[i]) of

'<':begin ntr:=ntr+1;optr[ntr]:=s[i];inc(i);end; '>':begin

there:=optr[ntr];ntr:=ntr-1; b:=oped[ned];ned:=ned-1; a:=oped[ned];

- 11 -

oped[ned]:=operation(a,there,b); end;

'=':begin ntr:=ntr-1;inc(i);end; end; end; end;

exp:=oped[1]; end; begin

assign(f,'equal.in');reset(f); readln(f,s[0]); readln(f,n);

for i:=1 to n do readln(f,s[i]); fillchar(ans,sizeof(ans),true); close(f);

for i:=0 to n do if ans[i] then for j:=-4 to 4 do begin

value[i,j]:=exp(s[i],j);

if value[i,j]<>value[0,j] then begin ans[i]:=false;break;end; end;

assign(f,'equal.out');rewrite(f); for i:=1 to n do

if ans[i] then write(f,chr(ord('A')+i-1)); writeln(f); close(f); end.

- 12 -

本文来源：https://www.bwwdw.com/article/d4pr.html