NOIP2001提高組解題報(bào)告1

1、第七屆（2001）分區(qū)聯(lián)賽復(fù)賽解題報(bào)告（提高組）俞瑋趙爽第一題：一元三次方程求解給出一個(gè)三次方程，試求它所有的三個(gè)根。這里所有的根都在區(qū)間中，并保證方程具有三個(gè)實(shí)根，且它們之間的差不小于1。分析：如果是一般的求三次方程根的問(wèn)題，那么只能直接使用求根公式，但這是非常復(fù)雜的。由于題目要求只精確到0.01，故我們考慮一下是否可以應(yīng)用數(shù)值方法進(jìn)行計(jì)算。由題目給出的方程在區(qū)間內(nèi)存在根的條件可知，我們可以用一個(gè)變量從-100.000到100.000以步長(zhǎng)0.001做循環(huán)。若，則可知在區(qū)間內(nèi)存在方程的解。這樣無(wú)論這個(gè)區(qū)間內(nèi)的解是什么，在取兩位小數(shù)的精度后都與取兩位小數(shù)的結(jié)果是一樣的。故我們就可以把取兩位小數(shù)

2、精度的作為問(wèn)題的解。另外還有可能方程的根在區(qū)間端點(diǎn)的情況，我們可以通過(guò)判斷是否為0來(lái)獲得。但這種方法由于用到了題目所要求的數(shù)值精度小的特殊性，故無(wú)法擴(kuò)展。而在用數(shù)值方法求方程根的時(shí)候，我們最常用的方法就是二分法。該方法的應(yīng)用在于如果確定了方程在區(qū)間內(nèi)如果存在且只存在一個(gè)根，那么我們可以用逐次縮小根可能存在范圍的方法確定出根的某精度的數(shù)值。該方法主要利用的就是題目所給的若在區(qū)間內(nèi)存在一個(gè)方程的根，則這個(gè)事實(shí)，并重復(fù)執(zhí)行如下的過(guò)程：l 取當(dāng)前可能存在解的區(qū)間；l 若或，則可確定根為并退出過(guò)程；l 若，則由題目給出的定理可知根在區(qū)間中，故對(duì)區(qū)間重復(fù)該過(guò)程；l 若，則必然有，也就是說(shuō)根在中，應(yīng)該對(duì)此區(qū)

3、間重復(fù)該過(guò)程。最后，就可以得到精確到0.001的根。再考慮什么樣的區(qū)間內(nèi)會(huì)有根 更確切地說(shuō)是只有一個(gè)根。由于題目給出了所有的根都在-100到100之間，且根與根之間差不小于1的限制條件，故我們可知，在、這201個(gè)區(qū)間內(nèi)，每個(gè)區(qū)間內(nèi)至多只能存在一個(gè)根。這樣對(duì)除去區(qū)間外 該區(qū)間顯然只有一個(gè)數(shù)，可以用用判斷是否為0的方法來(lái)求出該區(qū)間內(nèi)方程的根。對(duì)此，我們特殊處理。的其他的區(qū)間，要么，要么時(shí)這個(gè)方程在此區(qū)間內(nèi)才有解。若，顯然為解；若，則可以利用上面所說(shuō)的方法球出解來(lái)。這樣就可求出這個(gè)方程的所有解。最后是輸出的解要求排序。我們既可以在求出來(lái)之后排序，也可以從小到大的順序求解，就可以按照升序求出所有解。數(shù)

4、據(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ù)無(wú)序劃分成份互不相同的正整數(shù)之和的方法總數(shù)。分析：這是一道整數(shù)剖分的問(wèn)題。這類問(wèn)題的數(shù)學(xué)性很強(qiáng)，方法也很多。這里介紹一種較為巧妙的辦法。我們不必拘泥于原問(wèn)題如何求解，而把思維轉(zhuǎn)換一個(gè)角度來(lái)考慮一個(gè)與原問(wèn)題等價(jià)的問(wèn)題。我們可以形象的把n的k-自然數(shù)剖分看作把n塊積木堆成k列，且每列的積木個(gè)數(shù)依次遞增，也就是這n塊積木被

5、從左到右積木被堆成了“樓梯狀”。比如，下圖是10的幾種4-剖分?，F(xiàn)在，我們不妨把這三個(gè)圖順時(shí)針旋轉(zhuǎn)90度，成為 該圖為數(shù)學(xué)上的一個(gè)著名圖示（Ferrer圖），對(duì)此有興趣的讀者可以自己參看一些數(shù)學(xué)書。：不難發(fā)現(xiàn)，旋轉(zhuǎn)之后的模型還是10的剖分，不過(guò)約束條件有所不同。很明顯，由于原來(lái)是k剖分，因此新的模型中最大的一個(gè)元素必然是k。而其余的元素大小不限，但都不能大于k。因此問(wèn)題轉(zhuǎn)化成了求n的任意無(wú)序剖分，其中最大的元素是k 由于篇幅有限，這里就不嚴(yán)格證明這兩個(gè)問(wèn)題的等價(jià)性了。當(dāng)然，我們可以把n減去k，成為，剩下的問(wèn)題就是求的任意剖分，且其中每個(gè)元素都不大于k的方案總數(shù)了。求解這個(gè)新的模型可以用遞推的方

6、法。用表示把b做任意剖分，其中最大的一個(gè)部分恰好是a的方案總數(shù)。用表示把b做任意剖分，其中最大的一個(gè)部分不大于a的方案總數(shù)。那么，有：。消去，有：。我們可以按照a、b遞增的順序計(jì)算的值，這樣在在計(jì)算的時(shí)候，和都已經(jīng)得到，故我們只用進(jìn)行一次簡(jiǎn)單的加法運(yùn)算即可。最后的即為所求。這種方法的時(shí)間復(fù)雜度為?？臻g復(fù)雜度為O(nk)，或者我們可以用滾動(dòng)數(shù)組的方法降到O(n)。該題中模型轉(zhuǎn)化的思想，是很值得借鑒的。數(shù)據(jù)：輸入輸出17 23220 4643100 5382254200 55834645200 64132096第三題：統(tǒng)計(jì)單詞個(gè)數(shù)給出一個(gè)長(zhǎng)度不超過(guò)200的由小寫英文字母組成的字符串（約定：該字符串

7、以每行20個(gè)字母的方式輸入，且保證每行一定20個(gè)）。要求將此字符串分成k份（1<k40），且每份中包含的單詞個(gè)數(shù)加起來(lái)最大（每份中包含的單詞可以重疊。當(dāng)選用一個(gè)單詞之后，其第一個(gè)字母不能再用。例如字符串this中可以包含this和is，但是選用this之后就不能再選th）。分析：這一題應(yīng)該算是一道比較原創(chuàng)的題目。注意到題目中有一個(gè)非常特殊的地方，就是以串中某個(gè)位置的字母為首字母，最多只能分出一個(gè)單詞。由于在拆分字符串的過(guò)程中，如果以某位置為首某個(gè)較短單詞被截?cái)?，那么以該位置為首的較長(zhǎng)單詞必然也會(huì)被截?cái)?。也就是說(shuō)，對(duì)于各個(gè)位置來(lái)說(shuō)我們選取較短的單詞總不會(huì)比選取較長(zhǎng)的單詞所形成的單詞少。這樣

8、我們可以定義一個(gè)在位置的參數(shù)表示以位置的字母為首字母，所能形成的最短單詞的長(zhǎng)度。這樣如果在這個(gè)位置加上這個(gè)單詞的長(zhǎng)度之內(nèi)截?cái)?，則以該位置為首字母就不能形成單詞，否則就可能形成一個(gè)單詞 當(dāng)然前提是在這個(gè)位置可以匹配上一個(gè)單詞。這樣對(duì)于所有的不同 這里為該字串的長(zhǎng)度。個(gè)首位置，我們只要在各個(gè)位置依次對(duì)各個(gè)單詞進(jìn)行匹配就以得出所對(duì)應(yīng)的的值，這一部分的復(fù)雜度為O(wl2) 這里為單詞的個(gè)數(shù)。然后是計(jì)算把字串分為多個(gè)部分的過(guò)程中有什么單詞可以留下。由于是把字串分為多個(gè)部分，故我們類比其他的分割字串的問(wèn)題，列出動(dòng)態(tài)規(guī)劃的方程如下：這里有初值為：這個(gè)式子中，表示把字串前個(gè)字符分成段時(shí)所形成的最多單詞的數(shù)目，

9、表示字串的第個(gè)字符開始的個(gè)字符形成的字串中所能形成的單詞數(shù)。這里由于過(guò)于龐大，不能用預(yù)計(jì)算的方法加快速度，只能現(xiàn)用現(xiàn)算。計(jì)算的方法為對(duì)于所有的，如果存在（也就是有單詞可以在位置匹配上），且，則該位置必然可以匹配上一個(gè)單詞。把所有這樣位置的數(shù)目加起來(lái)就可以得到的值了。這樣算法的復(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ù)：輸入輸出12 1thisisapplei

10、sthistheoopbooktheisurrtoywe4isofthebook824 4dfhfghgdfksgdflsdsdssdsdsddfsdffssddsfdfasasassasdsdsdsdsdsdsadadadasdsdsdsdssdd4dssddfdfdfsdsdjkjjk13310 4aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

11、aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa1aaaaa193410 4sdfsdsassdasdddsasddsdasdsasdsadasdasdsaassasaasadassadsaaddssasdasdasdssddsassaasdasdasdasdasddsadsdsadasdasdasadssdssaasssdasdsasdassdssaadsaddsasdasdsadsaasaadsadsasddsadsadsssaadsdsaasddsaadsdsasa6aasadsdasasd125510 4sdfsdsassdasd

12、ddsasddsdasddassdsaadaasdsaassasaasadassadsaaddssasdsaasdassddsassasaddssassasdsaasssdsdsasdasdsddasdasdssaasssdasdsasdassdssaasadsassdssassdsasssasasdsasdsasdsasdsssasdsasdsasdsassdasdsa6asddsaadsdassadsda65第四題：CAR的旅行路線又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每個(gè)城市都有四個(gè)飛機(jī)場(chǎng)，分別位于一個(gè)矩形的四個(gè)頂點(diǎn)上，同一個(gè)城市的兩個(gè)機(jī)場(chǎng)之間有一條筆直的高速鐵路

13、，第i個(gè)城市高速鐵路的單位里程價(jià)格為Ti。任意兩個(gè)不同城市的機(jī)場(chǎng)之間均有航線，所有航線單位里程的價(jià)格均為t。那么Car應(yīng)如何安排到B的路線才能盡可能的節(jié)省花費(fèi)呢？她發(fā)現(xiàn)這并不是一個(gè)簡(jiǎn)單的問(wèn)題，于是她來(lái)向你請(qǐng)教。分析：我們換一種對(duì)題目描述的方法，就是給出一張地圖，求出某人從某點(diǎn)到另一點(diǎn)的最短距離。這是一個(gè)圖論中的標(biāo)準(zhǔn)問(wèn)題，就是在一個(gè)無(wú)向圖中求最短路徑的問(wèn)題。首先，這個(gè)人在從起點(diǎn)到終點(diǎn)所可能停下的點(diǎn)都是確定的，就是一個(gè)城市的四個(gè)機(jī)場(chǎng)（其他的時(shí)候是沒(méi)有更換交通工具的自由的）。所以我們可以以所有的機(jī)場(chǎng)為頂點(diǎn)，而機(jī)場(chǎng)與機(jī)場(chǎng)之間的交通路線 可能為鐵路或航線。為邊建立一個(gè)圖。該圖的邊權(quán)值為機(jī)場(chǎng)之間相互通行所

14、需的時(shí)間。至于求最短路，我們可以使用一個(gè)被稱為Dijkstra的算法。該算法的主要思想就是模擬液體等速的在管子內(nèi)流動(dòng)，先流到的位置就是離起點(diǎn)較近的位置。在使用算法實(shí)現(xiàn)的時(shí)候，我們可以把頂點(diǎn)劃分為已流到的和未流到的兩個(gè)部分。依次找出液體從已流到的部分最少還需經(jīng)過(guò)多少時(shí)間才能流到未流到的部分，并模擬流的過(guò)程。有關(guān)該算法的具體內(nèi)容，請(qǐng)讀者自行參見(jiàn)有關(guān)圖論的算法書籍，這里不贅述。最后，還需注意的是題目中對(duì)于一個(gè)城市只給出了三個(gè)機(jī)場(chǎng)的坐標(biāo)。但我們知道這四個(gè)機(jī)場(chǎng)是成矩形排列的，而矩形的對(duì)角線互相平分。故我們可以先找出這三個(gè)機(jī)場(chǎng)中相對(duì)的兩個(gè)機(jī)場(chǎng)，易知這樣的機(jī)場(chǎng)就是距離最大的兩個(gè)機(jī)場(chǎng)。然后通過(guò)對(duì)這兩個(gè)機(jī)場(chǎng)求平

15、均數(shù)求出該矩形的中心，再把另一個(gè)機(jī)場(chǎng)按矩形的中心作對(duì)稱就可以得出第四個(gè)機(jī)場(chǎng)的坐標(biāo)。還有題目中最多可能有400個(gè)節(jié)點(diǎn)，也就是說(shuō)可能有80000條邊。這些邊顯然是無(wú)法事先計(jì)算并保存下來(lái)的。但由于在求最短路徑的過(guò)程中，每一條邊最多只會(huì)訪問(wèn)兩遍，故我們可以采用現(xiàn)用現(xiàn)算的辦法。其他在計(jì)算點(diǎn)與點(diǎn)之間距離時(shí)也要注意對(duì)整數(shù)取平方時(shí)的運(yùn)算有可能引發(fā)整數(shù)越界的問(wèn)題，我們應(yīng)該先轉(zhuǎn)換成實(shí)數(shù)再進(jìn)行計(jì)算。該算法的時(shí)間復(fù)雜度為，空間復(fù)雜度為O(n)。數(shù)據(jù)：輸入輸出111 10 1 11 1 2 2 2 1 100.00213 10 1 32 2 2 1 1 2 102 12 12 2 22 12 122 22 22 32

16、32 22 10214.14313 10 1 310 1 1 10 1 1 1020 1 30 1 30 111 110 110 10 111 1 111 10310.004110 10 1 227 27 194 105 194 27 10366 290 381 290 366 305 1080 158 196 245 196 158 1289 154 358 154 358 86 217 284 84 350 84 284 1175 289 292 289 175 362 3450 371 420 371 420 32 2241 29 270 29 270 43 4251 182 347 2

17、70 251 270 5347 341 410 341 347 369 11885.035115 50 1 151 2 3 1 4 3 71 12 3 11 4 13 361 22 3 21 4 23 51 32 3 31 4 33 191 42 3 41 4 43 4711 2 13 1 14 3 211 12 13 11 14 13 611 22 13 21 14 23 111 32 13 31 14 33 2711 42 13 41 14 43 2921 2 23 1 24 3 3421 12 23 11 24 13 1621 22 23 21 24 23 1421 32 23 31 24 33 4121 42 23 41 24 43 31924.23關(guān)于 yuwei 和 zhaoshuang 的報(bào)告的一點(diǎn)補(bǔ)充第一題：其實(shí)最簡(jiǎn)單的方法是這樣子的：讓 x 從