noip2003提高组复赛试题分析

1、我看了李学武教授写的关于 NOIP 复赛的若干问题的思考一文，有很大触动，深刻感受到市信息学奥赛基础薄弱。我从事奥赛培训工作十三年，培训的学生在全国取得了一些好成绩，一块国际银牌，四块奥赛金牌，三块银牌，十块铜牌。我认为我有责任将培训工作介绍给同人和其他学校的同学，来推动市奥赛的发展。下面是我写的今年分区联赛高中组复赛的解题分析，供大家参考，并恳切希望能与“OIER”交流共勉。南开中学：300100，电子邮箱： 或 tj（.cn ）第一题：神经网络【试题分析】一、题意分析1、任务描述：从输入层开始，各节点按照传递公式，一层一层向下传递。输出输出层中信号大于零的节点号则输出 NULL。信号传递公

2、式：和信号大小。（节点由小到大）如果没有满足条件的编1）则此节点不是输出层；2）再判断此节点信号大于零则向下传递信号，将指向的节点入队（防止重复入队）。再出队再传递，直至全部出队。注意：1）输入层可以是输出层。2）信号传递公式中只减一次 Ui。【程序下面是】学生同学写的程序。NOIP 2003 Problem 1 by Xiao TianTest 1.5 :Program network; ConstInName=network.in;OutName=network.out; MM=100;VarInFile,OutFile:Text; C,U:Array1.MM Of Long; Map:A

3、rray1.MM,1.MM Of LongFlag:Array1.MM,1.MM Of;IsOut:Array1.MM OfQueue:Array1.MM Of Long;N,P,i,1,2,Head,Rear:Long;IsInQueue:Array1.MM OfIsNull:;BeginAssign(InFile,InName); Reset(InFile); ReadLn(InFile,N,P);For i:=1 To N Do ReadLn(InFile,Ci,Ui); FillChar(Flag,SizeOf(Flag),False);For i:=1 To P Do BeginRe

4、ad(InFile,1,2);ReadLn(InFile,Map1,2);Flag1,2:=True;End;Close(InFile);FillChar(IsOut,SizeOf(IsOut),True); FillChar(IsInQueue,SizeOf(IsInQueue),False); Head:=1; Rear:=1;For i:=1 To N Do BeginIf Ci0 Then Begin QueueRear:=i; Inc(Rear); IsInQueuei:=True;EndElse Ci:=-Ui;End;While Head0 Then BeginInc(Ci,Ma

5、pQueueHead,i*CQueueHead);If Not IsInQueuei Then QueueRear:=i; Inc(Rear); IsInQueuei:=True;End;BeginEnd;IsOutQueueHead:=False;End; Inc(Head);End;Assign(OutFile,OutName); Rewrite(OutFile); IsNull:=True;For i:=1 To N DoIf IsOuti ThenIf Ci0 ThenBeginWrin(OutFile,i, ,Ci);IsNull:=False; End;If IsNull Then

6、 WriClose(OutFile);n(OutFile,NULL);End.第二题：推理【试题分析】一、题意分析1、任务描述：M 个人参加，每人提供一句或多句证言，共P 句证言。其中 N 个人始终说假话，其余的人始终说真话。请你通过证言判断出谁是罪犯。证言形式如下：中出现的其它话，都不列入逻辑推理的内容。2、输入：第一行有三个整数，M（1M20）、N（1NM）和 P（1P100）：的明明的同学数，N 是其中始终说谎的人数，P 是证人的综述。M 是参加接下来M 行，每行是明明的一个同学的名字（英文字母组成，没有空格，全部大写）。往后有 P 行，每行开始是某个同学的名字，紧跟着一个冒号和一个空格

7、，后面是一句，符合前表中所列格式，每行不会好过 250 个字符。输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。3、输出：如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出 Cannot Determine；如果程序判断出没有人可能成为罪犯，则输出 Im二、问题分析sible。内容含义I am guilty.我是罪犯I am not guilty.我不是罪犯is guilty.是罪犯（表示某个同学的名字）isnot guilty.不是罪犯Today is.是（表示几，是 Monday Tuesday Wednesday Thursday Frid

8、ay Saturday Sunday 其中之一）1、根据题意可知可以利用枚举法完成。枚举罪犯和是几。满足 N 个人始终说谎话和M-N 个人始终说真话的条件，就可以确定罪犯。2、首先利用字符串操作将证言转化成计算机可表示的信息。1）定义 Guilty:Array1.MM,1.MM OfFillChar(Guilty,SizeOf(Guilty),0)eger;-1.1初值为 0Guiltyi,j=-1：表示第 i 个人说第 j 个人不是罪犯Guiltyi,j= 1：表示第i 个人说第 j 个人是罪犯其中包含 Guiltyi,i即第 i 个人说自己是不是罪犯注意：Guilty 不可以自相。2）定义

9、 WhatDay:Array1.MM,1.7 OfFillChar(WhatDay,SizeOf(WhatDay),False);WhatDayi,j:=True:表示第i 个人说过 j 是几言的人数。注意：有3、枚举罪犯和几，判断每句证言是真是假，统计说真可能又说过真话，又说过假话。4、根据题目要求输出罪犯或 Cannot Determine 或 Imsible。【程序下面是NOIP 2003Test 0.9Algorithm】学生同学写的程序。Problem 2 by Xiao Tian: Enumerate the guilty and whatthen we can determine

10、 whetherday it is today.each sentence istrueor not.Program logic; ConstInName=logic.in; OutName=logic.out;MM=20;DayS=(is,is,is,is,is,is,ie:Array1.7 Of String Monday. #Tuesday. # Wednesday. # Thursday. # Friday. # Saturday. #nday. #);cImsible=-1;cCannotDetermine=-2;VarInFile,OutFile:Text;M,N,P:eger;N

11、ame:Array1.MM Of String;Guilty:Array1.MM,1.MMWhatDay:Array1.MM,1.7OfOfeger;-1.1;i,j:eger;IsGuilty:Array1.MM OfAns,AnsC:eger;Procedure PrBegin(ID:eger);Assign(OutFile,OutName); Rewrite(OutFile);If ID=cImsible ThenWrin(OutFile,Imsible)Else If ID=cCannotDetermine ThenWriElse Wrin(OutFile,Cannot Determi

12、ne)n(OutFile,NameID);Close(OutFile);Halt;End;Procedure SetGuilty(CurID,NextID,NewValue: BeginIf GuiltyCurID,NextID=0 Then GuiltyCurID,NextID:=NewValueElse If GuiltyCurID,NextIDNewValueeger);ThenPr(cImsible);End;Procedure ReadS Varement;i,j,CurID,NextID:eger;CurStr,CurName:String;BeginFori:=1 To P Do

13、 Begin ReadLn(InFile,CurStr); CurStr:=CurStr+ #;CurName:=Copy(CurStr,1,(:,CurStr)-1);CurStr:=Copy(CurStr,(:,CurStr)+2,255); CurID:=0;For j:=1 To M DoIf CurName=Namej Then Begin CurID:=j;Break;End;If CurID=0 Then Continue;If CurStr=I am guilty. # Then SetGuilty(CurID,CurID,1)ElseIf CurStr=I am not gu

14、ilty. # Then SetGuilty(CurID,CurID,-1)BeginCurName:=Copy(CurStr,1,( ,CurStr)-1);ElseCurStr:=Copy(CurStr,( ,CurStr)+1,255);If CurName=Today Then BeginFor j:=1 To 7 DoIf CurStr=DaySej Then BeginWhatDayCurID,j:=True; Break;End;EndElse BeginNextID:=0;For j:=1 To M DoIf CurName=Namej Then Begin NextID:=j

15、;Break;End;If NextID=0 Then Continue;If CurStr=is guilty. # Then SetGuilty(CurID,NextID,1)Else If CurStr=is not guilty. #SetGuilty(CurID,NextID,-1);ThenEnd;End;End;End;Function Check(CurGuilty,CurDay: VarSayT,SayF:Array1.MM Ofeger):;i,j,TCount,FCount:eger;BeginFillChar(SayT,SizeOf(SayT),False); Fill

16、Char(SayF,SizeOf(SayF),False); For i:=1 To M Do BeginIf Guiltyi,CurGuilty=1 Then SayTi:=TrueElse If Guiltyi,CurGuilty=-1 SayFi:=True;End;For i:=1 To M Do For j:=1 To M DoIf jCurGuilty Then Begin If Guiltyi,j=1 Then SayFi:=TrueElse If Guiltyi,j=-1 Then SayTi:=True;End;For i:=1 To M DoThenIf WhatDayi,

17、CurDay Then SayTi:=True; For i:=1 To M DoFor j:=1 To 7 DoIf jCurDay ThenIf WhatDayi,j Then SayFi:=True; For i:=1 To M DoIf SayTi And SayFi Then Begin Check:=False;Exit;End;TCount:=0; FCount:=0; For i:=1 To M Do BeginIf SayTi Then Inc(TCount); If SayFi Then Inc(FCount);End;If (FCountN) Or (M-TCount1

18、Then(cCannotDetermine) (Ans);End.第三题：加分二叉树【试题分析】一、题意分析1、任务描述：在中序遍历为（1,2,3,n）的各种二叉树中，选出加分最高的一棵二叉树，输出最高加分和对此二叉树的前序遍历。加分规则：任意棵subtree（也包含 tree 本身）的加分计算方法如下：subtree 的若某个树的加分*subtree 的右的加分+subtree 的根的分数为空，规定其加分为 1，叶子的加分就是叶节点本身的分数，不考虑它的空。2、输入：节点数和每个节点的分值。（n30、分值y thenx=y thenbegbeg y doaxx,y:=1;exit;end;a

19、xx,y:=ax;exit;end;for i:=x tobeginifif ifmaxx,i-1=0 then try(x,i-1);maxi+1,y=0 then try(i+1,y); maxx,ymaxx,i-1*maxi+1,y+ai thenbeginmaxx,y:=maxx,i-1*maxi+1,y+ai;wayx,y:=i;end;end;end;procedure output(x,y:eger); beginwrite(f,wayx,y, );if x=wayx,y-1 then write(f,x, )else if xwayx,y-1 then output(x,wayx,y-1); if wayx,y+1=y then write(f,y, )else if wayx,y+1shorteb1+1) and (shorteb1=a-1) Then Begin root