[POJ 3415]Common Substrings (題解二)

請先參考題解一

上一篇有提到我們讓$B$在$A$的後綴自動機裡面進行轉移時，每走一步就要往失配邊回溯直到$max\_len<K$為止
那我們能不能把這個過程加速呢？

我們可以套用$O(\log N)$尋找$LCA$ ($Lowest\ Common\ Ancestor$) 的思想
考慮使用倍增的方法，我們對於每個點預先算好往失配邊走$1$步、走$2$步、走$4$步、走$8$步......會答案加多少
然後就可以盡量跨大步，同時維持$max\_len>=K$
這樣最多跨$\log\left|A\right|$步，形同在$O(\log\left|A\right|)$的時間複雜度內走完失配邊！
注意，還需要做一些加加減減的小細節才是要求的答案

預處理可以做到$O(\left|A\right|\log\left|A\right|)$
我的作法是先將所有失配邊反向形成的樹建出來，然後用$dfs$的方式以類似$LCA$的預處理方式算出需要的資料

這樣就做完了嗎？
好像還沒耶

注意到這裡的字元集大小是$52$ (題目沒說會全部小寫)！
這樣最多會需要$2*10^{5}*52$的時間和空間來初始化並建立後綴自動機
對這題的時限來說實在太大了

因此必須使用更省時間空間的方案
我自己實作了$list$

時間複雜度：$O(\left|A\right|\log\left|A\right|+\left|B\right|\log\left|A\right|)$

code:

[POJ 3415]Common Substrings (題解一)

從這題，我們已經知道在枚舉$B$的前綴$B_{p}$時，如何求出$B_{p}$最長的後綴，使得這個後綴同時也是$A$的子字串
方法就是讓$B$在$A$的後綴自動機裡面轉移，同時維護目前答案的長度 (稱作$len$)

那要怎麼求出節點$u$代表的最長字串在$A$裡面出現幾個地方呢？
就是「代表$A$的前綴的節點集合」中，有幾個可以直接或間接透過失配邊走到$u$囉～

這些資訊可以利用$queue$先進行預處理，我們得到一個儲存答案的陣列$count$

於是在$B$進行轉移時，我們每走一步，就將目前找到的最長屬於$A$子字串的後綴$S$，沿著失配邊枚舉$S$的後綴集合，然後把它們在$A$中出現的次數全部加進答案裡面
實作上可以將沿著失配邊走的路徑上的每個節點的$count$乘上一個權重，再加起來
權重就是這個節點代表的字串集合中有幾個長度$\geq K$且$\leq \left|S\right|$，透過$len$和每個節點的$max\_len$資訊可以$O(1)$計算出來

這篇先講到這裡，並給出實現目前算法的code
下一篇說明怎麼讓時間複雜度再降低

時間複雜度：$O(\left|A\right|+\left|A\right|\left|B\right|)$

code:

[POJ 1182]食物链

可以看出，我們永遠不會知道特定的某隻動物是$A$、$B$或$C$

為了方便說明，令$S_{i}$為第$i$隻動物

因此，我們只能對於$S_{i}$做出$S_{i}=A$、$S_{i}=B$或者$S_{i}=C$假設
當某個假設可以推到另一個假設，我們就將這兩個假設連邊，剛好在這題，如果$A$可以推到$B$，那麼$B$也可以推到$A$，因此可以直接連無向邊
再仔細想想，可以知道如果$X$吃$X$的情況出現，若且唯若可以從$S_{i}=A$的假設推到$S_{i}\neq A$的假設，也就是這兩個假設在同一個連通塊裡面

我們只要判斷連通性就好了，可以用並查集來維護！

如果上面的題解仔細看了好幾遍還是沒有頭緒，請參考code

時間複雜度：$O(K\alpha(N))$ (不過code裡面的並查集是$O(\log N)$)

p.s. POJ的測資結尾竟然還有其他數字！所以如果你是做重複輸入的，會莫名地得到WA，需要在code裡面加上那個break才能通過Orz

code:

[POJ 2431]Expedition

若現在卡車能跑到某個距離，那麼能加油的地方只能在這個距離裡面
要在哪裡加油呢？
在哪裡加油都沒差，唯一的差別就是能讓你多跑多少公里
就選一個加最多油的加油站加油吧
然後繼續跑，跑不到終點的話再繼續選一個距離內加最多油的加油站

可以用priority_queue維護加最多油的加油站

如果最後沒有加油站可以選惹，輸出-1

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

code:

[POJ 3017]Cut the Sequence

說明：
$S_{i}$為序列的第$i$個元素
$\max(a,b)=\max_{i=a}^{b}S_{i}$
$k_{i}$為滿足$\sum_{j=k}^{i}S_{j}\leq M$最小的$k$

我們可以構造一個$DP$，$DP[i]$代表把前$i$個元素組成了序列切一切，各段最大值總和的最小值
初始條件：$DP[0]=0$

於是，我們有了$DP[i]=\min(DP[k-1]+\max(k,i))$，其中$k_{i}\leq k\leq i$

如果有做過單調隊列的題目，相信很容易在將$i$從小到大枚舉的時候，均攤$O(1)$維護所有的$max(k,i)$，以及$k_{i}$

直接依照單調隊列裡面的元素去枚舉是$O(N^{2})$，也就是網路上宣稱不用set或平衡樹直接單調隊列解決的做法

例如這篇

我構了測資讓它跑了一分鐘還沒出來，所以請別偷懶，繼續看怎麼優化

這個測資是：

100000 9223372036854775807

100000 99999 99998 99997 ...... 5 4 3 2 1

怎麼優化呢？

可以發現，當$i$遞增時，$DP[i]$是非遞減的

因此，如果現在$i$跑到$9$，並算出$k_{9}=3$，單調隊列是$\{5,6,9\}$

那麼$DP[i]$的候選人就是$DP[2]+S_{5}$、$DP[5]+S_{6}$、$DP[6]+S_{9}$

除了第一個候選人，其他的如果用multiset存起來，在單調隊列執行pop_front、pop_back、push_back操作的時候就可以順便$O(\log N)$維護這些候選人了
為了確認你的理解，這些候選人的數量永遠是「單調隊列的大小-1」

因此，要算$DP[i]$時，只要取multiset裡面的最小值，和區間取$[k_{i},i]$時的花費 (也就是上述例子的第一個候選人)，這兩個的最小值就好了

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

code:

[POJ 3709]K-Anonymous Sequence

說明：
$S_{i}$為序列中第$i$個元素
$SUM_{i}$為$\sum_{k=1}^{i}S_{k}$

我們先來設計一個的$DP$，$DP[i]$代表$S_{1}\sim S_{i}$這個序列要符合$k$-anonymous，cost最小多少

起始狀態：
$DP[0]=0$
$DP[i]=INF$ ($1\leq i<K$)

然後，我們有了以下遞迴式：
$DP[i]=\min(DP[k]+(SUM_{i}-SUM_{k})-S_{k+1}*(i-k))$，$0\leq k\leq i-K$ (注意$k$的大小寫)

整理一下就變成這樣：
$DP[i]=\min((-S_{k+1})*i+(DP[k]-SUM_{k}+S_{k+1}*k)+(SUM_{i}))$

就會變成一條條斜率$(-S_{k+1})$，截距$(DP[k]-SUM_{k}+S_{k+1}*k)$的直線中找$x=i$時的最小值

如果$k$的範圍是$0\sim i-1$的話，相信大家知道怎麼用凸包優化的單調隊列來解

但是現在我們限制$k\leq i-K$
怎麼辦呢？

當要計算$DP_{i}$的時候，我們只需維護好範圍$0\sim i-K$的凸包就好了

給大家一個圖片想像，這個凸包會長得類似圖片中的紅線：

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

code:

[UVa 1613][POJ 3969]K-Graph Oddity

假設某個點的度數$<K$，那麼我們就乾脆先把其他點著色，再來決定這點要著甚麼顏色就好啦

可以發現，本題條件限制$K$和$N$都要是奇數，因此一定有一點的度數$<K$ (想一想，為甚麼XD)
找到這點後，把它從圖上移除，為剩餘的圖著色，這時相鄰的點的度數一定都$<K$，再把它移除，為剩餘的圖著色，......

這樣下去，會剩下一個點，把它塗成顏色1，然後慢慢把刪除的點加回去並著色，這樣整張圖就著色完成了！

把點移除真麻煩？
其實不用真的移除啦

我們只需要從某個度數$<K$的點開始dfs，當走到$u$時，先把$u$的子節點著色 (往$u$的子節點dfs)，再把$u$著色

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

p.s.重度優化後在POJ上還是TLE，但是在UVa上獲得第一名惹Orz
p.s.後來在網路上發現網友的解法，還真的可以在POJ上AC，他是用bfs的逆順序著色 (吧?)，是說......POJ有這麼恨遞迴嗎!@#%^&*......

code:

[POJ 1180][IOI 2002]Batch Scheduling

這裡先給出$O(N^{2})$的code：

#include<cstdio>
#include<cassert>
using namespace std;
const int INF=2147483647;
void getmin(int &a,const int b){if(b<a)a=b;}
int N,S,T[10001],C[10001],TSUM[10001],CSUM[10001],DP[10002];
int main()
{
    freopen("in.txt","r",stdin);
    while(scanf("%d",&N)==1)
    {
        scanf("%d",&S);
        for(int i=1;i<=N;i++)scanf("%d%d",&T[i],&C[i]),TSUM[i]=TSUM[i-1]+T[i],CSUM[i]=CSUM[i-1]+C[i];
        DP[N+1]=0;
        for(int i=N;i>=1;i--)
        {
            DP[i]=INF;
            for(int j=i;j<=N;j++)getmin(DP[i],(S+TSUM[j]-TSUM[i-1])*(CSUM[N]-CSUM[i-1])+DP[j+1]);
        }
        printf("%d\n",DP[1]);
    }
    return 0;
}

其中$(S+TSUM[j]-TSUM[i-1])*(CSUM[N]-CSUM[i-1])$可以拆解成$(S+TSUM[j]-TSUM[i-1])*(CSUM[j]-CSUM[i-1])$和$(S+TSUM[j]-TSUM[i-1])*(CSUM[N]-CSUM[j])$
前者代表批次執行第$i$項任務到第$j$項任務所花的成本，後者代表批次執行完第$i$項任務到第$j$項任務後害第$j+1$項以後的任務增加的成本

這樣對$DP$的定義清楚了吧^_^

可以發現，我們會枚舉$j$求$(S+TSUM[j]-TSUM[i-1])*(CSUM[N]-CSUM[i-1])+DP[j+1]$的最小值，展開後把項依照性質分離後，會變成以下形式：
1. 只受$i$影響，可以當常數：$S*CSUM[N]-S*CSUM[i-1]-TSUM[i-1]*CSUM[N]+TSUM[i-1]*CSUM[i-1]$
2. 只受$j$影響：$TSUM[j]*CSUM[N]+DP[j+1]$
3. 同時受$i$和$j$影響：$-TSUM[j]*CSUM[i-1]$

如果學過凸包優化，應該會知道要把$-TSUM[j]$當作$a$，$TSUM[j]*CSUM[N]+DP[j+1]$當作$b$，求$x=CSUM[i-1]$時，$ax+b$的最小值($ax+b$會被當作一條條的直線)

關於凸包優化這裡不再細講，網路上可以查到很多資料XD

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

code:

[POJ 1741]Tree

先備知識：樹重心

使用樹分治的思想，假設我們把$u$當作根結點，那麼所有路徑就分成了「經過$u$」和「不經過$u$」兩大類，其中「不經過$u$」的路徑可以透過子樹的遞迴來計算，因此我們只需考慮經過$u$的路徑

經過$u$的路徑又分成兩類：以$u$為端點、不以$u$為端點

以$u$為端點的算法：
我們可以先取得從$u$開始，所有長度$\leq K$的路徑，答案就是這種路徑的數目

不以$u$為端點的算法：($n$為目前考慮的子樹上節點的數量，因此我們有$\sum n=N$)
把上述的路徑排序一下，枚舉路徑$p$，二分搜找出有幾條路徑的長度$\leq K-p.length()$，就可以達到$O(n\log n)$的時間複雜度了，注意還要再把都在同一顆子樹的的「路徑對」扣掉，也是一樣的算法
不過......這樣雖然時間複雜度是正確的，不過在POJ上還是會TLE......
可以發現，枚舉的$p$長度會遞增，因此$K-p.length()$會遞減，具有單調性，就不用二分搜了，可以使用另一個遞減的指針達到$O(n)$的複雜度(不過總複雜度還是$O(n\log n)$，因為還有排序)

為了避免複雜度退化，每次根要選樹重心

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

code: