2.2　函數和遞歸

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

習題4-1　象棋（Xiangqi，ACM/ICPC Fuzhou 2011，UVa1589）

考慮一個象棋殘局，其中紅方有n（2≤n≤7）個棋子，黑方只有一個將。紅方除了有一個帥（G）之外還有3種可能的棋子：車（R）、馬（H）、炮（C），并且需要考慮蹩馬腿（如圖2.7所示）和將與帥不能照面（將帥如果同在一條直線上，中間又不隔著任何棋子的情況下，走子的一方獲勝）的規則。

輸入所有棋子的位置，保證局面合法并且紅方已經將軍。你的任務是判斷紅方是否已經把黑方將死。關于中國象棋的相關規則請參見原題。

【分析】

要判斷黑方是否必死，其實就是反過來判斷黑方是否有種走法，在走出一步之后能不被紅方的任何一個棋子將死。首先判斷，黑方是不是可以直接將紅方將死，如果可以，就無須進行下一步的判斷。

然后挨個嘗試黑方的各種合法走法（水平或者垂直，但是不能走出黑子的大本營）。如果所有走法都會導致被紅方某個棋子吃掉，說明紅方必勝。

需要特別注意的是，黑方走子時是可以吃掉紅方棋子的，如果有這種情況，需在吃子之后再判斷輸贏。

從實現過程中來說，有一個公共的過程可以抽取：就是判斷一個棋子是否可以從一個點p1直接水平或者垂直地走到另外一個點p2，中間有0個（車要吃子或者黑將直接將軍）或者恰好1個棋子（紅炮要將軍）。實現中，需要將跳馬的8個方向封裝成向量。

習題4-2　正方形（Squares，ACM/ICPC World Finals 1990，UVa201）

有n行n列（2≤n≤9）的小黑點，還有m條線段連接其中的一些黑點。統計這些線段連成了多少個正方形（每種邊長分別統計）。

行從上到下編號為1～n，列從左到右編號為1～n。邊用Hij和Vij表示，分別代表邊（i，j）-（i，j＋1）和（i，j）-（i＋1，j）。例如圖2.8最左邊的線段用V11表示。圖2.8中包含2個邊長為1的正方形和1個邊長為2的正方形。

【分析】

對于每一個點（i，j），記錄一個向右延伸和向下延伸的最長線段長度hExp和vExp，則二者都可以根據這個點上出發的線段類型來遞推：

（1）如果存在向右的線段，則“hExp（i，j）＝hExp（i，j＋1）＋1；”。

（2）如果存在向下的線段，則“vExp（i，j）＝vExp（i＋1，j）＋1；”。

順序遍歷每一個點P（i，j），依次判斷以P為左上頂點的可能正方形的邊長s，其中s為1到min（hExp（i，j），vExp（i＋1，j））的整數。然后可以根據s計算出正方形的左下以及右上頂點，再根據這兩個點對應的hExp和vExp是否大于等于s，即可判斷能否形成長度為s的正方形。完整程序如下：

習題4-3　黑白棋（Othello，ACM/ICPC World Finals 1992，UVa220）

你的任務是模擬黑白棋游戲的進程。黑白棋的規則為：黑白雙方輪流放棋子，每次必須讓新放的棋子“夾住”至少一枚對方棋子，然后把所有被新放棋子“夾住”的對方棋子替換成己方棋子。一段連續（橫、豎或者斜向）的同色棋子被“夾住”的條件是兩端都是對方棋子（不能是空位）。圖2.9中的白棋有6個合法操作，分別為（2，3），（3，3），（3，5），（6，2），（7，3），（7，4）。選擇在（7，3）放白棋后變成圖2.10（注意有豎向和斜向的共兩枚黑棋變白）。注意（4，6）的黑色棋子雖然被夾住，但不是被新放的棋子夾住，因此不變白。

輸入一個8×8棋盤以及當前下一次操作的游戲者，處理以下3種指令：

• □　L指令打印所有合法操作，按照從上到下、從左到右的順序排列（沒有合法操作時輸出No legal move）。
• □　Mrc指令放一枚棋子在（r，c）。如果當前游戲者沒有合法操作，則是先切換游戲者再操作。輸入保證這個操作是合法的。輸出操作完畢后黑白雙方的棋子總數。
• □　Q指令退出游戲，并打印當前棋盤（格式同輸入）。

【分析】

直接進行模擬即可，需要注意的是，可以將棋子移動的方向預先定義成8個向量，然后使用之前提到過的坐標和向量的運算。

習題4-4　骰子涂色（Cube painting, UVa253）

輸入兩個骰子，判斷二者是否等價。每個骰子用6個字母表示，如圖2.11所示。

例如，rbgggr和rggbgr分別表示如圖2.12和圖2.13所示的兩個骰子。二者是等價的，因為如圖2.12所示的骰子沿著豎直軸旋轉90°之后就可以得到如圖2.13所示的骰子。

【分析】

本題可以參考《算法競賽入門經典—訓練指南》中第1章例題8的思路，通過確定頂面和正面的編號來確定所有面的編號，使用程序生成所有面的24種排列。枚舉輸入的第一個立方體的所有姿態的編碼，逐一和第二個骰子的編碼比較即可。

習題4-5　IP網絡（IP Networks, ACM/ICPC NEERC 2005, UVa1590）

可以用一個網絡地址和一個子網掩碼描述一個子網（即連續的IP地址范圍）。其中，子網掩碼包含32個二進制位，前32-n位為1，后n位為0，網絡地址的前32-n位任意，后n位為0。所有前32-n位和網絡地址相同的IP都屬于此網絡。

例如，網絡地址為194.85.160.176（二進制為11000010|01010101|10100000|10110000），子網掩碼為255.255.255.248（二進制為11111111|11111111|11111111|11111000），則該子網的IP地址范圍是194.85.160.176～194.85.160.183。輸入一些IP地址，求最小的網絡（即包含IP地址最少的網絡），包含所有這些輸入地址。

例如，若輸入3個IP地址：194.85.160.177、194.85.160.183和194.85.160.178，包含上述3個地址的最小網絡的網絡地址為194.85.160.176，子網掩碼為255.255.255.248。

【分析】

首先需要將輸入的IP地址都轉換成二進制表示，然后得到這些二進制數的最長公共前綴P的長度L。則最小網絡IP的前L位就是P，剩余的位都是0。子網掩碼的前L位都是1，剩余都是0。網絡地址從二進制轉換到十進制的過程可以提取成公共函數，在輸出結果時復用。完整程序如下：

習題4-6　莫爾斯電碼（Morse Mismatches, ACM/ICPC World Finals 1997, UVa508）

輸入每個字母的Morse編碼、一個詞典以及若干個編碼。對于每個編碼，判斷它可能是哪個單詞。如果有多個單詞精確匹配，任選一個輸出并且后面加上“!”；如果無法精確匹配，可以在編碼尾部增加或刪除一些字符以后匹配某個單詞（增加或刪除的字符應盡量少）。如果有多個單詞可以這樣匹配上，任選一個輸出并且在后面加上“?”。

莫爾斯電碼的細節參見原題。

【分析】

輸入時，首先建立字符到對應Morse編碼的映射map。每輸入一個單詞，通過這個map將每一個字符翻譯成Morse編碼，然后建立所有Morse編碼到對應單詞的映射map<string ,vector<string> > context。

然后對于每一個輸入的Morse編碼M，首先在context中查找M對應的所有可能的單詞v。如果v中只有一個單詞，則輸出這個單詞即可；如果v中包含多個單詞，則任意輸出一個再加“!”。

如果不存在對應的v，則查找context中所有符合以下條件的Morse編碼CM：CM為M的前綴或者M為CM的前綴。找到其中長度和M相差最小的那個CM輸出即可。找到的所有CM可以用map<int,string>存放，key為CM和M的大小的差，value就是CM本身。因為map本身就是根據key來排序的，直接輸出第一個元素即可。完整程序（C++11）如下：

習題4-7　RAID技術（RAID!, ACM/ICPC World Finals 1997, UVa509）

RAID技術用多個磁盤保存數據。每份數據不止在一個磁盤上保存，因此在某個磁盤損壞時能通過其他磁盤恢復數據。本題討論其中一種RAID技術。數據被劃分成大小為s（1≤s≤64）比特的數據塊保存在d（2≤d≤6）個磁盤上。如圖2.14所示，每d-1個數據塊都有一個校驗塊，使得每d個數據塊的異或結果為全0（偶校驗）或者全1（奇校驗）。

例如d=5，s=2，偶校驗，數據6C7A79EDFC（二進制01101100 01111010 01111001 11101101 11111100）將這樣保存，如圖2.15所示。

其中加粗塊是校驗塊。輸入d, s, b校驗的種類（E表示偶校驗，O表示奇校驗）以及b（1≤b≤100）個數據塊（其中“?”表示損壞的數據），你的任務是恢復并輸出完整的數據。如果校驗錯或者由于損壞數據過多無法恢復，應報告磁盤非法。

【分析】

因為輸入是按照每個Disk依次進行，所以需要把每個Disk看成行，這個與題圖的行列是反過來的，這一點需要注意。

本題的本質就是要對每一列的01數據進行還原，首先是要檢查每一列是否有多個未知數據，如果多于1個，則無法還原，磁盤非法。對于全是已知數據的列，所有數據的異或運算結果必須符合校驗種類：E時為0，O時為1。如果不符合，表示校驗錯誤。

如果數據全部合法，則按照列的順序對修復過的數據進行依次組合，注意校驗塊所在的行是依次循環遞增的，在組合時要注意忽略校驗塊。另外，如果組合后的數據位數不是4的倍數，需要進行補0操作。

在組合的過程中，可以使用bitset來存儲每4位的數據結果，bitset.to_ulong()可以方便地把結果轉換成整數來輸出。注意bitset的第0位是從右邊算起，而我們組合時需要從左邊算起，需要進行處理。

習題4-8　特別困的學生（Extraordinarily Tired Students, ACM/ICPC Xi’an 2006, UVa12108）

課堂上有n個學生（n≤10）。每個學生都有一個“睡眠-清醒”周期，其中第i個學生醒A_i分鐘后睡B_i分鐘，然后重復（1≤A_i, B_i≤5），初始時第i個學生處在他的周期的第C_i分鐘。每個學生在臨睡前會察看全班睡覺人數是否嚴格大于清醒人數，若是才睡，否則再清醒A_i分鐘。問經過多長時間后全班都清醒。如果用（A,B,C）描述學生，圖2.16描述了3個學生(2,4,1)、(1,5,2)和(1,4,3)在每個時刻的行為。

【分析】

可以用一個循環來模擬每分鐘的行為，首先看看是否還有睡著的，如果沒有，直接輸出結果即可，然后依次判斷每個學生的行為并且進行模擬。

問題是整體狀態有可能進入死循環，為了避免這種情況，可以將每個學生的狀態放在一起編碼成字符串，然后使用set判重，如果發現重復，說明不會再清醒了，輸出-1即可。完整程序如下：

習題4-9　數據挖掘（Data Mining, ACM/ICPC NEERC 2003, UVa1591）

有兩個n元素數組P和Q。P數組每個元素占S_P個字節，Q數組每個元素占S_Q個字節。有時需直接根據P數組中某個元素P(i)的偏移量P_ofs(i)算出對應的Q(i)的偏移量Q_ofs(i)。當兩個數組的元素均為連續存儲時Q_ofs(i)=P_ofs(i)/S_p*S_q，但因為除法慢，可以把式子改寫成速度較快的Q_ofs'(i)=(P_ofs(i)+P_ofs(i)<<A)>>B。為了讓這個式子成立，在P數組仍然連續存儲的前提下，Q數組可以不連續存儲（但不同數組元素的存儲空間不能重疊）。這樣做雖然會浪費一些空間，但是提升了速度，是一種用空間換時間的方法。

輸入N、S_P和S_Q（N≤2²⁰，1≤S_P, S_Q≤2¹⁰），你的任務是找到最優的A和B，使得占的空間K盡量小。輸出K、A、B的值。多解時讓A盡量小，如果仍多解則讓B盡量小。

【分析】

注意是對32位整數進行位移操作，那么A和B必然是0～31的整數。所有的A、B組合就只有32*32個，完全可以使用暴力方式遍歷求解。

另外，Q的不同元素不可以重疊，這就要求Q_ofs'(i)>i*S_q。只需考慮i=1的情況就可以確定Q中一個元素的存儲空間，也就是說要求Q_ofs'(1)=(S_p+S_p<<A)>>B≥S_q，找到一組符合要求的A、B之后即可得：K=Q_n-1+S_q=(S_p*(n-1)+(S_p*(n-1))<<A)>>B+S_q。這里Q的最后一個元素之后不需要多余的存儲空間。

從小到大遍歷A和B，發現更小的K時更新答案，即可得到題目要求的解。

習題4-10　洪水！（Flooded! ACM/ICPC World Finals 1999, UVa815）

有一個n*m（1≤m, n<30）的網格，每個格子是邊長10米的正方形，網格四周是無限大的墻壁。輸入每個格子的海拔高度，以及網格內雨水的總體積v，輸出水位的海拔高度以及有多少百分比的區域有水（即高度嚴格小于水平面）。

【分析】

原題保證了水會從海拔最低的格子開始淹，然后依次上升。可以把所有n*m個格子按照海拔從低到高排列，編號從0開始計。從i=1到n*m，依次計算，如果體積為v的水把編號0～i-1的每個格子都淹沒所形成的水位高度wl，如果wl<格子i的高度，則說明水無法淹沒格子i。這樣就得到了水位高度wl和有水的格子個數i，求百分比即可。因為格子邊長是10，可以將v除以100，然后把格子邊長作為1來處理，這樣每個格子底面積就為1，方便計算。完整程序如下：