[SPOJ LCS2]LCS2 - Longest Common Substring II

此篇題解必須先熟悉後綴自動機的操作才能看懂
關於詳細的後綴自動機圖文教學，請參考這裡

簡單來說，題目給你一堆字串$S_{i}$ ($1\leq i\leq N\leq 10$)，要你求這些$S_{i}$最長的公共子字串長度

可以考慮先對$S_{1}$建立一個後綴自動機，這樣就只有$S_{1}$的子字串能夠被這個自動機接受了
之後每輸入一個字串$S_{i}$，就維護這個自動機，讓這個自動機只接受$S_{1}、S_{2}、...、S_{i}$的共同子字串

真的可行嗎？

我們先回顧一下只有兩個字串$A$和$B$時，找出$A$和$B$的最大共同子字串長度的方法
先對$A$建立後綴自動機，然後用$B$去嘗試在自動機裡面轉移
當轉移失敗時就沿著失配邊走一步，再繼續嘗試轉移

可以發現
每成功轉移一次，代表找到長度多$1$的共同子串
每沿著失配邊走一步，目前找到的共同子串長度就變為走到的節點的$max\_len$

而過程中走到的每一個節點和其沿著失配邊可以走到的所有點，每個點代表的字串集合聯集起來就恰好是$A$和$B$的共同子字串了，不多也不少

咦？真的嗎？

注意剛剛這句話：「每成功轉移一次，代表找到長度多$1$的共同子串」
因此就算目前找到了長度$x$的共同子串，不一定代表目前節點的$max\_len=x$ (但可以保證$max\_len\geq x$)

只有兩個字串時，只要持續更新找到共同子串的最大長度即可，因此這個問題可以忽略

但是這題要求處理多個字串，因此我們必須面對這個問題，否則會多考慮一些情況
回想建立後綴自動機的過程，好像也遇過同樣的問題耶！
都是因為某個節點代表的字串集合中有些是不想要的

因此，解決方法也一樣
把想要的點分離出來！

code中的Node *Split(Node *cur,const int c)就是回傳分離出來的點

因此，先對$S_{1}$建立一個後綴自動機，這樣就只有$S_{1}$的子字串能夠被這個自動機接受了
之後每輸入一個字串$S_{i}$，就維護這個自動機，讓這個自動機只接受$S_{1}、S_{2}、......、S_{i}$的共同子字串
方法是讓$S_{i}$在自動機裡面轉移，並藉由分裂點的方式確保走到的每個點和其沿著失配邊可以走到的點所包含的字串集合，聯集起來就恰好是所有的共同子串
每轉移一次最多需要分裂一次點，因此讓$S_{i}$進行轉移的時間複雜度是$\left|S_{i}\right|$

至於轉移完之後要怎麼維護讓這個自動機以後只接受$S_{1}、S_{2}、......、S_{i}$的共同子字串呢？
我們先把所有走過的點標記起來，這些點和其沿著失配邊可以走到的點都必須被保留下來，而其他的必須刪除

可以發現，把所有的失配邊反向後會形成一棵樹，因此可以用一個$queue$儲存所有樹葉，每當$S_{i}$加入完成後，就可以每個樹葉檢查看看能不能刪除
不能的話加入下一個$queue$供下次使用
可以的話將這個節點標記為刪除 (直接$delete$釋放記憶體會出錯。想一想，為甚麼XD)
當一個節點的所有子節點都被刪除了，這個節點就成了樹葉，必須被加入$queue$接受檢查

其實，上面的做法還忘記考慮一點：那分裂出來的點會不會成為新的樹葉呢？
答案是不會的 (想一想，為甚麼XD)

要實作上述過程，必須先做不少的預處理、建立並在適當的時機維護一些資訊，之後才能達到所需的複雜度 (複雜度是不允許有$\log$的)

因此，加入$S_{i}$的時間複雜度怎麼算呢？
首先必須先花費$O(\left|S_{i}\right|)$來進行轉移並視需要分裂一些點
然後再用$O(\left|S_{1}\right|)$來檢查所有的葉節點要不要刪除
這只是檢查
整個刪除葉子的過程的時間複雜度總共是$O(\sum_{i=1}^{N}\left|S_{i}\right|)$

總時間複雜度：$O(\left|S_{1}\right|+\sum_{i=2}^{N}\left|S_{i}\right|+(N-1)\left|S_{1}\right|+\sum_{i=1}^{N}\left|S_{i}\right|)\approx O(N\left|S_{1}\right|+\sum_{i=1}^{N}\left|S_{i}\right|)$

code:

後綴自動機 (SAM) 圖文教學 (六)

請先參考後綴自動機 (SAM) 圖文教學 (五)

先來看程式碼吧～

code:

#include<cstdio>
#include<cassert>
using namespace std;
struct Node
{
    Node *green,*edge[26];
    int max_len;
    Node(const int _max_len):green(NULL),max_len(_max_len){for(int i=0;i<26;i++)edge[i]=NULL;}
}*ROOT,*LAST;
void Extend(const int c)
{
    Node *cursor=LAST;LAST=new Node((LAST->max_len)+1);
    for(;cursor&&!cursor->edge[c];cursor=cursor->green)cursor->edge[c]=LAST;//添加LAST所有的黑色字串 
    if(!cursor)LAST->green=ROOT;//其實圖上沒有畫綠色邊的點，代表著它的綠色邊是直接指向「代表空串的根結點」

後綴自動機 (SAM) 圖文教學 (五)

請先參考後綴自動機 (SAM) 圖文教學 (四)

(Copyright：圖片轉載請註明來源網址，感謝～)

我們已經在紙上演練了這麼多次，該來看看這個很視覺化的東西要怎麼用程式來實作了吧？

首先是節點儲存問題
回顧定義，每個節點都代表了一個字串的一堆後綴所組成的字串集合
例如這張$S="abbbb"$圖：(還記得$S$是甚麼嗎？趕快到這裡複習一下吧～)

可以發現節點$7$代表了$"abbbb"$、$"bbbb"$、$"bbb"$、$"bb"$、$"b"$這些字串，也就是$"abbbb"$的所有後綴組成的字串集合

可是又不能很貪心地只儲存長度最長的$"abbbb"$，因為這些字串還有黑色和綠色之分，是會影響下一次加入新字母時的行為的......

咦？真的是這樣嗎？

後綴自動機 (SAM) 圖文教學 (四)

請先參考後綴自動機 (SAM) 圖文教學 (三)

(Copyright：圖片轉載請註明來源網址，感謝～)

說明：
用兩個「$"$」框起來的東西是字串
用兩個「$'$」框起來的東西是字元 (在這裡等價於單純的英文字母)
「路徑$"abcd"$」代表字串$"abcd"$在圖上會走過的一條路徑
「字串集合」代表很多字串 (?)

$"abbbb"$的圖要怎麼建呢？
我們可以照著上上篇的思路，一個字母一個字母慢慢加

依序加入邊$'a'$、邊$'b'$的過程和上上篇一模模模一樣樣樣，若已經忘記了可以翻回去回顧一下噢～
依序加完邊$'a'$、邊$'b'$時圖會長這樣：

加入邊$′b′$，讓路徑$"abb"$會走到新節點$3$，這時$3$代表了$"abb"$和$"bb"$ (因為是從$2$走過來的，因此代表了$"ab"$和$"b"$再加一個$′b′$)：

$3$還差一個$"b"$就可以代表$"abb"$的所有後綴了
一樣的問題又來了，路徑$"b"$已經存在了，會連到$2$！
套用一樣的老方法，從$3$到$2$連一條綠色的邊：

額......好像出錯惹......

後綴自動機 (SAM) 圖文教學 (三)

請先參考後綴自動機 (SAM) 圖文教學 (二)

(Copyright：圖片轉載請註明來源網址，感謝～)

說明：
用兩個「$"$」框起來的東西是字串
用兩個「$'$」框起來的東西是字元 (在這裡等價於單純的英文字母)
「路徑$"abcd"$」代表字串$"abcd"$在圖上會走過的一條路徑
「字串集合」代表很多字串 (?)

$"abaab"$的圖要怎麼建呢？
我們可以照著上一篇的思路，一個字母一個字母慢慢加

依序加入邊$'a'$和邊$'b'$的過程和上一篇一模模一樣樣，若已經忘記了可以翻回去回顧一下呦～
依序加完邊$'a'$和邊$'b'$時圖會長這樣：

加入$'a'$，讓路徑$"aba"$會走到新節點$3$，這時$3$代表了$"aba"$和$"ba"$ (因為是從$2$走過來的，因此代表了$"ab"$和$"b"$再加一個$′a′$)：

後綴自動機 (SAM) 圖文教學 (二)

請先參考後綴自動機 (SAM) 圖文教學 (一)

(Copyright：圖片轉載請註明來源網址，感謝～)

說明：
用兩個「$"$」框起來的東西是字串
用兩個「$'$」框起來的東西是字元 (在這裡等價於單純的英文字母)
「路徑$"abcd"$」代表字串$"abcd"$在圖上會走過的一條路徑
「字串集合」代表很多字串 (?)

還記得這張圖嗎？這是$S="abcd"$時預處理出來的樹

信不信，我可以把這張圖從$11$個節點縮到只剩$5$個節點，並且沒有讓圖喪失任何功能！
想知道怎麼做嗎？答案在這裡：

雖然這樣圖就不是一棵樹了
不過，還是可以依照上一篇講的方式走
舉個例子，子字串$"abc"$、$"bc"$、$"c"$都會走到$3$ (每個節點下面的那些字串集合就是會走到這個點的字串集合)
可以發現

後綴自動機 (SAM) 圖文教學 (一)

(Copyright：圖片轉載請註明來源網址，感謝～)

說明：(這些是關於字串的基本用語，非常重要，請務必牢記)
「$\left|s\right|$」代表字串$s$的長度
「字串$s$的後綴」代表由$s$的最後幾個字母組成的字串，$s$有$\left|s\right|$個後綴
「字串$s$的子字串 (簡稱子串)」代表$s$中一段連續的字母組成的字串，$s$有$\frac{\left|s\right|(\left|s\right|+1)}{2}$個子字串 (不計較重複的話)


假如我給你一個字串$S$，然後問你很多次一個字串$A_{i}$是不是$S$的子字串 (全部由小寫字母組成)
我們能不能對$S$做個預處理，然後$O(\left|A_{i}\right|)$回答每個詢問呢？

我們先來看一種$O(\left|S\right|^{2})$的預處理
我們可以先將$S$的所有後綴建成一棵樹
假設$S="abcd"$，那麼樹就長成這個樣子：

其中$0$是根，每條邊都有代表的字母
這樣的話，假如我問你$"bc"$是不是子字串
那就從$0$依序嘗試沿著代表字母$b$、$c$的邊走
於是，我們會經過$0$、$5$、$6$，最後停在$6$
走完了，因此$"bc"$是$S$的子字串！

如果問你$bca$呢？
那就從$0$依序嘗試沿著代表字母$b$、$c$、$a$的邊走
於是，我們會經過$0$、$5$、$6$
可是$6$後面沒有代表字母是$a$的邊 (只有$d$)，所以走不下去惹QQ
因此$"bca"$不是$S$的子字串！

如果$S="abccba"$，那麼樹就長成這個樣子：

[HDU 2243]考研路茫茫——单词情结

要計算有多少字包含任一個字根，我們可以先算出有多少字不包含任一個字根，然後再用全部的情況去扣掉

可以考慮把這些字根做成一個$AC$自動機
這樣一來，長度$n$不包含任何一個字根的單字數量就是在這個$AC$自動機裡面走$n$步沒有碰到結束集合的方法數了

可以發現，這個$AC$自動機的大小不會超過$5*5+1=26$ (根也要算進去)，因此可以直接利用矩陣快速冪計算走$n$步到達各個位置的方法數
設這個$AC$自動機的轉移矩陣是$A$

因此長度$\leq L$且不包含任一個字根的單字數量就是走$0$步、走$1$步、走$2$步、走$3$步、...、走$L$步的情況全部加起來
對應到的矩陣就是$A^{0}+A^{1}+A^{2}+A^{3}+...+A^{L}=\sum_{i=0}^{L}A^{i}$

直接算會超時

說明：
$Sum(n)=\sum_{i=0}^{n}A^{i}$
$M$為$A$的大小

可以發現，如果我們已經算出$Sum(n)$
再把它乘上$A^{0}+A^{n+1}$，就變成$Sum(2n+1)$了！

更精確地說，我們可以得到以下遞迴式：
$if$ $n$是奇數，$Sum(n)=Sum(\frac{n-1}{2})*(A^{0}+A^{\frac{n+1}{2}})$
$if$ $n$是偶數，$Sum(n)=Sum(n-1)*A^{n}$

算出$A^{n}$利用快速冪可以做到$O(M^{3}\log n)$
矩陣加法$O(M^{2})$
遞迴不會超過$O(\log n)$層
因此算出$Sum(n)$的時間複雜度就是$O((M^{3}\log n+M^{2})\log n)$了

注意答案不是$Sum(L)$，是所有情況減掉$Sum(L)$
所有情況的數量 ($\sum_{i=0}^{L}26^{i}$) 一樣可以依照以上方法計算出來
另外，題目要求$\mod 2^{64}$，因此只要在$unsigned\ long\ long$之下進行這些運算並自由讓它$over\ flow$即可

時間複雜度：$O(M^{3}\log^{2}L)$

code:

[COCI 2014/2015 contest #5]DIVLJAK (優化後的code)

前情提要

後來有找到了一個judge可以幫我測這題，結果原本沒優化的code TLE惹QQ
因此嘗試做了些優化
於是code就變成了這副模樣

傳上去，眼看著測資一筆一筆的在跑......
「AC、AC、AC、......」
最後一筆跑完了全部AC！

結果它讓我看到了這個畫面Orz

不管傳幾次，回傳結果都顯示IE (Internet Explorer Internal Error) ......
希望judge能盡快修復這個bug啊，我想AC啦啦啦www

code:

[COCI 2014/2015 contest #5]DIVLJAK

這題目不好找，附上題目連結

簡單來說，就是給你一個固定的字串集合$A$和不固定的字串集合$B$
操作$1$就是把一個字串加入$B$
操作$2$就是給你$i$，問你$A_{i}$是$B$中幾個$B_{k}$的子字串

首先，我們可以把$A$建成一個$AC$自動機
這樣當$B$加入一個新字串之後，就可以馬上和$A$進行匹配，找出$A$中哪幾個是這個新字串的子字串了

當然，不能直接沿著失配函數$fail$ (也有人稱作$next$) 直接更新$A$中每個$A_{i}$的計數器
我們必須想到一個巧妙的方法，讓所有被匹配到的$A_{i}$和其沿著$fail$往上的所有$A_{k}$一起被加$1$ (因為$A_{i}$匹配意味著其沿著$fail$往上的所有$A_{k}$也會匹配成功)

可以發現，如果將所有的$u\rightarrow fail[u]$邊反向成$fail[u]\rightarrow u$，然後建圖
我們會得到一棵根為$0$的樹 (稱作$fail\ tree$好了)
而上述操作就是將一堆節點和它們的祖先們全部加$1$

利用線段樹維護樹壓平的序列，就可以實現$O(\log N)$查詢某個節點的值、$O(\log N)$一次將某個節點和其所有的祖先們加$1$了
(方法是查尋的時候直接查詢整棵子樹加$1$的總次數，修改只需單點修改即可)

可是這樣有可能會造成某個祖先被多次加$1$的情況
可以發現，當某個節點被加$1$第二次，那麼這個節點的祖先們也都會被這個多加的$1$影響到
那就把多加的扣回來就好啦

我們可以將這一堆要讓自己和祖先們都加$1$的節點依照$fail\ tree$的$dfs$順序排序
假設排序完的序列是$\{v_{1},v_{2},v_{3},...,v_{n}\}$
對於每個$1\leq i\leq n$，將所有$v_{i}$及其祖先們都加$1$
對於每個$2\leq i\leq n$，將所有$LCA(v_{i-1},v_{i})$ ($Lowest\ Common\ Ancestor$) 及其祖先們都減$1$
這樣就剛好讓每個被影響到的點都恰好加$1$了

($\left|A\right|$代表集合$A$裡面所有的字串長度總和)
在$B$中加入一個字串$s$的複雜度：$O(\left|s\right|\log\left|A\right|)$
查詢的時間複雜度：$O(\log\left|A\right|)$

p.s.這個code沒有特別優化，在自己的電腦實測是$8$秒 (如下圖)，而時限是$4$秒
2016/2/27 15:54更新：後來找到judge可以傳了，這份code不意外地獲得了TLE，優化後的code在這裡

時間複雜度：$O(Q\log\left|A\right|+\left|B_{final}\right|\log\left|A\right|)$

code:

[NPSC 2015]上司的薪水 (題目備份)

NPSC官方網站好像找不到題目，所以就拍下帶回來的題本放在這裡了
請參考～ ^_^

這裡、這裡、這裡和這裡分別提供了不同作法，選個喜歡的去實現吧～

第一頁

第二頁

第三頁

結束，趕快做做看吧～

[ZJ d229]IOI研習營模考2-4砝碼

用暴搜寫了一個會TLE的code (請看這裡)

然後就在自己的電腦上跑出所有答案

再另寫個程式把輸出整理成code的樣子

稍作修改......完成！

這code看起來真是優美(?)

p.s.求正解作法啊......我真的看不出甚麼規律QQ......

code:

[ZJ d229]IOI研習營模考2-4砝碼 (答案產生器)

不是題解的題解在這裡
這份暴搜code在我的電腦上跑了一小時......
然後......ㄎㄎ你知道的 ^_^

code:

[HOJ 136][IOI 2007]Training

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

換句話說，題目希望不產生偶環的前提下，總權重最大化
感覺會超多奇環相互交錯再一起耶......好複雜QQ

我們先來討論兩個奇環的情況
1. 不相交：合法情況，之後再深入討論
2. 相交於一點：合法情況，之後再深入討論
3. 重合於任何邊：形成偶環了，不合法！
(原來奇環也只有這樣嘛www)

那些會在樹上形成偶環的非樹邊可以直接刪除了

我們來嘗試構造一個樹形$DP$
首先，我們必須避免同一條邊被多個環同時使用
因此，狀態中必須包含哪些邊被用過了
由於每個點的度數不超過$10$
因此我們可以利用位元壓縮的技巧，用$DP[u][s]$代表以$u$為節點的子樹中，連到$u$的邊 (包含樹邊和非樹邊) 的子集合$s$ (用$bit\ mask$表示) 被用過了，總權重最多多少

於是，我們可以枚舉所有「樹上路徑」會通過$u$的邊$e$，然後用以下方式直接算出每個$DP[u][s]$：

圖片來源：http://www.ioinformatics.org/locations/ioi07/contest/solutions.pdf

其中除了以下這個 (稱作$subtree$) 需要遞迴計算之外，其他的都已經在先前遞迴到子樹時計算好了

可是這樣要計算$subtree$的時候還要想辦法把兩端都在$subtree$內的非樹邊分離出來
想一想複雜度好像很容易又爛掉了QQ

沒關係，不用遞迴了，我們先算好只加一個環的部分

然後依照$bit\ mask$中$1$的數量由小到大更新$DP[u]$ (這時候如果用到的邊沒有重複就可以直接相加來更新更大的$DP[u]$了)
為了節省時間，只更新「加一個環」(用掉兩條邊) 和「加一棵子樹」(用掉一條邊) 的情況，然後順著$DP[u]$的更新順序就可以把所有情況都考慮進去了

小提醒：請記得答案是所有邊的權重總和減掉算出來的$DP$

時間複雜度：$O(N^{2}+NM+2^{10}M)$ (預處理從$u$走到$v$要先走連到$u$的第幾條邊、預處理一條邊是$u$的第幾條邊、更新$DP$)

code:

[HOJ 136][IOI 2007]Training (題目備份)

HSNU Online Judge

• Index
• User
• Problem
• Status
• Contest
• Course
• Discuss_Ura

HOJ生病惹QQ，因此在此悼念昔日光彩

題目備份，請參考～

題解和code在這裡和這裡

敬告：目前HOJ主機也許進入瀕死狀態了，常常無預警跳電。請看到這則公告的人能注意備份自己的資料，感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 

Submit　　Ranklist

Problem : 136 - Training

Problem Statistics

Solved Member: 9　　Submission: 28　　User Tried: 9

Problem：

馬可(Mirko)和史拉可(Slavko)為了參加一年一度在克羅埃西亞(Coratia)舉行的雙人自行車馬拉松大賽正在加緊努力訓練。他們須要選擇一條路線(route)來訓練。

在他們的國家有 N 座城市與 M 條雙向道路(roads)。每一條道路連接兩個城市。但只有 N-1條道路是已被鋪築好的，其它的道路則是還沒被鋪築好的道路，幸好任兩座城市間都有一條用已鋪築好的道路路徑所連結。換句話說，這 N 座城市與 N-1 條已被鋪築好的條道路形成了一顆樹狀結構。

此外，每座城市最多可以是 10 條道路的端點。

訓練的路線可以從某一座城市開始，在經過數條道路後最後回到原來出發的城市。馬可和史拉可喜歡經過新的地點，所以他們訂了一項規則: 就是絕不經過相同的城市且絕不騎過相同的道路。訓練的路線可以在任何一座城市開始並且不須要經過每一座城市。

騎乘在後座是較輕鬆的，因為騎乘者可以因為前座騎乘者的關係而避開風。就因為如此，馬可和史拉可在每個城市會交換座位。為了確保他們能獲夠得相同的訓練量，他們想要選擇一條含有偶數條道路的路線。

馬可和史拉可的對手決定要封鎖某些尚未鋪築好的道路，讓他們無法找到一條滿足上述條件的路線。封鎖沒被鋪築好的道路須要付出一些代價(一個正整數) ，而已被鋪築好的道路是不可能被封鎖的。

Task：

寫一個程式，當給定城市與道路的描述後，找出封鎖道路使其無法滿足上述條件的訓練路徑之最小總代價。

Input：

輸入的第一行有兩個整數 N 與 M (2 ≤ N ≤ 1 000, N−1 ≤ M ≤ 5 000)，分別代表城市的數目與道路的數目。

接下來的 M 行每一行都有三個整數 A 、B 和 C (1 ≤ A ≤ N, 1 ≤ B ≤ N, 0 ≤ C ≤ 10 000)，用來表示一條道路。A 與 B 是不同的數字，表示直接由這條道路所連接的兩座城市。如果 C=0，表示該道路已被鋪築好了；否則該道路是尚未被鋪築過，而 C 代表封鎖此一條道路所需付出的代價。

每座城市最多可以是 10 條道路的端點，且兩座城市間絕對不會有一條以上的道路直接連接。

Output：

輸出一個整數，代表在上述問題描述中的最小總代價。

Sample Input：

SAMPLE A:
5 8
2 1 0
3 2 0
4 3 0
5 4 0
1 3 2
3 5 2
2 4 5
2 5 1

SAMPLE B:
9 14
1 2 0
1 3 0
2 3 14
2 6 15
3 4 0
3 5 0
3 6 12
3 7 13
4 6 10
5 6 0
5 7 0
5 8 0
6 9 11
8 9 0

Sample Output：

SAMPLE A:
5

SAMPLE B:
48

HINT：

第一個例子中道路與城市的陳列。已被鋪築好的道路是以粗體的邊表示。

對於馬可和史拉可來說，共有5個可能的路線。如果邊1-3、 3-5 和2-5 被封鎖， 則馬可和史拉可將會不能使用5個路線中的任何一個。封鎖這三個邊的代價是5。

只封鎖兩個邊，像是2-4 和 2-5，也是可以的，但這樣會導致較高的代價，6 。

Source：

IOI 2007

Problem Setter

Nekosyndrome

Testdata：

Test	Time	Memory	Score
0-1	500ms	65536kb
0-2	500ms	65536kb
1-1	500ms	65536kb	9
1-2	500ms	65536kb
2-1	500ms	65536kb	9
2-2	500ms	65536kb
3-1	500ms	65536kb	9
3-2	500ms	65536kb
4-1	500ms	65536kb	9
4-2	500ms	65536kb
5-1	500ms	65536kb	9
5-2	500ms	65536kb
6-1	500ms	65536kb	9
6-2	500ms	65536kb
7-1	500ms	65536kb	9
7-2	500ms	65536kb
8-1	500ms	65536kb	9
8-2	500ms	65536kb
8-3	500ms	65536kb
9-1	500ms	65536kb	9
9-2	500ms	65536kb
9-3	500ms	65536kb
10-1	500ms	65536kb	9
10-2	500ms	65536kb
10-3	500ms	65536kb
10-4	500ms	65536kb
11-1	500ms	65536kb	10
11-2	500ms	65536kb
11-3	500ms	65536kb
11-4	500ms	65536kb

HSNU Online Judge System
推薦瀏覽環境: Firefox 4
頁面讀取時間: 0.2652 秒，使用記憶體: 2.87MB 。

[SPOJ SUBLEX]SUBLEX - Lexicographical Substring Search

這題目不好找，附上題目連結

這裡提供了另外一個做法，選個喜歡的去實現吧～

這題問你$500$次去重後字典序第$k$小的子字串

可以發現，後綴自動機已經幫你將子字串們自動去重了！
而且更棒的是，把後綴自動機當作樹遍歷一次，每一個子字串都會被遇到恰好一次！

當然，這題不能直接遍歷找第$k$個節點
有一個很棒的優化方法就是，當我們發現一棵子樹，它的大小太小以致遍歷完這棵子樹後計數器仍$\leq k$，那麼我們可以直接將計數器的值加上這棵子樹的大小 (或將$k$減掉這棵子樹的大小)，直接考慮下一棵子樹

因此，我們只需要先預處理後綴自動機的每個節點代表的子樹大小即可

時間複雜度：$O(N)$ (不過常數非常大，就算各種優化也不見起色，時間是這個寫法的$6$倍Orz)

code:

[SPOJ SUBLEX]SUBLEX - Lexicographical Substring Search

這題目不好找，附上題目連結

這裡提供了另外一個做法，選個喜歡的去實現吧～

這題問你$500$次去重後字典序第$k$小的子字串

可以發現，後綴陣列衍生的$height$陣列已經幫你依照字典序排好每個後綴了
現在的問題就是要怎麼好好的利用這個$height$陣列來不重複地計算子字串

$height[i]$代表字典序第$i-1$個後綴和第$i$個後綴前$height[i]$個字母是完全相同的
因此我們可以把這$height[i]$個子字串算到第$i-1$個後綴
屬於第$i$個後綴的子字串就從$height[i]+1$開始算起

這樣我們就能統計前$i$個後綴包含多少子字串了！記為$SUM[i]$

當要求第$k$大子字串時，就對$SUM$進行二分搜，找出第一個$SUM[i]\geq k$的，就是代表第$k$大子字串屬於第$i$個後綴
$SUM[i]-k$代表這個子字串的結尾和主串結尾的距離
答案就是$S_{SA[i]\sim SUM[i]-k}$ ($SA[i]$代表後綴陣列第$i$項)

時間複雜度：$O(N\log N)$ (這裡提供了$O(N)$的解法)

code:

[HOJ 136][IOI 2007]Training (純code不含題解)

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～
題解在這裡

code:

[POI 12 Stage 2]Template

這裡提供了另外一個做法，選個喜歡的去實現吧～

可以發現，能用來當模板的字串一定只能同時是主串的前綴和後綴
回顧$KMP$中失配函數$fail$ (有人稱作$next$) 的定義：(以下字串中的編號皆由$0$開始)
字串$S$的$fail[i]$代表$S$的最長前綴長度，使得這個前綴和$S_{0\sim i-1}$的後綴 (結尾是$i-1$的子串) 完全相符

於是，可以當作答案的前綴的長度就只能是$N$、$fail[N]$、$fail[fail[N]]$、......了 ($N$為主串長度)
把這些候選人依序存起來，$f_{0}=N$、$f_{1}=fail[N]$、$f_{2}=fail[fail[N]]$、......、$f_{n}=0$

於是，我們可以從$f_{n-1}$開始枚舉候選人 ($f_{n}=0$代表空串，是不合法的)，看看和$S_{0\sim f_{i}-1}$匹配的點中，相鄰點間的最大距離有沒有超過$f_{i}$，沒有的話答案就是$f_{i}$

注意，和這個作法不一樣的是，這些點代表的是字串尾端的位置 (也就是代表以這個點為結尾的子串)，而不是字串開頭的位置

與其找出所有和$S_{0\sim f_{i}-1}$匹配的點，不如改成只保留和$S_{0\sim f_{i}-1}$匹配的點

做法是：
先將所有$fail$的邊反向建圖，我們就得到了一棵根為$0$的樹
可以發現，對於任何一個節點$u$，和以$u$為根的子樹中任何一個節點$v$，$S_{v-u\sim v-1}$和$S_{0\sim u-1}$匹配

當枚舉到$f_{i}$這個候選人，就將$f_{i+1}$所有不包含$f_{i}$的子樹中涵蓋的點全部刪除 (因為這些點和$S_{0\sim f_{i+1}}$匹配，但不和$S_{0\sim f_{i}}$匹配)
這樣每一個點都只會被刪掉一次，沒有重複也沒有遺漏 (除了$N$這個最後的點)

利用雙向鏈表可以實現$O(1)$刪點並維護相鄰點間的最大距離

時間複雜度：$O(N)$

code:

[POI 12 Stage 2]Template

這裡提供了另外一個做法，選個喜歡的去實現吧～

可以發現，能用來當模板的字串一定只能是主串的某個前綴

於是，我們可以枚舉前綴，然後看看這個前綴和字串中的哪些地方吻合
如果這些吻合的位置相鄰間的最大距離不超過這個前綴的長度，答案就是這個前綴的長度了

要怎麼得到這個前綴和字串中的哪些地方吻合呢？
就是$Z\ Value\geq$這個前綴長度的位置啦

$O(N)$將$Z\ Value$求出後，利用基數排序$O(N)$將它們由小到大排好
然後由短到長枚舉前綴，將$Z\ Value$太小的點刪掉
然後看看剩餘的點，相鄰間的最大距離是不是不超過這個前綴的長度

用雙向鏈表可以實現$O(1)$刪點並維護相鄰點間的最大距離

你問我為甚麼不需要考慮這個前綴是不是也是主串的後綴 (才能剛好覆蓋完整串)？
如果不是的話，鏈表中$N+1$這個點和前一個點的距離就爆掉啦～ ($>$目前前綴長度)

時間複雜度：$O(N)$

code:

[HOJ 300][Codechef]Party Invitation (題目備份)

File failed to load: file:///C:/Users/user/Desktop/Dropbox/HSNU%20Online%20Judge/300_files/extensions/MathMenu.js

HSNU Online Judge

• Index
• User
• Problem
• Status
• Contest
• Course
• Discuss_Ura

HOJ生病惹QQ，因此在此悼念昔日光彩

題目備份，請參考～

題解在這裡

敬告：目前HOJ主機也許進入瀕死狀態了，常常無預警跳電。請看到這則公告的人能注意備份自己的資料，感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 

Submit　　Ranklist

Problem : 300 - Party Invitation

Problem Statistics

Solved Member: 5　　Submission: 12　　User Tried: 5

Problem：

瀚瀚有 n 位碰友，分別以 1,2,3,...,n 來編號。他今天想要邀請一些人來家裡一起7122。

然而，對於每一個碰友 i，會有一個特定討厭的碰友 a_i，代表瀚瀚不能同時邀請 i 與 a_i 兩個人，否則他們會打架，瀚瀚就7122不出來了。

請你找出瀚瀚有幾種邀請碰友的方法。

Input：

輸入資料的第一行有一個整數 t，代表測資的筆數。

每一筆測試資料的第一行有一個整數 n，代表瀚瀚的好友數量。
接下來有 n 個數字 a₁, a₂, ..., a_n，分別代表每個人討厭的人的編號。

限制：
t ≤ 10
2 ≤ n ≤ 100000
i ≠ a_i (沒有人會討厭自己)

其中 30% 的測試資料滿足： n ≤ 20
其中 70% 的測試資料滿足： n ≤ 2000

Output：

對於每一筆測試資料，請輸出一行，包含一個數字，代表瀚瀚有幾種邀請別人來7122的方法。
由於方法數可能很大，請輸出除以 1000000007 的餘數。

Sample Input：

3
4
2 3 4 1
3
2 1 2
2
2 1

Sample Output：

7
5
3

HINT：

我們用 {...} 來表示邀請到哪些人。

第一筆測試資料，瀚瀚可以邀請的可能為：{}, {1}, {2}, {3}, {4}, {1,3}, {2,4}，共七種

第二筆測試資料，瀚瀚可以邀請的可能為：{}, {1}, {2}, {3}, {1,3}

第三筆測試資料，瀚瀚可以邀請的可能為：{}, {1}, {2}

Source：

Codechef

Problem Setter

Nekosyndrome

Testdata：

Test	Time	Memory	Score
0	2000ms	131072kb
1	2000ms	131072kb	10
2	2000ms	131072kb	10
3	2000ms	131072kb	10
4	2000ms	131072kb	10
5	2000ms	131072kb	10
6	2000ms	131072kb	10
7	2000ms	131072kb	10
8	2000ms	131072kb	10
9	2000ms	131072kb	10
10	2000ms	131072kb	10

HSNU Online Judge System
推薦瀏覽環境: Firefox 4
頁面讀取時間: 0.2652 秒，使用記憶體: 2.87MB 。

[HOJ 299]比特集合 (題目備份)

HSNU Online Judge

• Index
• User
• Problem
• Status
• Contest
• Course
• Discuss_Ura

HOJ生病惹QQ，因此在此悼念昔日光彩

題目備份，請參考～

題解在這裡

敬告：目前HOJ主機也許進入瀕死狀態了，常常無預警跳電。請看到這則公告的人能注意備份自己的資料，感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 

Submit　　Ranklist

Problem : 299 - 比特集合

Problem Statistics

Solved Member: 5　　Submission: 24　　User Tried: 7

Problem：

瀚瀚有一個箱子，剛開始箱子裡面是空的。接著瀚瀚要對箱子做一些怪怪的操作：

1.Insert a：箱子裡放入一隻 a 歲的小雞
2.Delete b：將箱子裡面所有 b 歲的小雞都拿出來
3.Add c：時間過了 c 年，箱子裡的小雞都長大了 c 歲(歲數+c)
4.Q-bit d：瀚瀚想知道目前箱子裡的小雞中有幾隻歲數的二進位第 d 位數是 1

你可以假設小雞都長生不死，只要瀚瀚不把他拿出來，他們就會永遠在箱子裡面


我們可以將一隻小雞的歲數，假如 10 歲寫成二進位變成： 1010

這時候從右邊(最低位)數過來就分別為第 0 位、第 1 位、第 2 位......

對於二進位數字 1010 來說，第 0 位為 0，第 1 位為 1，第 2 位為 0......

Input：

第一行有一個數字 n，代表有幾組操作

接下來 n 行，代表瀚瀚依序做的操作。每行最前面有一個字串，有可能為「Insert」、「Delete」、「Add」、「Q-bit」之一，後面接著一個數字，意義如上面敘述。
請注意操作是有先後順序的


限制：
1 ≤ n ≤ 500000
對於 Insert、Delete 操作， 0 ≤ a,b ≤ 1000000000
對於 Add 操作， 0 ≤ c ≤ 1000
對於 Q-bit 操作， 0 ≤ d ≤ 15

其中 20% 的測試資料滿足： n ≤ 200
其中 30% 的測試資料滿足： n ≤ 2000
其中 60% 的測試資料滿足： n ≤ 10000

Output：

對於每一個 Q-bit 詢問，請輸出一行，包含一個數字，代表箱子裡面有幾隻小雞符合詢問。

Sample Input：

8
Insert 1
Q-bit 0
Add 1
Q-bit 0
Q-bit 1
Delete 2
Insert 1
Q-bit 1

Sample Output：

1
0
1
0

Problem Setter

Nekosyndrome

Testdata：

Test	Time	Memory	Score
0	2000ms	524288kb
1-1	2000ms	524288kb	10
1-2	2000ms	524288kb
1-3	2000ms	524288kb
2-1	2000ms	524288kb	10
2-2	2000ms	524288kb
2-3	2000ms	524288kb
3-1	2000ms	524288kb	10
3-2	2000ms	524288kb
3-3	2000ms	524288kb
4-1	2000ms	524288kb	10
4-2	2000ms	524288kb
4-3	2000ms	524288kb
5-1	2000ms	524288kb	10
5-2	2000ms	524288kb
5-3	2000ms	524288kb
6-1	2000ms	524288kb	10
6-2	2000ms	524288kb
6-3	2000ms	524288kb
7-1	3000ms	524288kb	10
7-2	3000ms	524288kb
7-3	3000ms	524288kb
8-1	3000ms	524288kb	10
8-2	3000ms	524288kb
8-3	3000ms	524288kb
9-1	3000ms	524288kb	10
9-2	3000ms	524288kb
9-3	3000ms	524288kb
10-1	3000ms	524288kb	10
10-2	3000ms	524288kb
10-3	3000ms	524288kb

HSNU Online Judge System
推薦瀏覽環境: Firefox 4
頁面讀取時間: 0.2652 秒，使用記憶體: 2.87MB 。

[HOJ 297][NOIP 2010 提高組]引水入城 (題目備份)

HSNU Online Judge

• Index
• User
• Problem
• Status
• Contest
• Course
• Discuss_Ura

HOJ生病惹QQ，因此在此悼念昔日光彩

題目備份，請參考～

題解在這裡

敬告：目前HOJ主機也許進入瀕死狀態了，常常無預警跳電。請看到這則公告的人能注意備份自己的資料，感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 

Submit　　Ranklist

Problem : 297 - 引水入城

Problem Statistics

Solved Member: 14　　Submission: 148　　User Tried: 14

Problem：

在一個遙遠的國度，一側是風景秀美的湖泊，另一側則是漫無邊際的沙漠。該國的行政區劃十分特殊，剛好構成一個N 行M 列的矩形，如上圖所示，其中每個格子都代表一座城市，每座城市都有一個海拔高度。

為了使居民們都盡可能飲用到清澈的湖水，現在要在某些城市建造水利設施。水利設施有兩種，分別為蓄水廠和輸水站。蓄水廠的功能是利用水泵將湖泊中的水抽取到所在城市的蓄水池中。因此，只有與湖泊毗鄰的第1行的城市可以建造蓄水廠。而輸水站的功能則是通過輸水管線利用高度落差，將湖水從高處向低處輸送。故一座城市能建造輸水站的前提，是存在比它海拔更高且擁有公共邊的相鄰城市，已經建有水利設施。

由於第N 行的城市靠近沙漠，是該國的干旱區，所以要求其中的每座城市都建有水利設施。

簡單的說你要在第一行選最少個城市建立蓄水廠，使得第N行的每個城市都能獲得水資源，當水資源能從城市A流往城市B，僅當城市A與城市B相鄰(上下左右)，且城市A的海拔高度大於城市B的海拔高度。

那麼，這個要求能否滿足呢？如果能，請計算最少建造幾個蓄水廠；如果不能，求乾旱區中不可能建有水利設施的城市數目。

Input：

輸入的第一行是兩個正整數N 和M，表示矩形的規模。

接下來N 行，每行M 個正整數，依次代表每座城市的海拔高度。

測試資料編號	能否滿足要求	N	M
1	不能	≤ 10	≤ 10
2	不能	≤ 100	≤ 100
3	不能	≤ 500	≤ 500
4	能	= 1	≤ 10
5	能	≤ 10	≤ 10
6	能	≤ 100	≤ 20
7	能	≤ 100	≤ 50
8	能	≤ 100	≤ 100
9	能	≤ 200	≤ 200
10	能	≤ 500	≤ 500

Output：

輸出有兩行。

如果能滿足要求，輸出的第一行是整數1，第二行是一個整數，代表最少建造幾個蓄水廠。

如果不能滿足要求，輸出的第一行是整數0，第二行是一個整數，代表有幾座乾旱區中的城市不可能建有水利設施。

Sample Input：

Sample #1:
2 5
9 1 5 4 3
8 7 6 1 2

Sample #2:
3 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2

Sample Output：

Sample #1:
1
1

Sample #2:
1
3

HINT：

Sample #1:
只需要在海拔為9 的那座城市中建造蓄水廠，即可滿足要求。

Sample #2:

上圖中，在3 個粗線框出的城市中建造蓄水廠，可以滿足要求。以這3 個蓄水廠為源頭。
在乾旱區中建造的輸水站分別用3 種顏色標出。當然，建造方法可能不唯一。

Source：

NOIP 2010 提高組

Problem Setter

hanhan0912

Testdata：

Test	Time	Memory	Score
0-1	1000ms	131072kb
0-2	1000ms	131072kb
1	1000ms	131072kb	10
2	1000ms	131072kb	10
3	1500ms	131072kb	10
4	1000ms	131072kb	10
5	1000ms	131072kb	10
6	1000ms	131072kb	10
7	1000ms	131072kb	10
8	1000ms	131072kb	10
9	1000ms	131072kb	10
10	1000ms	131072kb	10

HSNU Online Judge System
推薦瀏覽環境: Firefox 4
頁面讀取時間: 0.2808 秒，使用記憶體: 2.87MB 。