英雄哪里出來

      卡特蘭數(shù)

      題意：給定一個(gè)圓，上面有2K個(gè)點(diǎn)，這2K個(gè)點(diǎn)可以互相連接，一個(gè)點(diǎn)只能連一次，問連接完畢將圓分割成最小的平面數(shù)的分割種類數(shù)。

      題解：

      1）首先K=1，最小平面為2，種數(shù)為f[1] = 1種。

      2）然后考慮K=2的情況，將K0和K1連，那么剩下的情況就是K=1的情況，將K0和K3連，那么剩下的也是K=1的情況，所以K=2的情況為f[0]*f[1] + f[1]*f[0] = 2, 分割的平面數(shù)為3。

      3）按照和K=2一樣的遞推方式，K = 5 時(shí)的情況為：

               K0 - K1    ->   f[0] * f[4]

               K0 - K3    ->   f[1] * f[3]

               K0 - K5    ->   f[2] * f[2]

               K0 - K7    ->   f[3] * f[1]

               K0 - K9    ->   f[4] * f[0]

         于是可以得出遞推式： f[i] = sum { f[j] * f[i-1-j]  0 <= j < i }

131 Hardwood floor

       動(dòng)態(tài)規(guī)劃：狀態(tài)壓縮

 方塊A 方塊B

圖1

      題意：利用以上兩種積木（任意數(shù)量，可進(jìn)行旋轉(zhuǎn)），拼出一個(gè)M*N( 1<= M <= 9, 1 <= N <= 9)的矩形，問這樣的方式有多少種。如M = 2, N = 3 的情況 ，有以下5種拼接方式：

圖2

      題解：考慮到N和M都很小，所以可以將每一行的狀態(tài)壓縮在一個(gè)二進(jìn)制的整數(shù)中，0表示沒有放置，1表示已經(jīng)放置，圖3的第一行狀態(tài)就可以表示成101000（二進(jìn)制表示，紫羅蘭色表示上一行延伸過來的方塊，灰色表示暫時(shí)沒有放置方塊的格子）。這樣就可以通過枚舉第i行的所有狀態(tài)，擴(kuò)展出第i+1行的所有狀態(tài)。

      舉例說明：

      如圖3，枚舉到第i行的狀態(tài)為 101000（二進(jìn)制數(shù)，實(shí)際操作的時(shí)候是轉(zhuǎn)化成十進(jìn)制然后通過位運(yùn)算來變換狀態(tài)的），假設(shè)對(duì)于當(dāng)前狀態(tài)的所有解的情況已經(jīng)求出來，為DP[i][101000]，然后可以通過枚舉列將第i行填滿。并且要記錄下當(dāng)前行狀態(tài)now = 101000, 下一行狀態(tài) next = 000000。

      那么接下來一步就要開始枚舉列了，當(dāng)枚舉到第一列時(shí)，發(fā)現(xiàn)當(dāng)前格子已經(jīng)被i-1行所占據(jù)，所以直接進(jìn)入下一列，這一列為空，所以我們需要某種方式將它填滿，對(duì)于圖3的情況，一共有三種填充方式(圖3、圖4、圖5)，因?yàn)楦褡硬荒苤丿B，所以在枚舉的時(shí)候需要判斷當(dāng)前方塊放入的時(shí)候會(huì)不會(huì)導(dǎo)致和之前放置的方塊重疊，如果不會(huì)重疊說明狀態(tài)可達(dá)，否則不進(jìn)入下一次迭代。

 now = 101000   next = 000000

圖3

now = 111000   next = 110000

圖4

now = 111000   next = 010000

圖5

now = 111000   next = 011000

圖6

      圖3的狀態(tài)一共生成三種狀態(tài)，然后我們繼續(xù)對(duì)生成的狀態(tài)進(jìn)行擴(kuò)展。以圖5的狀態(tài)為例，對(duì)它的狀態(tài)進(jìn)行擴(kuò)展，可以得到以下幾種狀態(tài)（橙色表示當(dāng)前放入的方塊）：
      1)放置一個(gè)橫躺的方塊A

now = 111110   next = 010000

圖7

      2)放置一個(gè)豎著的方塊A

now = 111100   next = 010100

圖8

3)放置一個(gè) "反7" 字 方塊B

now = 111110   next = 010100

圖9

4)放置一個(gè) "L"字 方塊B

now = 111100   next = 010110

圖10

5)放置一個(gè) "7" 字方塊 B

now = 111110   next = 010010

圖11

6)放置一個(gè) "反L"字 方塊 B

now = 111100   next = 011100

圖12

      枚舉列的過程是用dfs遞歸實(shí)現(xiàn)的，遞歸出口為列數(shù)col == N的時(shí)候，那時(shí)候當(dāng)前行的狀態(tài)now一定是 2^N - 1，因?yàn)橐ＷC第i行能夠被填充滿，于是就可以得出狀態(tài)轉(zhuǎn)移方程DP[i+1][ next ] += DP[i][ now ]。

      繼續(xù)枚舉第i+1行的所有狀態(tài)，擴(kuò)展i+2行的可達(dá)狀態(tài)。

      然后就要考慮初始狀態(tài)的情況，可以虛擬出一個(gè)第0行，那么第0行的狀態(tài)除了2^N-1的情況為1，其他必定是0（因?yàn)槭翘摂M出來的，可以理解為全部填滿的狀態(tài)）。然后通過第0行的這個(gè)狀態(tài)可以迭代計(jì)算出第1行的各種可達(dá)狀態(tài)的解數(shù)。直到第M行，最后解的情況是DP[M+1][0]的值而非DP[M][2^N-1]（因?yàn)槊杜e到第M行后，第M行的非全滿的狀態(tài)也可以導(dǎo)致最后的格子鋪滿）。

132 Another Chocolate Maniac

      動(dòng)態(tài)規(guī)劃：狀態(tài)壓縮

      題意：給定一個(gè)M*N (M <= 70, N <= 7)的棋盤，求放置最少數(shù)量的多米諾骨牌(大小為2X1)，使得它不能再放置更多的骨牌，給定的棋盤某些點(diǎn)不能被放置。

      題解：沿用131那題的思路，但是這題只知道前一行的狀態(tài)是不夠的（因?yàn)槎嗝字Z骨牌的大小為2X1），考慮下面這種情況：

圖1

      現(xiàn)在需要推導(dǎo)第i+2行的狀態(tài)，考慮在(i+2, 4)（紅色方塊）上如果不放置骨牌是否合法，那么由于(i+1, 4)為空，但是我們無法知道第i行的那個(gè)？格子到底是空還是非空，所以無法對(duì)紅色格子進(jìn)行狀態(tài)轉(zhuǎn)移，所以需要將狀態(tài)表示稍作變形。

      對(duì)于每一行用一個(gè)3進(jìn)制的整數(shù)表示當(dāng)前一行的狀態(tài)，定義以下常量：

      #define STATE_PRE_EMPTY  0 // 上一行對(duì)應(yīng)格為空

      #define STATE_PRE_FULL    1 // 上一行對(duì)應(yīng)格為滿

      #define STATE_NOW_FULL   2 // 當(dāng)前行對(duì)應(yīng)格為滿

      那么圖1的情況就可以表示成下面的狀態(tài)：

圖2

      ？格子所代表的的狀態(tài)就可以通過i+1行的那個(gè)值來確定了，i+1行對(duì)應(yīng)列的格子值為0，表示第i行對(duì)應(yīng)列的格子為未放置狀態(tài)（再上一行的狀態(tài)就不需要關(guān)心了，因?yàn)楣桥频淖畲箝L度為2）。

       那么如果前一行對(duì)應(yīng)列的狀態(tài)值為0的時(shí)候，必須放置一個(gè)骨牌（如果因?yàn)橛姓系K無法放置，那么說明這個(gè)狀態(tài)無法往下轉(zhuǎn)移了）。知道方法之后，具體做法就是初始化狀態(tài)，這里我們?yōu)榱诉\(yùn)算簡便，可以虛擬出一個(gè)第零行來，對(duì)于第0行，它一定是全部塞滿的，所以第0行只有一個(gè)合法狀態(tài)，即：DP[0][ 3^N - 1 ] = 0（每格的狀態(tài)都是2，最小骨牌數(shù)為0）,然后通過這個(gè)狀態(tài)，進(jìn)行行枚舉，每一行進(jìn)行列位移（可以采用dfs實(shí)現(xiàn)），將上一行的狀態(tài)推導(dǎo)產(chǎn)生下一行的可行狀態(tài)，每次dfs模擬放置和不放置兩種情況；

       最后DP[M+1][ 3^N - 1 ]就是最后的答案。

133 Border

      簡單統(tǒng)計(jì)

      題意：給定N(N <= 16000)個(gè)整數(shù)對(duì)(A_i, B_i)，如果存在一個(gè)整數(shù)對(duì)(A _j, B_j)   使得  A_j < A_i  并且B_i < B_j  則稱(A_i, B_i)是多余的，問整數(shù)對(duì)中有多少是多余的。

      題解：將整數(shù)對(duì)按A_i遞增排序，然后遍歷B_i記錄最大值，每次遇到比最大值小的可以斷定一定是多余的，計(jì)數(shù)器加1。知道遍歷完畢輸出即可。

134 Centroid

      枚舉 + 樹形統(tǒng)計(jì)

題意：給定一棵樹，刪除樹上的某個(gè)結(jié)點(diǎn)（以及它所附帶的邊）i，剩下的各個(gè)連通塊中結(jié)點(diǎn)數(shù)目最大值為T_i，求 M = Min{T_i  1<= i <= n}，并且輸出刪除哪些點(diǎn)，能得到這個(gè)最小值M。

題解：遍歷一棵樹，并且用sum[i]記錄以i為根結(jié)點(diǎn)的樹的結(jié)點(diǎn)數(shù)目，通過一次遍歷就能把所有的sum求出來。記錄M = n；然后遍歷根結(jié)點(diǎn)，對(duì)于刪除i結(jié)點(diǎn)，剩下連通塊中的最大值為 max( n - sum[v],  max{sum[v]   v為i個(gè)直接子結(jié)點(diǎn)}  )。同樣一次遍歷就能將所有的值求出來。

135 Drawing Lines

136 Erasing Edges

      數(shù)學(xué)題

      題意：給定一個(gè)多邊形S的N條邊的中點(diǎn)，求這個(gè)多邊形S。

      題解：假設(shè)原多邊形中點(diǎn)集合為C_i，多邊形點(diǎn)集合P_i。

       假設(shè) 第0個(gè)點(diǎn)P₀ = (x, y)，那么第一個(gè)點(diǎn)的坐標(biāo)可以通過C₀計(jì)算出來，即P₁ = 2*C₀ - P₀,同理第二個(gè)點(diǎn)可以通過C₁計(jì)算出，并且可以用P₀的一次函數(shù)來表示，做n-1次迭代就可以把P_n-1用P₀表示出來，而 P_n-1 + P₀ = C_n-1，所以x，y都可以通過一次線性方程求出解來（也有可能有無解的情況）。然后再做n-1次迭代將所有點(diǎn)求出來即可。

137 Funny Strings

      記憶化搜索

      題意：對(duì)于一個(gè)序列S1, S2, S3 ... SN, 如果S1+1, S2, S3 ... SN-1進(jìn)過一些左移或者右移幾次操作，可以和原序列保持一致，則稱這個(gè)序列為Funny String，給定N和K，求長度為N，和為K的Funny String。

       題解：首先考慮，左移后第幾位和原來的第一位對(duì)應(yīng)，可以假設(shè)是第i位吧，那么有以下關(guān)系式：

       S[1] + 1 = S[i]      ...        (1)

       S[2] = S[i+1]        ...        (2)

       S[3] = S[i+2]        ...        (3)

       ......

       S[j] = S[1]              ...      (N-i+2)

       S[j+1] = S[2]          ...      (N-i+3)

       ......

       S[n-1] = S[i-2]        ...      (N-1)

       S[n] - 1 = S[i-1]     ...       (N)

       顯然i不可能為1，因?yàn)?/span>S[1] + 1 != S[1]

       并且GCD(N, (i-1)) 必須為1，否則這個(gè)等式組會(huì)存在內(nèi)環(huán)，無法求解。

       接下來就可以通過記憶化搜索將S[2] ... S[N] 的值都用S[1] 表示出來。

       表示方式有很多種，例如用一個(gè)二元組T_k = (a_k, b_k)來保存對(duì)于前一項(xiàng)的系數(shù)，

      例如：

             S[i] 可以表示為 Ti = (1, 1) (即 S[i] = 1 * S[1] + 1)

             S[i+1] 可以表示為 Ti+1 = (1, 0) (即 S[i+1] = 1 * S[2] + 0)

      這里的S[2]尚未計(jì)算出來，所以需要遞歸計(jì)算，具體計(jì)算方法第j項(xiàng)的方法如下：

      遞歸原因來自上面那N個(gè)等式，其中ta一定為1，tb為1或0。

      所以這題的做法就是枚舉左移點(diǎn)i，計(jì)算出所有數(shù)對(duì)于S[1]的一次線性表示形式，然后利用所有數(shù)之和為K這個(gè)條件，求出非負(fù)整數(shù)S[1]，就能將所有數(shù)都求出來了。

138 Games of Chess

      貪心

      題意：給定N(N <= 100)個(gè)人的比賽場(chǎng)數(shù)X[i]，需要構(gòu)造一個(gè)比賽安排，假設(shè)G表示所有人的參賽場(chǎng)數(shù)之和，一共G/2場(chǎng)比賽，那么需要輸出G/2行，每行為a b，a、b表示參賽隊(duì)員的編號(hào)，其中a不等于b，并且a是勝利方，當(dāng)前場(chǎng)的勝利方需要在上一場(chǎng)比賽中出現(xiàn)過（類似不斷淘汰的機(jī)制）。

      題解：將每個(gè)人的參賽場(chǎng)數(shù)X[i]從大到小排序，如圖1所示，共有八位參賽選手，參賽場(chǎng)數(shù)分別為4、3、2、1、1、1、1、1，總和為14，所以總共有7場(chǎng)比賽。從第一個(gè)選手開始，將他的前X[i] - 1場(chǎng)比賽在賽程表的前X[i] - 1個(gè)位置的勝場(chǎng)中填滿，他的最后一場(chǎng)比賽和場(chǎng)數(shù)次多的人比，并且輸?shù)簦瑢?chǎng)數(shù)次多的人的剩余場(chǎng)數(shù)按照同樣的方式去填賽程表，直到所有比賽的勝利方都確定（即表中左邊那一列不為空），然后將剩下的還有剩余比賽的填在失敗方即可。

圖1

 
139 Help Needed!

      數(shù)學(xué)證明

      
       題意：如圖，給定一個(gè)亂序的十六數(shù)碼，問是否能通過一些移動(dòng)，將它恢復(fù)到初始狀態(tài)（0的位置表示空缺位置，非0位置上的方塊可以向0移動(dòng)，移動(dòng)只能在上下左右四個(gè)方向進(jìn)行）。

圖1

      題解：只需要判斷 當(dāng)前狀態(tài)數(shù)碼的逆序數(shù) 和 0到目標(biāo)點(diǎn)曼哈頓距離 的奇偶性 即可。

      證明如下：

       首先將目標(biāo)數(shù)碼排成一排，計(jì)算它的逆序數(shù)為15（為了便于理解，將每一行的數(shù)碼涂成不同的顏色）。

圖2

       然后來看任意狀態(tài)的逆序數(shù)：

圖3

       I）如圖3，考慮當(dāng)前狀態(tài)下的水平移動(dòng)，即X可以向0移動(dòng)，Y也可以向0移動(dòng)（也可以理解成兩個(gè)方塊的交換）。對(duì)于這兩種情況：

       1) X 和0交換(X > 0)，交換后的數(shù)碼，逆序數(shù)-1；

       2) Y 和0交換(Y > 0)，交換后的數(shù)碼，逆序數(shù)+1；

圖4

       II）如圖4，考慮當(dāng)前狀態(tài)下的豎直移動(dòng)，即A可以向0移動(dòng)，B也可以向0移動(dòng)。

由于兩者情況是一樣的，這里只介紹A和0交換的情況。

       假設(shè)A和0中間的三個(gè)方塊（十六數(shù)碼，一定是三個(gè)方塊）中比A小的有x個(gè)，那么比A大的就是(3-x)個(gè)，這三個(gè)方塊的本身逆序數(shù)為K，那么：

       1）交換前，A 到0 這個(gè)區(qū)間段的逆序數(shù)為 x + 1 + K + 3;

       2）交換后，A 到0 這個(gè)區(qū)間段的逆序數(shù)為 (3-x) + K;

       交換前后逆序數(shù)的差值為  (3-x) + K - (x + 1 + K + 3) = -2x - 1;

      綜合I 、II發(fā)現(xiàn)，每進(jìn)行一次交換，逆序數(shù)的變化一定是奇數(shù)，最終狀態(tài)的逆序數(shù)15也是奇數(shù)，所以如果某個(gè)狀態(tài)逆序數(shù)和 0到目標(biāo)點(diǎn)的曼哈頓距離 的奇偶性一致時(shí)，必定是無解的。