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

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

2、,i 0.001)內(nèi)存在方程的解。這樣無論這個(gè)區(qū)間內(nèi)的解是什么，在取兩位小數(shù)的精度后都與i取兩位小數(shù)的結(jié)果是一樣的。故我們就可以把取兩位小數(shù)精度的i作為問題的解。另外還有可能方程的根在區(qū)間端點(diǎn)i的情況，我們可以通過判斷f (i)是否為0來獲得。但這種方法由于用到了題目所要求的數(shù)值精度小的特殊性，故無法擴(kuò)展。而在用數(shù)值方法求方程根的時(shí)候，我們最常用的方法就是二分法。該方法的應(yīng)用在于如果確定了方程f(x)=0在區(qū)間(a, b)內(nèi)如果存在且只存在一個(gè)根，那么我們可以用逐次縮小根可能存在范圍的方法確定出根的某精度的數(shù)值。該方法主要利用的就是題目所給的若在區(qū)間(a,b)內(nèi)存在一個(gè)方程的根，則f (a)

3、f(b) ：0這個(gè)事實(shí)，并重復(fù)執(zhí)行如下的過程：取當(dāng)前可能存在解的區(qū)間(a,b)；a + b若a 0.001 b或f 葺；=0，則可確定根為并退出過程；2 2若f (a) f 號(hào)；0，則由題目給出的定理可知根在區(qū)間a,號(hào) 中，故對(duì)區(qū)間a,號(hào)重復(fù)該過程；若f(a) f a2b .0,則必然有f呼 f(b)：0,也就是說根在 害，b中，應(yīng)該對(duì)此區(qū)間重復(fù)該過程。最后，就可以得到精確到0.001的根。再考慮什么樣的區(qū)間內(nèi)會(huì)有根。由于題目給出了所有的根都在-100到100之間，且根與根之間差不小于1的限制條件，故我們可知，在-100, 一99)、一99,一98)、99,100)、100,100這201個(gè)區(qū)

4、間內(nèi)，每個(gè)區(qū)間內(nèi)至多只能存在一個(gè)根。這樣對(duì)除去區(qū)間100,100夕卜的其他的區(qū)間a,a 1)，要么f(a)=0，要么f (a) f (a 1) ： 0時(shí)這個(gè)方程在此區(qū)間內(nèi)才有解。若f(a) = 0,顯然a為解；若f (a) f(a 1： 0，則可以利用上面所說的方法球出解來。這樣就可求出這個(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

5、-1.8 -8.59 -0.84-2.10 -0.10 4.00第二題：數(shù)的劃分求把一個(gè)整數(shù)n無序劃分成k份互不相同的正整數(shù)之和的方法總數(shù)。分析：這是一道整數(shù)剖分的問題。這類問題的數(shù)學(xué)性很強(qiáng)，方法也很多。這里介紹一種較為巧 妙的辦法。我們不必拘泥于原問題如何求解， 而把思維轉(zhuǎn)換一個(gè)角度來考慮一個(gè)與原問題等價(jià)的問 題。我們可以形象的把 n的k-自然數(shù)剖分看作把 n塊積木堆成k列，且每列的積木個(gè)數(shù)依 次遞增，也就是這 n塊積木被從左到右積木被堆成了“樓梯狀”。比如，下圖是10的幾種更確切地說是只有一個(gè)根。該區(qū)間顯然只有一個(gè)數(shù)，可以用用判斷4-剖分。f (100)是否為0的方法來求出該區(qū)間內(nèi)方程的根

6、。對(duì)此，我們特殊處理?，F(xiàn)在，我們不妨把這三個(gè)圖順時(shí)針旋轉(zhuǎn)90度，成為10=1+1+1+3+410=1+1+2+2+410=1+2+3+4不難發(fā)現(xiàn)，旋轉(zhuǎn)之后的模型還是10的剖分，不過約束條件有所不同。很明顯，由于原來是k剖分，因此新的模型中最大的一個(gè)元素必然是k。而其余的元素大小不限，但都不能大于k。因此問題轉(zhuǎn)化成了求 n的任意無序剖分，其中最大的元素是k。當(dāng)然，我們可以把n減去k，成為n，剩下的問題就是求 n的任意剖分，且其中每個(gè)元素都不大于k的方案總數(shù)了。求解這個(gè)新的模型可以用遞推的方法。用f a,b表示把b做任意剖分，其中最大的一個(gè)部分恰好是a的方案總數(shù)。用g a,b表示把b做任意剖分，其

7、中最大的一個(gè)部分不大于茲的方案總數(shù)。那么，有：”f(a,b)=g(a,b-a).!a。g(a,b)=52 f(i,b)L.7aa消去 f，有：ga,bfi,b -、gi,bi 二gai,b ga, b a。我們可以i=1i =1按照a、b遞增的順序計(jì)算 g(a,b)的值，這樣在在計(jì)算g a,b的時(shí)候，ga-1,b和 g a,b -a都已經(jīng)得到，故我們只用進(jìn)行一次簡(jiǎn)單的加法運(yùn)算即可。最后的gn= g k,n-k即為所求。該圖為數(shù)學(xué)上的一個(gè)著名圖示(Ferrer圖)，對(duì)此有興趣的讀者可以自己參看一些數(shù)學(xué)書 由于篇幅有限，這里就不嚴(yán)格證明這兩個(gè)問題的等價(jià)性了。這種方法的時(shí)間復(fù)雜度為O 2n k 1

8、k = O 2n3k"k 。空間復(fù)雜度為1 22O(nk)，或者我們可以用滾動(dòng)數(shù)組的方法降到O(n)。該題中模型轉(zhuǎn)化的思想，是很值得借鑒的。數(shù)據(jù):第三題：統(tǒng)計(jì)單詞個(gè)數(shù)給出一個(gè)長(zhǎng)度不超過 200的由小寫英文字母組成的字符串(約定：該字符串以每行20個(gè)字母的方式輸入，且保證每行一定20個(gè))。要求將此字符串分成 k份(1<k<40 ),且每份中包含的單詞個(gè)數(shù)加起來最大(每份中包含的單詞可以重疊。當(dāng)選用一個(gè)單詞之后， 其第一個(gè)字母不能再用。例如字符串this中可以包含this和is，但是選用this之后就不能再選 th )。分析：這一題應(yīng)該算是一道比較原創(chuàng)的題目。 注意到題目中有

9、一個(gè)非常特殊的地方， 就是以串 中某個(gè)位置的字母為首字母， 最多只能分出一個(gè)單詞。 由于在拆分字符串的過程中， 如果以 某位置為首某個(gè)較短單詞被截?cái)啵?那么以該位置為首的較長(zhǎng)單詞必然也會(huì)被截?cái)唷?也就是說， 對(duì)于各個(gè)位置來說我們選取較短的單詞總不會(huì)比選取較長(zhǎng)的單詞所形成的單詞少。 這樣我們 可以定義一個(gè)在位置i的參數(shù)mleni表示以位置i的字母為首字母，所能形成的最短單詞的長(zhǎng)度。這樣如果在這個(gè)位置加上這個(gè)單詞的長(zhǎng)度之內(nèi)截?cái)啵瑒t以該位置為首字母就不能形成單詞，否則就可能形成一個(gè)單詞 。這樣對(duì)于所有的不同丨個(gè)首位置，我們只要在各個(gè)位置 依次對(duì)各個(gè)單詞進(jìn)行匹配就以得出所對(duì)應(yīng)的mlen的值，這一部分的

10、復(fù)雜度為 O(wl 2)。然后是計(jì)算把字串分為多個(gè)部分的過程中有什么單詞可以留下。由于是把字串分為多個(gè)部分， 故我們類比其他的分割字串的問題，列出動(dòng)態(tài)規(guī)劃的方程如下：f|,k二檸備十1-i,k -1 gl i 1,小當(dāng)然前提是在這個(gè)位置可以匹配上一個(gè)單詞。這里l為該字串的長(zhǎng)度。 這里w為單詞的個(gè)數(shù)。這里有初值fl,1為:fi,i =gi,i這個(gè)式子中，fl,k表示把字串前l(fā)個(gè)字符分成k段時(shí)所形成的最多單詞的數(shù)目，g p,i表示字串的第 P個(gè)字符開始的i個(gè)字符形成的字串中所能形成的單詞數(shù)。這里gp,i由于過于龐大，不能用預(yù)計(jì)算的方法加快速度，只能現(xiàn)用現(xiàn)算。計(jì)算的方法為對(duì)于所有p _ q _ p

11、i -1的q，如果mlenq存在(也就是有單詞可以在位置q匹配上)，且q - mlenq -1 _ p i -1，則該位置必然可以匹配上一個(gè)單詞。把所有這樣位置的數(shù)目加 起來就可以得到gp,i的值了。這樣算法的復(fù)雜度為O(kl 3)。但這里計(jì)算還有一個(gè)技巧，就是我們可以依次按照 k增加，l增加，i增加的順序計(jì)算 f的值。這樣在i由i'增加到i' 1的時(shí)候，由于在計(jì)算i' 1所對(duì)應(yīng)的g值時(shí)可以用g p -1,i' 1二gp,i' 1 p -1 mle n p-1-1 _ p i'-1=g p,i' p -1 mlen p-1-1 pi

12、9;-1這個(gè)方程進(jìn)行復(fù)雜度為 0(1)的遞推計(jì)算，故總復(fù)雜度可以降到0(kl 2+wl 2)。這種被稱作雙重動(dòng)態(tài)規(guī)劃的方法，請(qǐng)讀者自己好好體會(huì)。數(shù)據(jù):輸入輸出12 1thisisappleisthisthe oopbooktheisurrtoywe4isofthebook824 4dfhfghgdfksgdflsdsds sdsdsddfsdffssddsfdf asasassasdsdsdsdsdsd sadadadasdsdsdsdssdd413dssddfdfdfsdsdjkjjk10 4aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

13、aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa3 aaaaaaaaaaaaaaaaaaaa193aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa1 aaaaa1256510 4 sdfsdsassdasdddsasdd sdasdsasdsadasdasdsa assasaasadassadsaadd ssasdasdasdssddsassa asdasdasdasdasddsads dsadasdasdasadssdssa

14、 asssdasdsasdassdssaa dsaddsasdasdsadsaasa adsadsasddsadsadsssa adsdsaasddsaadsdsasa 6 aasa ds da sasd10 4 sdfsdsassdasdddsasdd sdasddassdsaadaasdsa assasaasadassadsaadd5 ssasdsaasdassddsassa saddssassasdsaasssds dsasdasdsddasdasdssa asssdasdsasdassdssaa sadsassdssassdsasssasasdsasdsasdsasdsssa sdsa

15、sdsasdsassdasdsa 6 asd dsa ads das sad sda第四題：CAR的旅行路線又到暑假了，住在城市 A的Car想和朋友一起去城市 B旅游。她知道每個(gè)城市都有四 個(gè)飛機(jī)場(chǎng)，分別位于一個(gè)矩形的四個(gè)頂點(diǎn)上，同一個(gè)城市的兩個(gè)機(jī)場(chǎng)之間有一條筆直的高速鐵路，第i個(gè)城市高速鐵路的單位里程價(jià)格為 Ti。任意兩個(gè)不同城市的機(jī)場(chǎng)之間均有航線， 所有航線單位里程的價(jià)格均為 t。那么Car應(yīng)如何安排到B的路線才能盡可能的節(jié)省花費(fèi)呢？她發(fā)現(xiàn)這并不是一個(gè)簡(jiǎn)單 的問題，于是她來向你請(qǐng)教。分析:我們換一種對(duì)題目描述的方法，就是給出一張地圖，求出某人從某點(diǎn)到另一點(diǎn)的最短距離。這是一個(gè)圖論中的標(biāo)準(zhǔn)問

16、題，就是在一個(gè)無向圖中求最短路徑的問題。首先，這個(gè)人在從起點(diǎn)到終點(diǎn)所可能停下的點(diǎn)都是確定的，就是一個(gè)城市的四個(gè)機(jī)場(chǎng)（其他的時(shí)候是沒有更換交通工具的自由的）。所以我們可以以所有的機(jī)場(chǎng)為頂點(diǎn)，而機(jī)場(chǎng)與機(jī)場(chǎng)之間的交通路線 為邊建立一個(gè)圖。該圖的邊權(quán)值為機(jī)場(chǎng)之間相互通行所需的時(shí)間。至于 求最短路，我們可以使用一個(gè)被稱為Dijkstra 的算法。該算法的主要思想就是模擬液體等速的在管子內(nèi)流動(dòng)， 先流到的位置就是離起點(diǎn)較近的位置。在使用算法實(shí)現(xiàn)的時(shí)候， 我們可以把頂點(diǎn)劃分為已流到的和未流到的兩個(gè)部分。依次找出液體從已流到的部分最少還需經(jīng)過多少時(shí)間才能流到未流到的部分，并模擬流的過程。有關(guān)該算法的具體內(nèi)容，

17、 請(qǐng)讀者自行參見有關(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)。然后通過對(duì)這兩個(gè)機(jī)場(chǎng)求平均數(shù)求出該矩形的中心，再把另一個(gè)機(jī)場(chǎng)按矩形的中心作對(duì)稱就可以得出第四個(gè)機(jī)場(chǎng)的坐標(biāo)。還有題目中最多可能有 400個(gè)節(jié)點(diǎn)，也就是說可能有 80000 條邊。這些邊顯然是無法事先計(jì)算并 保存下來的。但由于在求最短路徑的過程中，每一條邊最多只會(huì)訪問兩遍，故我們可以采用現(xiàn)用現(xiàn)算的辦法。其他在計(jì)算點(diǎn)與點(diǎn)之間距離時(shí)也要注意對(duì)整數(shù)取平

18、方時(shí)的運(yùn)算有可能引發(fā) 整數(shù)越界的問題，我們應(yīng)該先轉(zhuǎn)換成實(shí)數(shù)再進(jìn)行計(jì)算。該算法的時(shí)間復(fù)雜度為空間復(fù)雜度為O(n)?？赡転殍F路或航線數(shù)據(jù):輸入輸出11 1 10 1 11 1 2 2 2 1 100.0013 10 1 32 2 2 2 1 1 2 102 12 12 2 22 12 122 22 22 32 32 22 10214.1413 10 1 33 10 1 1 10 1 1 1020 1 30 1 30 111 110 110 10 111 1 111 10110 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 2417 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 270 251 270 5347 341 410 341