NoiP2003提高组复赛试题分析

1、 第一题：神经网络【试题分析】一、题意分析1、任务描述：从输入层开始，各节点按照传递公式，一层一层向下传递。输出输出层中信号大于零的节点编号和信号大小。（节点编号由小到大）如果没有满足条件的编号则输出 NULL。信号传递公式：C W C Uijiji公式中( ,的) W （可能为负值）表示连接 j 号神经元和 i 号神经元的边的权值。j iEji当 C 大于 0 时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于i兴奋状态时，下一秒它会向其它神经元传递信号，信号的强度为 C 。i2、输入：两个整数 n（1n20）和 p。n 表示节点的个数；p 表示有向边的条数。下面 n 行表示 1-n

2、 号节点的状态和阈值。下面 p 行表示有向边及其权值。3、输出：输出输出层状态大于零的神经元编号和状态，并且按照编号有小到大顺序输出！若输出层的神经元最后状态小于等于0，则输出NULL。二、问题分析1、题目中给出每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。所以不必进行拓扑排序，一层一层的向下传递信号即可。输出最后一层中信号大于零的节点编号。2、可以建立一个队列，将输入层节点入队。3、取队首节点出队，寻找此节点有向边，如果有有向边：1）则记录此节点不是输出层；2）再判断此节点信号大于零则向下传递信号，将指向的节点入队（防止重复入队）。再出队再传递，直至全部出队。注意：1）输入

3、层可以是输出层。2）信号传递公式中只减一次 Ui。【程序清单】Program network;ConstInName=network.in;OutName=network.out; MM=100;VarInFile,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;IsInQ

4、ueue:Array1.MM Of Boolean;IsNull:Boolean;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 BeginRead(InFile,Int1,Int2);ReadLn(InFile,MapInt1,Int2);FlagInt1,Int2:=True;End;Close(InFile);FillChar(IsOut,S

5、izeOf(IsOut),True);FillChar(IsInQueue,SizeOf(IsInQueue),False);Head:=1; Rear:=1;For i:=1 To N Do BeginIf Ci0 Then BeginQueueRear:=i;Inc(Rear);IsInQueuei:=True;EndElse Ci:=-Ui; End;While Head0 Then BeginInc(Ci,MapQueueHead,i*CQueueHead);If Not IsInQueuei Then BeginQueueRear:=i;Inc(Rear);IsInQueuei:=T

6、rue;End;End;IsOutQueueHead:=False;End;Inc(Head);End;Assign(OutFile,OutName);Rewrite(OutFile);IsNull:=True;For i:=1 To N DoIf IsOuti ThenIf Ci0 Then BeginWriteLn(OutFile,i, ,Ci);IsNull:=False;End;If IsNull Then WriteLn(OutFile,NULL);Close(OutFile);End.第二题：侦探推理【试题分析】一、题意分析1、任务描述：M 个人参加游戏，每人提供一句或多句证言，共

7、 P 句证言。其中 N 个人始终说假话，其余的人始终说真话。请你通过证言判断出谁是罪犯。 证言形式如下：证词内容I am guilty.Today is XXX.今天是 XXX（XXX 表示星期几，是 Monday Tuesday WednesdayThursday Friday Saturday Sunday 其中之一）证词中出现的其它话，都不列入逻辑推理的内容。2、输入：第一行有三个整数，M（1M20）、N（1NM）和 P（1P100）：M 是参加游戏的明明的同学数，N 是其中始终说谎的人数，P 是证人的综述。接下来 M 行，每行是明明的一个同学的名字（英文字母组成，没有空格，全部大写）。

8、往后有 P 行，每行开始是某个同学的名字，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式，证词每行不会好过 250 个字符。输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。3、输出：如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出 Cannot Determine；如果程序判断出没有人可能成为罪犯，则输出 Impossible。二、问题分析1、根据题意可知可以利用枚举法完成。枚举罪犯和 今天是星期几 。满足 N个人始终说谎话和 M-N 个人始终说真话的条件，就可以确定罪犯。2、首先利用字符串操作将证言转化成计算机可表示的信息。1）

9、定义 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 是星

10、期几3、枚举罪犯和星期几，判断每句证言是真是假，统计说真假证言的人数。注意：有可能某人又说过真话，又说过假话。4、根据题目要求输出罪犯编号或 Cannot Determine 或 Impossible。【程序清单】Program logic;ConstInName=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. #);cImpo

11、ssible=-1;cCannotDetermine=-2;VarInFile,OutFile:Text;M,N,P:Integer;Name:Array1.MM Of String;Guilty:Array1.MM,1.MM Of Integer;-1.1WhatDay:Array1.MM,1.7 Of Boolean;i,j:Integer;IsGuilty:Array1.MM Of Boolean;Ans,AnsC:Integer;Procedure Print(ID:Integer);BeginAssign(OutFile,OutName);Rewrite(OutFile);If ID

12、=cImpossible Then WriteLn(OutFile,Impossible)Else If ID=cCannotDetermine ThenWriteLn(OutFile,Cannot Determine)Else WriteLn(OutFile,NameID);Close(OutFile);Halt;End;Procedure SetGuilty(CurID,NextID,NewValue:Integer);BeginIf GuiltyCurID,NextID=0 ThenGuiltyCurID,NextID:=NewValueElse If GuiltyCurID,NextI

13、DNewValue ThenPrint(cImpossible);End;Procedure ReadStatement;Vari,j,CurID,NextID:Integer;CurStr,CurName:String;BeginFor i:=1 To P Do BeginReadLn(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 DoIf CurName=Namej

14、 Then BeginCurID:=j;Break;End;If CurID=0 Then Continue;If CurStr=I am guilty. # ThenSetGuilty(CurID,CurID,1)Else If CurStr=I am not guilty. # Then SetGuilty(CurID,CurID,-1)Else BeginCurName:=Copy(CurStr,1,Pos( ,CurStr)-1);CurStr:=Copy(CurStr,Pos( ,CurStr)+1,255);If CurName=Today Then BeginFor j:=1 T

15、o 7 DoIf CurStr=DayStatej Then BeginWhatDayCurID,j:=True;Break;End;EndElse BeginNextID:=0;For j:=1 To M DoIf CurName=Namej Then BeginNextID:=j;Break;End;If NextID=0 Then Continue;If CurStr=is guilty. # ThenSetGuilty(CurID,NextID,1)Else If CurStr=is not guilty. # ThenSetGuilty(CurID,NextID,-1);End;En

16、d;End;End;Function Check(CurGuilty,CurDay:Integer):Boolean;VarSayT,SayF:Array1.MM Of Boolean;i,j,TCount,FCount:Integer;BeginFillChar(SayT,SizeOf(SayT),False);FillChar(SayF,SizeOf(SayF),False); For i:=1 To M Do BeginIf Guiltyi,CurGuilty=1 ThenSayTi:=TrueElse If Guiltyi,CurGuilty=-1 ThenSayFi:=True;En

17、d;For i:=1 To M DoFor j:=1 To M DoIf jCurGuilty Then BeginIf Guiltyi,j=1 ThenSayFi:=TrueElse If Guiltyi,j=-1 ThenSayTi:=True;End;For i:=1 To M DoIf WhatDayi,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 B

18、eginCheck:=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 ThenPrint(cCannotDetermine)Else Print(Ans);End.第三题：加分二叉树【试题分析】一、题意分析1、任务描述：在中序遍历为（1,2,3,n）的各种二叉树中，选出加分最 高的一棵二叉树，输出最高加分和对此二叉树的前序遍历。加分规则：任意棵子树 subtree

19、（也包含 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 dobeginif 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 thenbeginmaxx,y:=maxx,i-1*maxi+1,y+ai;wayx,y:=i;end;end;end;procedure output(x,y:integer);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)Th