NoiP2003提高组复赛试题分析_天津南开中学滕伟.doc

我看了李学武教授写的关于NOIP复赛的若干问题的思考一文，有很大触动，深刻感受到天津市信息学奥赛基础薄弱。我从事奥赛培训工作十三年，培训的学生在全国取得了一些好成绩，一块国际银牌，四块全国奥赛金牌，三块银牌，十块铜牌。我认为我有责任将我的培训工作介绍给同人和其他学校的同学，来推动天津市奥赛的发展。下面是我写的今年分区联赛高中组复赛的解题分析，供大家参考，并恳切希望能与“OIER”交流共勉。天津南开中学滕伟（ 邮编：300100，电子邮箱： 或 ）第一题：神经网络【试题分析】一、题意分析1、任务描述：从输入层开始，各节点按照传递公式，一层一层向下传递。输出输出层中信号大于零的节点编号和信号大小。（节点编号由小到大）如果没有满足条件的编号则输出NULL。信号传递公式：公式中的Wji（可能为负值）表示连接j号神经元和i号神经元的边的权值。当Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其它神经元传递信号，信号的强度为Ci。2、输入：两个整数n（1n20）和p。n表示节点的个数；p表示有向边的条数。下面n行表示1-n号节点的状态和阈值。下面p行表示有向边及其权值。3、输出：输出输出层状态大于零的神经元编号和状态，并且按照编号有小到大顺序输出！若输出层的神经元最后状态小于等于0，则输出NULL。二、问题分析1、题目中给出每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。所以不必进行拓扑排序，一层一层的向下传递信号即可。输出最后一层中信号大于零的节点编号。2、可以建立一个队列，将输入层节点入队。3、取队首节点出队，寻找此节点有向边，如果有有向边：1）则记录此节点不是输出层；2）再判断此节点信号大于零则向下传递信号，将指向的节点入队（防止重复入队）。再出队再传递，直至全部出队。注意：1）输入层可以是输出层。2）信号传递公式中只减一次Ui。【程序清单】下面是我校学生肖天同学写的程序。NOIP 2003 Problem 1 by Xiao TianTest 1.5 : All rightProgram network;Const InName=network.in; OutName=network.out; MM=100;Var InFile,OutFile:Text; C,U:Array1.MM Of LongInt; Map:Array1.MM,1.MM Of LongInt; Flag:Array1.MM,1.MM Of Boolean; IsOut:Array1.MM Of Boolean; Queue:Array1.MM Of LongInt; N,P,i,Int1,Int2,Head,Rear:LongInt; IsInQueue:Array1.MM Of Boolean; IsNull:Boolean;Begin Assign(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 Begin Read(InFile,Int1,Int2); ReadLn(InFile,MapInt1,Int2); FlagInt1,Int2:=True; End; Close(InFile); FillChar(IsOut,SizeOf(IsOut),True); FillChar(IsInQueue,SizeOf(IsInQueue),False); Head:=1; Rear:=1; For i:=1 To N Do Begin If Ci0 Then Begin QueueRear:=i; Inc(Rear); IsInQueuei:=True; End Else Ci:=-Ui; End; While Head0 Then Begin Inc(Ci,MapQueueHead,i*CQueueHead); If Not IsInQueuei Then Begin QueueRear:=i; Inc(Rear); IsInQueuei:=True; End; End; IsOutQueueHead:=False; End; Inc(Head); End; Assign(OutFile,OutName); Rewrite(OutFile); IsNull:=True; For i:=1 To N Do If IsOuti Then If Ci0 Then Begin WriteLn(OutFile,i, ,Ci); IsNull:=False; End; If IsNull Then WriteLn(OutFile,NULL); Close(OutFile);End.第二题：侦探推理【试题分析】一、题意分析1、任务描述：M个人参加游戏，每人提供一句或多句证言，共P句证言。其中N个人始终说假话，其余的人始终说真话。请你通过证言判断出谁是罪犯。证言形式如下：证词内容证词含义I am guilty.我是罪犯I am not guilty.我不是罪犯XXX is guilty.XXX是罪犯（XXX表示某个同学的名字）XXX is not guilty.XXX不是罪犯Today is XXX.今天是XXX（XXX表示星期几，是Monday Tuesday WednesdayThursday Friday Saturday Sunday其中之一）证词中出现的其它话，都不列入逻辑推理的内容。2、输入：第一行有三个整数，M（1M20）、N（1NM）和P（1P100）：M是参加游戏的明明的同学数，N是其中始终说谎的人数，P是证人的综述。接下来M行，每行是明明的一个同学的名字（英文字母组成，没有空格，全部大写）。往后有P行，每行开始是某个同学的名字，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式，证词每行不会好过250个字符。输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。3、输出：如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出Cannot Determine；如果程序判断出没有人可能成为罪犯，则输出Impossible。二、问题分析1、根据题意可知可以利用枚举法完成。枚举罪犯和今天是星期几。满足N个人始终说谎话和M-N个人始终说真话的条件，就可以确定罪犯。2、首先利用字符串操作将证言转化成计算机可表示的信息。1）定义Guilty:Array1.MM,1.MM Of Integer;-1.1FillChar(Guilty,SizeOf(Guilty),0)初值为0Guiltyi,j=-1：表示第i个人说第j个人不是罪犯Guiltyi,j= 1：表示第i个人说第j个人是罪犯其中包含Guiltyi,i即第i个人说自己是不是罪犯注意：Guilty不可以自相矛盾。2）定义WhatDay:Array1.MM,1.7 Of Boolean;FillChar(WhatDay,SizeOf(WhatDay),False)WhatDayi,j:=True:表示第i个人说过j是星期几3、枚举罪犯和星期几，判断每句证言是真是假，统计说真假证言的人数。注意：有可能某人又说过真话，又说过假话。4、根据题目要求输出罪犯编号或Cannot Determine或Impossible。【程序清单】下面是我校学生肖天同学写的程序。NOIP 2003 Problem 2 by Xiao TianTest 0.9 : All rightAlgorithm : Enumerate the guilty and what day it is today. then we can determine whether each sentence is true or not.Program logic;Const InName=logic.in; OutName=logic.out; MM=20; DayState:Array1.7 Of String =(is Monday. # ,is Tuesday. # ,is Wednesday. # ,is Thursday. # ,is Friday. # ,is Saturday. # ,is Sunday. #); cImpossible=-1; cCannotDetermine=-2;Var InFile,OutFile:Text; M,N,P:Integer; Name:Array1.MM Of String; Guilty:Array1.MM,1.MM Of Integer;-1.1 WhatDay:Array1.MM,1.7 Of Boolean; i,j:Integer; IsGuilty:Array1.MM Of Boolean; Ans,AnsC:Integer;Procedure Print(ID:Integer);Begin Assign(OutFile,OutName); Rewrite(OutFile); If ID=cImpossible Then WriteLn(OutFile,Impossible) Else If ID=cCannotDetermine Then WriteLn(OutFile,Cannot Determine) Else WriteLn(OutFile,NameID); Close(OutFile); Halt;End;Procedure SetGuilty(CurID,NextID,NewValue:Integer);Begin If GuiltyCurID,NextID=0 Then GuiltyCurID,NextID:=NewValue Else If GuiltyCurID,NextIDNewValue Then Print(cImpossible);End;Procedure ReadStatement;Var i,j,CurID,NextID:Integer; CurStr,CurName:String;Begin For i:=1 To P Do Begin ReadLn(InFile,CurStr); CurStr:=CurStr+ #; CurName:=Copy(CurStr,1,Pos(:,CurStr)-1); CurStr:=Copy(CurStr,Pos(:,CurStr)+2,255); CurID:=0; For j:=1 To M Do If CurName=Namej Then Begin CurID:=j; Break; End; If CurID=0 Then Continue; If CurStr=I am guilty. # Then SetGuilty(CurID,CurID,1) Else If CurStr=I am not guilty. # Then SetGuilty(CurID,CurID,-1) Else Begin CurName:=Copy(CurStr,1,Pos( ,CurStr)-1); CurStr:=Copy(CurStr,Pos( ,CurStr)+1,255); If CurName=Today Then Begin For j:=1 To 7 Do If CurStr=DayStatej Then Begin WhatDayCurID,j:=True; Break; End; End Else Begin NextID:=0; For j:=1 To M Do If CurName=Namej Then Begin NextID:=j; Break; End; If NextID=0 Then Continue; If CurStr=is guilty. # Then SetGuilty(CurID,NextID,1) Else If CurStr=is not guilty. # Then SetGuilty(CurID,NextID,-1); End; End; End;End;Function Check(CurGuilty,CurDay:Integer):Boolean;Var SayT,SayF:Array1.MM Of Boolean; i,j,TCount,FCount:Integer;Begin FillChar(SayT,SizeOf(SayT),False); FillChar(SayF,SizeOf(SayF),False); For i:=1 To M Do Begin If Guiltyi,CurGuilty=1 Then SayTi:=True Else If Guiltyi,CurGuilty=-1 Then SayFi:=True; End; For i:=1 To M Do For j:=1 To M Do If jCurGuilty Then Begin If Guiltyi,j=1 Then SayFi:=True Else If Guiltyi,j=-1 Then SayTi:=True; End; For i:=1 To M Do If WhatDayi,CurDay Then SayTi:=True; For i:=1 To M Do For j:=1 To 7 Do If jCurDay Then If WhatDayi,j Then SayFi:=True; For i:=1 To M Do If SayTi And SayFi Then Begin Check:=False; Exit; End; TCount:=0; FCount:=0; For i:=1 To M Do Begin If SayTi Then Inc(TCount); If SayFi Then Inc(FCount); End; If (FCountN) Or (M-TCount1 Then Print(cCannotDetermine) Else Print(Ans);End.第三题：加分二叉树【试题分析】一、题意分析1、任务描述：在中序遍历为（1,2,3,n）的各种二叉树中，选出加分最高的一棵二叉树，输出最高加分和对此二叉树的前序遍历。加分规则：任意棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分*subtree的右子树的加分+subtree的根的分数若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数，不考虑它的空子树。2、输入：节点数和每个节点的分值。（n30、分值y then begin maxx,y:=1;exit;end; if x=y then begin maxx,y:=ax;exit;end; for i:=x to y do begin if maxx,i-1=0 then try(x,i-1); if maxi+1,y=0 then try(i+1,y); if maxx,ymaxx,i-1*maxi+1,y+ai then begin maxx,y:=maxx,i-1*maxi+1,y+ai; wayx,y:=i; end; end;end;procedure output(x,y:integer);begin write(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+1sho