NOIP2000-2009提高組解題報(bào)告(c語言).doc

NOI分區(qū)聯(lián)賽 - 2000年第六屆提高組試題解析注意：解析和源程序均為OIBH站長劉汝佳所寫，疏漏在所難免，但至少程序均通過了比賽時(shí)使用的測試數(shù)據(jù)，所以還是可以一看。第一題：大家對(duì)正數(shù)進(jìn)制的轉(zhuǎn)換應(yīng)該比較熟悉吧?。ú粫?huì)的看我的循序漸進(jìn)）負(fù)數(shù)進(jìn)制一樣。每次取的余數(shù)保證在0-m-1之間。（例如m=-16,則余數(shù)應(yīng)該在015）就可以直接輸出。所以用系統(tǒng)的“mod”運(yùn)算符的時(shí)候必須注意檢查是不是在該范圍（可能在m+10），否則就調(diào)整。調(diào)整的方法是：if 余數(shù)0 thenbegin 余數(shù)=余數(shù)-m; 商=商+1;end;程序見附件。第二題：很明顯的動(dòng)態(tài)規(guī)劃。令di,j,k為第i個(gè)數(shù)字到第j個(gè)數(shù)字加k個(gè)乘號(hào)所能夠達(dá)到的最大值。狀態(tài)轉(zhuǎn)移方程是：di,j,k=maxnumi,t*dt+1,j,k-1 (枚舉t, 滿足i=t9-9-1第二次是：1和是21但顯然可以兩次把所有的數(shù)揀完(22)。本題是典型的多維動(dòng)態(tài)規(guī)劃，很象IOI93的第四題,另一個(gè)算法是網(wǎng)絡(luò)流，很象IOI97第一題，這里我只分析前者。這道題目的簡單之處是階段很好劃分（對(duì)角線），這種方法我就不介紹了，因?yàn)楹芏嗟胤蕉加薪榻B。這里講一種怪一點(diǎn)的動(dòng)態(tài)規(guī)劃_容易想到的思路是：令dx1,y1,x2,y2表示甲在x1,y1,乙在x2,y2以后（包括取走(x1,y1)）的過程中可以獲得的最大和。則d1,1,1,1就是原問題的解。但是是否能取數(shù)和另一個(gè)人是否事先已經(jīng)到過該格子有關(guān)，我們需要設(shè)計(jì)一種走的方法，使得只根據(jù)x1,y1,x2,y2就能判斷一些關(guān)鍵的格子是否已經(jīng)到達(dá)過。這樣，問題才具有無后效性。為此，我們把路線作如下處理：1)當(dāng)兩個(gè)人路線有交叉的時(shí)候，改成等效的，不交叉的。如下圖，1代表第一個(gè)人，2代表第二個(gè)人。X代表相遇點(diǎn)。X1112 1222X2 12 12 1X1 2X變成：X2221 2111X2 12 12 1X2 1X反正讓2走右邊就行了。2)現(xiàn)在1在第y1列，2在第y2列，讓1和2分別向右走,到達(dá)yy1和yy2列，然后向下走一格這樣如果yy1 = y1, y2 = y2(題目規(guī)定), y1 = y2(剛才的分析),遞推dy1,y2 d1:=d2; 只記錄相鄰兩個(gè)狀態(tài)end;邊界是什么呢？當(dāng)然是從第n列的值了，就是sumn,y1,n(從y1取到n)說了這么多，真不知道我說清楚了沒有（ 好象是沒有:-P ），如果有什么不明確的地方，請(qǐng)大家在論壇上提出來。一句話，就是兩個(gè)人一起，一行一行往下走，每一行可以一次向右走若干步，但是要保證2在1的右邊。注意最后輸出的是d21,1。如果輸出d11,1,n=1會(huì)得到0。（為什么？自己想啊）現(xiàn)在程序就不難寫了吧。程序見附件：第七屆（2001）分區(qū)聯(lián)賽復(fù)賽解題報(bào)告（提高組）俞瑋趙爽第一題：一元三次方程求解給出一個(gè)三次方程 ，試求它所有的三個(gè)根。這里所有的根都在區(qū)間 中，并保證方程具有三個(gè)實(shí)根，且它們之間的差不小于1。分析：如果是一般的求三次方程根的問題，那么只能直接使用求根公式，但這是非常復(fù)雜的。由于題目要求只精確到0.01，故我們考慮一下是否可以應(yīng)用數(shù)值方法進(jìn)行計(jì)算。由題目給出的方程在區(qū)間內(nèi)存在根的條件可知，我們可以用一個(gè)變量 從-100.000到100.000以步長0.001做循環(huán)。若 ，則可知在區(qū)間 內(nèi)存在方程的解。這樣無論這個(gè)區(qū)間內(nèi)的解是什么，在取兩位小數(shù)的精度后都與 取兩位小數(shù)的結(jié)果是一樣的。故我們就可以把取兩位小數(shù)精度的 作為問題的解。另外還有可能方程的根在區(qū)間端點(diǎn) 的情況，我們可以通過判斷 是否為0來獲得。但這種方法由于用到了題目所要求的數(shù)值精度小的特殊性，故無法擴(kuò)展。而在用數(shù)值方法求方程根的時(shí)候，我們最常用的方法就是二分法。該方法的應(yīng)用在于如果確定了方程 在區(qū)間 內(nèi)如果存在且只存在一個(gè)根，那么我們可以用逐次縮小根可能存在范圍的方法確定出根的某精度的數(shù)值。該方法主要利用的就是題目所給的若在區(qū)間 內(nèi)存在一個(gè)方程的根，則 這個(gè)事實(shí)，并重復(fù)執(zhí)行如下的過程：l取當(dāng)前可能存在解的區(qū)間 ；l若 或 ，則可確定根為 并退出過程；l若 ，則由題目給出的定理可知根在區(qū)間 中，故對(duì)區(qū)間 重復(fù)該過程；l若 ，則必然有 ，也就是說根在 中，應(yīng)該對(duì)此區(qū)間重復(fù)該過程。最后，就可以得到精確到0.001的根。再考慮什么樣的區(qū)間內(nèi)會(huì)有根 。由于題目給出了所有的根都在-100到100之間，且根與根之間差不小于1的限制條件，故我們可知，在 、 、 、 這201個(gè)區(qū)間內(nèi)，每個(gè)區(qū)間內(nèi)至多只能存在一個(gè)根。這樣對(duì)除去區(qū)間 外 的其他的區(qū)間 ，要么 ，要么 時(shí)這個(gè)方程在此區(qū)間內(nèi)才有解。若 ，顯然 為解；若 ，則可以利用上面所說的方法球出解來。這樣就可求出這個(gè)方程的所有解。最后是輸出的解要求排序。我們既可以在求出來之后排序，也可以從小到大的順序求解，就可以按照升序求出所有解。數(shù)據(jù)：輸入輸出11 -2 -1 2-1.00 1.00 2.0021 -4.65 2.25 1.4-0.35 1.00 4.0031 10 -1 -10-10.00 -1.00 1.0041 -1.8 -8.59 -0.84-2.10 -0.10 4.00第二題：數(shù)的劃分求把一個(gè)整數(shù) 無序劃分成 份互不相同的正整數(shù)之和的方法總數(shù)。分析：這是一道整數(shù)剖分的問題。這類問題的數(shù)學(xué)性很強(qiáng)，方法也很多。這里介紹一種較為巧妙的辦法。我們不必拘泥于原問題如何求解，而把思維轉(zhuǎn)換一個(gè)角度來考慮一個(gè)與原問題等價(jià)的問題。我們可以形象的把n的k-自然數(shù)剖分看作把n塊積木堆成k列，且每列的積木個(gè)數(shù)依次遞增，也就是這n塊積木被從左到右積木被堆成了“樓梯狀”。比如，下圖是10的幾種4-剖分。 現(xiàn)在，我們不妨把這三個(gè)圖順時(shí)針旋轉(zhuǎn)90度，成為 ： 不難發(fā)現(xiàn)，旋轉(zhuǎn)之后的模型還是10的剖分，不過約束條件有所不同。很明顯，由于原來是k剖分，因此新的模型中最大的一個(gè)元素必然是k。而其余的元素大小不限，但都不能大于k。因此問題轉(zhuǎn)化成了求n的任意無序剖分，其中最大的元素是k 。當(dāng)然，我們可以把n減去k，成為 ，剩下的問題就是求 的任意剖分，且其中每個(gè)元素都不大于k的方案總數(shù)了。求解這個(gè)新的模型可以用遞推的方法。用 表示把b做任意剖分，其中最大的一個(gè)部分恰好是a的方案總數(shù)。用 表示把b做任意剖分，其中最大的一個(gè)部分不大于a的方案總數(shù)。那么，有： 。消去 ，有： 。我們可以按照a、b遞增的順序計(jì)算 的值，這樣在在計(jì)算 的時(shí)候， 和 都已經(jīng)得到，故我們只用進(jìn)行一次簡單的加法運(yùn)算即可。最后的 即為所求。這種方法的時(shí)間復(fù)雜度為 。空間復(fù)雜度為O(nk)，或者我們可以用滾動(dòng)數(shù)組的方法降到O(n)。該題中模型轉(zhuǎn)化的思想，是很值得借鑒的。數(shù)據(jù)：給出一個(gè)長度不超過200的由小寫英文字母組成的字符串（約定：該字符串以每行20個(gè)字母的方式輸入，且保證每行一定20個(gè)）。要求將此字符串分成k份（1k40），且每份中包含的單詞個(gè)數(shù)加起來最大（每份中包含的單詞可以重疊。當(dāng)選用一個(gè)單詞之后，其第一個(gè)字母不能再用。例如字符串this中可以包含this和is，但是選用this之后就不能再選th）。分析：這一題應(yīng)該算是一道比較原創(chuàng)的題目。注意到題目中有一個(gè)非常特殊的地方，就是以串中某個(gè)位置的字母為首字母，最多只能分出一個(gè)單詞。由于在拆分字符串的過程中，如果以某位置為首某個(gè)較短單詞被截?cái)?，那么以該位置為首的較長單詞必然也會(huì)被截?cái)?。也就是說，對(duì)于各個(gè)位置來說我們選取較短的單詞總不會(huì)比選取較長的單詞所形成的單詞少。這樣我們可以定義一個(gè)在位置 的參數(shù) 表示以位置 的字母為首字母，所能形成的最短單詞的長度。這樣如果在這個(gè)位置加上這個(gè)單詞的長度之內(nèi)截?cái)?，則以該位置為首字母就不能形成單詞，否則就可能形成一個(gè)單詞 。這樣對(duì)于所有的不同 個(gè)首位置，我們只要在各個(gè)位置依次對(duì)各個(gè)單詞進(jìn)行匹配就以得出所對(duì)應(yīng)的 的值，這一部分的復(fù)雜度為O(wl2) 。然后是計(jì)算把字串分為多個(gè)部分的過程中有什么單詞可以留下。由于是把字串分為多個(gè)部分，故我們類比其他的分割字串的問題，列出動(dòng)態(tài)規(guī)劃的方程如下： 這里有初值 為： 這個(gè)式子中， 表示把字串前 個(gè)字符分成 段時(shí)所形成的最多單詞的數(shù)目， 表示字串的第 個(gè)字符開始的 個(gè)字符形成的字串中所能形成的單詞數(shù)。這里 由于過于龐大，不能用預(yù)計(jì)算的方法加快速度，只能現(xiàn)用現(xiàn)算。計(jì)算的方法為對(duì)于所有 的 ，如果 存在（也就是有單詞可以在位置 匹配上），且 ，則該位置必然可以匹配上一個(gè)單詞。把所有這樣位置的數(shù)目加起來就可以得到 的值了。這樣算法的復(fù)雜度為O(kl3)。但這里計(jì)算還有一個(gè)技巧，就是我們可以依次按照 增加， 增加， 增加的順序計(jì)算 的值。這樣在 由 增加到 的時(shí)候，由于在計(jì)算 所對(duì)應(yīng)的 值時(shí)可以用 這個(gè)方程進(jìn)行復(fù)雜度為O(1)的遞推計(jì)算，故總復(fù)雜度可以降到O(kl2+wl2)。這種被稱作雙重動(dòng)態(tài)規(guī)劃的方法，請(qǐng)讀者自己好好體會(huì)。數(shù)據(jù)：第四題：CAR的旅行路線又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每個(gè)城市都有四個(gè)飛機(jī)場，分別位于一個(gè)矩形的四個(gè)頂點(diǎn)上，同一個(gè)城市的兩個(gè)機(jī)場之間有一條筆直的高速鐵路，第i個(gè)城市高速鐵路的單位里程價(jià)格為Ti。任意兩個(gè)不同城市的機(jī)場之間均有航線，所有航線單位里程的價(jià)格均為t。那么Car應(yīng)如何安排到B的路線才能盡可能的節(jié)省花費(fèi)呢？她發(fā)現(xiàn)這并不是一個(gè)簡單的問題，于是她來向你請(qǐng)教。分析：我們換一種對(duì)題目描述的方法，就是給出一張地圖，求出某人從某點(diǎn)到另一點(diǎn)的最短距離。這是一個(gè)圖論中的標(biāo)準(zhǔn)問題，就是在一個(gè)無向圖中求最短路徑的問題。首先，這個(gè)人在從起點(diǎn)到終點(diǎn)所可能停下的點(diǎn)都是確定的，就是一個(gè)城市的四個(gè)機(jī)場（其他的時(shí)候是沒有更換交通工具的自由的）。所以我們可以以所有的機(jī)場為頂點(diǎn)，而機(jī)場與機(jī)場之間的交通路線 為邊建立一個(gè)圖。該圖的邊權(quán)值為機(jī)場之間相互通行所需的時(shí)間。至于求最短路，我們可以使用一個(gè)被稱為Dijkstra的算法。該算法的主要思想就是模擬液體等速的在管子內(nèi)流動(dòng)，先流到的位置就是離起點(diǎn)較近的位置。在使用算法實(shí)現(xiàn)的時(shí)候，我們可以把頂點(diǎn)劃分為已流到的和未流到的兩個(gè)部分。依次找出液體從已流到的部分最少還需經(jīng)過多少時(shí)間才能流到未流到的部分，并模擬流的過程。有關(guān)該算法的具體內(nèi)容，請(qǐng)讀者自行參見有關(guān)圖論的算法書籍，這里不贅述。最后，還需注意的是題目中對(duì)于一個(gè)城市只給出了三個(gè)機(jī)場的坐標(biāo)。但我們知道這四個(gè)機(jī)場是成矩形排列的，而矩形的對(duì)角線互相平分。故我們可以先找出這三個(gè)機(jī)場中相對(duì)的兩個(gè)機(jī)場，易知這樣的機(jī)場就是距離最大的兩個(gè)機(jī)場。然后通過對(duì)這兩個(gè)機(jī)場求平均數(shù)求出該矩形的中心，再把另一個(gè)機(jī)場按矩形的中心作對(duì)稱就可以得出第四個(gè)機(jī)場的坐標(biāo)。還有題目中最多可能有400個(gè)節(jié)點(diǎn)，也就是說可能有80000條邊。這些邊顯然是無法事先計(jì)算并保存下來的。但由于在求最短路徑的過程中，每一條邊最多只會(huì)訪問兩遍，故我們可以采用現(xiàn)用現(xiàn)算的辦法。其他在計(jì)算點(diǎn)與點(diǎn)之間距離時(shí)也要注意對(duì)整數(shù)取平方時(shí)的運(yùn)算有可能引發(fā)整數(shù)越界的問題，我們應(yīng)該先轉(zhuǎn)換成實(shí)數(shù)再進(jìn)行計(jì)算。該算法的時(shí)間復(fù)雜度為 ，空間復(fù)雜度為O(n)。關(guān)于 yuwei 和 zhaoshuang 的報(bào)告的一點(diǎn)補(bǔ)充第一題：其實(shí)最簡單的方法是這樣子的：讓 x 從 100.00 到 100.00 枚舉一下，得到20000個(gè) f(x) ， 取跟 0 最接近的三個(gè)f(x)，對(duì)應(yīng)的 x 就是答案了。（提示有時(shí)候會(huì)擾亂別人的思維）第二題：如果時(shí)間不是很嚴(yán)格的話，枚舉還是能過的。第三題：這跟我在分區(qū)賽前出的一道模擬試題方法類似。不過分區(qū)這題的數(shù)據(jù)巨弱，居然只輸出”有多少個(gè)位置開始至少可以有一個(gè)單詞”也能對(duì)4/5的點(diǎn)！真是佩服出數(shù)據(jù)的人第四題：標(biāo)準(zhǔn)算法的題目，不過這題算老題目了 算費(fèi)用的時(shí)候，令 A,B 城市內(nèi)的路費(fèi)為 0 的話，就可以直接得到結(jié)果，而不需要做4遍 Dijkstra。當(dāng)然，用 Flody 也可以做2002年全國青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽復(fù)賽提高組試題解題報(bào)告題一 均分紙牌（存盤名 NOIPG1）分析：如果你想到把每堆牌的張數(shù)減去平均張數(shù)，題目就變成移動(dòng)正數(shù)，加到負(fù)數(shù)中，使大家都變成0，那就意味著成功了一半！拿例題來說，平均張數(shù)為10,原張數(shù)9，8，17，6，變?yōu)?1，-2，7，-4，其中沒有為0的數(shù)，我們從左邊出發(fā)：要使第1堆的牌數(shù)-1變?yōu)?，只須將-1張牌移到它的右邊（第2堆）-2中；結(jié)果是-1變?yōu)?，-2變?yōu)?3，各堆牌張數(shù)變?yōu)?，-3，7，-4；同理：要使第2堆變?yōu)?，只需將-3移到它的右邊（第3堆）中去，各堆牌張數(shù)變?yōu)?，0，4，-4；要使第3堆變?yōu)?，只需將第3堆中的4移到它的右邊（第4堆）中去，結(jié)果為0，0，0，0，完成任務(wù)。每移動(dòng)1次牌，步數(shù)加1。也許你要問，負(fù)數(shù)張牌怎么移，不違反題意嗎？其實(shí)從第i堆移動(dòng)-m張牌到第i+1堆，等價(jià)于從第i+1堆移動(dòng)m張牌到第i堆，步數(shù)是一樣的。如果張數(shù)中本來就有為0的，怎么辦呢？如0，-1，-5，6，還是從左算起（從右算起也完全一樣），第1堆是0，無需移牌，余下與上相同；再比如-1，-2，3，10，-4，-6，從左算起，第1次移動(dòng)的結(jié)果為0，-3，3，10，-4，-6；第2次移動(dòng)的結(jié)果為0，0，0，10，-4，-6，現(xiàn)在第3堆已經(jīng)變?yōu)?了，可節(jié)省1步，余下繼續(xù)。程序清單program NOIPG1; const maxn=100; var i,j,n,step:integer;ave:longint; a:array1.maxnof integer; f:text;filename:string; begin write(Input filename:);readln(filename); assign(f,filename);reset(f); readln(f,n);ave:=0;step:=0; for i:=1 to n do begin read(f,ai); inc(ave,ai); end; ave:=ave div i; for i:=1 to n do ai:=ai-ave; i:=1;j:=n; while ai=0 do inc(i);過濾左邊的0 while aj=0 do dec(j);過濾右邊的0 while (ij) do begin inc(ai+1,ai);將第i堆牌移到第i+1堆中去 ai:=0;第i堆牌移走后變?yōu)? inc(step);移牌步數(shù)計(jì)數(shù) inc(i);對(duì)下一堆牌進(jìn)行循環(huán)操作 while ai=0 do inc(i);過濾移牌過程中產(chǎn)生的0 end; writeln(step); end.點(diǎn)評(píng)：基本題（較易） 本題有3點(diǎn)比較關(guān)鍵：一是善于將每堆牌數(shù)減去平均數(shù)，簡化了問題；二是要過濾掉0（不是所有的0，如-2，3，0，-1中的0是不能過濾的）；三是負(fù)數(shù)張牌也可以移動(dòng)，這是辯證法（關(guān)鍵中的關(guān)鍵）。 題二 字串變換 （存盤名: NOIPG2）分析：本題是典型的廣度優(yōu)先搜索的例子，但如果只采用正向搜索，某些情況下計(jì)算量過大，速度過慢，故采取雙向搜索且判重并適當(dāng)剪枝，效果較好。程序清單$A-,B-,D-,E-,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-,Y-$M 8192,0,655360program NOIPG2; const maxn=2300; type node=record定義節(jié)點(diǎn)數(shù)據(jù)類型 str:string115;dep:byte; end; str表示字串，其長度不會(huì)超過115（長度超過115的字串 不可能通過變換成為目標(biāo)字串，因?yàn)轭}目限定變換10次之內(nèi)，且串長 不超過20，即起始串最多可經(jīng)過5次變換時(shí)增長，中間串的最大長度 為20+5*19=115，否則經(jīng)過余下的步數(shù)不可能變?yōu)殚L度不超過20的 目標(biāo)串），dep表示深度 ctype=array1.maxnof node; bin=0.1; var maxk:byte;c:array 0.1of ctype; x0:array0.6,0.1of string20; filename:string; open,closed:array 0.1 of integer; procedure Init;讀取數(shù)據(jù)，初始化 var f:text;temp:string;i,j:integer; begin for i:=0 to 1 do for j:=1 to maxn do new(ci,j); write(Input filename:);readln(filename); assign(f,filename);reset(f);i:=0; while not eof(f) and (i=6) do begin readln(f,temp); x0i,0:=copy(temp,1,pos( ,temp)-1); x0i,1:=copy(temp,pos( ,temp)+1,length(temp); inc(i); end; maxk:=i-1;close(f); end; procedure calc; var i,j,k:integer;st:bin; d:string;f:text; procedure bool(st:bin);判斷是否到達(dá)目標(biāo)狀態(tài)或雙向搜索相遇 var i:integer; begin if x00,1-st=cst,closedst.str then begin 如果到達(dá)目標(biāo)狀態(tài)，則輸出結(jié)果，退出 writeln(cst,closedst.dep); halt; end; for i:=1 to closed1-st do if cst,closedst.str=c1-st,i.str then begin 如果雙向搜索相遇（即得到同一節(jié)點(diǎn)）， 則輸出結(jié)果（2個(gè)方向搜索的步數(shù)之和），退出 writeln(cst,closedst.dep+c1-st,i.dep); halt; end; end; procedure checkup(st:bin);判斷節(jié)點(diǎn)是否與前面重復(fù) var i:integer; begin for i:=1 to closedst-1 do if cst,i.str=cst,closedst.str then begin dec(closedst);exit;如果節(jié)點(diǎn)重復(fù)，則刪除本節(jié)點(diǎn) end; bool(st);如果節(jié)點(diǎn)不重復(fù)，再判斷是否到達(dá)目標(biāo)狀態(tài) end; procedure expand(st:bin);擴(kuò)展產(chǎn)生新節(jié)點(diǎn) var i,j,k,lx,ld:integer; begin inc(openst);d:=cst,openst.str;隊(duì)首節(jié)點(diǎn)出隊(duì) k:=cst,openst.dep;ld:=length(d); for i:=1 to maxk do begin 從隊(duì)首節(jié)點(diǎn)（父節(jié)點(diǎn)）出發(fā)產(chǎn)生新節(jié)點(diǎn)（子節(jié)點(diǎn)） lx:=length(x0i,st); for j:=1 to ld do begin if (copy(d,j,lx)=x0i,st) and (length(copy(d,1,j-1)+x0i,1-st +copy(d,j+lx,ld)=maxn then exit;如果隊(duì)列已滿，只好退出 inc(closedst);新節(jié)點(diǎn)入隊(duì)cst,closedst.str:=copy(d,1,j-1)+x0i,1-st+copy(d,j+lx,ld); cst,closedst.dep:=k+1;子節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+1 checkup(st);檢查新節(jié)點(diǎn)是否重復(fù) end; end; end; end; Begin for st:=0 to 1 do begin正向(st=0)逆向(st=1)搜索節(jié)點(diǎn)隊(duì)列初始化 openst:=0;closedst:=1; cst,closedst.str:=x00,st;cst,closedst.dep:=0; bool(st); end; repeat 選擇節(jié)點(diǎn)數(shù)較少且隊(duì)列未空、未滿、深度未達(dá)到10的方向先擴(kuò)展 if (open0=closed0) or (closed0=maxn) or (c0,closed0.dep10) then expand(0); if (open1=closed1) or (closed1=maxn) or (c1,closed1.dep10) then expand(1); 如果一方搜索終止，繼續(xù)另一方的搜索，直到兩個(gè)方向都終止 if not (open0=closed0) or (closed0=maxn) or (c0,closed0.dep10) then expand(0); if not (open1=closed1) or (closed1=maxn) or (c1,closed1.dep10) then expand(1); until (open0=closed0) or (c0,closed0.dep10) or (closed0=maxn) and (closed1=maxn) or (open1=closed1) or (c1,closed1.dep10); 終止條件：任一方隊(duì)空（無解）或搜索深度超過10（10步內(nèi)無解） 或雙方均溢出（可能有解也可能無解，應(yīng)盡量避免，要盡量把節(jié) 點(diǎn)數(shù)組開大一點(diǎn)，采用雙向搜索，采取剪枝措施等） End; BEGIN init; calc; writeln(NO ANSWER!) END.點(diǎn)評(píng)：基本題（較難） 考察隊(duì)列、（雙向）廣度優(yōu)先搜索算法及字符串的運(yùn)算，基本上可以考察出參賽者的數(shù)據(jù)結(jié)構(gòu)和算法水平。 題三 自由落體（存盤名:NOIPG3）問題描述:在高為 H 的天花板上有 n 個(gè)小球，體積不計(jì)，位置分別為 0，1，2，n-1。在地面上有一個(gè)小車（長為 L，高為 K，距原點(diǎn)距離為 S1）。已知小球下落距離計(jì)算公式為 d1/2*g*(t2)，其中 g=10，t 為下落時(shí)間。地面上的小車以速度 V 前進(jìn)。如下圖： 小車與所有小球同時(shí)開始運(yùn)動(dòng)，當(dāng)小球距小車的距離 = 0.00001 時(shí)，即認(rèn)為小球被小車接受（小球落到地面后不能被接受）。請(qǐng)你計(jì)算出小車能接受到多少個(gè)小球。輸入：鍵盤輸人：H，S1，V，L，K，n （l=H，S1，V，L，K，n =100000）輸出：屏幕輸出：小車能接受到的小球個(gè)數(shù)。輸入輸出樣例輸入:5.0 9.0 5.0 2.5 1.8 5輸出:1分析：顯然，小車太慢（即VVmax）時(shí)，一個(gè)球也接不到。即在VVmax時(shí)輸出為0。下面分別求Vmin和Vmax。當(dāng)?shù)趎-1個(gè)小球落地的瞬間，小車在小球的右端離小球尚有e=0.00001的距離，小車的這個(gè)極小速度就是Vmin。小車從天花板落到地面的時(shí)間t1= ,這段時(shí)間內(nèi)小車走了S1-（n-1）-e,所以Vmin= 。當(dāng)?shù)?個(gè)小球落到距小車的上表面為e的瞬間，小車在小球的左端離小球距離為e，小車的這個(gè)極大速度就是Vmax。小球從天花板落到離小車上表面為e的距離的時(shí)間為t2= ,小車移動(dòng)的距離為S1+L+e,所以Vmax= 。那么，當(dāng)VminV=Vmax時(shí)，就可接到球了。顯然，時(shí)間段t2,t1是小車接球的時(shí)間，在t2時(shí)刻，小車的位置為：左表面離原點(diǎn)距離為S1-V*t2,右表面離原點(diǎn)距離為S1-V*t2+L；在t1時(shí)刻，小車的位置為：左表面離原點(diǎn)距離為S1-V*t1,右表面離原點(diǎn)距離為S1-V*t1+L；故小車的接球范圍(在小車運(yùn)動(dòng)范圍外擴(kuò)展e)為S1-V*t1-e，S1-V*t2+L+e,球的個(gè)數(shù)就等于接球范圍內(nèi)所包含的0n-1之間的整數(shù)的個(gè)數(shù).程序清單program NOIPG3; const g=10重力加速度;e=1E-5;小車接受小球的極限距離 var H,s1,v,l,k,t1,t2,Vmin,Vmax:real; n2,n1,num,n:integer; begin readln(h,s1,v,l,k,n);num:=-1; t1:=sqrt(2*h/g);小球落地時(shí)間 if h=k+e then t2:=0 else t2:=sqrt(2*(h-k-e)/g);小球落到小車上的最短時(shí)間 if s1-v*t2+L+en-1 then n2:=n-1;n2取trunc(s1-v*t2+L+e)與n-1的較小值 if s1-v*t1-en-1 then num:=0 else if (s1-v*t1-e)=trunc(s1-v*t1-e) then n1:=trunc(s1-v*t1-e)小車接受的球的最小編號(hào)為n1 else n1:=trunc(s1-v*t1-e)+1; if num=-1 then num:=n2-n1+1;小車接受的球的個(gè)數(shù)為num writeln(num); end.點(diǎn)評(píng)：送分題 本題“物理味”有余而“信息味”不足，連循環(huán)語句都用不上！難見的“送分題”，可物理較差的人也得不到多少分哦！ 題四 矩形覆蓋（存盤名NOIPG4）問題描述:在平面上有 n 個(gè)點(diǎn)（n = 50），每個(gè)點(diǎn)用一對(duì)整數(shù)坐標(biāo)表示。例如：當(dāng) n4 時(shí)，4個(gè)點(diǎn)的坐標(biāo)分另為：p1（1，1），p2（2，2），p3（3，6），P4（0，7），見圖一。 這些點(diǎn)可以用 k 個(gè)矩形（1=k=4）全部覆蓋，矩形的邊平行于坐標(biāo)軸。當(dāng) k=2 時(shí)，可用如圖二的兩個(gè)矩形 sl，s2 覆蓋，s1，s2 面積和為 4。問題是當(dāng) n 個(gè)點(diǎn)坐標(biāo)和 k 給出后，怎樣才能使得覆蓋所有點(diǎn)的 k 個(gè)矩形的面積之和為最小呢。約定：覆蓋一個(gè)點(diǎn)的矩形面積為 0；覆蓋平行于坐標(biāo)軸直線上點(diǎn)的矩形面積也為0。各個(gè)矩形必須完全分開（邊線與頂點(diǎn)也都不能重合）。 輸入:鍵盤輸人文件名。文件格式為n kxl y1x2 y2. .xn yn （0=xi,yi=500) 輸出:輸出至屏幕。格式為：一個(gè)整數(shù)，即滿足條件的最小的矩形面積之和。 輸入輸出樣例d.in :4 21 12 23 60 7屏幕顯示：4分析1、本題的難度較大。如果你這樣認(rèn)為：即在假定已用i個(gè)矩形（面積和滿足最?。└采w所有點(diǎn)的基礎(chǔ)上，窮舉所有2個(gè)矩形合并成1個(gè)矩形（條件是：在所有合并方案中使合并后面積最?。?，從而使矩形個(gè)數(shù)減少為i-1那就錯(cuò)了，可是卻可以通過前4組測試數(shù)據(jù)！正確的做法是對(duì)不同的K值分別進(jìn)行計(jì)算，好在K值較小，否則.討論：k=1，只要求出n個(gè)點(diǎn)坐標(biāo)的最大、最小值，就可求得矩形的位置與面積；k=2，有2個(gè)矩形，它們只有2種分布形式：左右式（flag=0），上下式（flag=1）對(duì)于左右式，顯然要先將所有點(diǎn)按橫坐標(biāo)升序排列，可將點(diǎn)1點(diǎn)i-1放入矩形1中，將點(diǎn)i點(diǎn)n放入矩形2中，求兩矩形的面積之和；如果面積和比上一個(gè)值小，記下；讓i從2循環(huán)到n,就可完成左右式的全部搜索；對(duì)于上下式，先將所有點(diǎn)按縱坐標(biāo)升序排列，依此類推。k=3，有3個(gè)矩形，它們有6種分布形式：要用兩重循環(huán)進(jìn)行搜索：設(shè)i,j為循環(huán)變量，將點(diǎn)1i-1放入矩形1中，點(diǎn)ij-1放入矩形2中，點(diǎn)jn放入矩形3中；點(diǎn)必須在放入前排好序（均為升序）：對(duì)于flag=0,所有點(diǎn)按橫坐標(biāo)排序；對(duì)于flag=1,所有點(diǎn)按縱坐標(biāo)排序；對(duì)于flag=2,所有點(diǎn)先按橫坐標(biāo)排序，然后點(diǎn)in按縱坐標(biāo)排序；對(duì)于flag=3,所有點(diǎn)先按橫坐標(biāo)排序，然后點(diǎn)1j-1按縱坐標(biāo)排序；對(duì)于flag=4,所有點(diǎn)先按縱坐標(biāo)排序，然后點(diǎn)1j-1按橫坐標(biāo)排序；對(duì)于flag=5,所有點(diǎn)先按縱坐標(biāo)排序，然后點(diǎn)in按橫坐標(biāo)排序；至于k=4,4個(gè)矩形有22種分布形式，實(shí)在太復(fù)雜！幸好測試數(shù)據(jù)中沒有K=4的情形(似乎有意放了一馬？)。據(jù)說本題全國沒有一人全對(duì)?。ㄖ灰驥=1，2，3）程序清單$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+,Y+$M 65520,0,655360program NOIPG4; const maxn=50;maxk=3; type rect=record定義矩形數(shù)據(jù)類型 l,r,t,b:word;矩形的左邊，右邊，下邊，上邊距坐標(biāo)軸的距離 end; vxy=record定義點(diǎn)數(shù)據(jù)類型 x,y:word;點(diǎn)的橫、縱坐標(biāo) end; var ju:array1.maxkof rect; v:array1.maxn,0.2 of vxy;v0:vxy; n,k,i,j,ii,jj:byte;f:text;filename:string; Smin,temp:longint; function intersect(jui,juj:rect):boolean;判斷兩矩形是否有公共點(diǎn) var b1,b2,t1,t2,l1,l2,r1,r2:word; begin b1:=jui.b;b2:=juj.b;t1:=jui.t;t2:=juj.t; l1:=jui.l;l2:=juj.l;r1:=jui.r;r2:=juj.r; intersect:=(l2=l1) or (r2=l1) or (l2=r1) and (t2=t1) or (b2=t1) or (b2=b1) and (t2=t1); end; function area(ju:rect):longint;求矩形的面積 var temp:longint; begintemp:=ju.b-ju.t;area:=temp*(ju.r-ju.l);不能直接寫成area:=(ju.b-ju.t)*(ju.r-ju.l);因?yàn)檫@樣可能會(huì)溢出！ end; procedure insert(v:vxy;var ju:rect);將點(diǎn)放入矩形 begin if v.xju.r then ju.r:=v.x; if v.yju.b then ju.b:=v.y; end; procedure init;初始化 begin write(Input filename:);readln(filename); assign(f,filename);reset(f);readln(f,n,k); for i:=1 to n do begin read(f,vi,0.x,vi,0.y); vi,1.x:=vi,0.x;vi,1.y:=vi,0.y; end; for i:=1 to n-1 do按橫坐標(biāo)升序排列各點(diǎn)，存入vi,0 for j:=i+1 to n do if vi,0.xvj,0.x then begin v0:=vi,0;vi,0:=vj,0;vj,0:=v0; end; for i:=1 to n-1 do按縱坐標(biāo)升序排列各點(diǎn)，存入vi,1 for j:=i+1 to n do if vi,1.yvj,1.y then begin v0:=vi,1;vi,1:=vj,1;vj,1:=v0; end; end; procedure solve;核心計(jì)算 begin smin:=maxlongint; case k of 1:beginK=1的情形 ju1.b:=vn,1.y;ju1.t:=v1,1.y; ju1.r:=vn,0.x;ju1.l:=v1,0.x; smin:=area(ju1); end; 2:for jj:=0 to 1 do beginK=2的情形 flag=0,1的情形 ju1.b:=v1,jj.y;ju1.t:=v