noip2003提高組復(fù)賽試題分析

1、我看了李學(xué)武教授寫的關(guān)于 NOIP 復(fù)賽的若干問題的思考一文，有很大觸動，深刻感受到市信息學(xué)奧賽基礎(chǔ)薄弱。我從事奧賽培訓(xùn)工作十三年，培訓(xùn)的學(xué)生在全國取得了一些好成績，一塊國際銀牌，四塊奧賽金牌，三塊銀牌，十塊銅牌。我認(rèn)為我有責(zé)任將培訓(xùn)工作介紹給同人和其他學(xué)校的同學(xué)，來推動市奧賽的發(fā)展。下面是我寫的今年分區(qū)聯(lián)賽高中組復(fù)賽的解題分析，供大家參考，并懇切希望能與“OIER”交流共勉。南開中學(xué)：300100，電子郵箱： 或 tj（.cn ）第一題：神經(jīng)網(wǎng)絡(luò)【試題分析】一、題意分析1、任務(wù)描述：從輸入層開始，各節(jié)點(diǎn)按照傳遞公式，一層一層向下傳遞。輸出輸出層中信號大于零的節(jié)點(diǎn)號則輸出 NULL。信號傳遞公

2、式：和信號大小。（節(jié)點(diǎn)由小到大）如果沒有滿足條件的編1）則此節(jié)點(diǎn)不是輸出層；2）再判斷此節(jié)點(diǎn)信號大于零則向下傳遞信號，將指向的節(jié)點(diǎn)入隊(duì)（防止重復(fù)入隊(duì)）。再出隊(duì)再傳遞，直至全部出隊(duì)。注意：1）輸入層可以是輸出層。2）信號傳遞公式中只減一次 Ui?！境绦蛳旅媸恰繉W(xué)生同學(xué)寫的程序。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、任務(wù)描述：M 個人參加，每人提供一句或多句證言，共P 句證言。其中 N 個人始終說假話，其余的人始終說真話。請你通過證言判斷出誰是罪犯。證言形式如下：中出現(xiàn)的其它話，都不列入邏輯推理的內(nèi)容。2、輸入：第一行有三個整數(shù)，M（1M20）、N（1NM）和 P（1P100）：的明明的同學(xué)數(shù)，N 是其中始終說謊的人數(shù)，P 是證人的綜述。M 是參加接下來M 行，每行是明明的一個同學(xué)的名字（英文字母組成，沒有空格，全部大寫）。往后有 P 行，每行開始是某個同學(xué)的名字，緊跟著一個冒號和一個空格

7、，后面是一句，符合前表中所列格式，每行不會好過 250 個字符。輸入中不會出現(xiàn)連續(xù)的兩個空格，而且每行開頭和結(jié)尾也沒有空格。3、輸出：如果你的程序能確定誰是罪犯，則輸出他的名字；如果程序判斷出不止一個人可能是罪犯，則輸出 Cannot Determine；如果程序判斷出沒有人可能成為罪犯，則輸出 Im二、問題分析sible。內(nèi)容含義I am guilty.我是罪犯I am not guilty.我不是罪犯is guilty.是罪犯（表示某個同學(xué)的名字）isnot guilty.不是罪犯Today is.是（表示幾，是 Monday Tuesday Wednesday Thursday Frid

8、ay Saturday Sunday 其中之一）1、根據(jù)題意可知可以利用枚舉法完成。枚舉罪犯和是幾。滿足 N 個人始終說謊話和M-N 個人始終說真話的條件，就可以確定罪犯。2、首先利用字符串操作將證言轉(zhuǎn)化成計(jì)算機(jī)可表示的信息。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 是幾言的人數(shù)。注意：有3、枚舉罪犯和幾，判斷每句證言是真是假，統(tǒng)計(jì)說真可能又說過真話，又說過假話。4、根據(jù)題目要求輸出罪犯或 Cannot Determine 或 Imsible。【程序下面是NOIP 2003Test 0.9Algorithm】學(xué)生同學(xué)寫的程序。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、任務(wù)描述：在中序遍歷為（1,2,3,n）的各種二叉樹中，選出加分最高的一棵二叉樹，輸出最高加分和對此二叉樹的前序遍歷。加分規(guī)則：任意棵subtree（也包含 tree 本身）的加分計(jì)算方法如下：subtree 的若某個樹的加分*subtree 的右的加分+subtree 的根的分?jǐn)?shù)為空，規(guī)定其加分為 1，葉子的加分就是葉節(jié)點(diǎn)本身的分?jǐn)?shù)，不考慮它的空。2、輸入：節(jié)點(diǎn)數(shù)和每個節(jié)點(diǎn)的分值。（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