1、第九屆全國青少年信息學奧林匹克聯賽（N0IP2003）復賽提高組解題報告（2003年12月25日）By：湖北省水果湖高中 伍先軍E-mail:wuxianjun2001題一 神經網絡【問題背景】 人工神經網絡（Artificial Neural Network）是一種新興的具有自我學習能力的計算系統，在模式識別、函數逼近及貸款風險評估等諸多領域有廣泛的應用。對神經網絡的研究一直是當今的熱門方向，蘭蘭同學在自學了一本神經網絡的入門書籍后，提出了一個簡化模型，他希望你能幫助他用程序檢驗這個神經網絡模型的實用性。【問題描述】 在蘭蘭的模型中，神經網絡就是一張有向圖，圖中的節點稱為神經元，而且兩個神經

2、元之間至多有一條邊相連，下圖是一個神經元的例子： 神經元編號為1） 圖中，X1X3是信息輸入渠道，Y1Y2是信息輸出渠道，C1表示神經元目前的狀態，Ui是閾值，可視為神經元的一個內在參數。 神經元按一定的順序排列，構成整個神經網絡。在蘭蘭的模型之中，神經網絡中的神經無分為幾層；稱為輸入層、輸出層，和若干個中間層。每層神經元只向下一層的神經元輸出信息，只從上一層神經元接受信息。下圖是一個簡單的三層神經網絡的例子。蘭蘭規定，Ci服從公式：（其中n是網絡中所有神經元的數目） 公式中的Wji（可能為負值）表示連接j號神經元和 i號神經元的邊的權值。當 Ci大于0時，該神經元處于興奮狀態，否則就處于平靜

3、狀態。當神經元處于興奮狀態時，下一秒它會向其他神經元傳送信號，信號的強度為Ci。 如此在輸入層神經元被激發之后，整個網絡系統就在信息傳輸的推動下進行運作。現在，給定一個神經網絡，及當前輸入層神經元的狀態（Ci），要求你的程序運算出最后網絡輸出層的狀態。【輸入格式】輸入文件第一行是兩個整數n（1n200）和p。接下來n行，每行兩個整數，第i1行是神經元i最初狀態和其閾值（Ui），非輸入層的神經元開始時狀態必然為0。再下面P行，每行由兩個整數i，j及一個整數Wij，表示連接神經元i、j的邊權值為Wij。【輸出格式】 輸出文件包含若干行，每行有兩個整數，分別對應一個神經元的編號，及其最后的狀態，兩個

4、整數間以空格分隔。僅輸出最后狀態非零的輸出層神經元狀態，并且按照編號由小到大順序輸出！ 若輸出層的神經元最后狀態均為 0，則輸出 NULL。【輸入樣例】5 61 01 00 10 10 11 3 11 4 11 5 12 3 12 4 12 5 1【輸出樣例】3 14 15 1分析本題是比較簡單的，但要注意神經元的層數，只輸出最大層（輸出層）的狀態非零的神經元的狀態，在中間層中只有神經元處于興奮狀態時（Ci0）才會向下一層傳送信號。PASCAL源程序program NOIP2003_1_Network; const maxn=200;maxp=200; var i,j,n,p,maxlayer

5、:integer; w:array0.maxpof longint;存放邊的權值 start,terminal:array0.maxpof byte;存放邊的起點與終點 u,c:array0.maxnof longint;存放神經元的閥值與狀態值 layer:array0.maxnof byte;存放神經元的層數 f1,f2:text;fn1,fn2,fileNo:string; flag:boolean; begin write(Input fileNo:); readln(fileNo); fn1:=network.in+fileNo; fn2:=network.ou+fileNo; as

6、sign(f1,fn1);reset(f1); assign(f2,fn2);rewrite(f2); readln(f1,n,p); for i:=1 to n do readln(f1,ci,ui); fillchar(layer,sizeof(layer),0); for i:=1 to p do begin readln(f1,starti,terminali,wi);讀入邊的起點，終點，權 layerterminali:=layerstarti+1;計算終點的層數（比起點大1） end; close(f1); maxlayer:=layerterminalp;求最大層數，即輸出層的層

7、數 for i:=1 to n do計算非輸入層的節點i的狀態值 if layeri0 then begin for j:=1 to p do if (terminalj=i) and (cstartj0)與目標節點i有邊相連的節點j且其狀態處于興奮時（Cj0）才向節點I傳送信號 then ci:=ci+wj*cstartj; ci:=ci-ui; end;輸出結果flag:=true; for i:=1 to n do if (layeri=maxlayer) and (ci0) then begin writeln(f2,i, ,ci); flag:=false; end; if flag

8、 then writeln(f2,NULL); close(f2); end.點評基本題。題目閱讀起來有些費神，題中邊的權值W,神經元的狀態值C,閥值U，均未明確指出其取值范圍，反映出命題不嚴謹。題二 偵探推理【問題描述】明明同學最近迷上了偵探漫畫柯南并沉醉于推理游戲之中，于是他召集了一群同學玩推理游戲。游戲的內容是這樣的，明明的同學們先商量好由其中的一個人充當罪犯（在明明不知情的情況下），明明的任務就是找出這個罪犯。接著，明明逐個詢問每一個同學，被詢問者可能會說：證詞中出現的其他話，都不列入邏輯推理的內容。明明所知道的是，他的同學中有N個人始終說假話，其余的人始終說真。現在，明明需要你幫助他

9、從他同學的話中推斷出誰是真正的兇手，請記住，兇手只有一個！【輸入格式】 輸入由若干行組成，第一行有二個整數，M（1M20）、N（1NM）和P（1P100）；M是參加游戲的明明的同學數，N是其中始終說謊的人數，P是證言的總數。接下來M行，每行是明明的一個同學的名字（英文字母組成，沒有主格，全部大寫）。往后有P行，每行開始是某個同學的名宇，緊跟著一個冒號和一個空格，后面是一句證詞，符合前表中所列格式。證詞每行不會超過250個字符。 輸入中不會出現連續的兩個空格，而且每行開頭和結尾也沒有空格。【輸出格式】 如果你的程序能確定誰是罪犯，則輸出他的名字；如果程序判斷出不止一個人可能是罪犯，則輸出 Can

10、not Determine；如果程序判斷出沒有人可能成為罪犯，則輸出 Impossible。【輸入樣例】3 1 5MIKECHARLESKATEMIKE:I am guilty.MIKE:Today is Sunday.CHARLES:MIKE is guiltyKATE:I am guilty.KATE:How are you?【輸出樣例】MIKE分析基本思路有兩種：一是可以窮舉M個人中有N個人始終說假話的所有組合，據此出發，判斷每句證詞的真偽，再推斷誰是罪犯，但這樣做運算量大；二是可以窮舉M個人中的任意一個是罪犯，由此再來判斷每句證詞的真偽，推斷誰說真話誰說假話，這樣做運算量小得多。這里采

11、用后者。有幾點必須注意：一，不能說找到某人是罪犯或可能是罪犯就完事了，還必須確保是否還有別人是罪犯或可能是罪犯；二，如何處理關于星期的證詞呢？還是可以采用窮舉；三，某人的證詞可能前后矛盾，在給某人標記他是始終說真話還是始終說假話時，一定要考察他此前的誠信記錄；因此，對某人的誠信記錄要有4種不同的區分，可用0表示此人尚無有效記錄（未說過真話也未說過假話），用1表示此人說真話，用2表示此人說假話，用3表示此人說的話與他前面的證詞沖突；四，如何判斷最初窮舉時設定的前提（某人是罪犯）是否是本題的一個解呢？如果有人的誠信記錄為3，則肯定不是本題的解；但是也不能強求誠信記錄為2的人的總數一定要等于n，而是

12、只要誠信記錄為2的人不超過n且誠信記錄為1的人不超過m-n即可，因為誠信記錄為0的人可能說真話也可能說假話，他們只是沒有說話，或只說了廢話。五，由于證詞要反復用于判斷，可以先剔除其中的無效證詞；為處理方便，將有效證詞分為兩部分：不含星期的和含星期的。PASCAL源程序program NOIP2003_2_Logic; const maxm=20; dow:array1.7of string=(Sunday.,Monday.,Tuesday.,Wednesday., Thursday.,Friday.,Saturday.); var i,j,k,weekday,m,n,p,p1,p2,p3,in

13、dex,resolution,total1,total2:byte; name:array1.maxmof string;存放人名 witness10,witness20:array1.100of byte;存放說話人的序號,分為兩類,前者存放不含星期的證詞的說話人的序號,后者存放只含星期的證詞的說話人的序號 witness1,witness2:array1.100of string;存放證詞,分為兩類,第一類是不含星期的證詞,第二類是只含星期的證詞 name0,temp,temp0,temp1,temp2:string; truth,truth0:array1.maxmof byte; 存放

14、誠信記錄 f1,f2:text;fn1,fn2,fileNo:string; flag:boolean; begin write(Input fileNo:);readln(fileNo); fn1:=logic.in+fileNo;fn2:=logic.ou+fileNo; assign(f1,fn1);reset(f1);assign(f2,fn2);rewrite(f2); readln(f1,m,n,p); for i:=1 to m do readln(f1,namei); total1:=0;total2:=0; for i:=1 to p do begin對證詞預處理 readl

15、n(f1,temp); index:=pos(: ,temp); temp1:=copy(temp,1,index-1);取得說話人姓名 temp2:=copy(temp,index+2,length(temp)-index-1);取得證詞if (temp2=I am guilty.) or (temp2=I am not guilty.) then for j:=1 to m do if namej=temp1 then begin inc(total1);total1表示第一類證詞的總數 witness10total1:=j;記下第一類第total1條證詞的說話人的序號 witness1t

16、otal1:=temp2;記下第一類第total1條證詞 break; end; if (pos( is guilty.,temp2)0) or (pos( is not guilty.,temp2)0) then begin temp0:=copy(temp2,1,pos( is ,temp2)-1);取得證詞的敘述對象(主語) flag:=false; for k:=1 to m do if temp0=namek then begin flag:=true; break; end; if flag then如果證詞的敘述對象(主語)確實存在 for j:=1 to m do if nam

17、ej=temp1 then begin記入到第一類證詞中 inc(total1); witness10total1:=j; witness1total1:=temp2; break; end; end; flag:=false; for j:=1 to 7 do if temp2=Today is + dowj then begin flag:=true; break; end; if flag then如果證詞是關于星期的判斷 for j:=1 to m do if namej=temp1 then begin記入到第二類證詞中 inc(total2);total2表示第二類證詞的總數 wi

18、tness20total2:=j;記下第二類第total2條證詞的說話人的序號 witness2total2:=temp2;記下第二類第total2條證詞 break; end; end; close(f1); resolution:=0;resolution表示解的個數 for i:=1 to m do begin窮舉,第i個人為罪犯if resolution1 then break;如果解的個數多于1個,則跳出循環fillchar(truth,sizeof(truth),0);誠信記錄賦初值為0,表示此人尚無有效證詞 for j:=1 to total1 do begin逐條處理第一類證詞

19、 if witness1j=I am guilty. then begin如果證詞為I am guilty. if i=witness10j then如果說話人就是罪犯,則本證詞為真 case truthi of 0:truthi:=1;如果此人的誠信記錄為0,則此人說真話(記為1) 2:truthi:=3;如果此人的誠信記錄為2(即以前說假話),則此人自相矛盾(記為3) end else如果說話人不是罪犯,則本證詞為假 case truthwitness10j of 0:truthwitness10j:=2;如果此人的誠信記錄為0,則此人說假話(記為2) 1:truthwitness10j:

20、=3;如果此人的誠信記錄為1(即以前說真話),則此人自相矛盾(記為3) end; end; if witness1j=I am not guilty. then begin如果證詞為I am not guilty. if i=witness10j then如果說話人是罪犯,則本證詞為假 case truthi of 0:truthi:=2; 1:truthi:=3; end else如果說話人不是罪犯,則本證詞為真 case truthwitness10j of 0:truthwitness10j:=1; 2:truthwitness10j:=3; end; end; if (pos( is

21、guilty.,witness1j)0) then begin如果證詞含有is guilty. temp:=copy(witness1j,1,pos( is guilty.,witness1j)-1);取得證詞的主語 if namei=temp then如果證詞的主語是罪犯,則本證詞為真 case truthwitness10j of 0:truthwitness10j:=1; 2:truthwitness10j:=3; end else如果證詞的主語不是罪犯,則本證詞為假 case truthwitness10j of 0:truthwitness10j:=2; 1:truthwitness

22、10j:=3; end; end; if (pos( is not guilty.,witness1j)0) then begin如果證詞含有is not guilty. temp:=copy(witness1j,1,pos( is not guilty.,witness1j)-1);取得證詞的主語 if namei=temp then如果證詞的主語是罪犯,則本證詞為假 case truthwitness10j of 0:truthwitness10j:=2; 1:truthwitness10j:=3; end else如果證詞的主語不是罪犯,則本證詞為真 case truthwitness1

23、0j of 0:truthwitness10j:=1; 2:truthwitness10j:=3; end; end; end;第一類證詞全部處理完畢 if total20 then begin如果有第二類證詞存在,處理第二類證詞 for k:=1 to m do truth0k:=truthk;記下第一類證詞全部處理完畢后的誠信記錄 for weekday:=1 to 7 do begin窮舉,今天是星期日,星期一直到星期六 for k:=1 to m do truthk:=truth0k;誠信記錄還原為第一類證詞全部處理完畢后的誠信記錄 for j:=1 to total2 do逐條處理第

24、二類證詞 if pos(dowweekday,witness2j)0 then如果證詞中含有當前窮舉的星期值,則本證詞為真 case truthwitness20j of 0:truthwitness20j:=1; 2:truthwitness20j:=3; end else如果證詞中不含有當前窮舉的星期值,則本證詞為假 case truthwitness20j of 0:truthwitness20j:=2; 1:truthwitness20j:=3; end; p1:=0;p2:=0;p3:=0; for k:=1 to m do if truthk=1 then inc(p1);p1表示

25、始終說真話的人的總數 for k:=1 to m do if truthk=2 then inc(p2);p2表示始終說假話的人的總數 for k:=1 to m do if truthk=3 then inc(p3);p3表示說過自相矛盾的話的人的總數 if (p1=m-n) and (p2=n) and (p3=0) then begin如果說真話的人的總數小于等于m-n且說假話的人的總數小于等于n且沒有人說過自相矛盾的話,那么當前罪犯i就是本題的一個解 name0:=namei;記下罪犯的姓名 inc(resolution);解的個數增1 break;退出星期的窮舉 end; end;星

26、期的窮舉完畢 end;第二類證詞處理完畢 p1:=0;p2:=0;p3:=0; for k:=1 to m do if truthk=1 then inc(p1); for k:=1 to m do if truthk=2 then inc(p2); for k:=1 to m do if truthk=3 then inc(p3); if (p1=m-n) and (p2=n) and (p3=0) and (name0namei) then begin為避免重復計解,此處多加了一個條件: name0namei name0:=namei; inc(resolution); end; end;

27、 if resolution=1 then writeln(f2,name0);如果只有一個解,則輸出罪犯姓名 if resolution=0 then writeln(f2,Impossible);如果無解,則輸出Impossible if resolution1 then writeln(f2,Cannot Determine);如果有多個可能解,則輸出Cannot Determine close(f2); end.點評基本題，比較復雜，重點考查參賽者的字符串運算和邏輯運算，邏輯推理能力。難點主要在于如何處理關于星期的證詞，以及證詞之間是否存在矛盾。題三 加分二叉樹【問題描述】 設一個n個

28、節點的二叉樹tree的中序遍歷為（l,2,3,n），其中數字1,2,3,n為節點編號。每個節點都有一個分數（均為正整數），記第i個節點的分數為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含tree本身）的加分計算方法如下： subtree的左子樹的加分 subtree的右子樹的加分subtree的根的分數 若某個子樹為空，規定其加分為1，葉子的加分就是葉節點本身的分數。不考慮它的空子樹。 試求一棵符合中序遍歷為（1,2,3,n）且加分最高的二叉樹tree。要求輸出； （1）tree的最高加分 （2）tree的前序遍歷【輸入格式】 第1行：一個整數n（n30），為節點

29、個數。 第2行：n個用空格隔開的整數，為每個節點的分數（分數100）。【輸出格式】 第1行：一個整數，為最高加分（結果不會超過4,000,000,000）。 第2行：n個用空格隔開的整數，為該樹的前序遍歷。【輸入樣例】 5 5 7 1 2 10【輸出樣例】 145 3 1 2 4 5分析很顯然，本題適合用動態規劃來解。如果用數組valuei,j表示從節點i到節點j所組成的二叉樹的最大加分，則動態方程可以表示如下：valuei,j=maxvaluei,i+valuei+1,j,valuei+1,i+1+valuei,i*valuei+2,j, valuei+2,i+2+valuei,i+1*va

30、luei+3,j,valuej-1,j-1+valuei,j-2*valuej,j, valuej,j+valuei,j-1題目還要求輸出最大加分樹的前序遍歷序列，因此必須在計算過程中記下從節點i到節點j所組成的最大加分二叉樹的根節點，用數組rooti,j表示PASCAL源程序$N+program NOIP2003_3_Tree; const maxn=30; var i,j,n,d:byte; a:array1.maxnof byte; value:array1.maxn,1.maxnof comp; root:array1.maxn,1.maxnof byte; s,temp:comp;

31、f1,f2:text;fn1,fn2,fileNo:string; procedure preorder(p1,p2:byte);按前序遍歷輸出最大加分二叉樹 begin if p2=p1 then begin write(f2,rootp1,p2, ); preorder(p1,rootp1,p2-1); preorder(rootp1,p2+1,p2); end; end; begin write(Input fileNo:);readln(fileNo); fn1:=tree.in+fileNo;fn2:=tree.ou+fileNo; assign(f1,fn1);reset(f1);

32、 assign(f2,fn2);rewrite(f2); readln(f1,n); for i:=1 to n do read(f1,ai); close(f1); fillchar(value,sizeof(value),0); for i:=1 to n do begin valuei,i:=ai;計算單個節點構成的二叉樹的加分 rooti,i:=i;記錄單個節點構成的二叉樹的根節點 end; for i:=1 to n-1 do begin valuei,i+1:=ai+ai+1;計算相鄰兩個節點構成的二叉樹的最大加分 rooti,i+1:=i;記錄相鄰兩個節點構成的二叉樹的根節點；需

33、要說明的是，兩個節點構成的二叉樹，其根節點可以是其中的任何一個；這里選編號小的為根節點，則編號大的為其右子樹；若選編號大的為根節點，則編號小的為其左子樹；因此，最后輸出的前序遍歷結果會有部分不同，但同樣是正確的。如果最大加分二叉樹的所有節點的度數都是0或2，則最后輸出的前序遍歷結果是唯一的。 end; for d:=2 to n-1 do begin依次計算間距為d的兩個節點構成的二叉樹的最大加分 for i:=1 to n-d do begin s:=valuei,i+valuei+1,i+d;計算以i為根節點，以i+1至i+d間所有節點為右子樹的二叉樹的最大加分 rooti,i+d:=i;

34、 記錄根節點i for j:=1 to d do begin temp:=valuei+j,i+j+valuei,i+j-1*valuei+j+1,i+d;計算以i+j為根節點，以i至i+j-1間所有節點為左子樹，以i+j+1至i+d間所有節點為右子樹的二叉樹的最大加分 if temps then begin如果此值為最大 s:=temp;rooti,i+d:=i+j;記下新的最大值和新的根節點 end; end; temp:=valuei,i+d-1+valuei+d,i+d;計算以i+d為根節點，以i至i+d-1間所有節點為左子樹的二叉樹的最大加分 if temps then begin

35、s:=temp;rooti,i+d:=i+d+1; end; valuei,i+d:=s; end; end; writeln(f2,value1,n:0:0);輸出最大加分 preorder(1,n);輸出最大加分二叉樹的前序遍歷序列 close(f2); end.點評基本題。考查了二叉樹的遍歷和動態規劃算法。難點在于要記錄當前最大加分二叉樹的根節點。疑點是最大加分二叉樹的前序遍歷序列可能不唯一。題四 傳染病控制 【問題背景】 近來，一種新的傳染病肆虐全球。蓬萊國也發現了零星感染者，為防止該病在蓬萊國大范圍流行，該國政府決定不惜一切代價控制傳染病的蔓延。不幸的是，由于人們尚未完全認識這種傳染

36、病，難以準確判別病毒攜帶者，更沒有研制出疫苗以保護易感人群。于是，蓬萊國的疾病控制中心決定采取切斷傳播途徑的方法控制疾病傳播。經過 WHO（世界衛生組織）以及全球各國科研部門的努力，這種新興傳染病的傳播途徑和控制方法已經研究消楚，剩下的任務就是由你協助蓬萊國疾控中心制定一個有效的控制辦法。 【問題描述】 研究表明，這種傳染病的傳播具有兩種很特殊的性質； 第一是它的傳播途徑是樹型的，一個人X只可能被某個特定的人Y感染，只要Y不得病，或者是XY之間的傳播途徑被切斷，則X就不會得病。 第二是，這種疾病的傳播有周期性，在一個疾病傳播周期之內，傳染病將只會感染一代患者，而不會再傳播給下一代。 這些性質大

37、大減輕了蓬萊國疾病防控的壓力，并且他們已經得到了國內部分易感人群的潛在傳播途徑圖（一棵樹）。但是，麻煩還沒有結束。由于蓬萊國疾控中心人手不夠，同時也缺乏強大的技術，以致他們在一個疾病傳播周期內，只能設法切斷一條傳播途徑，而沒有被控制的傳播途徑就會引起更多的易感人群被感染（也就是與當前已經被感染的人有傳播途徑相連，且連接途徑沒有被切斷的人群）。當不可能有健康人被感染時，疾病就中止傳播。所以，蓬萊國疾控中心要制定出一個切斷傳播途徑的順序，以使盡量少的人被感染。你的程序要針對給定的樹，找出合適的切斷順序。【輸入格式】 輸入格式的第一行是兩個整數n（1n300）和p。接下來p行，每一行有兩個整數i和j

38、，表示節點i和j間有邊相連（意即，第i人和第j人之間有傳播途徑相連）。其中節點1是已經被感染的患者。【輸出格式】 只有一行，輸出總共被感染的人數。【輸入樣例】 7 6 1 2 1 3 2 4 2 5 3 6 3 7【輸出樣例】 3分析本題關鍵是要找到切斷傳染途徑的算法，這并不難。以測試數據Epidemic.in5為例說明如下：在圖1中，可以先切斷1與2或者1與8或者1與16之間的任何一條途徑，以先切斷1與2為例，結果如下：此時，1，8，16均已被感染，可將它們“合并”為一個新的節點，節點號取作8，如下圖：這樣，它與圖1十分相似，因此可用遞歸算法來做。PASCAL源程序program NOIP2003_4_Epidemic; const