A. Period PKU 1961 http://poj.org/problem?id=1961
題意：給定一個(gè)長度為N(N <= 106)的字符串S，求它的所有前綴中能夠表示成AK的前綴，并且要求求出每個(gè)前綴對(duì)應(yīng)的K。
題解：KMP
利用KMP求出該串的Next數(shù)組，然后枚舉每個(gè)前綴，根據(jù)Next數(shù)組的定義，對(duì)于某個(gè)前綴S[1...i]，有S[1...Next[i]] = S[i-Next[i]+1...i]，假設(shè)前綴S[1...i]能夠表示長AK的形式，則A = S[Next[i]+1...i]，所以必須滿足i能夠被i - Next[i] 整除，滿足條件后K = i/( i - Next[i])。
B. Corporative Network
PKU 1962 http://poj.org/problem?id=1962
題意：給定N(N <= 20000)個(gè)點(diǎn)和M(M <= 200000)次操作，每次操作有兩種類型：
I a b 將a的父結(jié)點(diǎn)設(shè)為b，并且合并距離為 |a-b| mod 1000
E a 詢問a到根結(jié)點(diǎn)的合并距離。
題解：并查集
利用路徑壓縮的思想，用dist[p]表示p和p的父結(jié)點(diǎn)的合并距離，每次查詢的時(shí)候累加p到根結(jié)點(diǎn)的合并距離，并且將p到p所在樹的根結(jié)點(diǎn)R的路徑上的所有點(diǎn)的父結(jié)點(diǎn)都設(shè)為R，然后更新各自的合并距離。
合并操作O(1)，查詢操作總復(fù)雜度O(N)。
C. Cave Exploration
PKU 1963 http://poj.org/problem?id=1963
題意：給出N(N <= 1000)條水平或者垂直的走廊，再給定走廊上任意一個(gè)坐標(biāo)點(diǎn)作為起點(diǎn)以及方向，按照以下策略走：能夠左轉(zhuǎn)就左轉(zhuǎn)，不能則筆直走，不能筆直走就右轉(zhuǎn)，都不能就掉頭。這樣走最后繞一圈又會(huì)回到起點(diǎn)，問哪些走廊是沒有經(jīng)過的，只要有一個(gè)點(diǎn)走過就算經(jīng)過。
題解：模擬 + 哈希。
將水平線段和豎直線段分開存，分兩種情況討論：
1、水平線段
對(duì)于任意一根水平線段，枚舉所有的豎直線段，計(jì)算出交點(diǎn)和水平線段的端點(diǎn)，保存下來并且按x坐標(biāo)遞增排序，去掉重復(fù)點(diǎn)，利用雙向鏈表將兩個(gè)相鄰點(diǎn)連接起來，由于x和y坐標(biāo)范圍為-32767~32767，而交點(diǎn)數(shù)不會(huì)超過N2，所以可以采用哈希將二維的點(diǎn)映射到一位數(shù)組中。每個(gè)點(diǎn)記錄水平走廊的編號(hào)。
2、豎直線段
同上操作，不同的是每個(gè)點(diǎn)記錄豎直走廊的編號(hào)。
經(jīng)過1和2兩步操作后，走廊上的關(guān)鍵點(diǎn)已經(jīng)被離散化了，并且所有點(diǎn)都通過四向鏈表串接起來，然后只需要從起點(diǎn)開始模擬行走即可，走到一個(gè)關(guān)鍵點(diǎn)，將關(guān)鍵點(diǎn)所在的兩個(gè)走廊編號(hào)標(biāo)記掉，最后統(tǒng)計(jì)沒有標(biāo)記的走廊編號(hào)就是答案了。
D. City Game
PKU 1964 http://poj.org/problem?id=1964
題意：給定一個(gè)M*N(M <= 1000，N <= 1000)的01矩陣，求它的一個(gè)子矩陣，滿足矩陣元素全為1，并且面積最大。
題解：枚舉行，對(duì)于第i行，以第i行為起點(diǎn)，掃描每一列j，找到第一個(gè)不是1的數(shù)所在的位置P[j]，令K[j] = P[j] - i，于是問題轉(zhuǎn)化成了一個(gè)一維的問題。
L[i] 表示 K [ L[i]+1 ... i] 中的元素都大于等于K[i]，但是L[i]小于K[i]；
R[i] 表示 K [i ... R[i]-1] 中的元素都大于等于K[i],但是R[i]小于K[i]；
Max{ (R[i] - L[i] - 1) * K[i], 1 <= i <= N }就是以當(dāng)前枚舉行為起點(diǎn)的最大矩陣，枚舉M次取最大值就是全局的最大子矩陣了。
E. Cube Root
PKU 1965 http://poj.org/problem?id=1965
題意：給定一個(gè)不超過150個(gè)數(shù)字的正整數(shù)，求它的三次方根，精確到小數(shù)點(diǎn)后10位。
題解：大數(shù)模擬
將輸入的數(shù)X用字符串存儲(chǔ)，乘上1030，利用二分求出最大的Y，使得Y3 <= X。然后在Y的后十位前插入一個(gè)小數(shù)點(diǎn)，輸出即可。
F. Cable TV Network
PKU 1966 http://poj.org/problem?id=1966
題意：求圖的點(diǎn)連通度。給定一個(gè)N(N <= 50)個(gè)點(diǎn)的圖，求去掉至少多少個(gè)點(diǎn)能夠?qū)⑺兂梢粋€(gè)非連通圖。
題解：搜索 + 剪枝 (或者 最大流)
枚舉每個(gè)點(diǎn)去掉或不去掉，總共250種狀態(tài)，每次去掉點(diǎn)后判斷當(dāng)前圖的連通性，一旦破壞了連通，去掉的點(diǎn)數(shù)即為答案；如果發(fā)現(xiàn)某個(gè)點(diǎn)去掉后，剩下點(diǎn)組成的圖變成了一個(gè)完全圖，那么不用繼續(xù)搜索了，因?yàn)楫?dāng)前狀態(tài)下不可能將剩下的圖變成非連通圖了；如果去掉的點(diǎn)數(shù)超過目前的最優(yōu)解也直接剪枝。
好吧...一定是數(shù)據(jù)弱了-_-||，正解是最大流拆點(diǎn)。
G. Alibaba
PKU 1967 http://poj.org/problem?id=1967
題意：給定N(N <= 104)個(gè)整數(shù)對(duì)(Pi, Di)表示在Pi位置有一個(gè)寶物，并且需要在Di 時(shí)間之前取走(給出順序?yàn)?/span>Pi遞增的順序)。起始可以任意選擇一個(gè)位置，往左或者往右取寶物，問是否能夠保證每個(gè)物品都在Di時(shí)間之前取走(時(shí)間和距離關(guān)系為1:1)，如果可以，給出取完所有寶物的最少時(shí)間。
題解：搜索 + 剪枝
首先可以想到的是，起始位置一定是N個(gè)寶物所在位置中的其中一個(gè)，所以首先可以枚舉每個(gè)寶物的起始點(diǎn)，比如當(dāng)前位置為pos，那么在第0秒內(nèi)，訪問過的區(qū)間為[pos, pos]，可以選擇往左走，也可以選擇往右走，那么是不是只要選擇某個(gè)方向走完，然后再反方向走到底如果能夠滿足所有點(diǎn)都在截止時(shí)間內(nèi)完成一定是對(duì)的呢？答案是否定的，來看一組數(shù)據(jù)，如圖1，起始點(diǎn)只能選擇3號(hào)位置，并且只能選擇往右走，走到4后再折回走到2，然后再折回走到5，以此類推，并且只有這一種路徑才能滿足所有寶物都在截至?xí)r間內(nèi)取完。
圖1
按照這個(gè)思路，進(jìn)行狀態(tài)的劃分，假設(shè)當(dāng)前已經(jīng)訪問的區(qū)間為[L, R]，并且現(xiàn)在的位置處于pos位置(這里pos要么等于L，要么等于R)，所以可以用三維來表示狀態(tài)DP[s][l][r](l、r表示訪問過的區(qū)間的左右端點(diǎn)，如果當(dāng)前位置在l則s = 0，如果當(dāng)前位置在r，則s=1)，總共狀態(tài)數(shù)目N2，狀態(tài)轉(zhuǎn)移的時(shí)候由大狀態(tài)推小狀態(tài)，即DP[s][l][r]一定是由DP[0][l-1][r]、DP[0][l][r+1]、DP[1][l-1][r]、DP[1][l][r+1]這四個(gè)狀態(tài)得出。
考慮到N比較大，所以把所有狀態(tài)存儲(chǔ)到數(shù)組中再利用動(dòng)態(tài)規(guī)劃進(jìn)行遞推，如果數(shù)據(jù)量不多的話，可以卡過，但是狀態(tài)存儲(chǔ)需要用滾動(dòng)數(shù)組，否則內(nèi)存吃不消，也可以采用搜索 + 剪枝，思路是沿用了動(dòng)態(tài)規(guī)劃的思想，假設(shè)當(dāng)前已經(jīng)訪問的區(qū)間為[L, R]，現(xiàn)在的位置處于pos位置(這里pos要么等于L，要么等于R)，并且已經(jīng)使用了T的時(shí)間，無論當(dāng)前的pos是在左區(qū)間端點(diǎn)L上還是在右區(qū)間端點(diǎn)R上，他都可以選擇走到L-1(L > 1)，或者R+1(R < N)，于是就可以遞歸求解了，遞歸出口為L=1，R=N的時(shí)候。
圖2
如圖，已經(jīng)訪問的寶物為紅色標(biāo)記的點(diǎn)，灰色標(biāo)記的為未曾訪問過的，并且現(xiàn)在的位置在已經(jīng)訪問區(qū)間的左端點(diǎn)L上，已經(jīng)使用了T的時(shí)間，我們需要判斷這個(gè)狀態(tài)是否合法，則需要滿足以下的幾個(gè)不等式。
1、保證右邊未訪問的都能在截止時(shí)間內(nèi)訪問到：
T + (P[R] - P[L]) + (P[R+1] - P[R]) < D[R+1]
T + (P[R] - P[L]) + (P[R+2] - P[R]) < D[R+2]
...
T + (P[R] - P[L]) + (P[N] - P[R]) < D[N]
將這些等式化簡，可得：
T - P[L] < D[R+1] - P[R+1]
T - P[L] < D[R+2] - P[R+2]
...
T - P[L] < D[N] - P[N]
再進(jìn)行進(jìn)一步化簡，得：
T - P[L] < Min{ D[k] - P[k], R < k <= N }
2、保證左邊未訪問的都能在截止時(shí)間內(nèi)訪問到：
同理，可以得出：
T + P[R] < Min{ D[k] + P[k], 1 <= k < R }
那么，令 POSTM[i] = Min{ D[k] - P[k], i < k <= N }
PREM[i] = Min{ D[k] + P[k], 1 <= k < i }
這兩個(gè)數(shù)組可以分別通過一次逆序和順序的線性掃描求出來，用于搜索的時(shí)候判斷可行性。例如，當(dāng)T - P[L] >= POSTM[R] 表示在右邊未訪問的寶物中有至少一個(gè)寶物不能在截止時(shí)間前被訪問到，T + P[R] >= PREM [R]表示在左邊未訪問的寶物中有至少一個(gè)寶物不能在截止時(shí)間前被訪問到，直接剪枝。
還需要一個(gè)剪枝，就是在當(dāng)前時(shí)間T加上當(dāng)前狀態(tài)下預(yù)計(jì)訪問完所有寶物的最小時(shí)間已經(jīng)比之前求出的最小時(shí)間大，直接剪枝。
H . Booklets
PKU 1968 http://poj.org/problem?id=1968
題意：N(N <= 3000)本小冊(cè)子需要分配給S個(gè)學(xué)校，每個(gè)學(xué)校得到的是N/S的上整本冊(cè)子或者N/S的下整本冊(cè)子，每本冊(cè)子有一個(gè)頁數(shù)，并且規(guī)定分配冊(cè)子的時(shí)候按照頁數(shù)遞增來分配，先把上整本冊(cè)子分完再分下整的，對(duì)于每個(gè)學(xué)校的分書規(guī)則，按照輸入的順序進(jìn)行分配。求問第T個(gè)學(xué)校分到的第一本冊(cè)子的頁數(shù)。
題解：需要求出幾個(gè)量：
上整冊(cè)子的數(shù)目UIP = (N+S-1) / S;
下整冊(cè)子的數(shù)目LIP = N/S;
分到上整冊(cè)子數(shù)目的學(xué)校個(gè)數(shù)UIPC = N % S;
分到下整冊(cè)子數(shù)目的學(xué)校個(gè)數(shù)LIPC = N - N % S;
首先對(duì)所有的冊(cè)子按頁數(shù)遞增來排序(如果頁數(shù)相同按照下標(biāo)遞增排序)，然后減去前T-1個(gè)學(xué)校的冊(cè)子總數(shù)，容易得出第T個(gè)學(xué)校分到的冊(cè)子數(shù)目C，從接下來的C個(gè)冊(cè)子中找到之前下標(biāo)最小的冊(cè)子，它對(duì)應(yīng)的頁數(shù)就是答案。
I. Count on Canton
PKU 1969 http://poj.org/problem?id=1969
題意：給定下圖所示的無限分?jǐn)?shù)序列，并且按照蛇形方式編號(hào)，即第一個(gè)為1/1，第二個(gè)為1/2，第三個(gè)為2/1，第四個(gè)為3/1，以此類推，問第N個(gè)分?jǐn)?shù)是什么。
1/1 1/2 1/3 1/4 1/5 ...
2/1 2/2 2/3 2/4
3/1 3/2 3/3
4/1 4/2
5/1
題解：數(shù)學(xué)題。
首先二分求出在第幾條斜線上，即(K-1)K/2 < N的最大的K，然后求根據(jù)K的奇偶性求出蛇形在第K條斜線的行走方向，第N - (K-1)K/2 個(gè)數(shù)就是答案。