NOI提高組解題報告

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

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

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

4、間內(nèi)，每個區(qū)間內(nèi)至多只能存在一個根。這樣對除去區(qū)間100,100夕卜的其他的區(qū)間a,a 1)，要么f(a)=0，要么f (a) f (a 1) ： 0時這個方程在此區(qū)間內(nèi)才有解。若f(a) = 0,顯然a為解；若f (a) f(a 1： 0，則可以利用上面所說的方法球出解來。這樣就可求出這個方程的所有解。最后是輸出的解要求排序。我們既可以在求出來之后排序，也可以從小到大的順序求解，就可以按照升序求出所有解。數(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ù)的劃分求把一個整數(shù)n無序劃分成k份互不相同的正整數(shù)之和的方法總數(shù)。分析：這是一道整數(shù)剖分的問題。這類問題的數(shù)學(xué)性很強(qiáng)，方法也很多。這里介紹一種較為巧 妙的辦法。我們不必拘泥于原問題如何求解， 而把思維轉(zhuǎn)換一個角度來考慮一個與原問題等價的問 題。我們可以形象的把 n的k-自然數(shù)剖分看作把 n塊積木堆成k列，且每列的積木個數(shù)依 次遞增，也就是這 n塊積木被從左到右積木被堆成了“樓梯狀”。比如，下圖是10的幾種更確切地說是只有一個根。該區(qū)間顯然只有一個數(shù)，可以用用判斷4-剖分。f (100)是否為0的方法來求出該區(qū)間內(nèi)方程的根

6、。對此，我們特殊處理?，F(xiàn)在，我們不妨把這三個圖順時針旋轉(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剖分，因此新的模型中最大的一個元素必然是k。而其余的元素大小不限，但都不能大于k。因此問題轉(zhuǎn)化成了求 n的任意無序剖分，其中最大的元素是k。當(dāng)然，我們可以把n減去k，成為n，剩下的問題就是求 n的任意剖分，且其中每個元素都不大于k的方案總數(shù)了。求解這個新的模型可以用遞推的方法。用f a,b表示把b做任意剖分，其中最大的一個部分恰好是a的方案總數(shù)。用g a,b表示把b做任意剖分，其

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

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

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

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

11、i -1的q，如果mlenq存在(也就是有單詞可以在位置q匹配上)，且q - mlenq -1 _ p i -1，則該位置必然可以匹配上一個單詞。把所有這樣位置的數(shù)目加 起來就可以得到gp,i的值了。這樣算法的復(fù)雜度為O(kl 3)。但這里計算還有一個技巧，就是我們可以依次按照 k增加，l增加，i增加的順序計算 f的值。這樣在i由i'增加到i' 1的時候，由于在計算i' 1所對應(yīng)的g值時可以用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這個方程進(jìn)行復(fù)雜度為 0(1)的遞推計算，故總復(fù)雜度可以降到0(kl 2+wl 2)。這種被稱作雙重動態(tài)規(guī)劃的方法，請讀者自己好好體會。數(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旅游。她知道每個城市都有四 個飛機(jī)場，分別位于一個矩形的四個頂點上，同一個城市的兩個機(jī)場之間有一條筆直的高速鐵路，第i個城市高速鐵路的單位里程價格為 Ti。任意兩個不同城市的機(jī)場之間均有航線， 所有航線單位里程的價格均為 t。那么Car應(yīng)如何安排到B的路線才能盡可能的節(jié)省花費呢？她發(fā)現(xiàn)這并不是一個簡單 的問題，于是她來向你請教。分析:我們換一種對題目描述的方法，就是給出一張地圖，求出某人從某點到另一點的最短距離。這是一個圖論中的標(biāo)準(zhǔn)問

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

17、 請讀者自行參見有關(guān)圖論的算法書籍，這里不贅述。最后，還需注意的是題目中對于一個城市只給出了三個機(jī)場的坐標(biāo)。但我們知道這四個機(jī)場是成矩形排列的， 而矩形的對角線互相平分。 故我們可以先找出這三個機(jī)場中相對的兩 個機(jī)場，易知這樣的機(jī)場就是距離最大的兩個機(jī)場。然后通過對這兩個機(jī)場求平均數(shù)求出該矩形的中心，再把另一個機(jī)場按矩形的中心作對稱就可以得出第四個機(jī)場的坐標(biāo)。還有題目中最多可能有 400個節(jié)點，也就是說可能有 80000 條邊。這些邊顯然是無法事先計算并 保存下來的。但由于在求最短路徑的過程中，每一條邊最多只會訪問兩遍，故我們可以采用現(xiàn)用現(xiàn)算的辦法。其他在計算點與點之間距離時也要注意對整數(shù)取平

18、方時的運算有可能引發(fā) 整數(shù)越界的問題，我們應(yīng)該先轉(zhuǎn)換成實數(shù)再進(jìn)行計算。該算法的時間復(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