作法：
我們只要知道一個人最好是可以到多少，還有最差可以到多少，就可以分別對兩個答案二分搜了。首先看一個人最好可以到多少，最佳情形當然是他剛好一直遇到比他弱的，所以一直贏，直到沒有人比弱為止開始一直輸。假設現在比他弱的人有$x$個，那麼不難得出下一輪比他弱的只會剩$\left \lfloor \frac{x-1}{2} \right \rfloor $個，因此只要一直除下去直到這數字變$0$為止，就知道他可以連續贏幾場了。並且一個人的最差狀況則是一直輸，最後再一直贏，也可以用類似的方法求出會先輸幾場才開始一直贏。
code :
2015年7月25日 星期六
[HOJ 272] 出納員的僱用
作法：
考慮二分搜答案，那麼問題就會變成是否恰好僱用$X$個人並滿足條件。記我們在每個小時僱用的人為$x_1,...,x_{24}$，將他循環延長$7$個，也就是變成$x_1,...,x_{31}$，其中$x_i=x_{i+24}$，那麼我們就可以列出一些條件：首先當然是僱用的人數不能超過給的人數，也就是$x_i\leq num[i]$，其中$num$代表這個時間可以請的人數。還有剛才提到的$x_i=x_{i+24}$，並且因為能夠在某個時間$i$工作的人們開始工作的時間可能會是$i-7,...,i$，也就是這些時間請的人數必須$\geq$需要的人數，因此可以列出$x_{i-7}+...+x_i\geq need[i]$，其中$need$陣列一樣以 $24$ 一循環。不難將這些條件改為前綴和的條件，也就是令$S_i=x_1+...+x_i$，那麼$x_i=x_{i+24}$的條件可以改寫為$S_{i+24}=S_i+X$，其中$X$是前面我們二分搜的值（也就是$x_1+...+x_{24}=S_{24}$），剩下的條件則是顯然的。這樣就可以用差分約束解他了，把圖建出來用 Bellman-Ford 判他有沒有負圈就可以了。
code :
考慮二分搜答案，那麼問題就會變成是否恰好僱用$X$個人並滿足條件。記我們在每個小時僱用的人為$x_1,...,x_{24}$，將他循環延長$7$個，也就是變成$x_1,...,x_{31}$，其中$x_i=x_{i+24}$，那麼我們就可以列出一些條件：首先當然是僱用的人數不能超過給的人數，也就是$x_i\leq num[i]$，其中$num$代表這個時間可以請的人數。還有剛才提到的$x_i=x_{i+24}$，並且因為能夠在某個時間$i$工作的人們開始工作的時間可能會是$i-7,...,i$，也就是這些時間請的人數必須$\geq$需要的人數，因此可以列出$x_{i-7}+...+x_i\geq need[i]$，其中$need$陣列一樣以 $24$ 一循環。不難將這些條件改為前綴和的條件，也就是令$S_i=x_1+...+x_i$，那麼$x_i=x_{i+24}$的條件可以改寫為$S_{i+24}=S_i+X$，其中$X$是前面我們二分搜的值（也就是$x_1+...+x_{24}=S_{24}$），剩下的條件則是顯然的。這樣就可以用差分約束解他了，把圖建出來用 Bellman-Ford 判他有沒有負圈就可以了。
code :
[HOJ 247][IOI 2008] Islands
作法：
首先當然是把所有連通塊分開看，這題簡單來說就是要找水母圖上的最長路（無向的），我們先找出這張水母圖的圈在哪裡，找法從隨便一個點開始沿著他唯一連出去的邊一直走，走到重複的點為止，就找到一個圈了。水母圖上的最長路分兩種，一種是沒有經過圈上的邊的，一種則是有的。對於前者，我們可以枚舉水母圈上的點，考慮這個點連往非水母圈的邊的那些點們，會形成一棵子樹，對這個子樹求最長路徑就可以了。至於經過水母圈上的邊的路徑，因為顯然如果我們已經決定好路徑和水母圈的交集的兩端點的話，剩下就取這個端點往他的子樹方向走過去的最長路就可以了，因此在回傳子樹內部的最長路時要順便回傳子樹根往下走的最長路。於是我們現在有圈上每個點往樹方向走下去的最長路了（以下稱為$val$值），還有圈上每條邊的長度，要求的是「兩點之間的距離$+$兩點的$val$值」的最大值。考慮把圈壓成序列，也就是如果原本圈上的點為$A_1,...,A_k$，考慮序列$A_1,...,A_k,A_{k+1},...,A_{2k-1}$，其中$A_{i+k}=A_i$，並且相鄰點的距離就和原本圈上連接這兩點的距離相等，記$dis[i]$代表$A_1$往右走到$A_i$的距離，和$val[i]$代表$A_i$的 val 值（最長路長），那麼我們要求的東西就是：$(i,j)$滿足$dis[i]-dis[j]+val[i]+val[j]$最大，其中$i-j<k$。因此當固定$i$的時候，我們需要的東西就會是$max\{ val[j]-dis[j] \}$，其中$j=i-k+1,...,i-1$。於是這就可以用 deque 優化在線性的時間內求出來了。
最後我傳上去 MLE 了，載測資來看發現那兩筆是DFS會到$10^6$層左右的，後來我把DFS改成自己用 stack 作才過的，感覺 IOI 沒必要這樣卡記憶體阿OAO......
code :
首先當然是把所有連通塊分開看，這題簡單來說就是要找水母圖上的最長路（無向的），我們先找出這張水母圖的圈在哪裡，找法從隨便一個點開始沿著他唯一連出去的邊一直走，走到重複的點為止，就找到一個圈了。水母圖上的最長路分兩種，一種是沒有經過圈上的邊的，一種則是有的。對於前者，我們可以枚舉水母圈上的點，考慮這個點連往非水母圈的邊的那些點們，會形成一棵子樹，對這個子樹求最長路徑就可以了。至於經過水母圈上的邊的路徑，因為顯然如果我們已經決定好路徑和水母圈的交集的兩端點的話，剩下就取這個端點往他的子樹方向走過去的最長路就可以了，因此在回傳子樹內部的最長路時要順便回傳子樹根往下走的最長路。於是我們現在有圈上每個點往樹方向走下去的最長路了（以下稱為$val$值），還有圈上每條邊的長度，要求的是「兩點之間的距離$+$兩點的$val$值」的最大值。考慮把圈壓成序列，也就是如果原本圈上的點為$A_1,...,A_k$，考慮序列$A_1,...,A_k,A_{k+1},...,A_{2k-1}$，其中$A_{i+k}=A_i$，並且相鄰點的距離就和原本圈上連接這兩點的距離相等，記$dis[i]$代表$A_1$往右走到$A_i$的距離，和$val[i]$代表$A_i$的 val 值（最長路長），那麼我們要求的東西就是：$(i,j)$滿足$dis[i]-dis[j]+val[i]+val[j]$最大，其中$i-j<k$。因此當固定$i$的時候，我們需要的東西就會是$max\{ val[j]-dis[j] \}$，其中$j=i-k+1,...,i-1$。於是這就可以用 deque 優化在線性的時間內求出來了。
最後我傳上去 MLE 了，載測資來看發現那兩筆是DFS會到$10^6$層左右的，後來我把DFS改成自己用 stack 作才過的，感覺 IOI 沒必要這樣卡記憶體阿OAO......
code :
[CF 559E] Gerald and Path
作法：
我們把一個路燈想像成一根直立的棍子，長度為他可以照到的範圍，那麼現在就變成我們要決定他們要往左倒還是往右倒，使得總覆蓋區間最大。假設現在我們已經全部決定好了，那麼倒下的棍子們會形成好幾陀連通塊（若兩根棍子有交集則在他們之間連邊，考慮這張圖可以獲得一些連通塊），首先不難發現每個連通塊一定都是由連續的棍子所組成的，因此我們可以考慮先求出$dp[i][j]$，代表「從第$i$根到第$j$根棍子倒下後若形成一個連通塊，那麼這個連通塊有哪些可能的左右端點」，也就是一個$dp[i][j]$其實一個 vector<pair<int,int>>，裡面存了很多條線段。這邊可以再發現，如果有兩條線段是互相包含的關係，那麼顯然外面的一定比裡面的還好，因此我們可以只留下必要的線段就可以了，也就是當左端點遞增時右端點也遞增的線段們。不難得知如果我們已經有了所有的$dp[i][j]$的線段，那麼最後就可以再用個DP求出答案了，因此接下來只要關注如何轉移就可以了。
首先當$i=j$的時候顯然有兩個線段，丟進去即可。假設現在我們要算$dp[i][j]$有哪些線段，我們可以先把一些候選的線段丟進$dp[i][j]$中，最後再一次處理掉剛才所說的「被別人包含的線段」。考慮枚舉斷點$k$，那麼我們現在有$dp[i][k]$的一堆線段，還有$dp[k+1][j]$的一堆線段，我們想要用他們合成出新的線段。我們可以先假設$dp[i][k]$裡的線段是被放在左邊的線段，因為可以等一下把$dp[i][k]$和$dp[k+1][j]$交換再作一次即可。考慮枚舉$dp[i][k]$中的線段，當左邊的線段確定後，因為$dp[k+1][j]$中的線段都是當左端點遞增時右端點也遞增的，因此我們只要想辦法找到$dp[k+1][j]$中「和此左線段有交集的右端點最大的線段」就可以了，這可以用一個 lower_bound 達成。這樣轉移複雜度為$O(n^2logn)$，總複雜度為$O(n^4logn)$，不過在 codeforces 上跑得很快，可能是因為線段數量沒有到每個 dp 陣列都$O(n)$那麼多。
code :
我們把一個路燈想像成一根直立的棍子，長度為他可以照到的範圍，那麼現在就變成我們要決定他們要往左倒還是往右倒，使得總覆蓋區間最大。假設現在我們已經全部決定好了，那麼倒下的棍子們會形成好幾陀連通塊（若兩根棍子有交集則在他們之間連邊，考慮這張圖可以獲得一些連通塊），首先不難發現每個連通塊一定都是由連續的棍子所組成的，因此我們可以考慮先求出$dp[i][j]$，代表「從第$i$根到第$j$根棍子倒下後若形成一個連通塊，那麼這個連通塊有哪些可能的左右端點」，也就是一個$dp[i][j]$其實一個 vector<pair<int,int>>，裡面存了很多條線段。這邊可以再發現，如果有兩條線段是互相包含的關係，那麼顯然外面的一定比裡面的還好，因此我們可以只留下必要的線段就可以了，也就是當左端點遞增時右端點也遞增的線段們。不難得知如果我們已經有了所有的$dp[i][j]$的線段，那麼最後就可以再用個DP求出答案了，因此接下來只要關注如何轉移就可以了。
首先當$i=j$的時候顯然有兩個線段，丟進去即可。假設現在我們要算$dp[i][j]$有哪些線段，我們可以先把一些候選的線段丟進$dp[i][j]$中，最後再一次處理掉剛才所說的「被別人包含的線段」。考慮枚舉斷點$k$，那麼我們現在有$dp[i][k]$的一堆線段，還有$dp[k+1][j]$的一堆線段，我們想要用他們合成出新的線段。我們可以先假設$dp[i][k]$裡的線段是被放在左邊的線段，因為可以等一下把$dp[i][k]$和$dp[k+1][j]$交換再作一次即可。考慮枚舉$dp[i][k]$中的線段，當左邊的線段確定後，因為$dp[k+1][j]$中的線段都是當左端點遞增時右端點也遞增的，因此我們只要想辦法找到$dp[k+1][j]$中「和此左線段有交集的右端點最大的線段」就可以了，這可以用一個 lower_bound 達成。這樣轉移複雜度為$O(n^2logn)$，總複雜度為$O(n^4logn)$，不過在 codeforces 上跑得很快，可能是因為線段數量沒有到每個 dp 陣列都$O(n)$那麼多。
code :
[CF 559D] Randomizer
作法：
題目要求的是任取一個子多邊形的內部格點數期望值，顯然必須先使用 Pick's 定理，因為我們有$A=i+\frac{b}{2}-1$，所以我們只要知道子多邊形的$A$值期望值，和$b$值期望值就可以了。首先看$A$值的期望值，對於每個子多邊形，如果我們用整個多邊形去扣掉他，那麼他就會剩下一堆「頂點是原多邊形中的連續幾個點」的子多邊形。因此我們只要先算好要扣掉部份的期望值，再用原本的整個面積去扣掉就可以了。至於要如何算扣掉的部份，對於一個「頂點是原多邊形上連續幾個點」的子多邊形來說，假設他總共有$i$個頂點，那麼不難算出他總共會被算到$2^{n-i}-1$次，並且總共有$2^n-1-n-C_2^n$種子多邊形，因此有$i$個頂點的子多邊形貢獻為$\displaystyle \frac{2^{n-i}-1}{2^n-1-n-C_2^n}\times $其面積。這樣我們可以先獲得一個$O(n^2)$的算法：直接把每一項都加起來，並且在算「有$i$個頂點的子多邊形的面積總和」時可以用$i-1$個頂點的總和花$O(n)$的時間推過來。但觀察這條式子可以發現，當$i$越來越大時其倍率是指數往下跑的，因此我們可以只計算$i$很小的前幾項就好了，稍微估一下大概可以知道一直算到$i=100$左右就很夠了。
再來則是計算$b$的值，我們可以把每條邊拆開看，每條邊的貢獻會是$gcd(x$座標差$,y$座標差$)$（這樣算才能保證把子多邊形的每個邊的貢獻加起來是我們要的值），並且我們想知道他會被算到幾次。假設以這條邊切開原多邊形，所得到的子多邊形其中一邊有$k$個點，那麼不難得出他被算到的次數為：$(2^{n-2-k}-1)+(2^k-1)$，因此我們可以把他拆成兩邊看，也就是我們把主角放在「原多邊形的一段頂點區間」而不是「邊」，這樣就可以套用剛才的作法了，只要考慮那些「頂點區間夠小」的區間就可以了，也是取到長度$100$左右就很夠了。
code :
題目要求的是任取一個子多邊形的內部格點數期望值，顯然必須先使用 Pick's 定理，因為我們有$A=i+\frac{b}{2}-1$，所以我們只要知道子多邊形的$A$值期望值，和$b$值期望值就可以了。首先看$A$值的期望值，對於每個子多邊形，如果我們用整個多邊形去扣掉他，那麼他就會剩下一堆「頂點是原多邊形中的連續幾個點」的子多邊形。因此我們只要先算好要扣掉部份的期望值，再用原本的整個面積去扣掉就可以了。至於要如何算扣掉的部份，對於一個「頂點是原多邊形上連續幾個點」的子多邊形來說，假設他總共有$i$個頂點，那麼不難算出他總共會被算到$2^{n-i}-1$次，並且總共有$2^n-1-n-C_2^n$種子多邊形，因此有$i$個頂點的子多邊形貢獻為$\displaystyle \frac{2^{n-i}-1}{2^n-1-n-C_2^n}\times $其面積。這樣我們可以先獲得一個$O(n^2)$的算法：直接把每一項都加起來，並且在算「有$i$個頂點的子多邊形的面積總和」時可以用$i-1$個頂點的總和花$O(n)$的時間推過來。但觀察這條式子可以發現，當$i$越來越大時其倍率是指數往下跑的，因此我們可以只計算$i$很小的前幾項就好了，稍微估一下大概可以知道一直算到$i=100$左右就很夠了。
再來則是計算$b$的值，我們可以把每條邊拆開看，每條邊的貢獻會是$gcd(x$座標差$,y$座標差$)$（這樣算才能保證把子多邊形的每個邊的貢獻加起來是我們要的值），並且我們想知道他會被算到幾次。假設以這條邊切開原多邊形，所得到的子多邊形其中一邊有$k$個點，那麼不難得出他被算到的次數為：$(2^{n-2-k}-1)+(2^k-1)$，因此我們可以把他拆成兩邊看，也就是我們把主角放在「原多邊形的一段頂點區間」而不是「邊」，這樣就可以套用剛才的作法了，只要考慮那些「頂點區間夠小」的區間就可以了，也是取到長度$100$左右就很夠了。
code :
[CF 559B] Equivalent Strings
作法：
首先我們可以證明，題目給的等於的定義是一個「等價關係」（equivalence relation），可以對字串的長度用數學歸納法即可，因此不難證明，兩個字串是等價的若且唯若：把兩個字串都換成與他等價的字典序最小的字串，兩字串相等。而這個過程就可以用分治來解決了。
另外，這題有很多人直接寫了$O(n^2)$的解卻過了（也就是直接遞迴檢查$4$種可能的子字串配對），例如這份 code 的寫法，實際上可以證明這樣的複雜度其實是$O(n^{1.57})$的，詳細可以參考這篇 comment 。
code :
首先我們可以證明，題目給的等於的定義是一個「等價關係」（equivalence relation），可以對字串的長度用數學歸納法即可，因此不難證明，兩個字串是等價的若且唯若：把兩個字串都換成與他等價的字典序最小的字串，兩字串相等。而這個過程就可以用分治來解決了。
另外，這題有很多人直接寫了$O(n^2)$的解卻過了（也就是直接遞迴檢查$4$種可能的子字串配對），例如這份 code 的寫法，實際上可以證明這樣的複雜度其實是$O(n^{1.57})$的，詳細可以參考這篇 comment 。
code :
[HOJ 251][IOI 2008] Pyramid Base
作法：
首先考慮二分搜答案，因為如果能夠在預算內放入邊長$x$的正方形，那顯然可以放入邊長$x-1$的正方形。當確定一個邊長時，我們想要知道他可不可行，而只要注意到：我們只要決定好正方形的左上角就可以了，並且對於平面上的某個障礙物來說，考慮那些「用來當正方形左上角的話會和這個障礙物有交集的格子」，不難發現這些格子形成一個長方形（其座標不難求），因此就可以想成：如果左上角放在這個長方形裡，就要多花（這個長方形的 cost ）元。並且我們想知道這個平面上花費最少的格子是否在預算之中。因此就轉換為經典問題了：給定平面上的一些長方形，每個長方形都把內部的格子同加某個值，求整個平面的最小值是多少。這就顯然可以用掃描線+線段樹做了。
但這樣傳上去TLE了，畢竟$O(nlog^2n)$對$n\leq 400000$來說太大了。但注意到剩下只有$B=0$的情形，因此可以思考另外一種算法。考慮對於每個左界$i$，都找出最大的右界$j$，使得存在一個空的正方形，他的左右界分別為$i$和$j$。注意到如果我們把$i$到$j$這幾排全部壓成一排，並且「有和$i$到$j$交集的障礙物」都被壓成一排中的區間，那麼就變成詢問這一排中有最多連續幾個格子沒有障礙物了。因此我們可以把有交集到的障礙物的兩個$y$座標看成「把這兩數之間的所有數的位置的值都$+1$」，並且詢問的是這個數列裡有最多多少個連續的$0$，因此可以用線段樹做。這樣我們得到了$O(n^2logn)$的算法，也就是對於每個左界$i$直接一個一個往右擴展，當多遇到一個障礙物的左界，就在該區間$+1$的地方$+1$，直到查詢出來的值無法在兩邊界之間形成正方形為止。但只要注意到：如果存在一個正方形的左右邊界是$i,j$，那麼也存在左右邊界是$i+1,j$的。因此就可以改成用雙指標掃過去一次就可以了。複雜度降為$O(nlogn)$
最後提一下，這裡的線段樹必須支援：區間加$1$，區間減$1$和查詢最大連續的$0$數量，作法和「求$n$個矩形在平面上的覆蓋面積」時掃描線所用的線段樹類似，可以參考這篇。
code :
首先考慮二分搜答案，因為如果能夠在預算內放入邊長$x$的正方形，那顯然可以放入邊長$x-1$的正方形。當確定一個邊長時，我們想要知道他可不可行，而只要注意到：我們只要決定好正方形的左上角就可以了，並且對於平面上的某個障礙物來說，考慮那些「用來當正方形左上角的話會和這個障礙物有交集的格子」，不難發現這些格子形成一個長方形（其座標不難求），因此就可以想成：如果左上角放在這個長方形裡，就要多花（這個長方形的 cost ）元。並且我們想知道這個平面上花費最少的格子是否在預算之中。因此就轉換為經典問題了：給定平面上的一些長方形，每個長方形都把內部的格子同加某個值，求整個平面的最小值是多少。這就顯然可以用掃描線+線段樹做了。
但這樣傳上去TLE了，畢竟$O(nlog^2n)$對$n\leq 400000$來說太大了。但注意到剩下只有$B=0$的情形，因此可以思考另外一種算法。考慮對於每個左界$i$，都找出最大的右界$j$，使得存在一個空的正方形，他的左右界分別為$i$和$j$。注意到如果我們把$i$到$j$這幾排全部壓成一排，並且「有和$i$到$j$交集的障礙物」都被壓成一排中的區間，那麼就變成詢問這一排中有最多連續幾個格子沒有障礙物了。因此我們可以把有交集到的障礙物的兩個$y$座標看成「把這兩數之間的所有數的位置的值都$+1$」，並且詢問的是這個數列裡有最多多少個連續的$0$，因此可以用線段樹做。這樣我們得到了$O(n^2logn)$的算法，也就是對於每個左界$i$直接一個一個往右擴展，當多遇到一個障礙物的左界，就在該區間$+1$的地方$+1$，直到查詢出來的值無法在兩邊界之間形成正方形為止。但只要注意到：如果存在一個正方形的左右邊界是$i,j$，那麼也存在左右邊界是$i+1,j$的。因此就可以改成用雙指標掃過去一次就可以了。複雜度降為$O(nlogn)$
最後提一下，這裡的線段樹必須支援：區間加$1$，區間減$1$和查詢最大連續的$0$數量，作法和「求$n$個矩形在平面上的覆蓋面積」時掃描線所用的線段樹類似，可以參考這篇。
code :
2015年7月22日 星期三
[HOJ 223] H. 項鍊
作法：
$m=1$時是顯然的，$m=2$不難自己構造出來，詳細可以參考 code 。但$m=3$以上的構造就很困難了，我的作法是直接 DFS 下去，剛好因為滿足這種條件的數列蠻多的，所以可以在時限內找到。比較正常的作法應該是把他轉成尤拉迴路問題：考慮一張有$n^{m-1}$個點的有向圖，每個點都代表一個長度為$m-1$字元集$1~n$的字串，並且如果某個點$A$可以經由「在後面加上一個數並丟掉最前面的數」轉換成$B$，那麼就從$A$連到$B$一條邊。這樣邊的總數會是$n^m\leq 3\cdot 10^5$，對這張圖求尤拉迴路就可以了。
code :
$m=1$時是顯然的，$m=2$不難自己構造出來，詳細可以參考 code 。但$m=3$以上的構造就很困難了，我的作法是直接 DFS 下去，剛好因為滿足這種條件的數列蠻多的，所以可以在時限內找到。比較正常的作法應該是把他轉成尤拉迴路問題：考慮一張有$n^{m-1}$個點的有向圖，每個點都代表一個長度為$m-1$字元集$1~n$的字串，並且如果某個點$A$可以經由「在後面加上一個數並丟掉最前面的數」轉換成$B$，那麼就從$A$連到$B$一條邊。這樣邊的總數會是$n^m\leq 3\cdot 10^5$，對這張圖求尤拉迴路就可以了。
code :
[HOJ 220] E. code
作法：
如果題目沒有$i\neq j$的條件的話，式子就可以寫成$\displaystyle (\sum_{i=1}^{n} n\% i)(\sum_{i=1}^{m} m\% i)$，因此這部份可以先分開算再乘起來。至於要怎麼計算$\displaystyle \sum_{i=1}^{n} n\% i$，一樣是把商一樣的區間合併起來看，因為$n$除以從$i$一直到$n/(n/i)$（這裡是整數除法）的這些數都會得到一樣的商，所以在這個區間裡$n\% i$會是一個等差數列，可以合併起來一起算。最後則是要扣掉$i=j$的部份，也就是要計算$\displaystyle \sum_{i=1}^{min(n,m)} (n\% i)(m\% i)$，這一樣可以用剛才的技巧，只不過區間的右端點必須取成$min(m/(m/i),n/(n/i))$而已。這部份則會變成一個二次函數在一個區間裡的所有函數值的總和，而這東西不難用$\displaystyle \sum k^2$的公式求得。
code :
如果題目沒有$i\neq j$的條件的話，式子就可以寫成$\displaystyle (\sum_{i=1}^{n} n\% i)(\sum_{i=1}^{m} m\% i)$，因此這部份可以先分開算再乘起來。至於要怎麼計算$\displaystyle \sum_{i=1}^{n} n\% i$，一樣是把商一樣的區間合併起來看，因為$n$除以從$i$一直到$n/(n/i)$（這裡是整數除法）的這些數都會得到一樣的商，所以在這個區間裡$n\% i$會是一個等差數列，可以合併起來一起算。最後則是要扣掉$i=j$的部份，也就是要計算$\displaystyle \sum_{i=1}^{min(n,m)} (n\% i)(m\% i)$，這一樣可以用剛才的技巧，只不過區間的右端點必須取成$min(m/(m/i),n/(n/i))$而已。這部份則會變成一個二次函數在一個區間裡的所有函數值的總和，而這東西不難用$\displaystyle \sum k^2$的公式求得。
code :
[HOJ 218] C. osu!
作法：
首先找出圓和四條邊界的交點（如果有的話），那麼可以得到相鄰交點中間形成的弧同在矩形內部或外部，因此可以直接選這段弧的中點判斷他是在內部還外部，在內部的話就把答案加上對應的值就可以了。另外要注意圓和邊界完全沒有交點的情形，而這只要一開始就加入兩個假的斷點（$\frac{\pi}{2}$和$-\frac{\pi}{2}$）就可以了。
code :
首先找出圓和四條邊界的交點（如果有的話），那麼可以得到相鄰交點中間形成的弧同在矩形內部或外部，因此可以直接選這段弧的中點判斷他是在內部還外部，在內部的話就把答案加上對應的值就可以了。另外要注意圓和邊界完全沒有交點的情形，而這只要一開始就加入兩個假的斷點（$\frac{\pi}{2}$和$-\frac{\pi}{2}$）就可以了。
code :
[HOJ 201] TRAMPOLIN
作法：
首先我們可以把相鄰的同高度的大樓黏起來，並且紀錄好黏起來的這陀大樓原本有幾棟，而如果原本黏起來的大樓中有可以瞬移的大樓，那麼黏起來後的也可以瞬移。因此現在問題轉化為相鄰高度皆不同的問題。首先如出發點往左邊或右邊走都沒辦法達到能夠瞬移的大樓，那麼答案就是往左走或往右走的經過大樓數比較多的那個，反之假設起點可以走到某個可瞬移的大樓，那麼對於所有的制高點（旁邊沒有比他高的大樓的大樓），如果他往左（或往右）走下去之後會可以遇到能瞬移的，那麼我們就可以從起點那邊瞬移到這個制高點，走完這段後再順移回去。因此我們可以先找出所有的這樣的路徑，把他們標記成全部都可以走到。最後只要再選一個制高點然後走到底就好，枚舉看要走哪條路徑可以增加更多被走到的大樓。
code :
首先我們可以把相鄰的同高度的大樓黏起來，並且紀錄好黏起來的這陀大樓原本有幾棟，而如果原本黏起來的大樓中有可以瞬移的大樓，那麼黏起來後的也可以瞬移。因此現在問題轉化為相鄰高度皆不同的問題。首先如出發點往左邊或右邊走都沒辦法達到能夠瞬移的大樓，那麼答案就是往左走或往右走的經過大樓數比較多的那個，反之假設起點可以走到某個可瞬移的大樓，那麼對於所有的制高點（旁邊沒有比他高的大樓的大樓），如果他往左（或往右）走下去之後會可以遇到能瞬移的，那麼我們就可以從起點那邊瞬移到這個制高點，走完這段後再順移回去。因此我們可以先找出所有的這樣的路徑，把他們標記成全部都可以走到。最後只要再選一個制高點然後走到底就好，枚舉看要走哪條路徑可以增加更多被走到的大樓。
code :
[HOJ 187] 小學老師
作法：
首先觀察有哪些數字的$f$值會變成$i$，會發現這就等價於這個數是$1,...,i-1$的倍數，但不是$i$的倍數。因此可以想像$10^{17}$範圍內的數字的$f$值都不會太大，因為$1,...,n$的最小公倍數成長的速度非常快。可以預處理出最大的$f$值只會到$41$，因此對於所求的值，對於每一項$L(i)$來說，可以先把他換成$L(f(i))+1$，這樣就只需要知道$[A,B]$之間有幾個數的$f$值等於$i$了（$i=1,...,41$），而這顯然用前面的等價條件就可以算了。
code :
首先觀察有哪些數字的$f$值會變成$i$，會發現這就等價於這個數是$1,...,i-1$的倍數，但不是$i$的倍數。因此可以想像$10^{17}$範圍內的數字的$f$值都不會太大，因為$1,...,n$的最小公倍數成長的速度非常快。可以預處理出最大的$f$值只會到$41$，因此對於所求的值，對於每一項$L(i)$來說，可以先把他換成$L(f(i))+1$，這樣就只需要知道$[A,B]$之間有幾個數的$f$值等於$i$了（$i=1,...,41$），而這顯然用前面的等價條件就可以算了。
code :
2015年7月20日 星期一
[HOJ 160] 紅色警戒區
作法：
首先對於每個圓，求出他和其他所有圓的交點，那麼對於相鄰交點形成的弧上的任意點來說，他們的狀態都是一樣的，也就是他們同為邊界或同不為邊界（或是說交點們就是「斷點」）。因此只要取這段弧上的中點，去判斷他是否落在某個圓內部就可以了。另外要注意到，這樣會沒辦法判斷一個圓被另一個圓包住的情形，此時裡面的圓沒有任何斷點，因此要先對每個圓都加入$\frac{\pi }{2}$和$-\frac{\pi}{2}$這兩個斷點（以極角表示斷點）才能自動把他判掉。最後還要處理兩個圓重和的情形，在一開始就直接把重複的丟掉就可以了。
code :
首先對於每個圓，求出他和其他所有圓的交點，那麼對於相鄰交點形成的弧上的任意點來說，他們的狀態都是一樣的，也就是他們同為邊界或同不為邊界（或是說交點們就是「斷點」）。因此只要取這段弧上的中點，去判斷他是否落在某個圓內部就可以了。另外要注意到，這樣會沒辦法判斷一個圓被另一個圓包住的情形，此時裡面的圓沒有任何斷點，因此要先對每個圓都加入$\frac{\pi }{2}$和$-\frac{\pi}{2}$這兩個斷點（以極角表示斷點）才能自動把他判掉。最後還要處理兩個圓重和的情形，在一開始就直接把重複的丟掉就可以了。
code :
[HOJ 164] 森森砍你的臉
作法：
考慮枚舉正方形左上角右下角所在的對角線，首先我們可以預處理出每個格子的$X$值和$Y$值，$X[i][j]$代表從$(i,j)$這格往右往下長度$X[i][j]$以內的格子都是$1$（或是$(i,j),...,(i,j+X[i][j]-1)$均為$1$，往下同理），$Y[i][j]$則是代表往左往上的，並且兩者都是取最大的值。那麼當我們枚舉一條對角線時，記這條對角線上第$i$格的$X,Y$值分別為$x[i],y[i]$，那我們想找的就是所有二元組$(i,j)$的數量（$i\leq j$），滿足$x[i]\geq j-i+1$，且$y[j]\geq j-i+1$。注意到這條式子中，不管怎麼樣當$i>j$時他一定會成立，因此我們可以把$i\leq j$這個條件拿掉，再扣掉多算到的部份就可以了。將上式移項得$i+x[i]\geq j+1$，$i\geq j+1-y[j]$，那麼就可以轉換成簡單的問題了：考慮平面上的$n$個紅點和$n$個藍點，其中第$i$個紅點的座標為$(i+x[i],i)$，第$i$個藍點的座標為$(i+1,i+1-y[i])$，求滿足「紅點的兩座標均$\geq$藍點的兩座標」的（紅點、藍點）的個數（或是說紅點包住藍點的點對數量）。這可以先把所有點按照$x$座標排序，再用個 BIT 查詢每個紅點包住了幾個藍點就可以了。
code :
考慮枚舉正方形左上角右下角所在的對角線，首先我們可以預處理出每個格子的$X$值和$Y$值，$X[i][j]$代表從$(i,j)$這格往右往下長度$X[i][j]$以內的格子都是$1$（或是$(i,j),...,(i,j+X[i][j]-1)$均為$1$，往下同理），$Y[i][j]$則是代表往左往上的，並且兩者都是取最大的值。那麼當我們枚舉一條對角線時，記這條對角線上第$i$格的$X,Y$值分別為$x[i],y[i]$，那我們想找的就是所有二元組$(i,j)$的數量（$i\leq j$），滿足$x[i]\geq j-i+1$，且$y[j]\geq j-i+1$。注意到這條式子中，不管怎麼樣當$i>j$時他一定會成立，因此我們可以把$i\leq j$這個條件拿掉，再扣掉多算到的部份就可以了。將上式移項得$i+x[i]\geq j+1$，$i\geq j+1-y[j]$，那麼就可以轉換成簡單的問題了：考慮平面上的$n$個紅點和$n$個藍點，其中第$i$個紅點的座標為$(i+x[i],i)$，第$i$個藍點的座標為$(i+1,i+1-y[i])$，求滿足「紅點的兩座標均$\geq$藍點的兩座標」的（紅點、藍點）的個數（或是說紅點包住藍點的點對數量）。這可以先把所有點按照$x$座標排序，再用個 BIT 查詢每個紅點包住了幾個藍點就可以了。
code :
[HOJ 199] KAMPANJA
作法：
考慮$d[A][B]$代表從$1$走到$A$走到$B$再走回$A$的路上最少可以經過幾個節點，那麼所求的答案就是$d[2][2]$。首先我們可以用 Floyd 求出任兩點之間的最短路（之後記為$dis[][]$），就可以先得到$d[A][B]$的一些初始值，並且由第一個範測可以觀察到：如果我們任取四個點$A,B,X,Y$，那麼$1\rightarrow X\rightarrow Y\rightarrow 1$實際上可以用$1\rightarrow A\rightarrow B\rightarrow X\rightarrow Y\rightarrow A\rightarrow B\rightarrow 1$來達成，也就是我們可以用$d[A][B]+dis[B][X]+dis[X][Y]+dis[Y][A]-1$來更新$d[X][Y]$的值。注意到上式中當$X,Y,A,B$不全相等時，$dis[B][X]+dis[X][Y]+dis[Y][A]-1\geq 0$，這就類似在求最短路的過程，因此我們可以直接套用 Dijkstra 求得答案。注意到這裡的 Dijkstra 不是用 priority_queue 優化的，而是優化前的「每次掃一遍所有的節點看誰目前距離最小，拿他來鬆弛其他人」，前者複雜度會變成$O(n^4logn)$，後者則是$O(n^4)$（因為這張圖是稠密圖）。
code :
考慮$d[A][B]$代表從$1$走到$A$走到$B$再走回$A$的路上最少可以經過幾個節點，那麼所求的答案就是$d[2][2]$。首先我們可以用 Floyd 求出任兩點之間的最短路（之後記為$dis[][]$），就可以先得到$d[A][B]$的一些初始值，並且由第一個範測可以觀察到：如果我們任取四個點$A,B,X,Y$，那麼$1\rightarrow X\rightarrow Y\rightarrow 1$實際上可以用$1\rightarrow A\rightarrow B\rightarrow X\rightarrow Y\rightarrow A\rightarrow B\rightarrow 1$來達成，也就是我們可以用$d[A][B]+dis[B][X]+dis[X][Y]+dis[Y][A]-1$來更新$d[X][Y]$的值。注意到上式中當$X,Y,A,B$不全相等時，$dis[B][X]+dis[X][Y]+dis[Y][A]-1\geq 0$，這就類似在求最短路的過程，因此我們可以直接套用 Dijkstra 求得答案。注意到這裡的 Dijkstra 不是用 priority_queue 優化的，而是優化前的「每次掃一遍所有的節點看誰目前距離最小，拿他來鬆弛其他人」，前者複雜度會變成$O(n^4logn)$，後者則是$O(n^4)$（因為這張圖是稠密圖）。
code :
2015年7月18日 星期六
[HOJ 128] Matching
作法：
我們一樣往KMP的方向想，首先我們會需要 fail 函數，回顧他的定義，$fail[i]$代表說「當已經匹配好$1,...,i$時，如果$i+1$失配，那麼要轉換成已經匹配好$1,...,fail[i]$的情形」，而這裡的匹配的定義根一般字串匹配不一樣，是要兩個子序列的「相對大小關係」一樣時則叫作匹配。因此回顧我們在算 fail 函數時的方法，假設當前要決定$i$的 fail 值，令$fail[i-1]=j$，那麼首先我們要判斷「$1,...,i$的長度為$j+1$的後綴」是否和「長度$j+1$的前綴」匹配（再次強調這裡匹配的定義不一樣），而這等價於：「在$x[i-j],...,x[i-1]$之中比$x[i]$小的數的個數」等於「在$x[1],...,x[j]$中比$x[j+1]$小的數的個數」，其中$x$為要求$fail$函數的陣列。因此就可以維護一個 BIT 來查詢所求的答案（因為會支援加數字和刪數字）。如果發現失配了就一樣沿著 fail 往回跳，直到長度變$0$或是匹配成功為止。由這裡就可以發現，其實 fail 函數建立的過程幾乎一樣，只是變成要多維護兩個 BIT ，並用 BIT 來查詢是否匹配成功而已。在和原數列匹配的過程也一模一樣（本來在原本的寫法中建 fail 函數和匹配的過程的程式碼就幾乎一樣了），失配就沿 fail 往前跳，維護好兩個 BIT 即可。最後要記得當找到一個地方成功匹配了模版串時也要沿 fail 往前跳，跟原本的 KMP 一樣。
code :
我們一樣往KMP的方向想，首先我們會需要 fail 函數，回顧他的定義，$fail[i]$代表說「當已經匹配好$1,...,i$時，如果$i+1$失配，那麼要轉換成已經匹配好$1,...,fail[i]$的情形」，而這裡的匹配的定義根一般字串匹配不一樣，是要兩個子序列的「相對大小關係」一樣時則叫作匹配。因此回顧我們在算 fail 函數時的方法，假設當前要決定$i$的 fail 值，令$fail[i-1]=j$，那麼首先我們要判斷「$1,...,i$的長度為$j+1$的後綴」是否和「長度$j+1$的前綴」匹配（再次強調這裡匹配的定義不一樣），而這等價於：「在$x[i-j],...,x[i-1]$之中比$x[i]$小的數的個數」等於「在$x[1],...,x[j]$中比$x[j+1]$小的數的個數」，其中$x$為要求$fail$函數的陣列。因此就可以維護一個 BIT 來查詢所求的答案（因為會支援加數字和刪數字）。如果發現失配了就一樣沿著 fail 往回跳，直到長度變$0$或是匹配成功為止。由這裡就可以發現，其實 fail 函數建立的過程幾乎一樣，只是變成要多維護兩個 BIT ，並用 BIT 來查詢是否匹配成功而已。在和原數列匹配的過程也一模一樣（本來在原本的寫法中建 fail 函數和匹配的過程的程式碼就幾乎一樣了），失配就沿 fail 往前跳，維護好兩個 BIT 即可。最後要記得當找到一個地方成功匹配了模版串時也要沿 fail 往前跳，跟原本的 KMP 一樣。
code :
[HOJ 149] 改建路徑
作法：
我們考慮一個非常樸素的DP：設$dp[i][j]$代表目前已把前$i$個數弄成非嚴格遞增了，則第$i$個數的值為$j$的最小花費，那麼顯然可以寫出轉移式：$dp[i][j]=min\{dp[i-1][k]+|a[i]-j|,k=1,...,j\}$。想像一下$dp[i]$的函數圖形，那麼他就是由$dp[i-1]$先取前綴 min ，再加上$|x-a[i]|$這個函數所形成的圖形（前綴 min 的意思就是前面轉移式中的$min\{ dp[i-1][k],k=1,...,j \}$）。不難發現他其實會形成一個下凸包，並且轉折的點只會出現在$x$座標為原本$a$數列裡出現過的值，並且每次加上$|x-a[i]|$這個函數時，可以看成$a[i]$左邊的斜率全部$-1$，右邊的斜率全部$+1$，因此就可以用線段樹來維護斜率們（所以在這之前要先離散化$a[i]$），並且取前綴 min 的操作可以等價成：把斜率$>0$的部份都設成$0$（因為他會一直維持他是下凸包的良好性質），這也不難在線段樹上做到。最後我們想知道的是$dp[n]$這個函數圖形的最小值是多少，但線段樹中只有紀錄每個區間的斜率，因此只要再多紀錄函數在$0$的值是多少就可以了（而他顯然會是所有$a[i]$的和），從左到右掃一遍就可以獲得$dp[n]$圖形的每個轉折點的座標，取$y$座標最小的點就是答案了。
最後，在「把斜率$>0$的部份都設成$0$」的操作其實可以很簡潔的完成，我們可以對每個線段樹區間都維護他的最小值，那麼就可以直接從根走下去，發現如果當前節點的右孩子的最小值$>0$（其實也只有可能是$1$），就把右孩子全部$-1$，往左孩子遞迴，反之則往右孩子遞迴就可以了。
code :
我們考慮一個非常樸素的DP：設$dp[i][j]$代表目前已把前$i$個數弄成非嚴格遞增了，則第$i$個數的值為$j$的最小花費，那麼顯然可以寫出轉移式：$dp[i][j]=min\{dp[i-1][k]+|a[i]-j|,k=1,...,j\}$。想像一下$dp[i]$的函數圖形，那麼他就是由$dp[i-1]$先取前綴 min ，再加上$|x-a[i]|$這個函數所形成的圖形（前綴 min 的意思就是前面轉移式中的$min\{ dp[i-1][k],k=1,...,j \}$）。不難發現他其實會形成一個下凸包，並且轉折的點只會出現在$x$座標為原本$a$數列裡出現過的值，並且每次加上$|x-a[i]|$這個函數時，可以看成$a[i]$左邊的斜率全部$-1$，右邊的斜率全部$+1$，因此就可以用線段樹來維護斜率們（所以在這之前要先離散化$a[i]$），並且取前綴 min 的操作可以等價成：把斜率$>0$的部份都設成$0$（因為他會一直維持他是下凸包的良好性質），這也不難在線段樹上做到。最後我們想知道的是$dp[n]$這個函數圖形的最小值是多少，但線段樹中只有紀錄每個區間的斜率，因此只要再多紀錄函數在$0$的值是多少就可以了（而他顯然會是所有$a[i]$的和），從左到右掃一遍就可以獲得$dp[n]$圖形的每個轉折點的座標，取$y$座標最小的點就是答案了。
最後，在「把斜率$>0$的部份都設成$0$」的操作其實可以很簡潔的完成，我們可以對每個線段樹區間都維護他的最小值，那麼就可以直接從根走下去，發現如果當前節點的右孩子的最小值$>0$（其實也只有可能是$1$），就把右孩子全部$-1$，往左孩子遞迴，反之則往右孩子遞迴就可以了。
code :
[HOJ 156] Xor路徑和
作法：
首先我們當然可以只看和$1,n$連通的分量就好了。考慮隨便取一條$1$走到$n$的路徑，設其 xor 值為$X$，然後隨便取一個圖中的圈，假設他邊的 xor 值為$Y$，那麼就存在一條從$1$走到$n$的路徑，使得其 xor 值為$X\; xor\; Y$。因為只要在走原本的路徑時，走到一半分出去走到圈上的某一個點，繞完一圈後再沿原路走回來，再繼續走到$n$就可以了。因此我們的想法為：隨便取一條$1$走到$n$的路徑，並且找出所有圖中的圈，那麼只要想辦法用這條路徑的 xor 值加上隨便取幾個圈湊出最大的 xor 值就可以了。但這樣顯然會遇到圖中的圈太多的問題，但其實我們可以只保留那些「沒辦法被之前找到的圈的值 xor 出來的圈」就可以了，具體來說，如果有個圈$C$的 xor 值為$X$，並且存在其他圈$C_1,...,C_r$其 xor 值分別為$X_1,...,X_r$，那麼當$X=X_1\; xor \; ... \; xor \; X_r$時$C$就沒有用了，因為如果取到他的話就可以直接把他換成$C_1,...,C_r$（或是說我們取的圈的值都是線性獨立的）。再來注意到，我們考慮一條一條把邊加到圖中，那麼當某條邊$AB$加進去並且形成了新的圈時，我們隨便取一條$A$到$B$的路徑，和新加的這條邊組成了一個圈，那麼（不難證明）在這個圖中所有新形成的圈的 xor 值都可以用這個新的圈的 xor 值和舊的那些圈的值 xor 出來，因此我們就可以獲得至多$m$個圈的 xor 值，並且要想辦法把他刪成線性獨立的（這樣就會不超過 $60$ 個了）。
我們先看要怎麼知道這些圈的 xor 值是多少，事實上我們可以在維護 disjoint set 的時候順便維護這個點沿著他父親走到根，路上經過的邊的 xor 值是多少，只要修改一下 find 的過程就可以了，詳細可以參考 code 。再來則是我們想把$m$個數（向量）刪成線性獨立的$\leq 60$個，這只要直接高斯消去就可以了，細節在此省略。有了這些線性獨立的向量後，剩下的問題是：給定一個數$x$（也就是我們任意取的$1$走到$n$的路徑的 xor 值），我們要想辦法用這些向量 xor 一個數，使得他和$x$的 xor 值盡量大。我們可以考慮由高到低一位一位確定答案，舉例來說，$x$的二進制為$110101$，並且我們已經知道能湊出的盡量大的值為$101***$（後面代表還沒確定），那麼接下來我們想知道能不能用那些向量湊出形如$0110**$的向量，就能確定答案的下一位了。確定這個的方法只要把所有已有的向量的最後兩位砍掉，並且去處理「給定一些向量，是否有辦法湊出給定的某個向量」的問題就可以了，作法當然就直接高斯消去就可以了。
code :
首先我們當然可以只看和$1,n$連通的分量就好了。考慮隨便取一條$1$走到$n$的路徑，設其 xor 值為$X$，然後隨便取一個圖中的圈，假設他邊的 xor 值為$Y$，那麼就存在一條從$1$走到$n$的路徑，使得其 xor 值為$X\; xor\; Y$。因為只要在走原本的路徑時，走到一半分出去走到圈上的某一個點，繞完一圈後再沿原路走回來，再繼續走到$n$就可以了。因此我們的想法為：隨便取一條$1$走到$n$的路徑，並且找出所有圖中的圈，那麼只要想辦法用這條路徑的 xor 值加上隨便取幾個圈湊出最大的 xor 值就可以了。但這樣顯然會遇到圖中的圈太多的問題，但其實我們可以只保留那些「沒辦法被之前找到的圈的值 xor 出來的圈」就可以了，具體來說，如果有個圈$C$的 xor 值為$X$，並且存在其他圈$C_1,...,C_r$其 xor 值分別為$X_1,...,X_r$，那麼當$X=X_1\; xor \; ... \; xor \; X_r$時$C$就沒有用了，因為如果取到他的話就可以直接把他換成$C_1,...,C_r$（或是說我們取的圈的值都是線性獨立的）。再來注意到，我們考慮一條一條把邊加到圖中，那麼當某條邊$AB$加進去並且形成了新的圈時，我們隨便取一條$A$到$B$的路徑，和新加的這條邊組成了一個圈，那麼（不難證明）在這個圖中所有新形成的圈的 xor 值都可以用這個新的圈的 xor 值和舊的那些圈的值 xor 出來，因此我們就可以獲得至多$m$個圈的 xor 值，並且要想辦法把他刪成線性獨立的（這樣就會不超過 $60$ 個了）。
我們先看要怎麼知道這些圈的 xor 值是多少，事實上我們可以在維護 disjoint set 的時候順便維護這個點沿著他父親走到根，路上經過的邊的 xor 值是多少，只要修改一下 find 的過程就可以了，詳細可以參考 code 。再來則是我們想把$m$個數（向量）刪成線性獨立的$\leq 60$個，這只要直接高斯消去就可以了，細節在此省略。有了這些線性獨立的向量後，剩下的問題是：給定一個數$x$（也就是我們任意取的$1$走到$n$的路徑的 xor 值），我們要想辦法用這些向量 xor 一個數，使得他和$x$的 xor 值盡量大。我們可以考慮由高到低一位一位確定答案，舉例來說，$x$的二進制為$110101$，並且我們已經知道能湊出的盡量大的值為$101***$（後面代表還沒確定），那麼接下來我們想知道能不能用那些向量湊出形如$0110**$的向量，就能確定答案的下一位了。確定這個的方法只要把所有已有的向量的最後兩位砍掉，並且去處理「給定一些向量，是否有辦法湊出給定的某個向量」的問題就可以了，作法當然就直接高斯消去就可以了。
code :
2015年7月16日 星期四
[CF 558E] A Simple Task
作法：
因為對一個區間正排序或逆排序後，所有同樣的字母都會擠在一起，因此就可以想到對每個字母分開維護，那麼對於特定一個字母就只要支援：把某段區間都設成不是這個字母，還有把某段區間都設成這個字母的操作，用個線段樹就可以輕鬆解決了。
code :
因為對一個區間正排序或逆排序後，所有同樣的字母都會擠在一起，因此就可以想到對每個字母分開維護，那麼對於特定一個字母就只要支援：把某段區間都設成不是這個字母，還有把某段區間都設成這個字母的操作，用個線段樹就可以輕鬆解決了。
code :
[CF 558D] Guess Your Way Out! II
作法：
因為每次獲得的條件都形如：某個區間裡的數有其中一個是答案，或是這個區間裡都不是答案。而對於後者可以改寫成：答案落在兩個區間的聯集中。這樣就可以用以下算法解決：如果我們獲得了某個區間裡的數有其中一個是答案的條件，就把這個區間裡的每個數的值都$+1$，而對於另外一種條件我們也把「兩個聯集起來裡面有答案的線段」裡的數值都$+1$，那麼不難發現全部加完$1$之後那些值變成$Q$的就會是答案的候選人了（$Q$是條件個數）。因此就可以用離散化來做了，把區間加值轉換成在起點有個事件是$+1$，最後一個點的後一格有個事件是$-1$，排序後掃過去就可以知道答案了。
code :
因為每次獲得的條件都形如：某個區間裡的數有其中一個是答案，或是這個區間裡都不是答案。而對於後者可以改寫成：答案落在兩個區間的聯集中。這樣就可以用以下算法解決：如果我們獲得了某個區間裡的數有其中一個是答案的條件，就把這個區間裡的每個數的值都$+1$，而對於另外一種條件我們也把「兩個聯集起來裡面有答案的線段」裡的數值都$+1$，那麼不難發現全部加完$1$之後那些值變成$Q$的就會是答案的候選人了（$Q$是條件個數）。因此就可以用離散化來做了，把區間加值轉換成在起點有個事件是$+1$，最後一個點的後一格有個事件是$-1$，排序後掃過去就可以知道答案了。
code :
2015年7月15日 星期三
[LA 4454] Subway Timing
作法：
首先考慮二分搜答案，這樣變成對於一個給定的誤差$M$，是否有辦法把邊權都改成$60$的倍數，使得任兩點之間的距離誤差絕對值不會超過$M$。對於一個子樹來說，記他的根為$R$，假設有一種改邊權的方法，使得這棵子樹中任兩點之間的距離誤差絕對值不會超過$M$，並且$R$到這棵子樹中每個點的距離誤差最小值為$a$，最大值為$b$（這裡的誤差指的是「新的距離扣掉舊的距離」的值，有正有負，因此這裡顯然會有$a\leq 0,b\geq 0$），那麼這個設邊權的方法就只有$a,b$是跟之後決策有關的資訊了。也就是一個節點需要的 dp 值會是一大堆的$(a,b)$ 的 pair 。實際上我們可以不用把所有的$(a,b)$都紀錄起來，觀察到如果有兩個 pair $(a_1,b_1),(a_2,b_2)$，滿足$a_2\leq a_1$且$b_2\geq b_1$，那麼取$(a_1,b_1)$一定會比取$a_2,b_2$好，因此我們可以只維護$a$值和$b$值都嚴格遞增的 pair 們就可以了。
轉移比較麻煩，我們可以把題目轉成二元樹比較好DP。轉成二元樹的方法如下圖（對每個節點都做這種轉換即可），其中紅色的點是新加的點，左右圖中的藍色的邊的邊權是相等的，並且紅色邊的邊權為$0$。
code :
首先考慮二分搜答案，這樣變成對於一個給定的誤差$M$，是否有辦法把邊權都改成$60$的倍數，使得任兩點之間的距離誤差絕對值不會超過$M$。對於一個子樹來說，記他的根為$R$，假設有一種改邊權的方法，使得這棵子樹中任兩點之間的距離誤差絕對值不會超過$M$，並且$R$到這棵子樹中每個點的距離誤差最小值為$a$，最大值為$b$（這裡的誤差指的是「新的距離扣掉舊的距離」的值，有正有負，因此這裡顯然會有$a\leq 0,b\geq 0$），那麼這個設邊權的方法就只有$a,b$是跟之後決策有關的資訊了。也就是一個節點需要的 dp 值會是一大堆的$(a,b)$ 的 pair 。實際上我們可以不用把所有的$(a,b)$都紀錄起來，觀察到如果有兩個 pair $(a_1,b_1),(a_2,b_2)$，滿足$a_2\leq a_1$且$b_2\geq b_1$，那麼取$(a_1,b_1)$一定會比取$a_2,b_2$好，因此我們可以只維護$a$值和$b$值都嚴格遞增的 pair 們就可以了。
轉移比較麻煩，我們可以把題目轉成二元樹比較好DP。轉成二元樹的方法如下圖（對每個節點都做這種轉換即可），其中紅色的點是新加的點，左右圖中的藍色的邊的邊權是相等的，並且紅色邊的邊權為$0$。
轉成二元樹之後工作就只剩下合併兩個子節點的 dp 陣列了，假設當前節點為$x$，並且我們已經決定好$x$連向他兩個子樹的邊的新邊權了，記這兩條邊的誤差分別為$dx,dy$（也就是新邊權扣掉舊邊權的值），那麼考慮左子樹 DP 陣列中的某個$(a_1,b_1)$，還有右子樹中的某個$(a_2,b_2)$，這兩個 pair 分別都代表了他所在子樹的某個設置邊權的方法。接下來我們想知道把這兩個方法並在一起是不是可行的，並且如果可以的話要知道$x$的 DP 陣列必須多丟什麼 pair 進去。我們想要知道這兩個 pair 是否是可行的，而可行的充要條件就是任兩點距離的誤差絕對值$\leq M$。分成$x$到非根節點和左子樹中的點到右子樹中的點來討論，考慮前者則必須滿足：$|a_1+dx|\leq M,|b_1+dx|\leq M,|a_2+dy|\leq M,|b_2+dy|\leq M$。後者的話則必須滿足：$|a_1+a_2+dx+dy|\leq M,|b_1+b_2+dx+dy|\leq M$。並且如果$(a_1,b_1),(a_2,b_2)$都滿足前面那些條件的話，那麼$dp[x]$就會新增一個 pair ：$(min(a_1+dx,a_2+dy,0),max(b_1+dx,b_2+dy,0))$。
我們當然不能枚舉所有左右子樹形成的 pair 的二元組，注意到當我們固定$(a_1,b_1)$時，我們可以把上述條件全部整理成：$a_2\leq $一坨東西、$a_2\geq $一坨東西（$b_2$）亦同，這裡就可以利用這些 pair 的遞增性，可以得到第二個子樹中滿足那些條件的 pair 會落在某個區間中（如果我們已經把子樹中的 pair 們排好序了），而我們不難用二分搜找出這個區間。再觀察到新增的 pair 的式子，可以不妨設$a_1+dx\leq a_2+dy$，因為我們可以把兩個子樹交換再作一次，因此新增的 pair 的第一項的值已經確定了，並且我們知道此時第二項要越小越好，也就是 $b_2$ 越小越好，因此我們只要枚舉第一個子樹中的$(a_1,b_1)$，並且取剛剛找到的那個區間的第一個 pair 就可以了，拿他配上$(a_1,b_1)$去更新$dp[x]$即可（當然當這個區間不存在時就沒辦法更新）。
[POI 17 Stage 3] Monotonicity 2
作法：
首先考慮一個樸素的算法：對於每個$i$，我們知道存在一些以$i$結尾的子字串是滿足題目要求的，那麼對每個子字串來說，都可以用他的長度去更新所有$i$之後的答案（依照這個長度時下一步應該要比$a[i]$大還是小，或是等於）。具體來說，如果有一個$i$結尾的子字串長度為$L$，並且$s[L]$為$<$，那麼就可以用$L+1$去更新$i$以後的值大於$a[i]$的位子的答案。這裡有個非常不顯然的結論，就是其實對於所有$i$結尾的子字串，我們只需要紀錄最長那個的長度就可以了！（證明補在後面），因此就可以用 DP 算出每個位子結尾的最長子序列長度了。具體來說，當算完$dp[i]$時，如果$s[dp[i]]$為$<$，那麼之後如果遇到有某個$>a[i]$的數，都要把他的答案和$dp[i]+1$取 max 。如果是$<$的話也一樣，因此這就可以用一個區間修改加上單點查詢的線段樹來作了。而因為要輸出解，所以在線段樹上會多紀錄說造成這個最大值的 index 是誰。
再來則是證明為什麼紀錄最長的就可以了，假設以$x$結尾有兩個滿足條件的子序列，長度分別是$L$和$l$，其中$L>l$。記兩個子序列的 index 分別為$i_1,...,i_L$和$j_1,...,j_l$（因此有$i_L=j_l=x$），並且不妨設$s[l]$為$<$（當$s[l]$為$=$時證法幾乎一樣，在此省略），並且此時$x$準備要拿$l+1$去更新$y$的答案。令$z=i_l$，如果$a[z]<a[y]$，那麼在我們前面算到$z$的答案時早就已經拿$l+1$去更新$y$的答案了，因此這個情況下長度$l$的這個子字串是完全沒有用的。反之如果$a[z]\geq a[y]$，由$s[l]$為$<$和$x$要拿長度$l$的子字串去更新$y$的答案可以推出$a[x]<a[y]$，所以有$a[z]\geq a[y]>a[x]$，推得$a[z]>a[x]$，因此考慮子序列$a[i_l],...,a[i_L]$，裡面一定存在相鄰的兩項使得左大於右，也就是存在一個 index $i_u$（$l\leq u < L$），滿足$a[i_u]>a[i_{u+1}]$（這也代表了$s[u]$為$>$）。我們取滿足這個條件的最小的$u$，不難發現$a[z]<a[i_u]$，因此有$a[i_u]>a[z]\geq a[y]$，因此當我們在算完$i_u$的答案時，就會拿$u+1$去更新$y$的答案了，所以在這種情況長度為$l$的子序列也是沒有用的，所以就可以直接不紀錄了。
code :
首先考慮一個樸素的算法：對於每個$i$，我們知道存在一些以$i$結尾的子字串是滿足題目要求的，那麼對每個子字串來說，都可以用他的長度去更新所有$i$之後的答案（依照這個長度時下一步應該要比$a[i]$大還是小，或是等於）。具體來說，如果有一個$i$結尾的子字串長度為$L$，並且$s[L]$為$<$，那麼就可以用$L+1$去更新$i$以後的值大於$a[i]$的位子的答案。這裡有個非常不顯然的結論，就是其實對於所有$i$結尾的子字串，我們只需要紀錄最長那個的長度就可以了！（證明補在後面），因此就可以用 DP 算出每個位子結尾的最長子序列長度了。具體來說，當算完$dp[i]$時，如果$s[dp[i]]$為$<$，那麼之後如果遇到有某個$>a[i]$的數，都要把他的答案和$dp[i]+1$取 max 。如果是$<$的話也一樣，因此這就可以用一個區間修改加上單點查詢的線段樹來作了。而因為要輸出解，所以在線段樹上會多紀錄說造成這個最大值的 index 是誰。
再來則是證明為什麼紀錄最長的就可以了，假設以$x$結尾有兩個滿足條件的子序列，長度分別是$L$和$l$，其中$L>l$。記兩個子序列的 index 分別為$i_1,...,i_L$和$j_1,...,j_l$（因此有$i_L=j_l=x$），並且不妨設$s[l]$為$<$（當$s[l]$為$=$時證法幾乎一樣，在此省略），並且此時$x$準備要拿$l+1$去更新$y$的答案。令$z=i_l$，如果$a[z]<a[y]$，那麼在我們前面算到$z$的答案時早就已經拿$l+1$去更新$y$的答案了，因此這個情況下長度$l$的這個子字串是完全沒有用的。反之如果$a[z]\geq a[y]$，由$s[l]$為$<$和$x$要拿長度$l$的子字串去更新$y$的答案可以推出$a[x]<a[y]$，所以有$a[z]\geq a[y]>a[x]$，推得$a[z]>a[x]$，因此考慮子序列$a[i_l],...,a[i_L]$，裡面一定存在相鄰的兩項使得左大於右，也就是存在一個 index $i_u$（$l\leq u < L$），滿足$a[i_u]>a[i_{u+1}]$（這也代表了$s[u]$為$>$）。我們取滿足這個條件的最小的$u$，不難發現$a[z]<a[i_u]$，因此有$a[i_u]>a[z]\geq a[y]$，因此當我們在算完$i_u$的答案時，就會拿$u+1$去更新$y$的答案了，所以在這種情況長度為$l$的子序列也是沒有用的，所以就可以直接不紀錄了。
code :
2015年7月13日 星期一
[TIOJ 1071] 字串消去問題(Censorship)
作法：
如果我們能計算出一個二維陣列$ok$，其中$ok[i][j]$代表$S[i,...,j]$是否可以恰好被完整刪除，那麼就可以用簡單的DP求出最後答案了。首先我們知道$S$中有許多子字串是可以「直接被刪除的」，也就是他剛好等於給定字串集合裡的其中一個字串。當我們把這種子字串刪掉時，有可能會造成新的子字串可以被刪掉。例如原字串為$caabbd$，並且可以刪掉$ab$，那麼在第二層就可以把$aabb$刪掉了，也就是$ok[2][5]=1$。我們可以概念上的稱「可直接被刪除的子字串」為一級的子字串，需要經過兩層才能刪除的為二級的子字串，那麼可知一個有辦法被刪除的子字串至多$n$層。因此我們要想辦法從$i$級的子字串的$ok$陣列推出$i+1$級的陣列，重複$n$次就可以得到我們要的$ok$陣列了。假設我們現在想知道$S[L,...,R]$這個子字串是否能在第$k+1$層時被刪掉，那麼考慮所有$S[L,...,R]$的可在第$k$層時被刪掉的子字串們，那麼$S[L,...,R]$可以在第$k+1$層時被刪掉若且唯若：存在$(l_1,r_1),...,(l_t,r_t)$滿足$L\leq l_1\leq r_1 < l_2 \leq r_2 < ... < l_t \leq r_t \leq R$，並且$S[l_i,...,r_i]$均可以在第$k$層被刪掉，還有把$S[L,...,R]$扣掉所有$S[l_i,...,r_i]$後所得到的字串是可以直接刪除的。有了這個之後就可以來算$S[L,...,R]$是否可以在第$k+1$層時刪除了。我們從$S[L]$開始往右邊掃，當遇到$S[i]$時，一個決策是：選一個$r$使得$S[i,...,r]$可以被刪除，那麼轉移到$S[r+1]$的狀態。另一個決策則是將$S[i]$放進一個「暫存字串」中，轉移到$S[i+1]$，並且我們想要在處理完$S[R]$時暫存字串是可以一次被刪除的（就和前面的條件等價了）。因此我們可以用一個 trie 節點搭配當前的 index 來做 DP 狀態，設 $dp[x][i]$ 代表只考慮字串$S[L,...,i]$時，是否可以讓「暫存字串」在 trie 上的節點為$x$，這樣就可以$O(1)$轉移了，總複雜度為$O(n^5)$。
code :
如果我們能計算出一個二維陣列$ok$，其中$ok[i][j]$代表$S[i,...,j]$是否可以恰好被完整刪除，那麼就可以用簡單的DP求出最後答案了。首先我們知道$S$中有許多子字串是可以「直接被刪除的」，也就是他剛好等於給定字串集合裡的其中一個字串。當我們把這種子字串刪掉時，有可能會造成新的子字串可以被刪掉。例如原字串為$caabbd$，並且可以刪掉$ab$，那麼在第二層就可以把$aabb$刪掉了，也就是$ok[2][5]=1$。我們可以概念上的稱「可直接被刪除的子字串」為一級的子字串，需要經過兩層才能刪除的為二級的子字串，那麼可知一個有辦法被刪除的子字串至多$n$層。因此我們要想辦法從$i$級的子字串的$ok$陣列推出$i+1$級的陣列，重複$n$次就可以得到我們要的$ok$陣列了。假設我們現在想知道$S[L,...,R]$這個子字串是否能在第$k+1$層時被刪掉，那麼考慮所有$S[L,...,R]$的可在第$k$層時被刪掉的子字串們，那麼$S[L,...,R]$可以在第$k+1$層時被刪掉若且唯若：存在$(l_1,r_1),...,(l_t,r_t)$滿足$L\leq l_1\leq r_1 < l_2 \leq r_2 < ... < l_t \leq r_t \leq R$，並且$S[l_i,...,r_i]$均可以在第$k$層被刪掉，還有把$S[L,...,R]$扣掉所有$S[l_i,...,r_i]$後所得到的字串是可以直接刪除的。有了這個之後就可以來算$S[L,...,R]$是否可以在第$k+1$層時刪除了。我們從$S[L]$開始往右邊掃，當遇到$S[i]$時，一個決策是：選一個$r$使得$S[i,...,r]$可以被刪除，那麼轉移到$S[r+1]$的狀態。另一個決策則是將$S[i]$放進一個「暫存字串」中，轉移到$S[i+1]$，並且我們想要在處理完$S[R]$時暫存字串是可以一次被刪除的（就和前面的條件等價了）。因此我們可以用一個 trie 節點搭配當前的 index 來做 DP 狀態，設 $dp[x][i]$ 代表只考慮字串$S[L,...,i]$時，是否可以讓「暫存字串」在 trie 上的節點為$x$，這樣就可以$O(1)$轉移了，總複雜度為$O(n^5)$。
code :
2015年7月12日 星期日
[TOI 2015 4模] P Game
題目：
給定一棵$n$個點的樹，每條邊都有個長度，然後有$Q$次操作/詢問，每次可以佔領一個點，或是詢問某個點到所有已被佔領的點的距離總和。$n,Q\leq 10^5$。
作法：
這題有兩種作法，第一種作法是用平方分割，因為如果是一次佔領完再全部詢問，那麼我們可以用 DFS $O(n)$ 求出每個點的答案，再$O(1)$回答詢問，詳細作法就不提了。而另外一種作法則是：把所有被佔領的點紀錄下來，每次詢問就直接去詢問給定點和所有被佔領點的距離總和，這樣一次的複雜度會是$O(被佔領點個數\cdot logn)$。於是我們考慮把兩種作法合併，當一個一個佔領點時，如果此時佔領的點還沒有那麼多，則直接用求距離再加起來的作法硬算，而當要硬算的點個數達到某個值（假設為$K$）時，就 DFS 一次把所有點的答案都更新好，這樣在詢問時我們就有了詢問的點到前$K$個被佔領點的距離總和了，剩下的部份就硬算即可。這樣可以得到單次詢問的複雜度為$O(Klogn)$，佔領一個點時因為我們不會 DFS 超過$\frac{Q}{K}$次，因此複雜度會是$O(\frac{Q}{K}n)$。由這兩式就可以知道取$K$讓$QKlogn=\frac{Q}{K}n$會是最好的，移項得$K=\sqrt{\frac{n}{logn}}$，總複雜度為$O(Q\sqrt{nlogn})$。但考試時不知道為什麼怎麼取$K$都TLE，後來乾脆取個$100$還$200$就莫名其妙的過了。
事實上可以做到單次詢問$O(logn)$，用的東西叫重心剖分，他的概念是先對原本的樹取重心，把樹分成很多個子樹，再對這些子樹遞迴下去取重心，並且將原樹的重心和其子樹們的重心連起來，這樣我們就得到了一棵重心樹（重心樹上的邊不一定在原樹上出現，但每個點都出現了），不難證明其深度會是$O(logn)$的（之後稱重心樹上的一個子樹為重心子樹）。因此當詢問一個點$x$的答案時，可以直接沿著重心樹往上走（因此要紀錄好每個點在重心子樹上的父親是誰），並在走的過程維護當前答案等於「$x$到當前重心子樹裡所有已被佔領點的距離總和」，這樣一路走到根就獲得答案了。接下來我們要知道如何維護好答案，記當前重心子樹為$T$，他的根$P$，還有如果只看原樹中這棵重心子樹裡的所有點的話，把$P$拔掉會讓他分成許多（原樹中的）子樹，稱其為$T_1,...,T_r$，並且不妨設$x$落在$T_1$裡面。那麼此時所求答案就必須要增加「$x$到所有$T_2,...,T_r$中被佔領點的距離」。這可以拆成兩部份，因為$x$走到這些點都必須經過$P$，因此如果假設在$T_2,...,T_r$中被佔領的點共有$t$個，那麼就可以把所求改成$t\cdot dist(P,x)+P$到$T_2,...,T_r$中被佔領點的距離總和（其中$dist$ 代表兩點在原樹中的距離）。對於前者，我們可以在預處理時，對於每個重心子樹，把他的根到所有他在重心子樹中的點的（在原樹中的）距離都存起來，這樣就能知道$dist(P,x)$了。再來則是要知道$t$，而這可以用「$T$中的被佔領點數扣掉$T_1$中的被佔領點數」得到，因此只要在多佔領一個點時沿重心樹走上去，維護好每個重心子樹中的被佔領點數就好了。最後則是要知道$P$到$T_2,...,T_r$中所有被佔領點的距離總和，這可以拆成「$P$到$T$中所有被佔領點的距離總和」扣掉「$P$到$T_1$中所有被佔領點的距離總和」，因此也只要在新佔領點時維護好這兩個值就可以了，都是利用到已算好的「重心到其子樹中某個點的距離」。
實作有很多寫法，但大部份都很麻煩，畢竟我們要存$P$的每個子樹的一些資訊，還有$P$到其子樹內每個點的距離。一個比較簡潔的記法是，首先我們先對每個點紀錄他是落在重心樹深度多少的地方，那麼如果我們想要紀錄某個重心$P$到某個點$x$的距離，就把這個值存在$dis[dep[P]][x]$裡面就可以了，其中$dep$代表這個點在重心樹上的深度，不難發現這個存法不會讓兩個要存的東西碰撞。再來也蠻麻煩的則是要存：對於每個重心$P$，紀錄他的每個子樹中被佔領的點離他的距離總和，而這也可以只用一個陣列來存，假設$P$在重心樹上落在$T_1$的子節點為$Q$，那麼就直接把$P$到$T_1$中被佔領點的距離總和存到$Q$的位子就可以了，也不難發現這樣不會碰撞。另外剩下的「$P$這個重心子樹中所有被佔領點到他的距離總和和有幾個被佔領點」當然只要存在$P$的位子就可以了。
code :
給定一棵$n$個點的樹，每條邊都有個長度，然後有$Q$次操作/詢問，每次可以佔領一個點，或是詢問某個點到所有已被佔領的點的距離總和。$n,Q\leq 10^5$。
作法：
這題有兩種作法，第一種作法是用平方分割，因為如果是一次佔領完再全部詢問，那麼我們可以用 DFS $O(n)$ 求出每個點的答案，再$O(1)$回答詢問，詳細作法就不提了。而另外一種作法則是：把所有被佔領的點紀錄下來，每次詢問就直接去詢問給定點和所有被佔領點的距離總和，這樣一次的複雜度會是$O(被佔領點個數\cdot logn)$。於是我們考慮把兩種作法合併，當一個一個佔領點時，如果此時佔領的點還沒有那麼多，則直接用求距離再加起來的作法硬算，而當要硬算的點個數達到某個值（假設為$K$）時，就 DFS 一次把所有點的答案都更新好，這樣在詢問時我們就有了詢問的點到前$K$個被佔領點的距離總和了，剩下的部份就硬算即可。這樣可以得到單次詢問的複雜度為$O(Klogn)$，佔領一個點時因為我們不會 DFS 超過$\frac{Q}{K}$次，因此複雜度會是$O(\frac{Q}{K}n)$。由這兩式就可以知道取$K$讓$QKlogn=\frac{Q}{K}n$會是最好的，移項得$K=\sqrt{\frac{n}{logn}}$，總複雜度為$O(Q\sqrt{nlogn})$。但考試時不知道為什麼怎麼取$K$都TLE，後來乾脆取個$100$還$200$就莫名其妙的過了。
事實上可以做到單次詢問$O(logn)$，用的東西叫重心剖分，他的概念是先對原本的樹取重心，把樹分成很多個子樹，再對這些子樹遞迴下去取重心，並且將原樹的重心和其子樹們的重心連起來，這樣我們就得到了一棵重心樹（重心樹上的邊不一定在原樹上出現，但每個點都出現了），不難證明其深度會是$O(logn)$的（之後稱重心樹上的一個子樹為重心子樹）。因此當詢問一個點$x$的答案時，可以直接沿著重心樹往上走（因此要紀錄好每個點在重心子樹上的父親是誰），並在走的過程維護當前答案等於「$x$到當前重心子樹裡所有已被佔領點的距離總和」，這樣一路走到根就獲得答案了。接下來我們要知道如何維護好答案，記當前重心子樹為$T$，他的根$P$，還有如果只看原樹中這棵重心子樹裡的所有點的話，把$P$拔掉會讓他分成許多（原樹中的）子樹，稱其為$T_1,...,T_r$，並且不妨設$x$落在$T_1$裡面。那麼此時所求答案就必須要增加「$x$到所有$T_2,...,T_r$中被佔領點的距離」。這可以拆成兩部份，因為$x$走到這些點都必須經過$P$，因此如果假設在$T_2,...,T_r$中被佔領的點共有$t$個，那麼就可以把所求改成$t\cdot dist(P,x)+P$到$T_2,...,T_r$中被佔領點的距離總和（其中$dist$ 代表兩點在原樹中的距離）。對於前者，我們可以在預處理時，對於每個重心子樹，把他的根到所有他在重心子樹中的點的（在原樹中的）距離都存起來，這樣就能知道$dist(P,x)$了。再來則是要知道$t$，而這可以用「$T$中的被佔領點數扣掉$T_1$中的被佔領點數」得到，因此只要在多佔領一個點時沿重心樹走上去，維護好每個重心子樹中的被佔領點數就好了。最後則是要知道$P$到$T_2,...,T_r$中所有被佔領點的距離總和，這可以拆成「$P$到$T$中所有被佔領點的距離總和」扣掉「$P$到$T_1$中所有被佔領點的距離總和」，因此也只要在新佔領點時維護好這兩個值就可以了，都是利用到已算好的「重心到其子樹中某個點的距離」。
實作有很多寫法，但大部份都很麻煩，畢竟我們要存$P$的每個子樹的一些資訊，還有$P$到其子樹內每個點的距離。一個比較簡潔的記法是，首先我們先對每個點紀錄他是落在重心樹深度多少的地方，那麼如果我們想要紀錄某個重心$P$到某個點$x$的距離，就把這個值存在$dis[dep[P]][x]$裡面就可以了，其中$dep$代表這個點在重心樹上的深度，不難發現這個存法不會讓兩個要存的東西碰撞。再來也蠻麻煩的則是要存：對於每個重心$P$，紀錄他的每個子樹中被佔領的點離他的距離總和，而這也可以只用一個陣列來存，假設$P$在重心樹上落在$T_1$的子節點為$Q$，那麼就直接把$P$到$T_1$中被佔領點的距離總和存到$Q$的位子就可以了，也不難發現這樣不會碰撞。另外剩下的「$P$這個重心子樹中所有被佔領點到他的距離總和和有幾個被佔領點」當然只要存在$P$的位子就可以了。
code :
2015年7月11日 星期六
[POI 13 Stage 3] Palindromes
作法：
考慮把兩個不同的字串$S_1,S_2$接起來會形成回文，不妨設$|S_1|\leq |S_2|$，那麼不難推得他是回文的充要條件為：$S_1$是$S_2$的前綴，並且$S_2$的長度為$|S_2|-|S_1|$的前綴也是回文。因此我們可以考慮先建一個 trie ，那麼就可以得出：對每個字串$S$來說，有幾個字串恰好為$S$的長度為$i$的前綴。並且再用 manacher 處理一個字串的子字串是否為回文的詢問就可以了。但直接建 trie 會 MLE ，因為一個 node 存 26 個子節點太浪費了，於是我苦苦的把子節點的紀錄方式改成用 treap 才過，詳細就參考 code 吧。
code :
考慮把兩個不同的字串$S_1,S_2$接起來會形成回文，不妨設$|S_1|\leq |S_2|$，那麼不難推得他是回文的充要條件為：$S_1$是$S_2$的前綴，並且$S_2$的長度為$|S_2|-|S_1|$的前綴也是回文。因此我們可以考慮先建一個 trie ，那麼就可以得出：對每個字串$S$來說，有幾個字串恰好為$S$的長度為$i$的前綴。並且再用 manacher 處理一個字串的子字串是否為回文的詢問就可以了。但直接建 trie 會 MLE ，因為一個 node 存 26 個子節點太浪費了，於是我苦苦的把子節點的紀錄方式改成用 treap 才過，詳細就參考 code 吧。
code :
2015年7月9日 星期四
[POI 12 Stage 2] Template
作法：
首先求出每個點的 Z value ，假設$L$是一個答案，那就代表如果只看字串中那些 Z value $\geq L$的位子，這些位置的相鄰位置的差不會超過$L$。因此我們就可以考慮由小到大枚舉$L$，維護好當前有哪些位置的 Z value $\geq L$，並維護相鄰位置的差的最大值，用可以用個 set 做到這件事。每次把新的數移除的時候就看看他的左右兩個數，並拿這兩個數的差來更新當前的相鄰位置差的最大值。不過實際上用個 linked list 就可以了，複雜度降為$O(n)$。
code :
首先求出每個點的 Z value ，假設$L$是一個答案，那就代表如果只看字串中那些 Z value $\geq L$的位子，這些位置的相鄰位置的差不會超過$L$。因此我們就可以考慮由小到大枚舉$L$，維護好當前有哪些位置的 Z value $\geq L$，並維護相鄰位置的差的最大值，用可以用個 set 做到這件事。每次把新的數移除的時候就看看他的左右兩個數，並拿這兩個數的差來更新當前的相鄰位置差的最大值。不過實際上用個 linked list 就可以了，複雜度降為$O(n)$。
code :
[POI 19 Stage 3] Prefixuffix
作法：
假設長度為$L$的前綴後綴為答案，那麼可以知道一定存在一個$k$，使得$S[1,...,k]$和$S[n-k+1,...,n]$長的一模一樣，並且$S[k+1,...,L]$和$S[n-L+1...n-k]$一模一樣（跟題目條件等價）。前面的條件很好檢查，不管是用 hash 還是 Z value 都可以。至於後面那個條件，這時我們需要知道：給定一個$i$，找出最長的長度$L$使得$S[i,...,n+1-i]$這個字串的長$L$的前綴和長$L$的後綴長的一模一樣。也就是我們關心的是位子關於整個字串中點對稱的長的一模一樣的字串。具體來說就是一些$(x,y)$滿足$S[x,...,y]$和$S[n+1-y,...,n+1-x]$長的一模一樣。我們考慮枚舉$(x,y)$數對的中點，那麼可以先二分搜出以某個點為中點的話滿足條件的$(x,y)$最多可以擴展到哪裡（因為有個性質是$(x,y)$滿足的話$(x+1,y-1)$也滿足）。假設我們二分搜出了$(L,R)$這段區間是滿足的，也就是$S[L,...,R]=S[n+1-R,...,n+1-L]$，並且$(L-1,R+1)$不滿足，令$len[i]$代表最大的「滿足$S[i+1,...,n-i]$的長$len[i]$的前綴和長$len[i]$的」的數，那麼這時就要用$R-L+1$去更新$len[L-1]$，$R-L-1$去更新$len[L]$，以此類推直到更新的值$<0$為止。這樣就可以直接往左往右掃得到每個$len$值了，只要當我們收到「把$a$和$x$取 max ，把$a+1$和$x-2$取 max ，...」時在$a$上紀錄$x+2a$的值，並在掃描過程中維護好這個數的值的最大值就可以了。
code :
假設長度為$L$的前綴後綴為答案，那麼可以知道一定存在一個$k$，使得$S[1,...,k]$和$S[n-k+1,...,n]$長的一模一樣，並且$S[k+1,...,L]$和$S[n-L+1...n-k]$一模一樣（跟題目條件等價）。前面的條件很好檢查，不管是用 hash 還是 Z value 都可以。至於後面那個條件，這時我們需要知道：給定一個$i$，找出最長的長度$L$使得$S[i,...,n+1-i]$這個字串的長$L$的前綴和長$L$的後綴長的一模一樣。也就是我們關心的是位子關於整個字串中點對稱的長的一模一樣的字串。具體來說就是一些$(x,y)$滿足$S[x,...,y]$和$S[n+1-y,...,n+1-x]$長的一模一樣。我們考慮枚舉$(x,y)$數對的中點，那麼可以先二分搜出以某個點為中點的話滿足條件的$(x,y)$最多可以擴展到哪裡（因為有個性質是$(x,y)$滿足的話$(x+1,y-1)$也滿足）。假設我們二分搜出了$(L,R)$這段區間是滿足的，也就是$S[L,...,R]=S[n+1-R,...,n+1-L]$，並且$(L-1,R+1)$不滿足，令$len[i]$代表最大的「滿足$S[i+1,...,n-i]$的長$len[i]$的前綴和長$len[i]$的」的數，那麼這時就要用$R-L+1$去更新$len[L-1]$，$R-L-1$去更新$len[L]$，以此類推直到更新的值$<0$為止。這樣就可以直接往左往右掃得到每個$len$值了，只要當我們收到「把$a$和$x$取 max ，把$a+1$和$x-2$取 max ，...」時在$a$上紀錄$x+2a$的值，並在掃描過程中維護好這個數的值的最大值就可以了。
code :
2015年7月8日 星期三
[POI 19 Stage 2] A Horrible Poem
作法：
考慮枚舉所求子字串的長度$L$，我們知道$L$是給定子字串長度的因數，所以可以只枚舉其因數就可以了。確定$L$之後，假設詢問的區間為$[x,y]$，那麼判斷這個$L$是否可以的方法就只要看$[x,y-L]$和$[x+L,y]$這兩個字串是否一模一樣就可以了，證明並不難。而只要用 hash 就可以$O(1)$判斷了，因此就得到了一個$O(logn)$的解。但這樣傳上去 TLE 了，而只要再注意到：假設詢問的區間中有$x_1$個$a$，那麼分的塊數也一定要是$x_1$的因數，這樣就又縮減一些可能性了。因此我們變成枚舉切的塊數，所有的可能會是某個數的因數，直接用$O(\sqrt{n})$的找因數方法就可以了。
code :
考慮枚舉所求子字串的長度$L$，我們知道$L$是給定子字串長度的因數，所以可以只枚舉其因數就可以了。確定$L$之後，假設詢問的區間為$[x,y]$，那麼判斷這個$L$是否可以的方法就只要看$[x,y-L]$和$[x+L,y]$這兩個字串是否一模一樣就可以了，證明並不難。而只要用 hash 就可以$O(1)$判斷了，因此就得到了一個$O(logn)$的解。但這樣傳上去 TLE 了，而只要再注意到：假設詢問的區間中有$x_1$個$a$，那麼分的塊數也一定要是$x_1$的因數，這樣就又縮減一些可能性了。因此我們變成枚舉切的塊數，所有的可能會是某個數的因數，直接用$O(\sqrt{n})$的找因數方法就可以了。
code :
2015年7月6日 星期一
[CF 451E] Devu and Flowers
作法：
簡單來說就是要問滿足$a_1+...+a_n=s$的$n$元組$(a_1,...,a_n)$的個數，並且$a_i\leq f_i$。記「滿足$a_i>f_i$且總和為$s$的$n$元組集合」為$A_i$，那麼所求就會是「總和為$s$的$n$元組」個數扣掉$|A_1\bigcup ... \bigcup A_n|$，因此可以考慮用排容原理。首先看所求的第一項，直接用排列組合的公式可以得到等於$C_{n-1}^{n+s-1}$，這東西直接算就可以了。接下來要考慮$A_i$的部份，我們想要知道好幾個$A_i$交集起來的大小為多少。假設現在我們要算$|A_{c_1}\bigcap ... \bigcap A_{c_r}|$，那麼就是對於每個$i$，都有$a_{c_i}>f_{c_i}$，因此我們先把$s$分給$a_{c_1},...,a_{c_r}$各$f_{c_1}+1,...,f_{c_r}+1$個，剩下再用排列組合的公式算就可以了。因此排容的過程就可以用個 DFS 來做，詳細可以參考 code 比較清楚。
code :
簡單來說就是要問滿足$a_1+...+a_n=s$的$n$元組$(a_1,...,a_n)$的個數，並且$a_i\leq f_i$。記「滿足$a_i>f_i$且總和為$s$的$n$元組集合」為$A_i$，那麼所求就會是「總和為$s$的$n$元組」個數扣掉$|A_1\bigcup ... \bigcup A_n|$，因此可以考慮用排容原理。首先看所求的第一項，直接用排列組合的公式可以得到等於$C_{n-1}^{n+s-1}$，這東西直接算就可以了。接下來要考慮$A_i$的部份，我們想要知道好幾個$A_i$交集起來的大小為多少。假設現在我們要算$|A_{c_1}\bigcap ... \bigcap A_{c_r}|$，那麼就是對於每個$i$，都有$a_{c_i}>f_{c_i}$，因此我們先把$s$分給$a_{c_1},...,a_{c_r}$各$f_{c_1}+1,...,f_{c_r}+1$個，剩下再用排列組合的公式算就可以了。因此排容的過程就可以用個 DFS 來做，詳細可以參考 code 比較清楚。
code :
[HOJ 329] Construct?!
作法：
假設我們交換的兩數分別為$x,y$，那麼對於那些數值不是落在$x,y$之間的數，交換之後並不會影響這些數和$x,y$之間的逆序數對數，不管這些數落在交換的兩位置的左右還是中間。對於那些數值落在$x,y$之間的數，只有當他的位子落在交換的兩數字位置之間才會影響逆序數對的數量。由此就可以推出，我們交換的兩個數一定是左邊大右邊小的，才可以讓交換後逆序數對減少越多。假設交換的兩數位置分別為$i,j$，數字則為$x,y$，那麼逆序數對的變化就會等於$2\times $位子落在$i,j$之間的介於$x,y$之間數的個數$+1$（還要加上交換的兩數形成的逆序數對）。這樣就可以轉化為平面上點集的問題了：把$(i,a[i])$看成座標平面上的點，那麼我們要的就是一個矩形的左上角和右下角，使得這個矩形內包含最多的點。考慮所有「左上方沒有點」的點，那麼不難知道所求矩形的左上角一定是取其中的某個點是最好的。同理所求的右下角是取「右下方沒有點」的點是最好的。我們可以$O(n)$找出所有的這樣的點（之後分別叫他們$X$陣列和$Y$陣列），所以現在我們得到了一個樸素的算法：在這些點之間枚舉左上角和右下角，計算其中包含了多少點。但這樣太慢了，我們反過來考慮一個點對哪些矩形有貢獻，對於某個點$P$，考慮所有落在$P$左上方的$X$陣列中的點，和落在$P$右下方的$Y$陣列中的點，那麼任取前者中的一個點和後者中的一個點形成的矩形都可以包住這個點，因此如果我們幫$X$陣列中的數編號$1,...,n_x$，$Y$陣列則編號$1,...,n_y$，那麼一個矩形就可以表示成一個平面上的點，以左上角的編號和右下角的編號來表示。並且我們把每個矩形內的點數寫在他對應的點上，那麼就可以用以下方式來得到所有點的數值：枚舉每個原題中的點，找出他對哪些矩形有貢獻，而被貢獻的這些矩形們的集合對應到的點就會形成一個矩形區域，並且我們需要把這個矩形區域中的點值都$+1$。於是這樣就轉換為新的問題了：平面上有好幾個矩形，問被最多矩形覆蓋的點被覆蓋了幾次，而這可以用個掃描線來做，只需要維護一個最大值線段樹，並支援區間加值操作就可以了。
code :
假設我們交換的兩數分別為$x,y$，那麼對於那些數值不是落在$x,y$之間的數，交換之後並不會影響這些數和$x,y$之間的逆序數對數，不管這些數落在交換的兩位置的左右還是中間。對於那些數值落在$x,y$之間的數，只有當他的位子落在交換的兩數字位置之間才會影響逆序數對的數量。由此就可以推出，我們交換的兩個數一定是左邊大右邊小的，才可以讓交換後逆序數對減少越多。假設交換的兩數位置分別為$i,j$，數字則為$x,y$，那麼逆序數對的變化就會等於$2\times $位子落在$i,j$之間的介於$x,y$之間數的個數$+1$（還要加上交換的兩數形成的逆序數對）。這樣就可以轉化為平面上點集的問題了：把$(i,a[i])$看成座標平面上的點，那麼我們要的就是一個矩形的左上角和右下角，使得這個矩形內包含最多的點。考慮所有「左上方沒有點」的點，那麼不難知道所求矩形的左上角一定是取其中的某個點是最好的。同理所求的右下角是取「右下方沒有點」的點是最好的。我們可以$O(n)$找出所有的這樣的點（之後分別叫他們$X$陣列和$Y$陣列），所以現在我們得到了一個樸素的算法：在這些點之間枚舉左上角和右下角，計算其中包含了多少點。但這樣太慢了，我們反過來考慮一個點對哪些矩形有貢獻，對於某個點$P$，考慮所有落在$P$左上方的$X$陣列中的點，和落在$P$右下方的$Y$陣列中的點，那麼任取前者中的一個點和後者中的一個點形成的矩形都可以包住這個點，因此如果我們幫$X$陣列中的數編號$1,...,n_x$，$Y$陣列則編號$1,...,n_y$，那麼一個矩形就可以表示成一個平面上的點，以左上角的編號和右下角的編號來表示。並且我們把每個矩形內的點數寫在他對應的點上，那麼就可以用以下方式來得到所有點的數值：枚舉每個原題中的點，找出他對哪些矩形有貢獻，而被貢獻的這些矩形們的集合對應到的點就會形成一個矩形區域，並且我們需要把這個矩形區域中的點值都$+1$。於是這樣就轉換為新的問題了：平面上有好幾個矩形，問被最多矩形覆蓋的點被覆蓋了幾次，而這可以用個掃描線來做，只需要維護一個最大值線段樹，並支援區間加值操作就可以了。
code :
2015年7月5日 星期日
[CF 449E] Jzzhu and Squares
作法：
考慮一個斜的正方形，設他下面頂點指向右邊頂點的向量為$(x,y)$（也就是如果下端點是$(0,0)$，那麼剩下三個點的座標為$(x,y),(x-y,x+y),(-y,x)$），我們想要知道這個正方形裡面包含了幾個單位正方形，而一個著名的結論是：給定一個$n\times m$的方格表，那麼他的對角線會經過$n+m-gcd(n,m)$個格點。因此就可以用這個結論算出這個正方形包住了幾個單位正方形了：把這個正方形補成邊平形座標軸的正方形，並把他切成四個$x\times y$的長方形，還有中間邊長$|x-y|$的正方形。那麼就可以知道在四個長方形中分別包含了$\frac{xy-x-y+gcd(x,y)}{2}$個所求格子了，再加上中間的正方形$(x-y)^2$個，就共有$(x-y)^2+2(xy-x-y+gcd(x,y))=x^2+y^2-2(x+y-gcd(x,y))$個。並且注意到這種正方形因為要用長$x+y$的正方形包住他，所以會在原本給定的範圍裡出現$(n-x-y+1)(m-x-y+1)$次，其中$x+y\leq min(n,m)$。並且注意到我們也要算$x=0$的情況（上面通式也會對），但是不能也算$y=0$的，否則會重複算到。因此就可以把答案寫成：
$\displaystyle \sum_{x\geq 0,y>0,x+y\leq min(n,m)} (n-x-y+1)(m-x-y+1)(x^2+y^2-2(x+y-gcd(x,y)))$
考慮把$x+y$值相同的一起算，令$t=x+y$，那麼就可以改寫成：
$\displaystyle \sum_{t=1}^{min(n,m)}\sum_{x=0}^{t-1} (n-t+1)(m-t+1)(x^2+(t-x)^2-2t+2gcd(t,x))$
其中用到了簡單的$gcd$的性質：$gcd(x,t-x)=gcd(x,t)$。我們可以把所求的$gcd$的部份拆出來，也就是改寫成
$\displaystyle \sum_{t=1}^{min(n,m)}\sum_{x=0}^{t-1} (n-t+1)(m-t+1)(x^2+(t-x)^2-2t)+$$\displaystyle 2\sum_{t=1}^{min(n,m)}\sum_{x=0}^{t-1} (n-t+1)(m-t+1)gcd(t,x)$
首先第一項其實就是一個$t$的多項式，只是係數會有$n,m$之類的，因此我們可以先預處理好$t^i$的前綴和陣列，其中$i=1,...,6$，就可以在$O(1)$算出第一項了（或是借住電腦的力量直接把通式爆出來XD）。再來則是第二項，把$(n-t+1)(m-t+1)$乘開後會得到其實我們主要需要的東西就是$\displaystyle \sum_{x=0}^{t-1} gcd(t,x)$，還有$\displaystyle \sum_{x=0}^{t-1} t\cdot gcd(t,x)$和$\displaystyle \sum_{x=0}^{t-1} t^2\cdot gcd(t,x)$的前綴和陣列，而我們只要有辦法對每個$t$都算出$\displaystyle \sum_{x=0}^{t-1} gcd(t,x)$的值就可以了。記我們要求的這個陣列為$f$，我們看某個數$i$在哪些$gcd(t,x)$的項出現了，首先$i$要整除$t$，因此只有index 被$i$整除的$f$值要加上一些$i$。至於要加上多少個$i$，因為$gcd(t,x)=i$，所以我們也可以設$x=y\cdot i$，其中$y<\frac{t}{i}$。這樣就可以兩邊同除以$i$，變成$gcd(\frac{t}{i},y)=1$，因此我們需要知道$1,...,\frac{t}{i}-1$中有幾個數和$\frac{t}{i}$互質，這正是歐拉函數 phi ，因此只要先預處理好每個數的 phi 值，再用他算出$f$陣列的值就可以了。
code :
考慮一個斜的正方形，設他下面頂點指向右邊頂點的向量為$(x,y)$（也就是如果下端點是$(0,0)$，那麼剩下三個點的座標為$(x,y),(x-y,x+y),(-y,x)$），我們想要知道這個正方形裡面包含了幾個單位正方形，而一個著名的結論是：給定一個$n\times m$的方格表，那麼他的對角線會經過$n+m-gcd(n,m)$個格點。因此就可以用這個結論算出這個正方形包住了幾個單位正方形了：把這個正方形補成邊平形座標軸的正方形，並把他切成四個$x\times y$的長方形，還有中間邊長$|x-y|$的正方形。那麼就可以知道在四個長方形中分別包含了$\frac{xy-x-y+gcd(x,y)}{2}$個所求格子了，再加上中間的正方形$(x-y)^2$個，就共有$(x-y)^2+2(xy-x-y+gcd(x,y))=x^2+y^2-2(x+y-gcd(x,y))$個。並且注意到這種正方形因為要用長$x+y$的正方形包住他，所以會在原本給定的範圍裡出現$(n-x-y+1)(m-x-y+1)$次，其中$x+y\leq min(n,m)$。並且注意到我們也要算$x=0$的情況（上面通式也會對），但是不能也算$y=0$的，否則會重複算到。因此就可以把答案寫成：
$\displaystyle \sum_{x\geq 0,y>0,x+y\leq min(n,m)} (n-x-y+1)(m-x-y+1)(x^2+y^2-2(x+y-gcd(x,y)))$
考慮把$x+y$值相同的一起算，令$t=x+y$，那麼就可以改寫成：
$\displaystyle \sum_{t=1}^{min(n,m)}\sum_{x=0}^{t-1} (n-t+1)(m-t+1)(x^2+(t-x)^2-2t+2gcd(t,x))$
其中用到了簡單的$gcd$的性質：$gcd(x,t-x)=gcd(x,t)$。我們可以把所求的$gcd$的部份拆出來，也就是改寫成
$\displaystyle \sum_{t=1}^{min(n,m)}\sum_{x=0}^{t-1} (n-t+1)(m-t+1)(x^2+(t-x)^2-2t)+$$\displaystyle 2\sum_{t=1}^{min(n,m)}\sum_{x=0}^{t-1} (n-t+1)(m-t+1)gcd(t,x)$
首先第一項其實就是一個$t$的多項式，只是係數會有$n,m$之類的，因此我們可以先預處理好$t^i$的前綴和陣列，其中$i=1,...,6$，就可以在$O(1)$算出第一項了（或是借住電腦的力量直接把通式爆出來XD）。再來則是第二項，把$(n-t+1)(m-t+1)$乘開後會得到其實我們主要需要的東西就是$\displaystyle \sum_{x=0}^{t-1} gcd(t,x)$，還有$\displaystyle \sum_{x=0}^{t-1} t\cdot gcd(t,x)$和$\displaystyle \sum_{x=0}^{t-1} t^2\cdot gcd(t,x)$的前綴和陣列，而我們只要有辦法對每個$t$都算出$\displaystyle \sum_{x=0}^{t-1} gcd(t,x)$的值就可以了。記我們要求的這個陣列為$f$，我們看某個數$i$在哪些$gcd(t,x)$的項出現了，首先$i$要整除$t$，因此只有index 被$i$整除的$f$值要加上一些$i$。至於要加上多少個$i$，因為$gcd(t,x)=i$，所以我們也可以設$x=y\cdot i$，其中$y<\frac{t}{i}$。這樣就可以兩邊同除以$i$，變成$gcd(\frac{t}{i},y)=1$，因此我們需要知道$1,...,\frac{t}{i}-1$中有幾個數和$\frac{t}{i}$互質，這正是歐拉函數 phi ，因此只要先預處理好每個數的 phi 值，再用他算出$f$陣列的值就可以了。
code :
2015年7月4日 星期六
[CF 449D] Jzzhu and Numbers
作法：
考慮一個$n\times 20$的表格，其中第$i$列就是把第$i$個數的二進制表示寫成橫的放在表格中。現在我們要算的東西是：要選出好幾個橫排，使得這些橫排的每個直行裡都至少有一個$0$，我們反過來看單一一個直行中的所有$1$形成的一個$\{ 1,2,...,n \}$的子集合，假設第$i$個直行的這樣的集合為$S_i$（$i=0,...,19$），那麼對於某個集合$T$來說，如果他是某個$S_i$的子集合，那麼$T$就是不符合條件的集合，並且反過來也是對的。因此我們只要算出「$S_0,...,S_{19}$總共有多少種不重複的子集合」就可以了。這可以用排容算，因為「$S_i$的所有子集合」可以看成一個集合，我們要算的就是這$20$個集合的聯集大小。因此我們需要知道：給定一個$\{0,...,19\}$的子集合${c_1,...,c_r}$，那麼$S_{c_1}\bigcap ... \bigcap S_{c_r}$中共有幾個數，對於所有$\{0,...,19\}$的子集合都必須知道這件事的答案。這裡要觀察到，如果$x\in S_{c_1}\bigcap ... \bigcap S_{c_r}$，那麼代表在第$x$列中的第$c_1,...,c_r$個位子都是$1$，也就是可以改寫為$a[x]\& S = S$，其中$S$代表$c_1,...,c_r$用位元壓起來的數。有了這件事之後，假設我們要算的陣列叫$num$陣列（也就是$num[S]$代表上述所說的$S_{c_1}\bigcap ... \bigcap S_{c_r}$大小，其中$S$是由$c_1,...,c_r$位元壓縮起來的）（大小為$2^{20}$），那麼就可以從另一個角度去算$num$陣列，就是在讀入一個$a[i]$時，將所有滿足$S\& a[i]=S$的$S$的$num$值都$+1$（或是說把輸入的$a[i]$看成一個集合的 bit ，那麼舊把這集合的子集合對應的 index 的$num$值都$+1$），那麼全部讀完後就會是我們要的$num$陣列了。而上面這件事又等價於：記$f[x]$代表在輸入中有幾個$x$，那麼$num[S]$的值就會等於所有$f[x]$的值，其中$x$滿足$x\& S=S$（或是說$x$是$S$的子集）。我們考慮固定$S$時要怎麼求出$num[S]$的值，例如$S$的二進制長的像$1010$好了，那麼就直接從最左邊那位往右 DFS 下去，遇到$1$的話代表這位只能放$1$，遇到$0$則代表這位可以放$1$或$0$，這樣我們會DFS到的數就會是$1010,1011,1110,1111$，恰好是所有滿足$S\& x=S$的$x$，把他們的$f$值加起來就是我們要的答案了。觀察剛才DFS的過程，我們可以用「當前已經確定到第幾位了」還有「當前的數字是多少」來當作傳入DFS的參數，那麼就不難發現這其實可以改成一個DP了（$dp[21][2^{20}]$），並且轉移式只要看DFS時是怎麼求答案的就可以了。邊界為當所有位子都確定時就回傳$f$的值，也就是$dp[20][i]=f[i]$。
code :
考慮一個$n\times 20$的表格，其中第$i$列就是把第$i$個數的二進制表示寫成橫的放在表格中。現在我們要算的東西是：要選出好幾個橫排，使得這些橫排的每個直行裡都至少有一個$0$，我們反過來看單一一個直行中的所有$1$形成的一個$\{ 1,2,...,n \}$的子集合，假設第$i$個直行的這樣的集合為$S_i$（$i=0,...,19$），那麼對於某個集合$T$來說，如果他是某個$S_i$的子集合，那麼$T$就是不符合條件的集合，並且反過來也是對的。因此我們只要算出「$S_0,...,S_{19}$總共有多少種不重複的子集合」就可以了。這可以用排容算，因為「$S_i$的所有子集合」可以看成一個集合，我們要算的就是這$20$個集合的聯集大小。因此我們需要知道：給定一個$\{0,...,19\}$的子集合${c_1,...,c_r}$，那麼$S_{c_1}\bigcap ... \bigcap S_{c_r}$中共有幾個數，對於所有$\{0,...,19\}$的子集合都必須知道這件事的答案。這裡要觀察到，如果$x\in S_{c_1}\bigcap ... \bigcap S_{c_r}$，那麼代表在第$x$列中的第$c_1,...,c_r$個位子都是$1$，也就是可以改寫為$a[x]\& S = S$，其中$S$代表$c_1,...,c_r$用位元壓起來的數。有了這件事之後，假設我們要算的陣列叫$num$陣列（也就是$num[S]$代表上述所說的$S_{c_1}\bigcap ... \bigcap S_{c_r}$大小，其中$S$是由$c_1,...,c_r$位元壓縮起來的）（大小為$2^{20}$），那麼就可以從另一個角度去算$num$陣列，就是在讀入一個$a[i]$時，將所有滿足$S\& a[i]=S$的$S$的$num$值都$+1$（或是說把輸入的$a[i]$看成一個集合的 bit ，那麼舊把這集合的子集合對應的 index 的$num$值都$+1$），那麼全部讀完後就會是我們要的$num$陣列了。而上面這件事又等價於：記$f[x]$代表在輸入中有幾個$x$，那麼$num[S]$的值就會等於所有$f[x]$的值，其中$x$滿足$x\& S=S$（或是說$x$是$S$的子集）。我們考慮固定$S$時要怎麼求出$num[S]$的值，例如$S$的二進制長的像$1010$好了，那麼就直接從最左邊那位往右 DFS 下去，遇到$1$的話代表這位只能放$1$，遇到$0$則代表這位可以放$1$或$0$，這樣我們會DFS到的數就會是$1010,1011,1110,1111$，恰好是所有滿足$S\& x=S$的$x$，把他們的$f$值加起來就是我們要的答案了。觀察剛才DFS的過程，我們可以用「當前已經確定到第幾位了」還有「當前的數字是多少」來當作傳入DFS的參數，那麼就不難發現這其實可以改成一個DP了（$dp[21][2^{20}]$），並且轉移式只要看DFS時是怎麼求答案的就可以了。邊界為當所有位子都確定時就回傳$f$的值，也就是$dp[20][i]=f[i]$。
code :
[CF 449C] Jzzhu and Apples
作法：
我一開始是考慮一個構造：從$2$開始枚舉質數，當枚舉到一個質數$p$時，考慮所有被他整除且還沒被用過的數，如果有偶數個就全部連完，如果有奇數個就想辦法留一個下來。但後來發現不管留哪個都不對，例如當$p=2$且$n=6$時必須留$6$，$n=10$時則必須留$10$。而如果質數枚舉是從$3$開始，把$2$放在最後一個，並且如果$p$的倍數裡有奇數個沒被用過，就把$2p$留下來，這樣就可以把所有有辦法被選的數都選到了。（沒辦法被選到的點有$1$和比$\frac{n}{2}$大的質數）
code :
我一開始是考慮一個構造：從$2$開始枚舉質數，當枚舉到一個質數$p$時，考慮所有被他整除且還沒被用過的數，如果有偶數個就全部連完，如果有奇數個就想辦法留一個下來。但後來發現不管留哪個都不對，例如當$p=2$且$n=6$時必須留$6$，$n=10$時則必須留$10$。而如果質數枚舉是從$3$開始，把$2$放在最後一個，並且如果$p$的倍數裡有奇數個沒被用過，就把$2p$留下來，這樣就可以把所有有辦法被選的數都選到了。（沒辦法被選到的點有$1$和比$\frac{n}{2}$大的質數）
code :
[CF 449B] Jzzhu and Cities
作法：
考慮先建出這張圖的最短路徑圖，並且他是有向的。那麼對於那些不在最短路徑圖的中的鐵軌邊就顯然可以拔掉了。在最短路徑圖中，如果$1$有連向$x$的邊，並且$1$有另一種走法可以走到$x$，那麼$1$連向$x$的這條邊就可以拔了（注意到如果單單只是$1$有兩種走法走到$x$，那麼是沒有邊可以拔的）。而這其實等價於$x$的入度$>1$，因此只要對每個鐵路終點都判斷這件事就可以了。
code :
考慮先建出這張圖的最短路徑圖，並且他是有向的。那麼對於那些不在最短路徑圖的中的鐵軌邊就顯然可以拔掉了。在最短路徑圖中，如果$1$有連向$x$的邊，並且$1$有另一種走法可以走到$x$，那麼$1$連向$x$的這條邊就可以拔了（注意到如果單單只是$1$有兩種走法走到$x$，那麼是沒有邊可以拔的）。而這其實等價於$x$的入度$>1$，因此只要對每個鐵路終點都判斷這件事就可以了。
code :
[CF 449A] Jzzhu and Chocolate
作法：
假設橫著切了$a$刀，直著切了$b$刀，那麼所求就會是$\left \lfloor \frac{n}{a+1} \right \rfloor\cdot \left \lfloor \frac{m}{b+1} \right \rfloor$，其中$a,b\geq 0$，並且$a+b=k$。可以先改成$\left \lfloor \frac{n}{x} \right \rfloor\cdot \left \lfloor \frac{m}{y} \right \rfloor$，其中$x,y\geq 1$，並且$x+y=k+2$，等等會比較好處理。枚舉所有的$x$顯然是不行的，而因為這條式子有高斯，所以可以用常見的優化方法，因為當上式中$x$慢慢增加時，$\left \lfloor \frac{n}{x} \right \rfloor$的值會在連續的區間保持不變。具體來說，設此時$\left \lfloor \frac{n}{x} \right \rfloor=q$，那麼不難證明$x$的值從$x$一直往上跑到$\left \lfloor \frac{n}{q} \right \rfloor$的話，$\left \lfloor \frac{n}{x} \right \rfloor$的值都會一直保持$q$，因此這段區間可以一起做。而$\left \lfloor \frac{m}{y} \right \rfloor$的部份因為$y$是往下跑的，這裡則可以推出$y$一直往下跑到$\left \lfloor \frac{m}{\left \lfloor \frac{m}{y} \right \rfloor+1} \right \rfloor+1$，因此只要對兩個可以一起做的區間取比較小的就可以了，類似的東西可以參考這篇。
code :
假設橫著切了$a$刀，直著切了$b$刀，那麼所求就會是$\left \lfloor \frac{n}{a+1} \right \rfloor\cdot \left \lfloor \frac{m}{b+1} \right \rfloor$，其中$a,b\geq 0$，並且$a+b=k$。可以先改成$\left \lfloor \frac{n}{x} \right \rfloor\cdot \left \lfloor \frac{m}{y} \right \rfloor$，其中$x,y\geq 1$，並且$x+y=k+2$，等等會比較好處理。枚舉所有的$x$顯然是不行的，而因為這條式子有高斯，所以可以用常見的優化方法，因為當上式中$x$慢慢增加時，$\left \lfloor \frac{n}{x} \right \rfloor$的值會在連續的區間保持不變。具體來說，設此時$\left \lfloor \frac{n}{x} \right \rfloor=q$，那麼不難證明$x$的值從$x$一直往上跑到$\left \lfloor \frac{n}{q} \right \rfloor$的話，$\left \lfloor \frac{n}{x} \right \rfloor$的值都會一直保持$q$，因此這段區間可以一起做。而$\left \lfloor \frac{m}{y} \right \rfloor$的部份因為$y$是往下跑的，這裡則可以推出$y$一直往下跑到$\left \lfloor \frac{m}{\left \lfloor \frac{m}{y} \right \rfloor+1} \right \rfloor+1$，因此只要對兩個可以一起做的區間取比較小的就可以了，類似的東西可以參考這篇。
code :
[CF 557E] Ann and Half-Palindrome
作法：
以下記原字串為$S$。首先核心當然就是一個一個確定答案要是$a$還是$b$，或是決定停止加字元並輸出。在確定答案時，一開始答案為空字串，接下來我們必須知道「有多少個半回文子字串的前綴是$a$」，假設有$num$個好了，如果$num\geq k$，那麼可以知道答案的第一個字元會是$a$，否則會是$b$，並且把$k$扣掉$num$後繼續下去（因為當在第一個位子放上$b$的同時答案字串就已經自動大於$num$個半回文子字串了）。另外我們還要知道什麼時候停止繼續加字元，而這只要滿足：假設當前的答案字串為$T$，那麼如果$T$是半回文且他在$S$中的出現次數$\geq k$時，$T$就是我們要的答案，證明並不難。因此我們會需要詢問兩個東西，一個是「給定某個字串$T$，問$S$中有幾個半回文子字串使得他的前綴是$T$」，另一個則是「給定某個字串$T$，問他是否為半回文，並且知道他在$S$裡出現了幾次」。並且這些詢問頂多$O(n)$次。後者中問半回文就直接$O(n)$判斷，在$S$裡出現幾次則用個後綴數組來作就可以了。至於前者比較麻煩，我們考慮先用後綴數組找出所有$T$在$S$裡出現的位置，假設對於某個$i$，$S[i,...,i+|T|-1]$和$T$字串一模一樣，那我們想知道的是有幾個$j$滿足：$j\geq i$，並且$S[i,...,j]$為半回文。這個東西就是某種後綴和，也就是我們如果可以先得出所有的$S$的子字串$S[i,...,j]$是否為半回文，用個二維陣列紀錄起來，再對第二維作後綴和（前綴和也可以），就可以$O(1)$詢問前面所需要的東西了。而這個二維陣列的求法就類似回文的想法，因為對於所有同一個中心點的$S$的子字串來說，設他從中心往左往右的長度為$L$，那麼只考慮所有$L$的奇偶性相同且同中心點的子字串，那麼當長度比較小的不是半回文時，長度比較大的也不是，因此只要枚舉中心點和字串半長度的奇偶性，從中間往外跑就可以了。
code :
以下記原字串為$S$。首先核心當然就是一個一個確定答案要是$a$還是$b$，或是決定停止加字元並輸出。在確定答案時，一開始答案為空字串，接下來我們必須知道「有多少個半回文子字串的前綴是$a$」，假設有$num$個好了，如果$num\geq k$，那麼可以知道答案的第一個字元會是$a$，否則會是$b$，並且把$k$扣掉$num$後繼續下去（因為當在第一個位子放上$b$的同時答案字串就已經自動大於$num$個半回文子字串了）。另外我們還要知道什麼時候停止繼續加字元，而這只要滿足：假設當前的答案字串為$T$，那麼如果$T$是半回文且他在$S$中的出現次數$\geq k$時，$T$就是我們要的答案，證明並不難。因此我們會需要詢問兩個東西，一個是「給定某個字串$T$，問$S$中有幾個半回文子字串使得他的前綴是$T$」，另一個則是「給定某個字串$T$，問他是否為半回文，並且知道他在$S$裡出現了幾次」。並且這些詢問頂多$O(n)$次。後者中問半回文就直接$O(n)$判斷，在$S$裡出現幾次則用個後綴數組來作就可以了。至於前者比較麻煩，我們考慮先用後綴數組找出所有$T$在$S$裡出現的位置，假設對於某個$i$，$S[i,...,i+|T|-1]$和$T$字串一模一樣，那我們想知道的是有幾個$j$滿足：$j\geq i$，並且$S[i,...,j]$為半回文。這個東西就是某種後綴和，也就是我們如果可以先得出所有的$S$的子字串$S[i,...,j]$是否為半回文，用個二維陣列紀錄起來，再對第二維作後綴和（前綴和也可以），就可以$O(1)$詢問前面所需要的東西了。而這個二維陣列的求法就類似回文的想法，因為對於所有同一個中心點的$S$的子字串來說，設他從中心往左往右的長度為$L$，那麼只考慮所有$L$的奇偶性相同且同中心點的子字串，那麼當長度比較小的不是半回文時，長度比較大的也不是，因此只要枚舉中心點和字串半長度的奇偶性，從中間往外跑就可以了。
code :
2015年7月1日 星期三
[CF 452F] Permutation
作法：
考慮從左邊往右邊掃，當掃到$i$的時候判斷是否存在兩數分別在$i$的左右，使得$a[i]$是他們的平均數。記$a[i]=x$，那麼不存在這樣的兩個數若且唯若「$j$和$2x-j$在$a[1],...,a[i-1]$中同時出現或同時不出現」，對於每個不讓上數值越界的$j$。因此我們考慮維護一個每個數分別出現了幾次的陣列，這樣就會變成詢問這個陣列中的其中一段是否和另一段倒過來一模一樣，並且支援把陣列中的$0$改成$1$。考慮維護正反的這樣的陣列，並且用 hash 來判字串相等，那麼求一個子字串的 hash 值就可以用 BIT 來作。這裡用的 hash 函數和一般的不太一樣，子字串$s[i...j]$的 hash 值會是 $a[i]+a[i+1]x+...+a[j]x^{j-i}$ ，這樣才能用 BIT 算出子字串的 hash 值（因為要修改，所以才用 BIT），並且要預處理出$x^{-1}$的所有冪次，才能快速算出 hash 值。詳細可以參考 code 。
code :
考慮從左邊往右邊掃，當掃到$i$的時候判斷是否存在兩數分別在$i$的左右，使得$a[i]$是他們的平均數。記$a[i]=x$，那麼不存在這樣的兩個數若且唯若「$j$和$2x-j$在$a[1],...,a[i-1]$中同時出現或同時不出現」，對於每個不讓上數值越界的$j$。因此我們考慮維護一個每個數分別出現了幾次的陣列，這樣就會變成詢問這個陣列中的其中一段是否和另一段倒過來一模一樣，並且支援把陣列中的$0$改成$1$。考慮維護正反的這樣的陣列，並且用 hash 來判字串相等，那麼求一個子字串的 hash 值就可以用 BIT 來作。這裡用的 hash 函數和一般的不太一樣，子字串$s[i...j]$的 hash 值會是 $a[i]+a[i+1]x+...+a[j]x^{j-i}$ ，這樣才能用 BIT 算出子字串的 hash 值（因為要修改，所以才用 BIT），並且要預處理出$x^{-1}$的所有冪次，才能快速算出 hash 值。詳細可以參考 code 。
code :
[CF 452E] Three strings
作法：
考慮對三個字串都建個後綴自動機，那麼假設對於某個出現在三字串中的子字串$T$來說，令$u_1,u_2,u_3$分別是三個自動機吃了字串$T$之後達到的狀態，而我們知道$u_i$其實會代表某個範圍長度的子字串（也就是這篇中講到的 min 值和 max 值），因此這樣可以得到我們必須要在答案陣列中的某個區間同時加上一個數，他的值是這三個節點的 right 集合大小的乘積（right 集合的定義也在上面那篇中有提到）（因為 right 集合就是子字串的出現位置集合，取他的大小就是這個子字串出現的幾次）。先不談要怎麼求每個節點的 right 集合大小，事實上只有這三個後綴自動機是不夠的，因為這三個節點的 min 值和 max 值不盡相同，也就是這三個節點代表的子字串集合不一樣，沒辦法知道要在答案的哪個區間加上 right 集合大小的積。因此我們需要第四個後綴自動機，他是將三個字串中間用沒看過的字元串起來得到的，那麼就可以同時對這四個後綴自動機DFS並求答案了。具體來說，當DFS到某個節點時，設四個節點分別為$u_1,u_2,u_3,u$，那麼我們就知道要用$u_1,u_2,u_3$的 right 集合大小乘積去更新$u$的 min 值到 max 值這個區間的答案，對這四台自動機 DFS 一次即可（每次只走前三台有轉移邊的節點，至於第四台當前三台都有轉移邊的話他也必定會有）。
於是重點剩下要怎麼知道一個節點的 min,max 值，還有 right 集合的大小。max 值在構造的時候就已經算好了，min 值比較好算，因為如果 $u$ 在自動機中的父親是 $p$ ，那麼 $u$ 的 min 值就會是$p$的 max 值再$+1$，詳細也在上面那篇裡有。至於 right 集合的大小，作法為：首先將所有用前綴轉移到的節點的值設成$1$，那麼一個節點的 right 集合大小就會是他在 parent 樹中子數裡的數值總和。而 parent 樹有個特性，就是一個節點的的 max 值會比他父親的 max 值還大，所以可以把所有節點按照 max 值排序，按照 max 值大到小拿自己的 right 集合大小值更新父親的 right 集合大小值就可以了。
code :
考慮對三個字串都建個後綴自動機，那麼假設對於某個出現在三字串中的子字串$T$來說，令$u_1,u_2,u_3$分別是三個自動機吃了字串$T$之後達到的狀態，而我們知道$u_i$其實會代表某個範圍長度的子字串（也就是這篇中講到的 min 值和 max 值），因此這樣可以得到我們必須要在答案陣列中的某個區間同時加上一個數，他的值是這三個節點的 right 集合大小的乘積（right 集合的定義也在上面那篇中有提到）（因為 right 集合就是子字串的出現位置集合，取他的大小就是這個子字串出現的幾次）。先不談要怎麼求每個節點的 right 集合大小，事實上只有這三個後綴自動機是不夠的，因為這三個節點的 min 值和 max 值不盡相同，也就是這三個節點代表的子字串集合不一樣，沒辦法知道要在答案的哪個區間加上 right 集合大小的積。因此我們需要第四個後綴自動機，他是將三個字串中間用沒看過的字元串起來得到的，那麼就可以同時對這四個後綴自動機DFS並求答案了。具體來說，當DFS到某個節點時，設四個節點分別為$u_1,u_2,u_3,u$，那麼我們就知道要用$u_1,u_2,u_3$的 right 集合大小乘積去更新$u$的 min 值到 max 值這個區間的答案，對這四台自動機 DFS 一次即可（每次只走前三台有轉移邊的節點，至於第四台當前三台都有轉移邊的話他也必定會有）。
於是重點剩下要怎麼知道一個節點的 min,max 值，還有 right 集合的大小。max 值在構造的時候就已經算好了，min 值比較好算，因為如果 $u$ 在自動機中的父親是 $p$ ，那麼 $u$ 的 min 值就會是$p$的 max 值再$+1$，詳細也在上面那篇裡有。至於 right 集合的大小，作法為：首先將所有用前綴轉移到的節點的值設成$1$，那麼一個節點的 right 集合大小就會是他在 parent 樹中子數裡的數值總和。而 parent 樹有個特性，就是一個節點的的 max 值會比他父親的 max 值還大，所以可以把所有節點按照 max 值排序，按照 max 值大到小拿自己的 right 集合大小值更新父親的 right 集合大小值就可以了。
code :
訂閱：
文章 (Atom)