第2章　 《算法競(jìng)賽入門(mén)經(jīng)典（第2版）》習(xí)題選解

2.1　數(shù)組和字符串

本節(jié)選解習(xí)題來(lái)源于《算法競(jìng)賽入門(mén)經(jīng)典（第2版）》一書(shū)的第3章。

習(xí)題3-1　得分（Score，ACM/ICPC Seoul 2005，UVa1585）

給出一個(gè)由O和X組成的串（長(zhǎng)度為1～80），統(tǒng)計(jì)每個(gè)字符的得分之和。每個(gè)O的得分為已經(jīng)連續(xù)出現(xiàn)的O的個(gè)數(shù)，X得分為0。例如，OOXXOXXOOO的得分為1＋2＋0＋0＋1＋0＋0＋1＋2＋3。

【分析】

使用for循環(huán)對(duì)輸入串的字符進(jìn)行遍歷，維護(hù)一個(gè)已經(jīng)連續(xù)出現(xiàn)的‘O‘個(gè)數(shù)的計(jì)數(shù)器cnt以及串的得分和sum。初始cnt＝0，sum＝0。如果遇到‘O‘就＋＋cnt，然后把cnt加到sum中，如果遇到‘X‘就重置cnt為0。

完整程序（C＋＋11）如下：

習(xí)題3-2　分子量（Molar Mass，ACM/ICPC Seoul 2007，UVa1586）

給出一種物質(zhì)的分子式（不帶括號(hào)），求分子量。本題中的分子式只包含4種原子，分別為C、H、O、N，原子量分別為12.01、1.008、16.00、14.01（單位：g/mol）。例如，C6H5OH的分子量為6×（12.01g/mol）＋6×（1.008g/mol）＋1×（16.00 g/mol）＝94.108g/mol。

【分析】

依次掃描即可，注意原子后面不帶數(shù)目的情況。掃描的過(guò)程中，維護(hù)一個(gè)當(dāng)前已經(jīng)輸入的數(shù)字字符組成的數(shù)字cnt。一開(kāi)始以及遇到一個(gè)新原子時(shí)，cnt＝-1，表示“還未開(kāi)始計(jì)數(shù)”的狀態(tài)。方便遇到原子后不帶數(shù)目以及數(shù)字有多位的情況處理。

和習(xí)題3-1類(lèi)似，也要在循環(huán)結(jié)束之后處理最后一個(gè)原子。完整程序如下：

習(xí)題3-3　數(shù)數(shù)字（Digit Counting，ACM/ICPC Danang 2007，UVa1225）

把前n（n≤10000）個(gè)整數(shù)按順序?qū)懺谝黄穑?23456789101112…數(shù)一數(shù)0～9各出現(xiàn)多少次（輸出10個(gè)整數(shù)，分別是0，1，…，9出現(xiàn)的次數(shù)）。

【分析】

因?yàn)?i>n的最大值比較小，可以用建表的方式來(lái)計(jì)算。令C［n］［k］表示前n個(gè)數(shù)字寫(xiě)在一起，k（k＝0～9）總共出現(xiàn)幾次，則有C［n＋1］［k］＝C［n］［k］＋x，其中x是k在n中出現(xiàn)的次數(shù)。直接按照這個(gè)公式就可以把所有答案提前計(jì)算出來(lái)，然后每讀入一個(gè)n就直接輸出預(yù)處理的結(jié)果即可。

習(xí)題3-4　周期串（Periodic Strings，UVa455）

如果一個(gè)字符串可以由某個(gè)長(zhǎng)度為k的字符串重復(fù)多次得到，就可以說(shuō)該串以k為周期。例如，abcabcabcabc以3為周期（注意，它也以6和12為周期）。

輸入一個(gè)長(zhǎng)度不超過(guò)80的字符串，輸出它的最小周期。

【分析】

字符串的周期p只可能是閉區(qū)間［1，k］內(nèi)能被k整除的數(shù)，然后從小到大遍歷所有的p，看看對(duì)于每個(gè)i＝0～k-1是否符合S［i］＝S［i%C］，找到第一個(gè)全部符合的p就是所求結(jié)果。完整程序如下：

習(xí)題3-5　謎題（Puzzle，ACM/ICPC World Finals 1993，UVa227）

有一個(gè)5*5的網(wǎng)格，其中恰好有一個(gè)格子是空的，其他格子各有一個(gè)字母。一共有4種指令：A、B、L、R，分別表示把空格上／下／左／右的相鄰字母移到空格中。輸入初始網(wǎng)格和指令序列（以數(shù)字0結(jié)束），輸出指令執(zhí)行完畢后的網(wǎng)格。如果有非法指令，應(yīng)輸出“This puzzle has no final configuration．”，例如圖2.1執(zhí)行ARRBBL0后為圖2.2。

【分析】

使用以下結(jié)構(gòu)表示坐標(biāo)和向量：

然后直接模擬即可，可以將4種指令字符以及對(duì)應(yīng)4個(gè)方向的向量存放到一個(gè)map＜char，Vector＞中，方便移動(dòng)時(shí)計(jì)算新的空格位置。

完整程序如下：

習(xí)題3-6　縱橫字謎的答案（Crossword Answers，ACM/ICPC World Finals 1994，UVa232）

輸入一個(gè)r行c列（1≤r，c≤10）的網(wǎng)格，黑格用“*”表示，每個(gè)白格都填有一個(gè)字母。如果一個(gè)白格的左邊相鄰位置或者上邊相鄰位置沒(méi)有白格（可能是黑格，也可能出了網(wǎng)格邊界），則稱(chēng)這個(gè)白格是一個(gè)起始格。

首先把所有起始格按照從上到下、從左到右的順序編號(hào)為1、2、3、…，如圖2.3所示。接下來(lái)要找出所有橫向單詞（Across），這些單詞必須從一個(gè)起始格開(kāi)始，向右延伸到一個(gè)黑格的左邊或者整個(gè)網(wǎng)格的最右列。最后找出所有豎向單詞（Down），這些單詞必須從一個(gè)起始格開(kāi)始，向下延伸到一個(gè)黑格的上邊或者整個(gè)網(wǎng)格的最下行。輸入輸出格式和樣例請(qǐng)參考原題。

【分析】

還是和習(xí)題3-5一樣，建立坐標(biāo)和向量的結(jié)構(gòu)方便進(jìn)行位置的移動(dòng)處理。依次掃描，用一個(gè)全局的Point數(shù)組eligible存放所有單詞的起始點(diǎn)坐標(biāo)，同時(shí)要用兩個(gè)vector＜int＞，即across和down來(lái)分別記錄掃描出的橫向單詞和豎向單詞的起點(diǎn)坐標(biāo)在eligible中的編號(hào)。

在讀取兩個(gè)方向單詞時(shí)，使用兩個(gè)向量計(jì)算來(lái)讀取所有的單詞，即dRight（0，1）和dDown（1，0），這樣可以降低代碼復(fù)雜度。具體請(qǐng)參見(jiàn)代碼，完整程序如下：

習(xí)題3-7　DNA序列（DNA Consensus String，ACM/ICPC Seoul 2006，UVa1368）

輸入m個(gè)長(zhǎng)度均為n的DNA序列，求一個(gè)DNA序列，到所有序列的總Hamming距離盡量小。兩個(gè)等長(zhǎng)字符串的Hamming距離等于字符不同的位置個(gè)數(shù)，如ACGT和GCGA的Hamming距離為2（左數(shù)第1、4個(gè)字符不同）。

輸入整數(shù)m和n（4≤m≤50，4≤n≤1000），以及m個(gè)長(zhǎng)度為n的DNA序列（只包含字母A、C、G、T），輸出到m個(gè)序列的Hamming距離和最小的DNA序列和對(duì)應(yīng)的距離。如有多解，要求字典序最小的解。例如，對(duì)于下面5個(gè)DNA序列，最優(yōu)解為T(mén)AAGATAC。

TATGATAC

TAAGCTAC

AAAGATCC

TGAGATAC

TAAGATGT

【分析】

對(duì)于所求結(jié)果序列S來(lái)說(shuō)，Hamming距離和最小意味著S中每一列的字符都在m個(gè)序列的對(duì)應(yīng)列上出現(xiàn)次數(shù)最多?？梢砸来螌?duì)m個(gè)序列中每一列的字符進(jìn)行統(tǒng)計(jì)，字典序最小并且出現(xiàn)次數(shù)最多的那個(gè)就是S中這一列的字符。完整程序如下：

習(xí)題3-8　循環(huán)小數(shù)（Repeating Decimals，ACM/ICPC World Finals 1990，UVa202）

輸入整數(shù)a和b（0≤a≤3000，1≤b≤3000），輸出a/b的循環(huán)小數(shù)表示以及其循環(huán)節(jié)長(zhǎng)度。例如a＝5，b＝43，小數(shù)表示為0．（116279069767441860465），循環(huán)節(jié)長(zhǎng)度為21。

【分析】

首先簡(jiǎn)單介紹一下長(zhǎng)除法，以3/7為例，如圖2.4所示。

本題實(shí)際上就是模擬長(zhǎng)除法的計(jì)算過(guò)程，其中每一次除法時(shí)都有被除數(shù)和余數(shù)，當(dāng)被除數(shù)出現(xiàn)重復(fù)時(shí)就表示出現(xiàn)循環(huán)節(jié)了。所以需要記錄每一次的被除數(shù)及其在循環(huán)小數(shù)中的位置，需要注意當(dāng)除數(shù)不夠除，每一次補(bǔ)零也需要記錄其對(duì)應(yīng)的位置。

完整程序如下：

習(xí)題3-9　子序列（All in All，UVa10340）

輸入兩個(gè)字符串s和t，判斷是否可以從t中刪除0個(gè)或多個(gè)字符（其他字符順序不變），得到字符串s。例如，abcde可以得到bce，但無(wú)法得到dc。

【分析】

可以使用兩個(gè)變量i和j對(duì)兩個(gè)字符串s和t同時(shí)進(jìn)行遍歷，對(duì)于每個(gè)i，如果t［j］！＝s［i］，那么一直對(duì)j進(jìn)行遞增操作，如果j越界，說(shuō)明t［j…］中不存在等于s［i］的字符，查找失敗。如果對(duì)于每個(gè)i匹配成功，則說(shuō)明問(wèn)題有解，否則無(wú)法從t中刪除字符得到s。完整程序如下：

習(xí)題3-10　盒子（Box，ACM/ICPC NEERC 2004，UVa1587）

給定6個(gè)矩形的長(zhǎng)和寬w_i和h_i（1≤w_i，h_i≤1000），判斷它們能否構(gòu)成長(zhǎng)方體的6個(gè)面。

【分析】

注意長(zhǎng)方體的6個(gè)面一定是可以形成3對(duì)相同的矩形，并且邊的長(zhǎng)度剛好只有3個(gè)。對(duì)輸入的矩形的長(zhǎng)寬進(jìn)行處理，使得長(zhǎng)x≥寬y。輸入完按照先x后y對(duì)輸入的矩形進(jìn)行排序。排序完成之后，如果輸入合法，應(yīng)該就是3對(duì)矩形，每一對(duì)都應(yīng)該完全一致；否則非法。

記排完序的矩形為rects［6］，則長(zhǎng)方體的3條邊就是rects［0］．x、rects［4］．x、rects［5］．y，此時(shí)就可以按照這3個(gè)邊長(zhǎng)，把6個(gè)矩形重新構(gòu)造出來(lái)，與輸入數(shù)據(jù)比對(duì)。如果相同，說(shuō)明合法，否則非法。

習(xí)題3-11　換低檔裝置（Kickdown，ACM/ICPC NEERC 2006，UVa1588）

給出兩個(gè)長(zhǎng)度分別為n₁、n₂（n₁，n₂≤100）且每列高度只為1或2的長(zhǎng)條，需要將它們放入一個(gè)高度為3的容器（如圖2.5所示），問(wèn)能夠容納它們的最短容器長(zhǎng)度。

【分析】

數(shù)據(jù)范圍比較小，可以直接遍歷上方長(zhǎng)條的所有位置，看看能不能和下方匹配即可?？梢砸胍痪S坐標(biāo)，其中下方的長(zhǎng)條起始點(diǎn)放在100，依次遍歷上方長(zhǎng)條所有可能的起始點(diǎn)b2，b2的可能范圍是［100-n₁, 100＋n₁＋n₂］。對(duì)于一個(gè)起始點(diǎn)b2，依次嘗試放置序列的每一個(gè)點(diǎn)，看看數(shù)軸上對(duì)應(yīng)點(diǎn)的兩個(gè)長(zhǎng)條對(duì)應(yīng)列的高度和是否大于3，如果大于3，說(shuō)明放不到容器里面；否則繼續(xù)。這樣用O（n₁*n₂）的時(shí)間復(fù)雜度就可以求出最短的容器長(zhǎng)度。

習(xí)題3-12　浮點(diǎn)數(shù)（Floating-Point Numbers，UVa11809）

計(jì)算機(jī)常用階碼－尾數(shù)的方法保存浮點(diǎn)數(shù)。如圖2.6所示，如果階碼有6位，尾數(shù)有8位，可以表達(dá)的最大浮點(diǎn)數(shù)為。注意小數(shù)點(diǎn)后第一位必須為1，所以一共有9位小數(shù)。

這個(gè)數(shù)換算成十進(jìn)制之后就是0.998046875*2⁶³＝9.205357638345294*10¹⁸。你的任務(wù)是根據(jù)這個(gè)最大浮點(diǎn)數(shù)，求出階碼的位數(shù)E和尾數(shù)的位數(shù)M。輸入格式為AeB，表示最大浮點(diǎn)數(shù)為A*10^B，0＜A＜10，并且恰好包含15位有效數(shù)字。輸入結(jié)束標(biāo)志為0e0。對(duì)于每組數(shù)據(jù)，輸出M和E。輸入保證有唯一解，且0≤M≤9，1≤E≤30。在本題中，M＋E＋2不必為8的整數(shù)倍。

【分析】

根據(jù)題意可以推算出最大值。因?yàn)閮蛇叾急容^大，所以可以同時(shí)求以10為底的對(duì)數(shù)：。

可以遍歷所有可能的M，根據(jù)上述公式求出E的值，然后再用E和M求出lgv和輸入的值進(jìn)行比較，如果相等，說(shuō)明M、E就是所求的值。做兩個(gè)浮點(diǎn)數(shù)相等判斷時(shí)，二者之差的絕對(duì)值如果小于1e-6，則認(rèn)為二者相等。完整程序（C＋＋11）如下：

注意，本題代碼使用了C＋＋11中提供的round函數(shù)（屬于C語(yǔ)言的math標(biāo)準(zhǔn)庫(kù)）來(lái)做四舍五入操作，不再需要使用類(lèi)似floor（x＋0.5）這樣的技巧。

浮點(diǎn)數(shù)在計(jì)算機(jī)科學(xué)中是非常重要的課題，有興趣的讀者可以參考如下鏈接：http://share.onlinesjtu.com/mod/tab/view.php?id=176。