高中信息技術(shù) NOIP2005信息學(xué)奧林匹克提高組解題報(bào)告

1、NOIP2005信息學(xué)奧林匹克分區(qū)聯(lián)賽解題報(bào)告第一題：誰(shuí)拿了最多的獎(jiǎng)學(xué)-Scholar 問(wèn)題評(píng)估這個(gè)題目據(jù)問(wèn)題本身而言是相當(dāng)簡(jiǎn)單的，沒(méi)有牽涉到過(guò)多的算法，屬于普及型試題。同時(shí)也是對(duì)實(shí)際問(wèn)題一種分析和判斷?？偟膩?lái)看，本題在方向上，向現(xiàn)實(shí)問(wèn)題邁出了一步，是信息學(xué)和生活有了更多的聯(lián)系。問(wèn)題的算法是模擬。當(dāng)中唯一的難點(diǎn)就是數(shù)據(jù)處理，考察點(diǎn)為數(shù)據(jù)庫(kù)的建立和統(tǒng)計(jì)。 程序?qū)崿F(xiàn)由于程序數(shù)據(jù)范圍只有100，當(dāng)中不牽涉到數(shù)據(jù)移動(dòng)，所以用一個(gè)紀(jì)錄型數(shù)組，或者多個(gè)數(shù)組均可，在這里我們使用紀(jì)錄型來(lái)描述。對(duì)于輸入數(shù)據(jù)有兩種方式來(lái)實(shí)現(xiàn)。法一逐個(gè)字符累加。首先定義C:char; 然后利用Until c= ;作為終止符，將讀入

2、的字符連接存儲(chǔ)到中。代碼為：Repeat read(c); :=+c; until c= ; :=copy(,1,length(ai.s)-1);這樣做的好處是，后面的值可以直接用read語(yǔ)句讀入。但是最后一個(gè)值后，要記得readln;法二一次讀入,然后分離。這樣做需要逐個(gè)分離，對(duì)本題來(lái)說(shuō)稍顯復(fù)雜，但對(duì)NOIP來(lái)說(shuō)此方法必須掌握，有的時(shí)候一定要用。具體實(shí)現(xiàn)，讀入一個(gè)字符串S。利用pos( ,s);找出空格位置。再利用Copy函數(shù)，和Val函數(shù)進(jìn)行截取，和轉(zhuǎn)換。部分代碼：(s:string;j,ok:integer)readl

3、n(s);j:=pos( ,s);:=copy(s,1,j-1);s:= copy(s,j+1,50); /當(dāng)長(zhǎng)度字符串長(zhǎng)度是，為后面全部截取。j:=pos( ,s);Val(copy(s,1,j-1),ai.qp,ok);s:= copy(s,j+1,50);.對(duì)于符號(hào)用if語(yǔ)句作一下判斷就是了，太easy不寫了，后面還有幾個(gè)值，用同樣方法處理就可以了。以上完成了數(shù)據(jù)庫(kù)的建庫(kù)工作，后面是統(tǒng)計(jì)，當(dāng)然，我們?cè)跊](méi)讀完一行數(shù)據(jù)后就可進(jìn)行統(tǒng)計(jì)。用If語(yǔ)句判斷他是否能得到相應(yīng)的分值即可。分5條If語(yǔ)句寫，每回可以就加入相應(yīng)的分值。將每個(gè)的分值匯總計(jì)入到總數(shù)變量ZD當(dāng)中。與當(dāng)前最大值進(jìn)行比較

4、，得到Max對(duì)應(yīng)的I值。后面就是輸出的問(wèn)題了。小結(jié)、注意本題為簡(jiǎn)單題，只要思路明確清晰，就可AC。時(shí)間復(fù)雜度O(n)。但有一個(gè)細(xì)節(jié)，ZD變量必須定義Longint或以上類型否則會(huì)Error201的。第二題 過(guò)河-River 問(wèn)題分析此題初看是一個(gè)典型的搜索題。從河的一側(cè)到河的另一側(cè)，要找最少踩到的石頭數(shù)。但從數(shù)據(jù)范圍來(lái)看。1.109長(zhǎng)度的橋。就算是O(n)的算法也不能在一秒內(nèi)出解。如果搜索石子，方法更困難。這要考慮到前面以及后面連續(xù)的石子。若換一種方法。用動(dòng)態(tài)規(guī)劃，以石子分階段的一維動(dòng)規(guī)，時(shí)間復(fù)雜度是O(n2)。最多也只有100100的時(shí)間。但是這樣分狀態(tài)就十分復(fù)雜。因?yàn)槭^的分布是沒(méi)有任何規(guī)

5、律，而且會(huì)有后效性。這樣只好有回到搜索。搜索石子會(huì)和動(dòng)規(guī)一樣沒(méi)有規(guī)律。我們一橋的長(zhǎng)度為對(duì)象進(jìn)行搜索，然后再加上一個(gè)巧妙的剪枝就可以在很短的時(shí)間內(nèi)出解?？梢蕴?hào)稱為O(m2)。批注：號(hào)稱一詞已成為湖南OI本世紀(jì)流行詞匯 題目實(shí)現(xiàn)先以時(shí)間為對(duì)象進(jìn)行搜索。時(shí)間復(fù)雜度為O(L)。從橋的一側(cè)到另一側(cè)，中間最多只有100個(gè)石子。假設(shè)橋長(zhǎng)為最大值(109)，石頭數(shù)也為最大值(100)。這樣中間一定會(huì)有很多“空長(zhǎng)條” (兩個(gè)石子中的空地)，處理時(shí)把這些跳過(guò)，就只會(huì)有M次運(yùn)算。關(guān)鍵是找出每一個(gè)可以跳過(guò)的“空長(zhǎng)條”。我們可以先把青蛙可以跳出的所有可能求出，然后就可以求出可以忽略的“空長(zhǎng)條”。特殊算法ai:前i個(gè)坐標(biāo)

6、中石子最小個(gè)數(shù),初始為第i個(gè)坐標(biāo)的石子個(gè)數(shù)bi:第i個(gè)石子坐標(biāo)動(dòng)規(guī)a0=0;對(duì)n=tan=minan+an-s,an+an-s-1, .,an+an-t對(duì)s=nt，顯然對(duì)于bi-1+tnbi，an總是等于abi-1.abi-1+t中的數(shù)，因此可對(duì)其進(jìn)行壓縮。注意，在計(jì)算過(guò)程中，由于其中有一些坐標(biāo)是永遠(yuǎn)走不到的，因此需要用一個(gè)布爾型的數(shù)組cn進(jìn)行判斷。方法是，對(duì)于cn,如果0ns,cn-t,cn-t+1,.,cn-s都為false,則cn也為false。第三題 篝火晚會(huì)-fire 問(wèn)題評(píng)估此題或許大多數(shù)人會(huì)覺(jué)得很麻煩。或許有人會(huì)選擇搜索來(lái)做，顯然，50000的數(shù)據(jù)量不可能允許搜索不超時(shí)。或許有人

7、會(huì)用貪心，但是卻無(wú)從下手。動(dòng)態(tài)規(guī)劃？怎么劃階段更是一個(gè)難題。然而，此題卻不是考察選手的算法的，而是考察你從題目中找出基本核心的能力。 題目實(shí)現(xiàn)題目給你的初始狀態(tài)是一個(gè)回路，從第一個(gè)同學(xué)前斷開，不難看出這是一個(gè)嚴(yán)格的上升序列。而輸入的數(shù)據(jù)也可以將之構(gòu)成一個(gè)包含所有同學(xué)的回路，否則就達(dá)不到?jīng)]個(gè)人的愿望。我們可以用兩的數(shù)組來(lái)儲(chǔ)存兩個(gè)數(shù)組的狀態(tài)，初始狀態(tài)為st，目標(biāo)狀態(tài)為en。sti=i,i取隨機(jī)函數(shù)生成的數(shù)列。這種方法比較有效，無(wú)規(guī)律。2取偽隨機(jī)數(shù)列。這是一種比較便于人工控制的手段。3取實(shí)數(shù)。由于其他皆為整數(shù)，小數(shù)部分便成為判斷的優(yōu)越條件。一般情況下取47組值便可通過(guò)極大部分情況，實(shí)數(shù)需要更小。如果

8、取更多組的值，便可以通過(guò)幾乎所有的情況（將兩式連立，只有當(dāng)取值都為方程的解時(shí)才會(huì)出現(xiàn)誤判，顯然這樣的幾率是極小的）。補(bǔ)充：這道題可能會(huì)有選手在數(shù)據(jù)類型上選擇不當(dāng)，導(dǎo)致一些情況會(huì)出現(xiàn)溢出。 表達(dá)式求值 經(jīng)過(guò)上面的敘述，難點(diǎn)落在了表達(dá)式求值上，在這里我們介紹一下最一般、最簡(jiǎn)單的方法，棧運(yùn)算。用棧實(shí)現(xiàn)表達(dá)式求值的方法：首先，我們要給每一個(gè)符號(hào)一個(gè)優(yōu)先級(jí)：符號(hào)+ - * /()棧內(nèi)級(jí)別24608棧外級(jí)別13580可以看到，優(yōu)先級(jí)高的符號(hào)先算。為了方便起見，我們定義特殊符號(hào)#，它級(jí)別最低（賦-1）先將它置棧底，然后依次讀入每個(gè)字符，如果是數(shù)字則入數(shù)棧。如果是符號(hào)，就與棧頂符號(hào)比較優(yōu)先級(jí)。如果相等，則退棧，讀下一字符。如果棧外大，則入棧。如果棧內(nèi)大，則取棧頂元素與數(shù)棧最頂2元素運(yùn)算，結(jié)果入數(shù)棧。這個(gè)符號(hào)繼續(xù)處理（再與棧頂比較）。直到讀到最后符號(hào)#使棧底#出棧時(shí)。數(shù)棧頂即為表達(dá)式結(jié)果。由此，本題已經(jīng)變得清晰了，剩下的就是具體將我們的表述變成代碼。文檔信息文章總排版、總發(fā)布：Clf-梁燁 In 麓山國(guó)際長(zhǎng)郡集團(tuán)第一題分析：Clf-梁燁 In 麓山國(guó)際長(zhǎng)郡集團(tuán)第二題分析：標(biāo)準(zhǔn)算法-Eastorn-李向東In 麓山國(guó)際長(zhǎng)郡集團(tuán) 特殊算法-Whb-吳海波In 麓山國(guó)際長(zhǎng)郡集團(tuán)第三題分析：MaskCai-