第2章　 《算法競賽入門經典（第2版）》習題選解

2.1　數組和字符串

本節選解習題來源于《算法競賽入門經典（第2版）》一書的第3章。

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

給出一個由O和X組成的串（長度為1～80），統計每個字符的得分之和。每個O的得分為已經連續出現的O的個數，X得分為0。例如，OOXXOXXOOO的得分為1＋2＋0＋0＋1＋0＋0＋1＋2＋3。

【分析】

使用for循環對輸入串的字符進行遍歷，維護一個已經連續出現的‘O‘個數的計數器cnt以及串的得分和sum。初始cnt＝0，sum＝0。如果遇到‘O‘就＋＋cnt，然后把cnt加到sum中，如果遇到‘X‘就重置cnt為0。

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

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

給出一種物質的分子式（不帶括號），求分子量。本題中的分子式只包含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。

【分析】

依次掃描即可，注意原子后面不帶數目的情況。掃描的過程中，維護一個當前已經輸入的數字字符組成的數字cnt。一開始以及遇到一個新原子時，cnt＝-1，表示“還未開始計數”的狀態。方便遇到原子后不帶數目以及數字有多位的情況處理。

和習題3-1類似，也要在循環結束之后處理最后一個原子。完整程序如下：

習題3-3　數數字（Digit Counting，ACM/ICPC Danang 2007，UVa1225）

把前n（n≤10000）個整數按順序寫在一起：123456789101112…數一數0～9各出現多少次（輸出10個整數，分別是0，1，…，9出現的次數）。

【分析】

因為n的最大值比較小，可以用建表的方式來計算。令C［n］［k］表示前n個數字寫在一起，k（k＝0～9）總共出現幾次，則有C［n＋1］［k］＝C［n］［k］＋x，其中x是k在n中出現的次數。直接按照這個公式就可以把所有答案提前計算出來，然后每讀入一個n就直接輸出預處理的結果即可。

習題3-4　周期串（Periodic Strings，UVa455）

如果一個字符串可以由某個長度為k的字符串重復多次得到，就可以說該串以k為周期。例如，abcabcabcabc以3為周期（注意，它也以6和12為周期）。

輸入一個長度不超過80的字符串，輸出它的最小周期。

【分析】

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

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

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

【分析】

使用以下結構表示坐標和向量：

然后直接模擬即可，可以將4種指令字符以及對應4個方向的向量存放到一個map＜char，Vector＞中，方便移動時計算新的空格位置。

完整程序如下：

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

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

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

【分析】

還是和習題3-5一樣，建立坐標和向量的結構方便進行位置的移動處理。依次掃描，用一個全局的Point數組eligible存放所有單詞的起始點坐標，同時要用兩個vector＜int＞，即across和down來分別記錄掃描出的橫向單詞和豎向單詞的起點坐標在eligible中的編號。

在讀取兩個方向單詞時，使用兩個向量計算來讀取所有的單詞，即dRight（0，1）和dDown（1，0），這樣可以降低代碼復雜度。具體請參見代碼，完整程序如下：

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

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

輸入整數m和n（4≤m≤50，4≤n≤1000），以及m個長度為n的DNA序列（只包含字母A、C、G、T），輸出到m個序列的Hamming距離和最小的DNA序列和對應的距離。如有多解，要求字典序最小的解。例如，對于下面5個DNA序列，最優解為TAAGATAC。

TATGATAC

TAAGCTAC

AAAGATCC

TGAGATAC

TAAGATGT

【分析】

對于所求結果序列S來說，Hamming距離和最小意味著S中每一列的字符都在m個序列的對應列上出現次數最多。可以依次對m個序列中每一列的字符進行統計，字典序最小并且出現次數最多的那個就是S中這一列的字符。完整程序如下：

習題3-8　循環小數（Repeating Decimals，ACM/ICPC World Finals 1990，UVa202）

輸入整數a和b（0≤a≤3000，1≤b≤3000），輸出a/b的循環小數表示以及其循環節長度。例如a＝5，b＝43，小數表示為0．（116279069767441860465），循環節長度為21。

【分析】

首先簡單介紹一下長除法，以3/7為例，如圖2.4所示。

本題實際上就是模擬長除法的計算過程，其中每一次除法時都有被除數和余數，當被除數出現重復時就表示出現循環節了。所以需要記錄每一次的被除數及其在循環小數中的位置，需要注意當除數不夠除，每一次補零也需要記錄其對應的位置。

完整程序如下：

習題3-9　子序列（All in All，UVa10340）

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

【分析】

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

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

給定6個矩形的長和寬w_i和h_i（1≤w_i，h_i≤1000），判斷它們能否構成長方體的6個面。

【分析】

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

記排完序的矩形為rects［6］，則長方體的3條邊就是rects［0］．x、rects［4］．x、rects［5］．y，此時就可以按照這3個邊長，把6個矩形重新構造出來，與輸入數據比對。如果相同，說明合法，否則非法。

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

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

【分析】

數據范圍比較小，可以直接遍歷上方長條的所有位置，看看能不能和下方匹配即可。可以引入一維坐標，其中下方的長條起始點放在100，依次遍歷上方長條所有可能的起始點b2，b2的可能范圍是［100-n₁, 100＋n₁＋n₂］。對于一個起始點b2，依次嘗試放置序列的每一個點，看看數軸上對應點的兩個長條對應列的高度和是否大于3，如果大于3，說明放不到容器里面；否則繼續。這樣用O（n₁*n₂）的時間復雜度就可以求出最短的容器長度。

習題3-12　浮點數（Floating-Point Numbers，UVa11809）

計算機常用階碼－尾數的方法保存浮點數。如圖2.6所示，如果階碼有6位，尾數有8位，可以表達的最大浮點數為。注意小數點后第一位必須為1，所以一共有9位小數。

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

【分析】

根據題意可以推算出最大值。因為兩邊都比較大，所以可以同時求以10為底的對數：。

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

注意，本題代碼使用了C＋＋11中提供的round函數（屬于C語言的math標準庫）來做四舍五入操作，不再需要使用類似floor（x＋0.5）這樣的技巧。

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