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

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