A. Constellations
PKU 3690 http://poj.org/problem?id=3690
題意：給定N*M(N<=1000, M <= 1000)的01矩陣S，再給定T(T <= 100)個(gè)P*Q(P <= 50, Q <= 50)的01矩陣，問(wèn)P*Q的矩陣中有多少個(gè)是S的子矩陣。
題解：位壓縮 + KMP
由于P <= 50，所以我們可以把所有P*Q的矩陣進(jìn)行二進(jìn)制位壓縮，將P*Q的矩陣的每一列壓縮成一個(gè)64位整數(shù)，這樣P*Q的矩陣就變成了一個(gè)長(zhǎng)度為Q的整數(shù)序列，用同樣的方式對(duì)N*M的矩陣進(jìn)行壓縮，總共可以產(chǎn)生(N-P+1)個(gè)長(zhǎng)度為M的整數(shù)序列，剩下的就是進(jìn)行最多(N-P+1)次KMP匹配了。
KMP相關(guān)算法可以參閱：
http://www.shnenglu.com/menjitianya/archive/2014/06/20/207354.html
圖1 ‘*’代表二進(jìn)制的1, ’0’代表二進(jìn)制的0
B. DNA repair
PKU 3691 http://poj.org/problem?id=3691
題意：給定N(N <= 50)個(gè)長(zhǎng)度不超過(guò)20的模式串，再給定一個(gè)長(zhǎng)度為M(M <= 1000)的目標(biāo)串S，求在目標(biāo)串S上最少改變多少字符，可以使得它不包含任何的模式串（所有串只有ACGT四種字符）。
題解：AC自動(dòng)機(jī) + 動(dòng)態(tài)規(guī)劃
利用模式串建立trie圖，trie圖的每個(gè)結(jié)點(diǎn)(即下文講到的狀態(tài)j)維護(hù)三個(gè)結(jié)構(gòu)，
Node{
Node *next[4]; // 能夠到達(dá)的四個(gè)狀態(tài) 的結(jié)點(diǎn)指針
int id; // 狀態(tài)ID，用于到數(shù)組下標(biāo)的映射
int val; // 當(dāng)前狀態(tài)是否是一個(gè)非法狀態(tài) （以某些模式串結(jié)尾）
}
用DP[i][j]表示長(zhǎng)度為i (i <= 1000)，狀態(tài)為j(j <= 50*20 + 1)的字符串變成目標(biāo)串S需要改變的最少字符，設(shè)初始狀態(tài)j = 0，那么DP[0][0] = 0，其他均為無(wú)窮大。從長(zhǎng)度i到i+1進(jìn)行狀態(tài)轉(zhuǎn)移，每次轉(zhuǎn)移枚舉共四個(gè)字符(A、C、G、T)，如果枚舉到的字符和S對(duì)應(yīng)位置相同則改變值T=1，否則T=0；那么有狀態(tài)轉(zhuǎn)移方程 DP[i][j] = Min{ DP[i-1][ fromstate ] + T, fromstate為所有能夠到達(dá)j的狀態(tài) };最后DP[n][j]中的最小值就是答案。
C. Kindergarten
PKU 3692 http://poj.org/problem?id=3692
題意：給定G(G <= 200)個(gè)女孩和B(B <= 200)個(gè)男孩，以及M(0 <= M <= G*B)條記錄(x, y)表示x號(hào)女孩和y號(hào)男孩互相認(rèn)識(shí)。并且所有的女孩互相認(rèn)識(shí)，所有的男孩互相認(rèn)識(shí)，求找到最大的一個(gè)集合使得所有人都認(rèn)識(shí)。
題解：二分圖最大匹配
一個(gè)點(diǎn)集中所有人都認(rèn)識(shí)表示這個(gè)點(diǎn)集是個(gè)完全圖，該問(wèn)題就是求原圖的一個(gè)最大團(tuán)(最大完全子圖)，可以轉(zhuǎn)化為求補(bǔ)圖的最大獨(dú)立集，而補(bǔ)圖恰好是個(gè)二分圖。二分圖的最大獨(dú)立集 = 總點(diǎn)數(shù) - 二分圖的最大匹配。于是問(wèn)題就轉(zhuǎn)化成了求補(bǔ)圖的最大匹配了。
D. Maximum repetition substring
PKU 3693 http://poj.org/problem?id=3693
題意：給定長(zhǎng)度為N(N <= 105)的字符串S，求它的一個(gè)最多重復(fù)子串(注意：最多重復(fù)子串不等于最長(zhǎng)重復(fù)子串，即ababab和aaaa應(yīng)該取后者)。
題解：后綴數(shù)組 + RMQ
枚舉重復(fù)子串的長(zhǎng)度L，如果對(duì)于某個(gè)i，有S[i*L ... N]和S[(i+1)*L ... N]的最長(zhǎng)公共前綴大于等于L(這一步可以利用后綴數(shù)組求解height數(shù)組，然后通過(guò)RMQ查詢區(qū)間最小值來(lái)完成)，那么以i*L為首，長(zhǎng)度為L的子串至少會(huì)重復(fù)兩次。
圖2
如圖，L=3，i=3的情況，S[3...10]和S[6...10]的最長(zhǎng)公共前綴為3，即S[3...5]和S[6...8]完全匹配，所以S[3...5]重復(fù)了兩次。反之，如果最長(zhǎng)公共前綴小于L，必定不會(huì)重復(fù)（因?yàn)閮蓚€(gè)子串之間出現(xiàn)了斷層）。
推廣到更一般的情況，如果S[i*L ... N]和S[(i+1)*L ... N]的最長(zhǎng)公共前綴為T，那么以S[i*L]為首的重復(fù)子串的重復(fù)次數(shù)為T / L + 1，而且我們可以發(fā)現(xiàn)如果以S[i*L]為首，長(zhǎng)度為L的子串的重復(fù)次數(shù)大于等于2，那么它一定不會(huì)比以S[(i+1)*L]為首的子串的重復(fù)次數(shù)少，這個(gè)是顯然的，比如L為2的時(shí)候，ababab一定比abab多重復(fù)一次，基于這個(gè)性質(zhì)，我們定義一個(gè)new_flag標(biāo)記，表示是否需要計(jì)算接下來(lái)匹配到的串(如ababab和abab的情況，前者計(jì)算過(guò)了，就把new_flag置為false，就不會(huì)計(jì)算abab的情況了)，得出完整算法：
1) 枚舉重復(fù)子串的長(zhǎng)度L，初始化new_flag標(biāo)記為true；
2) 枚舉i，計(jì)算S[i*L ... N]和S[(i+1)*L ... N]的最長(zhǎng)公共前綴T；
a) 如果T < L，new_flag標(biāo)記為true；
b) 如果T >= L，判斷new_flag是不是為false，如果為false，說(shuō)明以S[i*L]為首的串和S[(i-1)*L]為首的串的最長(zhǎng)公共前綴大于等于T，跳轉(zhuǎn)到2)；否則轉(zhuǎn)3)；
3) 因?yàn)?/span>S[i*L, (i+1)*L]有重復(fù)子串，但是字典序不一定最小，所以還需要枚舉區(qū)間 [i-L+1, i+L]，看是否存在字典序更小的子串，比較字典序這一步可以直接使用后綴數(shù)組計(jì)算出來(lái)的rank值進(jìn)行比較。
RMQ相關(guān)算法可以參閱：
http://www.shnenglu.com/menjitianya/archive/2014/06/26/207420.html
E. Network
PKU 3694 http://poj.org/problem?id=3694
題意：給定N(N <= 105)個(gè)點(diǎn)和M(N-1 <= M <= 2*105)條邊的無(wú)向連通圖，進(jìn)行Q(Q <= 1000)次加邊，每次加入一條邊要求輸出當(dāng)前圖中有多少條割邊。
題解：無(wú)向圖割邊、最近公共祖先
利用tarjan求出原圖的割邊，由于這題數(shù)據(jù)量比較大，所以用遞歸可能會(huì)爆棧，需要棧模擬實(shí)現(xiàn)遞歸過(guò)程，tarjan計(jì)算的時(shí)候用parent[u]保存u的父結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)進(jìn)出棧各一次，出棧時(shí)表示以它為根結(jié)點(diǎn)的子樹(shù)訪問(wèn)完畢，然后判斷(u, parent[u])是否為割邊。每次詢問(wèn)u, v加入后會(huì)有多少割邊，其實(shí)就是求u和v的到它們的最近公共祖先lca(u, v)的路徑上有多少割邊，由于在進(jìn)行tarjan計(jì)算的時(shí)候保存了每個(gè)結(jié)點(diǎn)的最早訪問(wèn)時(shí)間dfn[u]，那么有這么一個(gè)性質(zhì)：dfn[ parent[u] ] < dfn[u]，這是顯然的(父結(jié)點(diǎn)的訪問(wèn)先于子結(jié)點(diǎn))。于是當(dāng)dfn[u] < dfn[v]，將parent[v]賦值給v，反之，將parent[u]賦值給u，因?yàn)槭且豢脴?shù)，所以進(jìn)過(guò)反復(fù)迭代，一定可以出現(xiàn)u == v 的情況，這時(shí)候的u就是原先u和v的最近公共祖先，在迭代的時(shí)候判斷路徑上是否存在割邊，路徑上的割邊經(jīng)過(guò)(u, v)這條邊的加入都將成為非割邊，用一個(gè)變量保存割邊數(shù)目，輸出即可。
圖3
如圖3，圖中實(shí)線表示樹(shù)邊，虛線表示原圖中的邊，但是進(jìn)行tarjan計(jì)算的時(shí)候7這個(gè)結(jié)點(diǎn)被(6, 7)這條邊“捷足先登”了，于是(4, 7)成為了一條冗余邊，計(jì)算完后這個(gè)圖的割邊為(1, 2)、(1,3)、(3, 4)、(3, 5)，分別標(biāo)記bridge[2]、bridge[3]、bridge[4]、bridge[5]為true。
當(dāng)插入一條邊(7, 5)，那么沿著7的祖先路徑和5的祖先路徑最后找到的最近公共祖先為3(路徑為7 -> 6 -> 4 -> 3 和 5 -> 3)，(3, 4)、(3, 5)這兩條割邊因?yàn)榧尤肓?/span>(7, 5)這條邊而變成了普通邊，將標(biāo)記bridge[4]、bridge[5]置為false。
F. Rectangles
PKU 3695 http://poj.org/problem?id=3695
題意：給定N(N <= 20)個(gè)矩形，以及M(M <= 105)次詢問(wèn)，詢問(wèn)R(R <= N)個(gè)矩形的并。
題解：離散化 + 暴力( 或 容斥原理 )
離散化：由于矩形很少，所以可以將它們的XY坐標(biāo)分別離散到整點(diǎn)，兩個(gè)維度分別離散，點(diǎn)的總數(shù)不會(huì)超過(guò)2N，對(duì)于本次詢問(wèn)，利用前一次詢問(wèn)的結(jié)果進(jìn)行面積的增減，對(duì)每個(gè)矩形進(jìn)行判斷，一共有兩種情況：
1）這個(gè)矩形前一次詢問(wèn)出現(xiàn)，本次詢問(wèn)不出現(xiàn)，對(duì)它的所有離散塊進(jìn)行自減操作，如果某個(gè)離散塊計(jì)數(shù)減為0，則總面積減去這個(gè)離散塊的面積；
2）這個(gè)矩形前一次詢問(wèn)沒(méi)出現(xiàn)，本次詢問(wèn)出現(xiàn)，對(duì)它的所有離散塊進(jìn)行自增操作，如果某個(gè)離散塊計(jì)數(shù)累加后為1，則總面積加上這個(gè)離散塊的面積；
容斥原理：對(duì)于每個(gè)詢問(wèn)，利用dfs枚舉每個(gè)矩形取或不取，取出來(lái)的所有矩形作相交操作，所有[奇數(shù)個(gè)矩形交]的面積和 – 所有[偶數(shù)個(gè)矩形交]的面積和 就是答案，因?yàn)槭?/span>dfs枚舉，所以在枚舉到某次相交矩形面積為0的時(shí)候就不需要再枚舉下去了，算是一個(gè)比較強(qiáng)的剪枝。
如圖4，紅色區(qū)域?yàn)楸桓采w了一次的區(qū)域，橙色區(qū)域?yàn)楸桓采w了兩次的區(qū)域，黃色區(qū)域?yàn)楸桓采w了三次的區(qū)域，那么先將所有的三個(gè)矩形加起來(lái)，然后需要減掉重疊的部分，重疊的減掉后發(fā)現(xiàn)，重疊的部分多減了，即圖中黃色的部分被多減了一次，需要加回來(lái)。所以容斥原理可以概括為：奇數(shù)加，偶數(shù)減。
圖4
G. The Luckiest number
PKU 3696 http://poj.org/problem?id=3696
題意：給定L(L <= 2*109)，求一個(gè)最小的數(shù)T，滿足T僅由數(shù)字’8’組成，并且T是L的倍數(shù)。
題解：歐拉定理
首先，長(zhǎng)度為N的僅由8組成的數(shù)字可以表示為8*(10N-1)/9。
如果它能被L整除，則可以列出等式(1)：
8*(10N-1)/9 = KL (其中K為任意正整數(shù)) (1)
將等式稍作變形得到等式(2)：
(10N-1) = 9KL/8 (2)
由于存在分母，所以我們需要先對(duì)分?jǐn)?shù)部分進(jìn)行約分，得到等式(3)：
令A = L/GCD(8, L), B = 8/GCD(8, L)
(10N-1) = 9K*A / B (3)
因?yàn)?/span>A和B已經(jīng)互質(zhì)，所以如果B不為1，為了保證等式右邊仍為整數(shù)，K必須能被B整除，而K為任意整數(shù)，所以一定能夠找到一個(gè)K正好是B的倍數(shù)，所以可以在等式兩邊同時(shí)模9A，得到(10N-1) mod (9A) = 0，稍作變形，得到等式(4):
(4)
于是需要引入一個(gè)定理，即歐拉定理。
歐拉定理的描述為：若n, a為正整數(shù)，且n, a互質(zhì)，則：
圖5
(ψ(n)表示n的歐拉函數(shù)，即小于等于n并且和n互素的數(shù)的個(gè)數(shù))
這樣一來(lái)，我們發(fā)現(xiàn)只要10和9A互質(zhì)，只需要求9A的歐拉函數(shù)，但是求出來(lái)的歐拉函數(shù)是不是一定使得N最小呢，并不是，所以還需要枚舉歐拉函數(shù)的因子，如果它的某個(gè)因子T也滿足(4)的等式，那么T肯定不會(huì)比ψ(9A)大，所以T一定更優(yōu)。
這里9A有可能超過(guò)32位整數(shù)，所以計(jì)算過(guò)程中遇到的乘法操作不能直接相乘(兩個(gè)超過(guò)32位整數(shù)的數(shù)相乘會(huì)超過(guò)64位整數(shù))，需要用到二分乘法，即利用二進(jìn)制加法模擬乘法，思想很簡(jiǎn)單，就直接給出一段代碼吧。
1 #define LL __int64
2
3 //計(jì)算 a*b % mod
4 LL Produc_Mod(LL a, LL b, LL mod) {
5 LL sum = 0;
6 while(b) {
7 if(b & 1) sum = (sum + a) % mod;
8 a = (a + a) % mod;
9 b >>= 1;
10 }
11 return sum;
12 }
13
14
15 //計(jì)算a^b % mod
16 LL Power(LL a, LL b, LL mod) {
17 LL sum = 1;
18 while(b) {
19 if(b & 1) sum = Produc_Mod(sum, a, mod);
20 a = Produc_Mod(a, a, mod);
21 b >>= 1;
22 }
23 return sum;
24 }
H. USTC campus network
PKU 3697 http://poj.org/problem?id=3697
題意：給定N, M(N <= 104, M <= 106)，求N個(gè)點(diǎn)的完全圖刪掉M條邊后，和1這個(gè)結(jié)點(diǎn)相鄰的點(diǎn)的數(shù)目。
題解：BFS
利用前向星存邊(這里邊的含義是反的，i和j有邊表示i和j不直接連通)。然后從1開(kāi)始廣搜，將和1有邊的點(diǎn)hash掉，然后枚舉hash數(shù)組中沒(méi)有hash掉的點(diǎn)(這些點(diǎn)是和1連通的)，如果點(diǎn)沒(méi)有被訪問(wèn)過(guò)，標(biāo)記已訪問(wèn)，入隊(duì)；然后不斷彈出隊(duì)列首元素進(jìn)行相同的處理。
這里可以加入一個(gè)小優(yōu)化，將所有點(diǎn)分組，編號(hào)0-9的分為一組，10-19的分為一組，20-29的分為一組，然后用一個(gè)計(jì)數(shù)器來(lái)記錄每個(gè)組中的點(diǎn)是否被訪問(wèn)，每次訪問(wèn)到一個(gè)點(diǎn)的時(shí)候計(jì)數(shù)器自增，當(dāng)某個(gè)組的計(jì)數(shù)器為10的時(shí)候表示這個(gè)組內(nèi)所有點(diǎn)都被訪問(wèn)過(guò)了，不需要再進(jìn)行枚舉了，這樣可以把最壞復(fù)雜度控制在 O( N*N/10 ) 以下。