2.5　練習題

習題2-1

題目來源：HDU 5536。

題目類型：01字典樹。

題目思路：把每個數字看成一個01字符串插入Trie樹中去，枚舉i和j，然后把si和sj從Trie樹中刪去。然后在Trie樹中通過貪心算法找與si+sj異或得到的最大值。具體匹配的過程為：首先看樹中最高位能否異或得到1，能的話就往能的那個方向走，否則往另外一個方向走。另外刪除操作是這樣實現的，每個節(jié)點記錄一個val值，插入時對所有經過節(jié)點的val值加1，刪除就將對應節(jié)點的val值減1。在樹上匹配的時候就只走那些val值為正的節(jié)點。

習題2-2

題目來源：HDU 482。

題目類型：01字典樹。

題目思路：求某個數與一些數異或的最大值，是字典樹應用的一個經典問題。主要思想是貪心算法，將給定的數按照二進制構成一棵字典樹，每一層分別對應各個位數上的01狀態(tài)。然后進行查詢，如果對應位置為0，則要往1的方向走；如果對應位置為1，則要往0的方向走。但是要注意，走的前提是對應分支是存在的。

習題2-3

題目來源：POJ 3764。

題目類型：01字典樹。

題目思路：這道題是要在樹中找兩個節(jié)點，且兩個節(jié)點之間路徑唯一，求最長的異或路徑。很明顯不能用暴力算法，O（N2）時間復雜度為100000個點。首先需要知道一個性質：a⊕b=（a⊕c）⊕（b⊕c），這樣就可以考慮找出a與b公共的c，實際上就是求出從根節(jié)點到每個節(jié)點的異或值，這樣任意兩個點做異或，即是它們之間的異或路徑（相同部分異或抵消了）。先使用DFS（Depth First Search）方法遍歷一遍，找出所有節(jié)點到樹根的路徑異或值，這樣就將問題轉化成了求這些點中任意兩個點的異或值，接下來就很簡單了，將使用DFS方法所得的每個點的異或值轉化成二進制數后保存在字典樹中，然后從高位至低位對字典樹進行貪心搜索，找出最大的那個值即可。

習題2-4

題目來源：HDU 3746。

題目類型：KMP。

題目思路：題目要求的是給定一個字符串，還需要添加幾個字符可以構成一個由n個循環(huán)節(jié)組成的字符串。由題目可知，應該先求出字符串的最小循環(huán)節(jié)的長度。假設字符串的長度為len，那么最小的循環(huán)節(jié)cir=len-next[len]；如果有l(wèi)en%cir==0，那么這個字符串就已經是要求的字符串了，不用添加任何字符；如果不是要求的那么需要添加的字符數為cir-（len-（len/cir）×cir））。如果cir=1，說明字符串只有一種字符，例如“aaa”；如果cir=m，說明最小的循環(huán)節(jié)長度為m，那么至少還需m個字符；如果m%cir==0，說明已經不用添加了字符。

習題2-5

題目來源：POJ 2406。

題目類型：KMP。

題目思路：對于next數組表示的模式串，如果第i位（設str[0]為第0位）與第j位不匹配，則要回到第next[i]位繼續(xù)與模式串第j位匹配，則模式串第1位到next[n]與模式串第n-next[n]位到n位是匹配的。所以思路和上面一樣，如果n%（n-next[n]）=0，則存在重復連續(xù)子串，長度為n-next[n]。

例如，“a　b　a　b　a　b”，next[]={-1,0,0,1,2,3,4}，next[n]=4，代表前綴“abab”與后綴“abab”相等的最長長度，這說明，“ab”這兩個字母為一個循環(huán)節(jié)，長度=n-next[n]。

習題2-6

題目來源：BZOJ 1717。

題目類型：后綴數組+二分法。

題目思路：先二分答案，然后將后綴分成若干組。判斷有沒有一個組的后綴個數不小于k。如果有，那么存在k個相同的子串滿足條件，否則不存在。

習題2-7

題目來源：BZOJ 2251。

題目類型：后綴數組。

題目思路：首先根據后綴數組的一些經典應用，可以知道每個后綴對子串個數的貢獻是n-H[i]-sa[i]，而且順序就是字典序，枚舉每個子串暴力的用H數組前后求匹配：L為向前最多到哪，R為向后最多到哪，答案是R-L。還有更簡單的Trie樹方法。

習題2-8

題目來源：BZOJ3238。

題目類型：后綴數組。

題目思路：首先這個式子可以拆成兩部分計算，一部分是兩個后綴長度之和，一部分是最長公共前綴（Longest Common Prefix，LCP）長度之和。第一部分很簡單，發(fā)現每個長度的后綴都計算了n-1次，所以第一部分的答案為（n-1）×[n×（n+1）/2]，注意計算過程中需要強制類型轉換。而第二部分和之前的一個模型類似，需要用到單調棧。兩個后綴的LCP在h數組里其實就是一段區(qū)間的最小值，而反過來h數組每段區(qū)間的最小值對應著兩個后綴的LCP，然后計算總和。單調棧維護一個遞增的、用f[i]表示h數組中從i到n所有區(qū)間的LCP之和，每次計算f[i]，f[i]=f[st[top]]+h[i]×（st[top]-i），然后計入總和就行。

習題2-9

題目來源：HDU6194。

題目類型：后綴數組。

題目思路：先考慮至少出現k次的子串，所以枚舉排好序的后綴i（sa[i]）。假設當前枚舉的是sa[i]～sa[i+k-1]，假設這一段的最長公共前綴是L的話，那么就有L個不同的子串至少出現了k次，要減去至少出現k+1次的子串，但還要和這個k段的LCP有關系，因此肯定就是sa[i]～sa[i+k-1]這一段向上找一個后綴或者向下找一個后綴。即sa[i-1]～sa[i+k-1]和sa[i]～sa[i+k]求兩次LCP減去即可。但是會減多了，減多的顯然是sa[i-1]～sa[i+k]的LCP，加上即可。注意k=1的情況在求LCP會有問題，即求一個字符串的最長公共前綴會有問題，特判一下即可。