[CF 555E] Case of Computer Network

作法：

因為是要把邊定向，所以對於一個邊雙連通分量來說，把裡面的邊的方向定成兩兩互相可達是最佳的，不難證明沒有這樣定的話改成這樣定會更好。因此首先找出所有的邊雙連通分量，並縮成一個點，這樣就變成樹上的問題了：給定一棵樹和一些起點終點，問是否有辦法幫所有邊定向，使得起點都可以走到終點。當給定一條路徑$a\rightarrow b$時，假設他們的LCA為$c$，那麼就可以先把路徑拆成$a\rightarrow c$和$c\rightarrow b$。因此問題可以再簡化成：將沿著$a$往父親走一直走到$b$的這條路徑上的邊都標上$1$或$2$，問是否有矛盾（$1,2$分別代表這條邊是往上還是往下）。考慮樸素的算法，也就是每次直接往上走完整條鍊，這樣複雜度會爆掉，不過只要注意到：當正在沿著$a$往父親跳的時候，如果這時跳到了一個點，他連向他父親的邊已經被標記過了，如果這條邊上的數字和當前要標記的數字不一樣則產生矛盾，否則可以直接往上跳到第一個「他連向他父親的邊還沒被標記」的點，節省時間。這部份可以用個類似 disjoint set 的東西來作，詳細可以參考 code ，這樣就可以讓複雜度變回好的了。

code :

[CF 452D] Washer, Dryer, Folder

作法：

一開始每台機器可以運行的時間都是$0$，因此第一件衣服可以馬上丟進去。再來依次處理每件衣服，找出他最早可以丟進去的時間並放進去。至於如何找最早的時間，我們對三台機器都維護一個 priority_queue ，裡面分別存每台機器要到時間多少時才有空，那麼每次從中取出最小的三個時間就可以算出下一次的衣服要在什麼時候放進去了。並且也可以計算出處理這件衣服的機器分別會在什麼時候結束工作。

code :

[CF 555D] Case of a Top Secret

作法：

首先看要如何模擬，可以把繩子的動作分成兩種，第一種是當前繩子往下垂並且物體正在往右邊移，另一種則是當前繩子是往上的並且物體正在往左邊移。把輸入的座標排序就可以用 lower_bound / upper_bound 找出繩子接下來會繞誰轉，就可以模擬了。但直接做會TLE，首先觀察到我們可以先把繩子的長度縮減到比$a[n]-a[1]$還短，其中$a[1],...,a[n]$代表已排序後的釘子座標。接下來考慮模擬時要如何優化，設當前繩子繞著$a[i]$轉，並且是前面所述的第一種狀態，如果他是由第二種狀態轉移過來的，那麼顯然會滿足$a[i]-a[i-1]>L$，其中$L$為當前繩子長度。首先求出他之後會繞著$a[x]$轉，那麼他的長度就會變為$L-(a[x]-a[i])$。如果每次長度都減少了一半以上，那麼模擬的次數就會變成$O(logL)$，會是好的。但如果在這次$L$的長度沒有減少一半以上，那麼不難發現再繞完$x$旋轉的下一步會再去繞$i$旋轉，重複繞這兩個點旋轉直到$L$小於他們之間的距離為止，因此我們可以直接把$L$的長度縮減成$L\% (a[x]-a[i])$，並由他們的商來判斷此時是繞$i$轉還是繞$x$轉。由於此時$(a[x]-a[i])<\frac{L}{2}$，所以$L$也會至少砍半，而對於第二種狀態作法也幾乎一樣，因此這樣就得到了單次詢問$O(lognlogL)$的算法了。

code :

[CF 555C] Case of Chocolate

作法：

假設這次的詢問是$(x,y,L)$，那麼如果我們已經知道在第$1,...,x-1$行中每行的最上面那個被吃掉的格子座標的話，就可以算出答案了。對於$U$的詢問也一樣可以用類似的資料結構來做。但是$n$太大了，所以考慮先把輸入都離散化，這樣就可以用線段樹來做了：維護兩棵線段樹，並且當詢問$(x,y,L)$時（詢問為$U$時幾乎一模一樣），我們會需要在其中一棵線段樹中查詢「最大的$i$使得$i,...,x$中的最大值$\leq y$」的$i$，這顯然可以在$logn$的時間內做到，但我比賽時寫了二分搜答案的作法，複雜度多一個$log$，不至於TLE。查詢完後再去更新另一棵線段樹上的值就可以了。

另外也有不用線段樹的作法，詳細可以參考這篇，比線段樹的作法簡潔多了。

code :

[CF 555B] Case of Fugitive

作法：

可以蓋在$i$和$i+1$中間的橋的長度必須滿足$\geq l[i+1]-r[i]$，且$\leq r[i+1]-l[i]$，因此先將所有橋的長度排序，那麼可用的橋會在排序序列中形成一個區間，這樣就轉換為經典問題了，也就是現在有$m$個點和$n-1$個區間，問是否有辦法幫每個區間選一個他對應的點，滿足選出的每個點都不同。考慮從第$1$個點開始往右掃，當掃到一個點$i$時，把所有左端點$\leq i$的區間加進某個資料結構中，如果此時資料結構沒有東西，那麼代表$i$這個點可以不用被取，否則取出資料結構中右端點值最小的區間出來，不難證明這個 greedy 是對的，而這只要用個 priority_queue 就可以了。

code :

[CF 453E] Little Pony and Lord Tirek

作法：

我們先處理每個$s[i]$都是$0$的情形（也就是初始值都是$0$）。考慮用線段樹，把詢問的區間拆成好幾個小區間，分別求出答案再加起來。對於某個線段樹節點代表的區間$[L,R]$而言，我們想要快速求出這個區間中的答案總和。如果這個區間擁有良好的性質：在$t_0$秒的時候這個區間全部都被設成$0$，並且之後不再動到他（因此一開始所有節點都有這個良好性質，並且$t_0$值都是$0$），那麼假設當前詢問時間是$t$秒，就可以把$[L,R]$中的小馬們分成兩類，一類是「經過了$t-t_0$秒沒辦法長到最大值」的，另一類則是長不到的，那麼對於前者，他所貢獻的答案就會是$r[i]\cdot (t-t_0)$，後者貢獻的答案則為$m[i]$。因此我們可以考慮先對每隻馬算出他「要長幾天才會長到最大值」（之後記為$t[i]$），並且在每個線段樹的節點$[L,R]$中，把「這區間中的所有馬按照$t$值排序後的結果」記錄下來，並且算出這些馬的$r$值和$m$值的前綴和陣列，這樣就能快速查詢答案了。但上述算法的前提是這個節點擁有前面所講的好性質（以下簡稱這個節點是好的），如果沒有的話就只好再把詢問區間拆開遞迴下去，直到遇到的節點是好的為止。並且我們也容易維護有哪些是好的：當遇到一個詢問時，如果詢問區間遞迴下去經過的節點被詢問區間完全覆蓋了，那麼在詢問過後他就會變成好的。並且當詢問時如果走到了一個好的節點，但是詢問區間沒有完整覆蓋這個節點的區間的話，就要把這個好的標記往下 push ，並且自己在詢問過後就不再是好節點了。總結以上算法，對於每個節點要記錄的東西有：這個區間中按$t$值排序的馬們，排完序後的馬們的$r$值、$m$值前綴和，還有在詢問時需要維護的$ok$值（代表他是否是好的）和$t_0$值，其中$t_0$代表如果$ok=1$，則$t_0$是最近一次將整個區間設成$0$的時間。以上算法解決了$s[i]$全部都是$0$的情形，但實際上一般情形也可以這樣做，因為這樣一開始時所有區間都是不好的，一次詢問下來會遞迴到底，也就是把詢問區間拆成長度均為$1$的區間暴力處理，顯然長度為$1$可以直接算出答案。不難發現暴力算的次數加起來不會超過$n$次，因此這部份複雜度會是好的。但整個算法我還證不太出他的複雜度是多少，可能是$O(qlog^2n)$之類的......

另外我還有在別人的 comment 中看到另一種作法，詳細見這裡，寫的還蠻清楚的。

code :

[CF 453D] Little Pony and Elements of Harmony

作法：

這題我是看官方解寫的，但他寫的很不清楚，這裡紀錄一下詳細，雖然應該有不用用到這種東西的作法......

題目簡單來說就是要求向量$A^t\cdot e_0$是多少，其中$A$是一個$n\times n$的矩陣，滿足他的$(i,j)$項為$b[bit(i\; xor\; j)]$（其中用$bit(x)$代表$x$的二進制中$1$的個數），$e_0$則是一個給定的$n$維向量。如果$A$有$n$個線性獨立的 eigenvector，設其為$v_0,...,v_{n-1}$，並且對應的 eigenvalue 為$\lambda _0,...,\lambda _{n-1}$，那麼可以先把$e_0$拆成$v_i$的組合，也就是令$c_0,...,c_{n-1}$滿足$\displaystyle e_0=\sum_{i=0}^{n-1} c_iv_i$，那麼所求就會$\displaystyle =A^t\sum_{i=0}^{n-1} c_iv_i=\sum_{i=0}^{n-1}c_iA^tv_i =\sum_{i=0}^{n-1} c_i\lambda _i^tv_i$。所以接下來的步驟就是先求出$c_i$和$\lambda _i$，算出$v_i$前面的係數之後再想辦法組合起來。

神奇的是$A$這個矩陣的確有$n$個 eigenvector ，並且$v_i$的第$j$項恰好等於$(-1)^{bit(i\& j)}$（這篇中所有的證明都放在最後）。記矩陣$H=\begin{bmatrix}v_0 & v_1 & \dots & v_{n-1}\end{bmatrix}$，並且回到$\displaystyle e_0=\sum_{i=0}^{n-1} c_iv_i$這個式子，他就會等價於
$e_0=H\cdot \begin{bmatrix}c_0\\c_1\\\vdots\\c_{n-1}\end{bmatrix}$，所以$\begin{bmatrix}c_0\\c_1\\\vdots\\c_{n-1}\end{bmatrix}=H^{-1}e_0$。又因為$H$是對稱的，還有$v_0,...,v_{n-1}$兩兩正交，所以可以得到$H\cdot H=n\cdot I$，也就是$H^{-1}=\frac{1}{n}H$，所以這裡本質上就是要算$H$乘以一個向量得到的向量是多少。

我們把求$H$乘上一個向量的作法留到後面，先來看$\lambda _i$的求法。因為$Av_i=\lambda _iv_i$，所以我們只要比對兩邊第一項的值就好了。可以得到$\displaystyle \sum_{k=0}^{n-1} b[bit(k)](-1)^{bit(i\& k)}=\lambda _i$（這裡代入了$A$的第$(0,k)$項為$b[bit(0\; xor \; k)]=b[bit(k)]$，還有$v_i$的第$k$項為$(-1)^{bit(i\& k)}$）。令另一個$n$維向量$d$的第$k$項等於$b[bit(k)]$，那麼上式可以改寫為$\lambda _i = d \cdot v_i$，因此把$n$條式子（$i=0,...,n-1$）寫在一起就可以變成$\begin{bmatrix}\lambda _0\\\lambda _1\\\vdots\\\lambda _{n-1}\end{bmatrix}=\begin{bmatrix}v_0^T\\v_1^T\\\vdots\\v_{n-1}^T\end{bmatrix}\cdot d=H\cdot d$，因此這裡也會變成求$H$乘上一個向量的問題。

最後則是求出所求的向量$\displaystyle \sum_{i=0}^{n-1} c_i\lambda _i^tv_i$，他可以改寫成$\begin{bmatrix}v_0 & v_1 & \dots & v_{n-1}\end{bmatrix}\cdot \begin{bmatrix}c_0\lambda _0^t \\ c_1\lambda _1^t\\\vdots\\c_{n-1}\lambda _{n-1}^t \end{bmatrix}$，因此一樣是求$H$乘一個向量，所以現在問題剩下這件事要怎麼作了。事實上我們可以用遞迴來定義$H$，定義$H_0$代表只有一個$1$的$1\times 1$的矩陣，$H_i$則定義為$\begin{bmatrix}H_{i-1} & H_{i-1} \\ H_{i-1} & -H_{i-1}\end{bmatrix}$，其中他是$2^i\times 2^i$的矩陣，那麼這邊的$H$就會是$H_m$（這不難由前面$H$的定義得出）。有了這個遞迴式就能幫助我們在$O(nlogn)$的時間內算出$H$乘上一個向量是多少了。考慮「求出$H_i\begin{bmatrix}u_0 \\ \vdots \\ u_{2^i-1} \end{bmatrix}$」這個問題，由上面的遞迴式可得他就等於$\begin{bmatrix}H_{i-1} & H_{i-1} \\ H_{i-1} & -H_{i-1}\end{bmatrix}\begin{bmatrix}u_0 \\ \vdots \\ u_{2^i-1} \end{bmatrix}$，因此我們先遞迴下去算出$H_{i-1}\begin{bmatrix}u_0 \\ \vdots \\ u_{2^{i-1}-1} \end{bmatrix}$和$H_{i-1}\begin{bmatrix}u_{2^{i-1}} \\ \vdots \\ u_{2^i-1} \end{bmatrix}$，假設分別得到$U_1$和$U_2$，那麼不難得到所求就會等於$\begin{bmatrix}U_1+U_2 \\ U_1-U_2 \end{bmatrix}$，也就是能在線性的時間內合併兩個子問題，因此複雜度是$O(nlogn)$。他的寫法就有點類似FFT，但這個簡潔多了。

=======================================================================

最後補上前面沒證的證明，一個是為什麼$v_i$們就會是$A$的 eigenvector ，還有為什麼$v_i$們兩兩正交。兩兩正交比較好證，我們要證明$v_i\cdot v_j=0$（其中$i\neq j$），這等價於$\displaystyle \sum_{k=0}^{n-1} (-1)^{bit(i\& k)+bit(j\& k)}=0$，假設$i,j$的第$x$個 bit 不同，那麼考慮上式中將第$k$項和第$k\; xor \; 2^x$項配對，不難證明這兩項一個是$1$一個是$-1$，因此總和為$0$。最後證明$v_i$為 eigenvector ，考慮$Av_i=\lambda _i v_i$這式子兩邊的第$j$項，可以得到$\displaystyle \sum_{k=0}^{n-1}b[bit(j\; xor \; k)](-1)^{bit(i\& k)}=\lambda _i (-1)^{bit(i\& j)}$，我們要證明的是當$j$跑遍$0,...,n-1$時$\lambda _i$都會是固定的。考慮左式中$b[z]$的係數，可以得到他會是$\displaystyle \sum_x (-1)^{bit(i\& x)}$，其中$x$跑遍所有和$j$差了$z$個 bit 的數（也就是$bit(j\; xor \; x)=z$）。考慮把$j$的第$r$個 bit 改掉時$b[z]$的係數會如何變化，分成$i$的第$r$個 bit 是$0$或$1$兩種情況，而不管是哪種情況在計算$b[z]$的那條式子中的$x$們必須把他們的第$r$個 bit 都改掉才會滿足他和新的$j$差$z$個 bit ，因此當$i$的第$r$個 bit 是$1$的時候，對於所有的$b[z]$係數中的$(-1)^{bit(i\& x)}$都會乘上一個負號，否則係數都不會變。回到我們要證明的那條式子，剛才說明了當$j$的某個 bit 改變時左式會發生什麼事，而右式中的$(-1)^{bit(i\& j)}$也恰好會發生一樣的改變，當$j$變動的 bit 在$i$那邊也是$1$時則變為$-1$倍，否則不變，這就得到了當$j$跑遍所有$0,...,n-1$的數時$\lambda _i$都會是定值，因此$v_i$為$A$的 eigenvector。


code :

[CF 553D] Nudist Beach

作法：

考慮二分搜答案，那麼可以先對每個點算出「如果取他的話至少要取幾個他的鄰居」，以下稱其為$num$值，再來要判斷是否有可能。最好的情況是取下了所有非堡壘的點，因為這時每個點可以獲得最多的被取到的鄰居數，但有些點儘管如此還是不能被取的，他們就是「$num$值大於鄰居中非堡壘點」的點，所以必須先把他們去除掉。把他們去除後又可能多了一些新的不能取的點，因此就可以得到這會是某種BFS的過程：先把一開始的$k$個點標成不可取他的，並推入 queue 中，每次從 queue 取出一個點時，更新他所有鄰居的「當前還有幾個鄰居是可以被取的」的值，如果發現有一個鄰居的值已經$<$他的$num$值時就也把他推入 queue 裡面。過程結束後如果還有沒被BFS到的點那麼就是可行的，否則不行，這個算法的充要條件證明則算是顯然的。

code :

[CF 553C] Love Triangles

作法：

首先把圖轉換成「兩人相愛若且唯若兩點之間連邊」，觀察這張圖會有什麼特性。首先當$A,B$連邊且$B,C$連邊時，$A,C$也要連邊，因此可以知道每個連通塊一定都是完全圖。再來如果有大於兩個的連通塊，那麼在三個連通塊中各挑一個點就形成了兩兩沒有連邊的三角形，和題意矛盾，因此至多只有兩個連通塊。這樣就轉換成經典問題了：給一張圖，還有一些「兩點之間同色」和「兩點之間異色」的條件，問有幾種塗兩色的方法。這只要先用 disjoint set 判有沒有可能，若有可能則答案為$2$的(連通塊數量$-1$)次方，其中這裡的圖是「當給定條件$x,y$同色或異色」時則在$x,y$之間連一條邊所得到的圖。

code :

[CF 453C] Little Pony and Summer Sun Celebration

作法：

首先如果有兩個連通塊裡都有$1$那顯然無解，因此現在只要考慮有一個連通塊有$1$的情形。通常這種構造題只要隨便取個生成樹DFS下去就可以了。考慮在DFS的過程中，當DFS完$x$這個點時$x$必須要完成他的目標，然後回到他父親（記為$f$）。如果發現$x$還需要被走一次，那麼就走$f\rightarrow x\rightarrow f$就可以讓$x$多走一次了，而如果$x$不用再被走一次就直接回去$f$。這樣可以處理根節點以外的所有點，至於如果回到根節點時還沒滿足條件，那麼隨便取他的一個孩子$s$，走$s\rightarrow x\rightarrow s$就可以了。

code :

[CF 455E] Function

作法：

觀察$f$函數的式子可以發現他就類似某種最短路，$i$指的就是走了$i$步，因為$f(i,j)$都是從$f(i-1,x)$轉移過來的。觀察到這件事就可以先把原題轉換成最短路問題：考慮一張$n+1$個點的圖，第$i$有連到自己的邊權為$a[i]$的邊($i=1,...,n$)，$i$也有連到$i+1$的邊權為$a[i+1]$的邊($i=1,...,n-1$)，並且$n+1$有連到$i$的邊權為$a[i]$的邊($i=1,..,n$)，那麼$f(i,j)$就等於從$n+1$開始走$i$步到達$j$的最短距離。假設現在要算$f(x,y)$，如果從$n+1$開始第一步走到$k$，那麼走$i$步的距離就可以表示成$\displaystyle \sum_{i=k}^{y} c[i]\cdot a[i]$，其中$c[i]$同時也代表這條路徑在$i$走了$c[i]-1$次自環。並且由走$x$步的限制可知$\displaystyle \sum_{i=k}^{y} c[i]=x$，並且顯然的有$c[i]\geq 1$，因此$k$必須滿足$k\geq y-x+1$。接下來看達到最小值時$c$陣列應該要長怎樣，考慮$a[k],...,a[y]$中最小的那個數，那麼把所有的$c$都集中到那個數一定是最好的，並且如果那個數不是$k$的話可以把$k$的$c$值也丟到他身上，因此最佳解中$c$陣列一定長的像：$c[k+1]=...=c[y]=1$。此時我們得到的路徑長度$=a[k+1]+...+a[y]+(x-y+k)a[k]$
$=S[y]-S[k]+(x-y+k)a[k]$
$=S[y]-(y-x)a[k]+(k\cdot a[k]-S[k])$，其中$S[i]=a[1]+...+a[i]$。
其中的$S[y]$可以先不用理他，最後再加到答案上就可以了。至於後面那項，因為在詢問的時候只有$y-x$的值會變，$a[k],S[k]$的值都是不變的（$k$固定時），因此當不同的$y-x$代入時可以把這東西看成一個一次函數，也就是令直線$L[i]:y=-a[k]\cdot x+(k\cdot a[k]-S[k])$，那麼這樣在詢問$f(x,y)$時就等價於詢問$y-x$這個數代入$L[y-x+1],...,L[y]$的最小值是多少。這可以用線段樹套凸包來作，具體來說，假設線段樹的某個節點區間為$[L,R]$，那麼就在這個節點先算好第$L,...,R$條直線形成的上凸包長怎樣（紀錄頂點們和直線們），這樣就可以在這個節點上用$log$的時間查詢某個數代入這個區間中所有直線所得到的最小值是多少了。而當詢問一個區間時就只要把他拆成好幾個線段樹的節點，合併起來就是答案了。

code :

[CF 455D] Serega and Fun

作法：

通常這種時限比較長而且操作很奇怪的題目都可以考慮根號作法。考慮把整段序列切成$\sqrt{n}$塊，再根據題目的要求決定每塊中要維護的資料結構是什麼。當要把某段區間循環右移時，把他拆成已經切好的幾小塊，就可以得到每個小塊中所必須支援的操作為「將這塊中的某個區間整個右移（因此最右邊的數會消失），並且在左邊補上$x$」。並且大部分的情形右移的區間都是整個塊，因此可以考慮當操作的區間不是整塊的時候暴力重建這個資料結構即可，也就是我們只需要快速的支援「將整塊往右移並在左邊補上$x$」這個操作。至於詢問也是拆成好幾個小塊，對於詢問區間不完全是整塊的部份暴力掃過去就可以了，因此我們需要在一塊中詢問某個數出現了幾次，所以只要在這塊中用一個陣列$cnt$紀錄所有數字出現的次數就可以了。當把整塊中的數都右移時，我們會需要知道此時這塊中的最後一個數是多少，才能維護好$cnt$陣列，也就是會需要查詢某塊中的第$k$個數是誰，並且支援右移操作。這可以用一個環狀的結構來維護，具體來說是一個陣列$a$和一個起點值$st$，代表從$a[st]$開始往後走$i$步就是代表這塊中的第$i$個數是誰（以下記這塊的長度為$sz$），也就是當我們想知道這塊中的第$i$個數時，要查詢的是$a[(st+i)\% sz]$的值。這樣就可以輕鬆維護循環右移操作了，只要把$st$值減一再維護好$cnt$陣列就可以了。

code :

[CF 455C] Civilization

作法：

由條件知到他的圖會是一個森林。這題只要注意到連接兩個連通塊時連接兩連通塊的重心是最好的選擇，因此只要對每個連通塊計算他的最長鍊是多長就可以了，最長鍊的計算方法為：先任遠一個點對他DFS，找出離他最遠的點，再以找到的那個點當根做一次DFS，所得到的最長距離就是這棵樹的最長練了。假設兩個連通分量的最長鍊分別為$x,y$，那麼連接他們的重心之後會產生一條長為$\left \lceil \frac{x}{2} \right \rceil+\left \lceil \frac{y}{2} \right \rceil+1$的鍊，再和$x,y$取 max 就是新連通塊的最長鍊長度了，至於實作用個 disjoint set 並維護好最長鍊值就可了。類似的題目還有 IOI 2013 Dreaming （HOJ 288）。

code :

[CF 455B] A Lot of Games

作法：

首先當然是決定如果$k=1$時誰有必勝策略，這可以先建出所有字串的 trie 後DP得到。這樣解決了$k=1$的問題，但$k=2$時可能第一局先手故意輸掉，下一局再用必勝策略獲勝之類的（因為下一場的先手會給輸方），因此我們還需知道誰有必敗策略，這和必勝策略的求法幾乎一樣。有了這兩個之後就只要討論四種情形就好了：能夠必勝的是先手還後手，能夠必敗的是先手還後手（這個必敗指的是他可以強迫自己輸，而不是他的對手有必勝策略）。如果後手能夠必勝，那麼他就一路贏到底就好了。否則當先手必勝時，討論一下即可知道當先手可以必敗時必定先手贏，後手可以必敗時則是當$k$是奇數時先手贏了。

code :

[CF 457C] Elections

作法：

考慮枚舉$0$號的得票數，那麼策略就是先買票數$\geq$他的候選人的最便宜的幾張票，讓他的票數小於自己的，這時如果自己的票數已經超過預定的了，那就代表這次是無效的，否則再從剩下的票裡面選最小的幾張票補滿就好了。至於要如何加速到$O(nlogn)$，考慮從小到大枚舉得票數，那麼可以用一個資料結構維護剛才所說的後者的動作中的「在剩下的票裡選最小的幾張票」，他必須支援「加入一個數」和「詢問這些數裡前$k$小的數的總和」是多少，而這可以用一個分裂合併式的 treap 完成。

code :

[CF 457B] Distributed Join

作法：

感覺題目寫的不太好懂......簡單來說就是，現在有左邊$n$坨資料，右邊$m$坨資料，每坨資料裡都有一定數量的行。一次操作可以把某一行複製到某坨資料中塞進去，問至少要幾次操作才能滿足在左邊任選一行，右邊任選一行，都有某一坨資料裡面含了這兩行（任兩行的內容都不一樣）。首先觀察最佳解會有怎樣的特性，對於某一行來說，簡稱「這一行被複製到了哪幾坨資料」為他的目的地，那麼某坨資料中的所有行的目的地都一樣。因為如果某坨中有兩行的目的地不一樣（假設這坨在左邊），對於其中一種目的地來說，那幾坨的聯集裡面一定包含了所有右邊的行，因此可以把目的地坨數比較多的那個方法換成比較少的，這樣答案不會更差，因此一坨資料中任兩行的目的地相同。再來則是最佳解中至少有一坨資料內的每一行是沒被複製過的（之後簡稱這件事為這坨資料不動），因為如果每坨的資料都有動，那麼隨便取一坨，稱他為$A$，考慮這坨資料的目的地集合$S$和所有進行過的操作，把所有「把某行複製到$S$中某一坨」的操作都替換成「把那行複製到$A$」，顯然這樣替換還是可以滿足原題條件，並且總複製次數不會增加。因為這裡的假設是每坨資料都有動，因此不會發生「某坨資料的目的地集合嚴格變大」這件事（否則代表他原本的目的地集合就是空集合）。

因此我們可以假設右邊有一坨資料不動，之後將左右的資料對調再求一次答案即可。不妨設右邊不動的資料們的行數分別為$b_1,...,b_k$，剩下的為$b_{k+1},...,b_m$，那麼因為這幾坨都不動，所以對於左邊的每一行都要複製進$b_1,...,b_k$的每坨資料中，這需要花$k\cdot (a_1+...+a_n)$次操作。而因為$b_{k+1},...,b_m$都有動，也就是他們的目的地至少有一個，所以這部份至少要進行$b_{k+1}+...+b_m$次操作。而我們的確可以只用$k\cdot (a_1+...+a_n)+b_{k+1}+...+b_m$完成任務，只要把$b_{k+1},...,b_m$中每一行都複製進$b_1$就可以了。因此對於固定的$k$來說，取$b$中前$k$大的數是最好的，所以只要先把$b$由大到小排序，掃過去並維護前綴和就可以了。

code :

[CF 459E] Pashmak and Graph

作法：

考慮把邊權從小到大排序，一條一條加進圖中，並維護好當前圖的以每個點為終點的最長路長就可以了。但要處理邊權一樣時的問題，解決方法是先把這些邊權一樣的邊的起點都找出來，把這些點和他們的當前答案值存下來，再用存下來的值去更新這些邊的終點的答案就可以了。

code :

[CF 552E] Vanya and Brackets

作法：

只要注意到加上的括號一定會落在兩個乘號的中間就好了。但如果整個表達式的乘號太少就會有問題，因此我們可以在字串最前面加上$1*$，最後面加上$*1$就可以了。枚舉括號的位置，剩下就是要如何算出表達式的值是多少。對於一個表達式來說，考慮從左邊掃到右邊，維護兩個數字$x,y$分別代表「當右邊再出現了一個數為$a$時，表達式的值為$x+y\cdot a$」。例如當算完$1+2*3+4*5*$這個部份時，$x=7,y=20$。並且不難維護好這兩個值。而對於括號分開的三個表達式也都用一樣的方法就可以算出來了。

code :

[CF 461E] Appleman and a Game

作法：

考慮給定字串$s$之後要如何用最少步湊出$s$。這只要取一個最長的$s$的前綴，滿足他是$t$的子字串，把他拼上去之後重複這個過程就好了，因為如果我們取的是比較短的子字串，那麼可以用「把第一個子字串伸長，第二個子字串的前面截掉」來把原本的湊法換成剛才講的湊法。因此當我們想要算長度為$n$的$s$最差狀況下要幾次才能湊出來，可以考慮取某個$t$的子字串$U$，滿足他的後面再加上$c$之後就不會是$t$的子字串了（$c$是$ABCD$中的某一個），那麼就可以在$s$的最前面寫上$U$這個字串，並且約定下一個字元放的是$c$，這樣湊出$s$的第一步就是選$t$的$U$這個子字串並放上去了。由這個就可以想到，令$dp[i][j]$代表長度為$i$，開頭為$j$的字串最差狀況下要用幾個$t$的子字串湊出來，那麼為了計算$dp[i][j]$，我們需要取一個開頭是$j$的$U$字串放在所求字串的最前面才行（$U$和前面提到的一樣），也就是如果我們記開頭為$j$的$U$字串，且他後面準備要放的字元是$k$時的最短長度為$L[j][k]$，那麼就可以列出轉移式了：$dp[i][j]=max\{ dp[i-L[j][k]][k]+1 \},k=0,1,2,3$。其中我們以$0,1,2,3$分別代表$A,B,C,D$。

而首要工作就是要先求出$L[i][j]$是多少，這可以用後綴自動機加上簡單的DP得到，關於後綴自動機可以參考這篇，寫的蠻詳細的。

再來我們想要求出當$i$很大時的$dp$值。仔細觀察轉移式可以發現，可以把他解讀成當第二維從$j$走到$k$之後，第一維的值就會增加$L[j][k]$，這就有點類似在一張圖上從$j$走到$k$的距離是$L[j][k]$一樣，因此如果考慮構造一張四個點的圖，其中任兩點$j,k$之間連一條有向邊，邊權為$L[j][k]$，那麼問題就轉化成了：從某一個點開始一直走，走到總權重的和$\geq n$時最多走了幾步。而這個問題可以二分搜解決，等於是變成要算出走$m$步後走過的最短距離為多少，這可以用倍增法算出，也就是預先算出「從$i$走了$2^k$步到$j$所走的最短路徑長」就可以了。

code :

[CF 461D] Appleman and Complicated Task

作法：

首先把所有格子以$x+y$的奇偶性分成兩類，這兩類可以分開處理，因為題目給的條件中當某個格子的顏色改變的時候，不會影響到所有和他不同類的格子是否滿足條件。再來注意到，考慮把白色賦值成$1$，黑色則為$0$，那麼題目的條件就變成：對於每一個$(i,j)$，$c_{i-1,j}\; xor \; c_{i,j-1}\; xor \; c_{i,j+1} \; xor \; c_{i+1,j}=0$，其中$c_{i,j}$代表$(i,j)$的顏色的值。而$xor$可以看成二進制下的加法，所以可以把條件改寫成$c_{i-1,j}+c_{i,j-1}+ c_{i,j+1}+ c_{i+1,j}=0$，或是$c_{i-1,j}=c_{i,j-1}+ c_{i,j+1}+ c_{i+1,j}$。以下稱第一類格子為$x+y$值為奇數的，第二類則是偶數的。接下來我們先只考慮第一類格子，可以發現到當正方形中的主對角線旁邊的兩排格子的顏色都確定後，整個盤面上的所有第一類格子的值都確定了，所以只要確定好這兩排的值就好了（他們就是$x,y$座標差$1$的格子們）。並且由$(1,1)$的條件限制可得$c_{1,2}=c_{2,1}$，再由$(2,2)$的條件限制得$c_{2,3}=c_{3,2}$，一直推下去就可以得到$c_{i,i+1}=c_{i+1,i}$了。因此接下來記$C_i=c_{i,i+1}$，那麼我們想要知道：當題目給了一個限制條件$c_{x,y}$是$0$或$1$的時候（他是第一類格子），會對$C_i$造成什麼限制。

上圖中代表每一格分別是由哪些$C_i$所$xor$出來的，這樣可以發現一個規律：$(i,j)$會是由$C_{\frac{i-j-1}{2}}$和$C_{\frac{i+j-1}{2}}$所$xor$出來的，並且再觀察$(7,5)$的限制條件，會得到$C_1=C_6$，還有$(7,3),(7,1)$的限制條件分別可以得到$C_2=C_5$和$C_3=C_4$，而這也是蠻顯然的條件，因為整個盤面會對兩條對角線對稱。因此一般來說，必須要有$C_{i}=C_{n-i}$。由上圖可推得，當我們得到了「$c_{x,y}$是多少」的條件時，其實就等於獲得了$C_p\; xor \; C_q$等於多少，也就是他們兩個是否相等的條件。並且當給定的$(x,y)$本身就是$C_i$的一員時條件就變成「$C_i$等於多少」。因此這樣就轉換成經典問題了：給定一張圖，跟其中一些節點的顏色，並且給定許多「某兩個點同色」和「某兩個點異色」的條件，問共有幾種塗法。而這只要對每個連通塊分開做，並把所有答案乘起來。並且當某個連通塊不滿足那些條件限制時答案為$0$，否則當這個連通塊中已經有某個點的顏色確定的話答案為$1$，如果沒有的話就是$2$。

至於第二類格子的處理和上面類似，這時是只要決定主對角線上的顏色就好了，並且一樣記$C_i=c_{i,i}$，那麼這次可以得到$(i,j)$會是由$C_{\frac{i-j}{2}}$和$C_{\frac{i+j}{2}}$所$xor$出來的，並且一樣有盤面對稱的條件，也就是$C_{i}=C_{n+1-i}$，之後的處理就和前面一模一樣了。

code :

[CF 463E] Caisa and Tree

作法：

首先因為修改操作至多$50$次，所以可以直接把他當成沒有修改，在有修改時就直接砍掉重建就好了。對於一個節點$x$來說，假設他的質因數為$p_1,...,p_r$，那麼對於$x$子樹裡的所有點來說，如果某個點$y$的值有$p_1,...,p_r$中任意一個質因數，那麼就可以用$x$去更新$y$的答案，並且$y$的答案要取深度最深的點。因此就可以想到，對這棵樹DFS，假設當前點是$u$，那麼對每個質因數都維護一個數，代表如果之後遇到的點的值有這個質因數的話，就可以用他來更新答案，不難在DFS時更新和回溯那些值，所以就可以$O(1)$回答詢問了。

code :

[CF 464E] The Classic Problem

作法：

這題我是照官方解寫的。重點就是要實作一個資料結構來模擬二進制的操作，有：把$0$修改成$1$，詢問某個位置的右邊第一個$0$落在哪裡，把一串連續的$1$全部改成$0$，還有詢問兩棵子樹是否一模一樣（在判斷兩棵線段樹的大小時會用到）。對於詢問某個位置的右邊第一個$0$，我們可以對每個節點紀錄「緊貼在這個區間右邊的連續的$1$有幾個」，例如$0110011$的值就是$2$，這樣就不難直接從線段樹的根走下去獲得答案了。再來則是判斷兩棵子樹是否相等，我的作法是對每個 bit 都 random 一個 unsigned long long 給他，則一棵子樹的 hash 值就是所有他底下是$1$的 bit 的 random 值 xor 起來的結果，可以用把個這樣的 hash 值包起來來避免碰撞。最後把這東西包起來就可以丟進 Dijkstra 裡了。

code :

[CF 464D] World of Darkraft - 2

作法：

首先由期望值的線性的特性可以知道，其實可以看成只有一種裝備，每次打完怪之後只有$\frac{1}{k}$的機率可以讓他有機會升級，剩下則什麼都不變。最後答案就是只有一種裝備的答案再乘以$k$。

記$dp[i][j]$代表打完$i$隻怪之後，裝備等級為$j$時期望賺的錢，那麼計算$dp[i][j]$時要考慮由以下幾種狀態轉移過來：

$dp[i-1][j-1]$，機率$=\frac{1}{kj}$，賺的錢$=j-1$。

$dp[i-1][j]$，機率$=\frac{1}{k(j+1)}$，賺的錢$=x$。其中$x\in [1,j]$。

$dp[i-1][j]$，機率$=\frac{k-1}{k}$，賺的錢$=0$。

但轉移式並沒有那麼顯然。考慮某個進行了$i-1$次操作的過程（例如可能是不變、獲得等級$2$裝備、不變、獲得等級$1$裝備），並且最後裝備等級是$j$，那麼這一連串的操作有一個發生的機率$p$，還有他賺的錢數$c$。因此$dp[i-1][j]$中就會有一項等於$p\cdot c$，並且$dp[i-1][j]$就是所有操作$i-1$次變成等級$j$的方法的$p\cdot c$總和。現在要從$dp[i-1][j]$轉移到$dp[i][j]$，假設轉移的機率為$q$（也就是$\frac{1}{k(j+1)}$），獲得的錢為$x$，那麼就要在$dp[i][j]$中加上$(pq)\cdot (c+x)$，並且$dp[i][j]$一樣是所有可能的方法的(機率*錢數)的總和。因為$pq(c+x)=q(pc)+pqx$，因此把$(p,c)$取遍所有$dp[i-1][j]$中的值時，$q\cdot (pc)$的總和就會是$q\cdot dp[i-1][j]$，$pqx$的總和則因為$p$的總和其實就是「進行$i-1$次操作後等級為$j$的機率」，所以可以改寫成$P[i-1][j]\cdot qx$，其中$P[i][j]$代表進行$i$次操作後等級為$j$的機率，並且$P$的遞迴式蠻顯然的。因此就可以得到這樣的轉移式：
$\displaystyle dp[i][j]=dp[i-1][j-1]\cdot \frac{1}{kj}+P[i-1][[j-1]\cdot \frac{1}{kj}\cdot (j-1)$
$\displaystyle +\sum_{x=1}^{j} (dp[i-1][j]\cdot \frac{1}{k(j+1)}+P[i-1][j]\cdot \frac{1}{k(j+1)}\cdot x)$
$\displaystyle +\frac{k-1}{k}\cdot dp[i-1][j]$
其中這三行分別對應三種轉移過來的狀態，並且第二行的顯然可以化簡成$O(1)$計算的東西。因此我們得到了一個$O(n^2)$的算法。

如同很多需要算機率和期望值的題目一樣，若列出的轉移式為$O(n^2)$的，但數字範圍不允許這種複雜度，那麼就可以考慮把機率值太小的地方直接砍掉不算他。在這題中，注意到經過$n$天之後期望的等級不會太大，因為每次增加$1$的機率會越來越小。如果要算準確的話，當等級$i$時只有$\frac{1}{i+1}$的機率會增加，也就是期望需要$i+1$天才能增加$1$，因此可以列出$2+3+...+(x+1)=n$，其中$x$是期望的等級數。因此期望等級數大約在$\sqrt{2n}$左右，因此就可以考慮把超過$\sqrt{2n}$太多的$dp$值直接當成$0$。所以我們的DP陣列的第二維就只要開$1000$左右就可以了，這樣就得到了$O(n\sqrt{n})$的算法。

這樣傳上去很哀傷的TLE了，後來我加了個「若$dp$值或$P$值太小就直接把他的值變成$0$」就過了，並且自己測跑的時間快了非常多，至於為什麼可以參考這篇，要是之前我沒有看到那篇這題可能就要TLE到死了......

code :

[CF 464C] Substitutes in Number

作法：

對於一連串的替換操作，可以發現到其實「$1$」這個字不管是落在原字串的哪裡，最後一定都會變成一個固定的很長的字串，這對於$0,...,9$都成立。因此如果我們能算出每個字元在經過所有的替換之後變成的字串的長度，和這個字串本身模$10^9+7$的值，就可以$O(n)$算出答案了。具體來說，假設原字串是$123456$，並且一連串的操作把$6$變成了$777$，$5$變成了$888$，$4$變成了$999$，那麼我們可以算出原本的$4$變成$999$之後應該要乘上$10$的幾次才會是他實際上的值，不難發現他其實就是「$5$最後的字串長度$+6$最後的字串長度」，所以就得到了$999\cdot 10^6$。只要這樣算出每個字元的答案的總和就可以了。

至於如何求最後字串長度和模$10^9+7$的值（以下稱其為$len$值和$val$值），可以把整個過程倒過來看。當沒有進行任何替換時，$0~9$的長度都是$1$，$val$值則是他本身。再來觀察只有進行最後一次替換時$0~9$的$len$值和$val$值應該會是多少，假設這次替換是$x->S$，那麼可以發現此時$len[x]=S$的長度，$val[x]$則變成了$S$代表的值，其他數的$len,val$則不變。

再來我們的目的是，假設現在已經有了「考慮第$i$個替換到最後一個替換時，每個數的$len$和$val$值」，想要推到「考慮第$i-1$個到最後一個時」的兩種值，而這很容易從上面觀察出一般的情形，可以發現其實新的$len[x]$值就是由舊的$len$陣列中，把$S$的每一個字元代入再加起來的結果，而$val[x]$則比較複雜，不過基本上和前面所講的「$O(n)$算出原數列的答案」的精神類似，因為我們知道$S$中的每個字元在經過了第$i$次到最後一次替換之後會變成什麼值了，所以就可以求出$S$經過了第$i$次到最後一次替換後會變成多少，而這個值就是新的$val[x]$了。

最後要注意到，$len$值會爆 long long，事實上我們可以把$len$值拿去模$10^9+7-1$，因為其實可以發現$len$值就是被用來放在$10$的冪次，以求得一個字元真正代表的值的，而因為$10^9+7$是一個質數（記為$p$），由費馬小定理知$a^{p-1}\equiv 1(mod p)$，因此把$len$值加減$p-1$並不會影響結果，所以模$p-1$才會是對的。

code :

[CF 467E] Alex and Complicated Task

作法：

首先想法是 greedy ，我們只要找到一個最小的$i$，使得$a[1],...,a[i]$中存在一個長度為$4$的子序列，滿足他形如$x,y,x,y$即可。當找到這個$i$之後顯然最好的方法就是取那$4$個數，然後把一切清空，當成原數列只有$a[i+1],...,a[n]$去作就可以了。因此問題變為要如何決定那樣子的最小的$i$。

考慮從$1$開始往右掃描，當遇到一個數是之前出現過的數時，假設此時掃描到$a[x]$，並且前一個出現過同樣數字的位子為$a[y]$，那麼我們可以把$a[x],a[y]$之間的所有數字當標記上$a[x]$（注意不是標記位置，是標記數值），因為之後只要一遇到$a[x],a[y]$中間的任何一個數，我們就找到所求的序列了。而為了避免重複標記相同位置的數，可以用一個 stack 來維護，每次加入新數字時，如果這個數字已經在 stack 裡出現過了，那麼就不斷 pop 直到遇到那個數為止，並且把中間 pop 掉的數都標記上當前的數的值。而只要當前遇到的數字是已被標記過的，那麼就等於找到所求的最小$i$了，把那$4$個數丟進答案裡並把所有資料結構清空即可。另外還要注意到也有可能四個數相同，而這只要再多用一個 map 紀錄一個數字出現了幾次就可以了，當一有某個數字出現$4$次時也等於找到一組解了。

code :

[CF 551E] GukiZ and GukiZiana

作法：

將整個序列切成$\sqrt{n}$塊，我們先看每一塊中必須支援什麼操作才有辦法處理題目的要求。對於把原數列的某個區間同加一個數的操作，把他拆成由好幾個已經切好的好幾塊組成，對於其中一塊來說，可能要加的區間完整覆蓋他，或是沒有完整覆蓋，並且滿足沒有完整覆蓋的塊頂多只有$2$個。至於題目的詢問，只要能夠在每塊中查詢某個數第一次和最後一次出現的位置就可以了，枚舉$\sqrt{n}$塊即可找出答案。因此對於每一塊，我們可以用一個 map<long long,vector<int>> ，代表某個數值出現的所有位置（因為可能一個數被加超過 int），還有一個$tag$值代表這裡面所有數都應該要增加$tag$，也就是當查詢的值為$x$時要去 map 的 key 值為$x-tag$的 vector 裡面找。而當我們要把一塊中的部份幾個數同加一個值時，就直接把那塊砍掉重建就好了，因為每次操作至多發生兩次這樣的事，所以複雜度不會爛掉。

但這樣傳上去TLE了，我後來加了個優化才過：因為詢問的數頂多到$10^9$，而且每次對一個區間加的數都是非負的，所以當某個位子的數超過$10^9$時他就再也不可能被詢問到了，因此可以在重建某一塊時直接忽略掉那個位子的數。另外對於每一塊也一樣，如果有一天某一塊的$tag$值超過$10^9$，那麼那一塊就廢掉了，之後重建就可以不用裡他了。這樣就可以把所有 long long 都改回 int ，因為測資很大，所以這樣就可以快很多了。

code :

[CF 468E] Permanent

作法：

這題我是按照官方解寫的，但官方解寫的蠻簡略的，這裡紀錄一下詳細作法。

我們要處理的問題現在已經轉換成要求「在一張二部圖中的所有有$t$條邊的匹配的權重總和」，其中一個匹配的權重等於裡面所有邊的邊權乘積。對每個$0\leq t\leq 50$都要求出這個東西的答案（要注意到空匹配的權重等於$1$）。我們可以把每個連通塊分開求，然後再合併成所求的答案陣列。具體來說，如果其中一個連通塊的答案陣列為$a$（也就是$a[0],...,a[50]$分別是那個連通塊的答案），另一個的則為$b$，那麼可以得到在這兩個連通塊中有$i$條邊的匹配的權重總和等於$\displaystyle \sum_{j=0}^{i} a[j]\cdot b[i-j]$，因為兩個連通塊中的邊數加起來要等於$i$。至於為什麼是直接相乘，因為$a[j]$其實是由好幾個$j$個數（邊權）的乘積加起來得到的，其中每個乘積都代表一種這個連通塊中的選$j$條邊的匹配方法，$b[i-j]$也類似，因此把這兩個數相乘就對應了「所有在第一塊中選$j$條，在第二塊中選$i-j$條的所有匹配的權重和」，恰好就是我們要的了。

因此現在就對每個連通塊分開處理，在第一種算法中，因為他是二部圖，設在這個連通分量中被分成的兩部份分別有$x,y$個點，那麼考慮$dp[i][j]$代表所有滿足以下條件的匹配的權重總和：這個匹配在第一部份中只用到了前$x$個點，並且在第二部份中有被匹配到的點的集合恰好為$j$。這樣的DP可以在$O(|E|\cdot 2^y)$的時間內找出所有的 DP 值，其中$|E|$是這個連通塊的邊數（DP的轉移式蠻顯然的，這裡省略），進而求出這個連通塊的答案。因此當$x$或$y\leq 17$時就可以使用這個算法。這裡要先處理好這個連通塊中的那$x$個點和$y$個點分別是誰，還有一個點是落在他那部份的第幾個點。

再來則是第二種算法，先找出這個連通塊的任意一個生成樹，把所有非樹邊都找出來，然後$2^k$暴力枚舉要用哪些非樹邊。所以這裡如果有一個點屬於被選到的兩條邊的話就是不合法的。選完之後算出共有幾條邊，還有這些邊的權重乘積，並且把被蓋到的點都標記起來，等一下不能夠選到有碰到這些點的邊。再來則是對這棵生成樹DP，因為我們需要的東西是「這棵樹中所有有$t$條邊的匹配的權重總和」，所以每個節點紀錄的東西就會是一個陣列，代表「在他以下的這棵子樹裡，所有有$t$條邊的匹配的權重總和」的對於每個$t$的答案。再來看如何轉移，因為在算$x$的DP陣列時，有一種可能是「取了$x$連到他其中一個兒子的這條邊當作匹配邊」，因此我們紀錄的狀態還要再多一維（只有$0$或$1$），代表那棵子樹的根是否有被匹配。這樣就可以轉移了，注意到這裡是要從$x$的子樹的DP陣列們合併成$x$本身的DP陣列，這可以一個子樹一個子樹合併，也就是當我們合併完前$i$棵子樹時，$x$本身的DP陣列會是「只考慮$x$的前$i$棵子樹，加上$x$這個點形成的子樹」的DP陣列。具體來說，記$dp[i][j][k]$代表滿足「以$i$為根的子樹中，選了$j$對匹配點，$k$代表是否有選到根（$k=0$代表沒有）」這些條件的匹配的權重總和，並且假設現在在算$x$的DP陣列，記$x_1,...,x_r$為所有$x$的子節點，那麼記$dp2[i][j][k]$代表「只看$x_1,...,x_i$這些子樹再加上$x$形成的子樹，裡面選了$j$對匹配點，$k$的意義一樣」的匹配的權重總和，那麼就不難列出轉移式了：
$dp2[i-1][j][0]\cdot (dp[x_i][j_2][0]+dp[x_i][j_2][1])$  轉移到  $dp2[i][j+j_2][0]$
$dp2[i-1][j][1]\cdot (dp[x_i][j_2][0]+dp[x_i][j_2][1])$  轉移到  $dp2[i][j+j_2][1]$

$dp2[i-1][j][0]\cdot dp[x_i][j_2][0]\cdot w_{x,x_i}$  轉移到  $dp2[i][j+j_2+1][1]$

其中第三條轉移式只有在$x$和$x_i$都沒有被標記起來時才可以用，$w_{x,x_i}$代表$x$和$x_i$之間的這條邊的權重，邊界為$dp2[0][0][0]=1$。

如同許多需要在樹上合併DP陣列的題目一樣，因為每個節點的DP陣列大小都要開$k\cdot 2$，所以如果直接作的話單次DP複雜度會到$O(k^3)$，再乘上枚舉非樹邊的最差狀況$2^{17}$會TLE掉，而這只要注意到：對於一個子樹$x$來說，$dp[x][j][k]$在$2\cdot j>size[x]$時就都會是$0$了，因為沒有那麼多點可以匹配，其中$size[x]$是$x$的子樹的大小。因此當我們在從$dp2[i-1]$這個陣列去計算$dp2[i]$這個陣列時，令$S=x$的前$i-1$棵子樹的$size$總和$+1$，那麼我們只要用$dp2[i-1]$這個陣列的前$S/2+1$個值來轉移就好了（也就是$dp2[i-1][0][k],...,dp2[i-1][S/2][k]$），因為剩下的一定都是$0$。並且在枚舉$dp[x_i][j_2][k]$時$j_2$一樣枚舉到$size[x_i]/2$就夠了，後面的也都會是$0$。加了這件事之後單次DP複雜度就能降回$O(k^2)$了，證明可以參考這篇。大部份需要在樹上合併DP陣列的題目都可以用這件事來降複雜度。

code :

[CF 468D] Tree

作法：

首先先觀察最佳解的排列會滿足什麼特性。現在等於是樹上有$n$條路徑，分別是$i$走到$p[i]$。如果兩條路徑$(i,p[i])$和$(j,p[j])$沒有公共點的話，那麼把$p[i],p[j]$交換會讓答案更大，因此就可以得到在最佳解時任兩條路徑都有公共點。接下來證明若在一棵樹上有很多條路徑，並且任兩條路徑都有公共點，那麼所有路徑有一個公共點。記這些路徑為$P_1,...,P_k$，考慮$P_1$和其他路徑的交集部份，他們都是由$P_1$上的某一段連續的點組成的（所以可以看成一個區間），並且易證明任兩個區間都有交集，否則原圖中會出現圈，矛盾。那麼這個命題就變得顯然了，因為這樣的$n$個區間必定會有一個公共點。

再來我們想知道有哪些點有資格被當作所有路徑都經過的點。對於某個點$P$來說，考慮$P$的最大的子樹，如果這棵子樹的大小$>\left \lfloor \frac{n}{2} \right \rfloor$，那麼顯然$P$不能被當作剛才所說的公共點，因為在那棵子樹裡的點都必須連向不在那棵子樹裡的點，但那棵子樹裡的點太多了，所以矛盾。因此我們得到了公共點必須滿足「把他拔掉後剩下的所有子樹大小都$\leq \left \lfloor \frac{n}{2} \right \rfloor$」。並且不難證明這是充要條件，任意構造一個就可以了，在這裡省略。有了這個條件後就不難想到取重心應該是對的，而事實上也只有重心會滿足這個條件，證明就補在這篇的最後面。

因此就可以得到第一個答案是所有點到重心的距離和的兩倍，麻煩的是要求出字典序最小的解。首先以重心為根建成有根樹，我們把題目轉成二分圖完美匹配來看，對於$i$指向$p[i]$，可以把他看成「$i$的出點」連向了「$p[i]$的入點」，所以如果把每個點都拆成出點和入點，並且若$i,j$在不同的重心的子樹裡，那麼在$i$的出點和$j$的入點之間連一條邊，這樣就變成了求這張圖的字典序最小的完美匹配了。首先考慮這樣的算法：當要決定$p[i]$為多少時，就從$1$開始往上枚舉，找出第一個「$i$的出點連了他的入點之後整張圖還存在完美匹配」的點，並且他還沒被別人選過，那麼$p[i]$就等於他。但問題是要知道存在完美匹配的條件，才能從剩餘的候選人裡選出值最小的拿來當$p[i]$。記重心的所有子樹們為$T_1,...,T_r$，對於某個瞬間來說，假設$T_i$的出點數量為$a_i$，入點數量則為$b_i$（因此在一開始$a_i=b_i=T_i$的大小），那麼可以列出一條蠻顯然的式子：$a_i\leq b_1+...+b_{i-1}+b_{i+1}+...+b_r$，因為$T_i$中的剩下的出點必須去找$T_i$以外的子樹的入點來連，所以顯然個數要比候選人少。而由 Hall 定理（二分圖存在完美匹配的充要條件）可以得到這件事就是充要條件了。將上式改寫成$a_i+b_i\leq b_1+...+b_r$，並且易知$b_1+...+b_r$等於還沒匹配的點的對數，也就是我們得到了在任一瞬間，對於所有的$i$都必須滿足$a_i+b_i\leq$還沒匹配的點的對數。因此就得到了這樣的算法：當要計算$p[i]$時，先看看有沒有哪棵子樹的$a+b$的值已經等於還沒匹配的點的對數了（這裡還沒匹配的點的對數其實就等於$n-i+1$），如果有的話那麼$p[i]$就必須要從那棵子樹裡取，那麼就取那棵子樹中值最小的點即可。如果沒有這樣的子樹的話，就可以取$i$所在的子樹以外的所有點，因此也取這些點中的最小的點即可。實作上可以對每棵子樹紀錄一個 set ，代表還有哪些入點還沒用，還有一個 set 裡面放了每棵子樹的入點的最小值，根一個 set<pair<int,int>> ，其中 pair 的第一個值為某棵子樹的$a+b$值，第二個則為這是第幾棵子樹，維護好這些東西就好了。另外還要特判根，也就是要記得判$i$是根的情形，還有有可能取的$p[i]$是根的情形。

最後，以下證明前面提到的「一個點是重心若且唯若可以被當作公共點」。

設$P$為重心，若$P$不可被當作公共點，設$T_1$是$P$的大小$> \left \lfloor \frac{n}{2} \right \rfloor$的子樹，其根為$Q$，那麼把$Q$拔掉的話，包含$P$的那棵子樹的大小就會$<n-\left \lfloor \frac{n}{2} \right \rfloor=\left \lceil \frac{n}{2} \right \rceil$$\leq  \left \lfloor \frac{n}{2} \right \rfloor+1\leq T_1$的大小，並且把$Q$拔掉後的其他子樹大小顯然都會小於$T_1$的大小，因此把$Q$拔掉會讓剩餘的最大子樹的大小比把$P$拔掉的還要小，則$P$不是重心，矛盾。因此重心可以被當作公共點。

再來證明非重心的點不能被當作公共點，一樣設$P$為重心，並且$Q$不是重心，他落在$P$的$T_1$子樹中，那麼有$T_1$的大小$\leq \left \lfloor \frac{n}{2} \right \rfloor$，因此整棵樹扣掉$T_1$的大小$\geq \left \lceil \frac{n}{2} \right \rceil$，因此可以得到若$Q$想要當公共點，他就必須是$T_1$的根，並且滿足$T_1$的大小剛好是$\left \lfloor \frac{n}{2} \right \rfloor$，並且整棵樹扣掉$T_1$的大小要剛好是$\left \lceil \frac{n}{2} \right \rceil$，所以就可以得到$n$為偶數，$T_1$的大小為$\frac{n}{2}$，所以$Q$也是重心，矛盾。

code :

[CF 471E] MUH and Lots and Lots of Segments

作法：

首先大概可以想到把所有連通塊分開作（如果兩條線段有相交的話就在他們之間連邊，這樣子形成的連通塊）。對於一個連通塊來說，可以發現如果答案是用這個連通塊的話，所有線段會形成一個類似生成樹的東西，但也不完全是，而如果把一條線段的每個單位長全部拆開來，他就的確變成了一棵生成樹了，因此就只要算出這個連通塊的線段總共覆蓋了多少個格點，再減一就會是這個連通塊砍完多餘線段後剩下的線段長度了，這個部份就可以用掃描線作了。但要注意到如果有兩條同方向的線段有交集要先處理掉，把直的和橫的線段都轉換成同方向沒有公共點的線段們。再來問題剩下要如何把每個連通塊都分出來，這裡反而比較麻煩，首先考慮一個比較樸素的算法，利用掃描線按照縱座標由下往上掃描，維護此時有哪些$x$座標有鉛直的線段，並且在遇到一條橫線時把所有他有交到的鉛直線和他都連到同一個連通塊中，這裡可以用 disjoint set 實作。問題是這樣太慢了，而注意到要被歸到同一個連通塊裡的鉛直線們是在座標上連續的一段區間，所以可以考慮用 Treap 加上 lazy tag 來維護所有的當前鉛直線，當我們要把一段區間的所有區間都歸到同一個連通塊時，就把那段區間的 Treap 切下來，在他的根放上 lazy tag 然後 merge 回去就好了。並且這時也可以順便算答案，因為當遇到一條橫線，我們把對應的區間切下來時，被切下來的這棵 Treap 的大小就是這條橫線交到的直線數量，有了這些值和每條線段所屬的連通塊後就不難算出每個連通塊的答案，取最大的那個就是我們要的了。

code :

[CF 472G] Design Tutorial: Increase the Constraints

作法：

這題我是照官方解寫的，而有很多人是直接想辦法加速位元運算來過的，但我沒有仔細看他們的寫法，詳細可以去看看別人寫的 code 。總之我寫了FFT，首先把原始的第一個字串拆成好幾塊，每一塊都做一次FFT求得那一塊和第二個字串反過來的多項式乘積。對每個詢問都把他拆成遇處理好的幾塊根左右的一些小渣渣，那兩小塊就暴力做就可以了，但不能一個一個比，一個簡單的加速方法就是把這兩個字串的$64$個 bit 壓成一個數，然後直接對他位元運算，然後用$\_\_builtin\_popcountll()$這個函式來算出一個 long long 裡有幾個 bit 是$1$。這樣就能讓暴力那部份的常數少$64$倍。具體來說，只要先對兩個字串的每個位置都遇處理一個數，代表「從這個數開始往後數64個（若到底了就停），這些 bit 壓起來的值是多少」就可以了。

對了，這次的FFT我換成了模大質數和原根版本的FFT，以一個質數的原根來取代$1$的$n$次單位根，並且所有數字和運算都是在模那個大質數意義下進行的，詳細可以參考這篇。（這種寫法好像叫作NTT）

code :

[CF 472F] Design Tutorial: Change the Goal

作法：

這題我是照著官方解寫的，這裡紀錄一下大概作法和證明。

首先就是對給定的陣列和目標陣列做高斯消去，找出這兩個陣列的基底們。假設前者的為$u_1,...,u_x$，後者的則為$v_1,...,v_y$。再來我們需要一個函數把$v_i$以$u$們表示出來，或是回傳無解。也就是我們想要找出$a_1,...,a_x\in \{0,1\}$，使得$\displaystyle \sum_{i=1}^{x} a_i\cdot u_i = w$，其中$w$是一個給定的向量。這也可以透過高斯消去得到解，只要在作完高斯消去時從最後一個變數往前解回去就可以解出所有的$a_i$了（因為此時矩陣已變成了 row echelon form），詳細可以參考 code 。因此就從$v_1$開始，找出他用$u$表示的型式，然後不難把$u_i$們的$u_1$ xor 成$v_1$（因為已經知道他的組成了），並且做完這件事後（不難證明）$u_i$們還會是一組基底。而當我們已經把$u_1,...,u_k$都歸位了（也就是他們分別等於$v_1,...,v_k$時），首先找出$v_{k+1}$對$u_i$們的分解，這時因為我們不能再動到$u_1,...,u_k$，所以如果$u_{k+1}$本身不在$v_{k+1}$的組成中時必須拿$u_{k+2},...,u_x$這些向量的其中一個來和$u_{k+1}$交換，並且滿足這個向量在$v_{k+1}$的組成中。這件事是總是辦的到的，因為如果$v_{k+1}$的組成中沒有任何$u_{k+1},...,u_x$裡的向量，那麼就代表他是由$u_1,...,u_k$組成的，而$u_1,...,u_k$分別等於$v_1,...,v_k$，也就代表$v_1,...,v_k$可以組成$v_{k+1}$，和$v$是一組基底矛盾，因此這樣做不會有問題。最後還要注意到的是，如果$y<x$，那麼要記得把$u_{x+1},...,u_y$全部都自己 xor 自己變成$0$，才會和目標陣列高斯消去後的結果一樣。

code :

[CF 472E] Design Tutorial: Learn from a Game

作法：

首先當$n=1$或$m=1$時暴力枚舉即可。其他情形先確認是否所有珠子的個數都是對的，如果不是那就顯然無解。

首先可以想到策略大概就是一個一個把珠子歸位。首先拿起和目標盤面右下角同色的珠子，用他來轉，然後由上到下一排一排歸位，同排時由左到右一個一個歸位，直到剩下兩排時再從左到右兩顆兩顆歸位。當我們想要把$(x,y)$的珠子歸位時，如果當前手指的位置不在這裡，並且這格和目標格的顏色一樣，那麼什麼都不用作。反之找一個和這格的目標格顏色相同的珠子，假設位於$(x_1,y_1)$，那麼此時要想辦法把$(x_1,y_1)$轉到$(x,y)$上。首先找一條$(x_1,y_1)$走到$(x,y)$的路徑（走八方位都可以），這可以用DFS完成，並且在DFS時每次只走「離終點距離最近」的那幾個後繼節點。找到這條路徑後，假設$(x_1,y_1)$走上這條路徑的下一步是$(x_2,y_2)$，那麼此時只要想辦法讓手指的位置走到$(x_2,y_2)$，途中要避免走到$(x_1,y_1)$，然後再和$(x_1,y_1)$交換即可。因此我們需要一個「找一格到另一格的路徑，其中避免走到另外一格」的函式，不難發現一定存在這樣的路徑，實作也是DFS就可以了（和前面講到的那個DFS可以寫在一起）。

code :

[CF 549F] Yura and Developers

作法：

通常這種需要考慮區間最大值的題目，可以先令整個數列的最大值的位置為$x$，那麼所有包含了$x$的區間的最大值都會是$x$，這樣問題就變成要如何找有幾個包含$x$的區間，滿足他裡面的總和模$k$是給定的一個數。處理完這個之後就可以拆成$x$左邊和$x$右邊遞迴下去解了。考慮樸素的作法，就是直接枚舉包含了$x$的區間，這樣複雜度會高達$O(n^2)$，不過仔細想想可以發現，假設現在固定了所求區間的右端點，我們想要知道有幾個左端點可以讓這個區間滿足條件，而把一個區間的數的總和改寫成前綴和相減後就可以得到，這個問題就等價於「在前綴和陣列的某一個區間中有幾個數模$k$是某個特定的數」。這可以透過建立模$k$的餘數的所有出現的位置加上二分搜得到答案。於是現在處理上述問題的複雜度變成了其中一邊的長度再乘上$logn$，不過最差狀況下這樣還是會退化到$O(n^2logn)$，而事實上只要每次都取短的那邊去枚舉就好了，這樣複雜度就會是好的。因為當一個點被枚舉到一次時，他所在的區間就至少縮短了兩倍，因此每個點至多被枚舉到$logn$次，所以總複雜度就會是$O(nlog^2n)$。

code :

[CF 549G] Happy Line

作法：

這題只要觀察到：當$a_i$和$a_{i+1}$交換時，所有數形成的$i+a_i$的集合都不會變，因為當交換時這兩數的$i+a_i$值是從$(i+a_i,i+1+a_{i+1})$變成$((a_{i+1}+1)+i,(a_i-1)+i+1)$ 。並且顯然這是充要的，也就是如果兩數列的$i+a_i$集合相同，那麼就可以把一個變成另一個（只要一個一個放到對的位子就好了）。所以現在有了$i+a_i$的集合，我們想要讓$a_1,...,a_n$是遞增的，那麼$a_1$的值越小越好，那麼就取$i+a_i$集合裡最小的那個數扣掉$1$就是所求的$a_1$了，這樣取會是最好的。同理$a_2$會取集合裡第二小的數，以此類推。因此只要按照$i+a_i$值排序就可以找出解了。

code :

[CF 549C] The Game Of Parity

作法：

記總共有$x$個奇數和$y$個偶數。首先發現，如果最後一個人拿的時候奇數和偶數都至少還有一個，那他就贏了，因為他一定可以選其中一個使得他贏。所以非最受一手的那人就要想辦法把其中一堆拿光。這樣就分成四種情況：先手/後手最後拿、還有$k$是奇數/偶數。當先手最後拿時，如果$k$是奇數，那麼後手只能把$x$拿光，否則後手可以選擇把$x$拿光或把$y$拿光。當後手最後拿時，如果$k$是奇數，那麼先手就必須把$y$拿光，$k$是偶數時則必為後手贏。最後要記得判掉$n=k$的情形，這東西陰了一堆人=ㄦ=

code :

[CF 549B] Looksery Party

作法：

這題簡單來說就是，給定$n$個字串，還有一個目標字串$S$，要求在這$n$個字串裡選出幾個，使得把他們逐位加起來之後每位都和$S$不一樣。首先當$S$裡沒有$0$的時候顯然什麼都不取就可以了，而如果有一個位子$x$是$0$的話，因為題目保證第$i$個字串的第$i$項會是$1$，那麼就考慮直接取第$x$個字串看看，這樣可以發現：不管之後如何選，$x$那個位子的值只會增不會減，也就是之後可以完全忽略他了。這樣就得到了一個非常簡潔的算法：當還有位子的值和$S$的那個位子的值一樣時，就取對應的那個字串，一直作到滿足目標為止就可以了。

code :

[CF 477E] Dreamoon and Notepad

作法：

這題我是看了官方解的大概才會作的，這裡紀錄一下詳細的作法。

首先在讀入問題時，就可以把「按一次HOME」和「一路按往上/下到指定那列，再按左右調整到所求的位置」的答案算好了，後者需要一次RMQ，我是用 Sparse Table $O(1)$查詢的，因為之後也需要RMQ，用$O(1)$可以降一些複雜度。

對於官方解中的第二種情形，假設此次詢問是$(x_0,y_0),(x_1,y_1)$，其中可以假設$x_0\leq x_1$。那麼假設我們在第$x$列的時候按下了END，那麼走的步數就會是：$x_1-x_0+|y_1-min\{ a_x,...,a_{x_1}\} |+1$（注意到因為沒有按下END的情形已經在前面處理過了，所以這裡的$+1$是一定會存在的），並且$x$還要滿足$x\geq x_0$，因此此時會需要$min\{ a_x,...,a_{x_1}\}$這個東西的函數圖形。而不難知道這是一個隨著$x$變小而變小的階梯狀函數，所以考慮當$x$從$x_1$開始往左邊跑，把所有「$a_x$創新小」的點紀錄起來，具體來說那些「創新小」的點就是滿足$a_x<a_{x+1},...,a_{x_1}$的$(x,a_x)$（包含$x_1$本身）。有了這些點就可以很好的代表這個函數圖形了（之後稱這些點為這個函數的「代表」）。假設我們現在已經有了這個函數圖形（也就是這些點們），那麼可以發現我們要 minimize 的函數只和$y_1$和階梯函數的差值有關，因為這個階梯函數是單調的，所以只要找代表點們和$y_1$最接近的地方就可以了，因此就用一個 lower_bound 找出第一個$x$座標$\geq x_0$的代表是誰（假設叫$id_1$），然後從$id_1$到最後一個代表裡用一個 lower_bound 找出第一個$y$座標$\geq y_1$的代表是誰（假設叫$id_2$）（把代表點的$x$座標和$y$座標分開存就可以輕鬆 lower_bound 了），那麼就可以拿$id_2-1$和$id_2$代入上面那坨我們要 minimize 的函數裡面更新答案。這裡有可能所有代表的$y$座標都同時大於$y_1$或小於$y_1$，不過這樣的算法可以好好的處理這種情形。

但實作上總不能對每次詢問再去找出他的$x_1$造出的$min$函數的代表們，所以才離線處理所有詢問。把所有詢問按照$x_1$由小到大排序，用一個 stack 來存當此時詢問的 $x_1$ 值是 $i$ 的話他的代表們會長怎樣，那麼當詢問的$x_1$值變大的時候就不難維護這些代表們了。注意到這裡只處理了$x_0\leq x_1$的情形，當$x_0 > x_1$ 時必須略過這個詢問（因為現在這個 stack 不會是我們要的） ，這個到後面講實作的時候再來提要怎麼處理他。

再來是官方解中的第三種情形（這邊不用假設$x_0\leq x_1$），那麼此時就是先往上走到第$x$列，然後按下END（或不按），再往下走到目標列。我們先討論有按END鍵的情形，因為就算沒有按也可以按下一次（雖然沒有意義），之後再看怎樣的情形是可以不用按END鍵的，兩個都拿去更新答案就會對了。如果往上走到第$x$列，那麼總共的步數就會是$|y_1-min\{ a_x,...,a_{x_1}\} |+(x_0-x)+(x_1-x)+1$$=|y_1-min\{ a_x,...,a_{x_1}\} |-2x+x_0+x_1+1$。想像$x$從$x_0$開始慢慢變小，那麼一樣$min\{ a_x,...,a_{x_1}\}$會變小，$-2x$會變大，所以可以推得這個函數達到最小值的時候，其$x$座標一定會是那個$min$函數的一個代表。因為如果不是的話，那麼取這個點右邊的一個點，他的$min$函數值跟原本自己的一樣（因為他不是代表），但所求值中的$-2x$值變小了，因此所求函數在不是代表的數不可能達到最小值。再來想像當$x$一直變小，到有一天$min\{ a_x,...,a_{x_1}\}$ 變得$\leq y_1$時，比這個$x$小的所有數都不會讓這個函數取到最小值了，因此可以把求這個函數的最小值分為兩段來處理，一段是讓那坨$min$值$\geq y_1$的，另一段則是那坨$min$值$\leq y_1$的，由上面的推論知道第二段裡只須考慮一個點就好。對於第一段裡的代表們來說，可以把絕對值拆開，就變成$min\{ a_x,...,a_{x_1}\}-y_1-2x+x_0+x_1+1$$=(min\{ a_x,...,a_{x_1}\}-2x)+(x_0+x_1+1-y_1)$。因此我們要在$min$函數的代表們的一段區間中，詢問「代表的$y$座標扣掉兩倍的$x$座標」的最小值是多少，其中這個區間是滿足$min\{ a_x,...,a_{x_1}\} \geq y_1$且$x\leq x_0$的代表$x$們（一樣可以分別用個 lower_bound 求出）。因此在離線處理詢問維護 stack 的同時也要維護一棵線段樹，這顆線段樹用來維護的底層序列的第$i$項的值就是現在在 stack 中的第 $i$ 個代表的$y$座標扣掉兩倍$x$座標的值。那麼當把一個東西 push 進 stack 的時候就等於修改這棵線段樹的底層序列的某個值， pop 的時候則什麼都不用作，這樣就能得到上述函式的最小值了。

接下來還要處理不用按END的情形，還有被分出來的$min$值$\leq y_1$的那個代表。先看前者，既然不用按END，那麼代表此時是從第$x_0$列往上走到第$x$列，然後直接往下走回第$x_1$列，並且我們需要 minimize 的式子和剛才那條幾乎一樣，兩式只有差$1$，所以可以套用剛才的一些結果。在這裡分成兩種情形來看，首先是$x_0\leq x_1$時，由剛才的結論可知最佳解$x$一定是一個代表，那麼此時就必須滿足$a_x\leq y_0$，又因為$a_x$是個代表，所以可以寫成$min\{ a_{x_1},...,a_x \} \leq y_0$。反過來當$x$滿足他是一個代表，並且$a_x\leq y_0$時，不難得出從$x_0$往上走到$x$時其橫座標會停留在$a_x$，所以此時不用按END。再來則是$x_0\geq x_1$時，那麼當從$x_0$往上走的時候，會先經過$x_1$，此時其橫座標會是$min\{ y_0,a_{x_1},...,a_{x_0} \}$，並且由一樣的理由可以得到此時$x$必須滿足$a_x\leq min\{ y_0,a_{x_1},...,a_{x_0} \}$，且他也是充要條件（這就可以用之前建好的 Sparse Table 來算）。因此這樣就得到了「不用按END」的那些列的範圍了，只要再用一次 upper_bound 就可以得到此時$x$必須$\leq$某個值，再和前面「不考慮是否要按END」時得到的區間交集，就知道要對線段樹的哪一段 query 了，然後拿上面的式子的值去更新答案（但此時是少了$+1$的）。

最後則是被分出來的$min$值$\leq y_1$的那個代表，由上面的條件容易確認當$x$等於他時到底要不要按END，一樣拿他去更新答案即可。

到這裡我們解決了官方解中的第一、三種情形，還有第二種情形的一半，接下來則是要把整個$a$數列反轉，把每一個詢問也反轉（原本的$x_0,x_1$變成$n+1-x_0,n+1-x_1$），再重做一次上述過程就可以了（Sparse Table 要重建，線段樹則不用理他），這樣就能把官方解中剩餘的情形（二的一半和四）補完了。

code :

[CF 477D] Dreamoon and Binary

作法：

這題我的作法跟官方解幾乎一樣，但最後輸出答案的時候可能會有問題。因為題目要問的是「最後一塊的數字大小加上切的塊數」的最小值，所以可能可以想到最後一步就是枚舉最後一段的開頭是誰，那麼從$dp[i][n]$就可以得出答案。但我們總不能把所有所求的答案用大數表示出來後再來比大小，這樣時間可能會很恐怖。只要注意到因為切的塊數$\leq n\leq 5000$，並且當最後一個區間越來越大時，最後一塊的數字大小幾乎是一直在乘$2$的（因為最後一塊的開頭當然也不能是$0$），因此在大約十幾之後數字大小就會成為主要的關鍵。因此最後的找法就變成：先考慮長度$\leq 20$的後綴，如果有可以達到的狀態，把他們的答案的值都算出來，找出他們的最小值，那麼這個數就會是答案了。否則從長度$20$的後綴開始往長度大的方向找，找到的第一個合法狀態就會是答案了。

code :

[CF 550E] Brackets in Implications

作法：

這題就是個構造題，看了這份code之後就覺得我寫的解也太複雜了QQ
首先我是考慮用遞迴來輸出解，所以對於一個區間$[L,R]$來說，當要 print $[L,R]$ 中的數時，用一個 map 來存這個區間的切的端點是誰，也就是令那個值等於 $mid$ 的話，要先遞迴下去$[L,mid]$輸出，再遞迴下去$[mid+1,R]$輸出。首先觀察出當$a[n]=1$時無解，所以只須考慮$a[n]=0$的情形。注意到因為$1\rightarrow 0=0$，因此可以先讓所有的$0$把他左邊所有的$1$都吃掉，讓整串剩下全部都是$0$。如果只剩一個$0$那就做完了。否則如果剩下的$0$的個數$\geq 3$，那麼就可以把倒數第二和第3個$0$包起來變成$1$，$1$再往左把所有的$0$作用掉，最後再和右邊的$0$作用。至於兩個$0$的情形，如果$a[n-1]=0$，那麼可以推得此時也無解（怎麼消都還是長一樣），所以只須考慮原本的兩個$0$之間有$1$的情形，這時則可以先用$1$把那個$0$消掉，這樣就變成只有一個$0$的情形了。

code :

[CF 550D] Regular Bridge

作法：

這題我的構造跟官方解的一樣，這裡就寫一下我是怎麼想到的。
因為要有橋，所以大概可以想到把橋的兩邊分開構。因為每個點的度都要是$k$，所以當把橋拔掉後，其中一個連通分量裡每個點的度會長的像：$k-1,k,...,k$。因此當$k$是偶數的時候無解，因為度總和必須是偶數。當$k$奇數時，$k=1$題目構完了，如果$k=3$，先試著構一個度為$2,3,3,3,3$的圖（因為$3$個$3$時奇偶性不對，$3$個以下時點太少），假設五個點分別為$ABCDE$，那麼先連$BD,CE$，剩下的只要再找一個圈就可以了，也就是連上$AB,BC,CD,DE,EA$，這樣就構完$k=3$的情形了。仔細觀察可以發現，其實他就是一個$k+2$接完全圖，拔掉$A$和其中兩個點（$C,D$）連的邊，然後把剩下的點（$B,E$）兩兩配對，把他們之間的邊拔掉所得來的，並且這個構造容易推廣到$k$是更大的奇數的情形，於是在把兩個這樣的圖用橋連起來就做完了。

code :

[CF 480E] Parking Lot

作法：

把整個過程反過來，變成原本有很多格子是被佔的，當一格一格移除時詢問此時的答案是多少，那麼顯然答案會是遞增的。假設當前答案為$A$，那麼當移除一個格子$(x,y)$時，如果答案變大了，那就代表新的正方形一定包含了(x,y)。因此我們需要判斷「是否存在一個正方形，邊長為$A+1$，並且包含了$(x,y)$」。每次修改一個點之後就一直增加答案，直到不存在那麼大的正方形為止，那麼可以知道這個函數只會被呼叫$O(n)$次，因此可以考慮在$O(nlogn)$的時間實作他。

假設現在要處理的是包含$(x_0,y_0)$的邊長為$k$的正方形，那麼在這個正方形有覆蓋到的每一個橫排中，都包含了$y$座標為$y_0$的格子，並且這個正方形有可能覆蓋的橫排至多有$2k-1$個。因此如果我們對每個橫排，都找出$y$座標離$y_0$最近但比$y_0$小/大的格子，就知道如果那個正方形摸到了這個橫排，那麼他一定要被卡在哪兩個格子之間了。也就是對每個$i\in [x_0-k+1,x_0+k-1]$，記$L[i],R[i]$代表在這個橫排中，第$L[i]$到第$R[i]$個格子都是未被佔領的，並且其中包含了$y_0$。注意到如果$y_0$本身就已經被佔領了，那麼就可以把這個區間為設為$[y_0,y_0-1]$之類的空區間。有了這些$L,R$值之後，只要看連續$k$個橫排的$L$值的最大值，和同樣這$k$排的$R$值的最小值，看相差是否有$\geq k-1$就可以了。因此就從上往下掃，用兩個 multiset 維護$L,R$值們就好了。另外記得預處理每個橫排中有哪些被佔領的格子，把他們加入一個 set 中，才可以用 lower_bound 快速找出$L,R$的值。

code :

[CF 480D] Parcels

作法：

首先把每個箱子的進入時間和出去時間畫在數線上，轉換成一條線段，那麼可以到如果有兩個箱子都有出現在台子上，那麼要嘛一個箱子的線段完全包含另一個的，要嘛兩個箱子的線段不相交（端點可以碰到），或是說他會形成一個類似樹形結構的東西，所以大概可以想的到是某種DP。以下我們稱滿足上述條件的線段們為「合法的」，還有如果把這些線段（箱子）拿去模擬放在平台上的話平台所需支撐的最大重量為這群線段的「最大重量」。

我們要處理的問題是「在這個耐重$S$的台子上，使用那$n$條線段所獲得的最大價值」，因此我們可以加上第$n+1$個箱子，他對應的線段是$[0,2n-1]$，耐重是$S$。因此就可以考慮以下的DP狀態：$dp[i][j]$代表現在只考慮所有第$i$條線段所包含的線段（包括$i$本身），那麼當在這之中選出一群合法的線段，並且這群線段的「最大重量」不超過$j$時，所能獲得的最大價值。在轉移的部份，如果$i$沒有自己以外包含在他內部的線段，那麼他的所有$dp$值都是顯然的。否則第一種轉移方法是：不取第$i$條線段，此時我們可以選好幾條包含在$i$內的線段$S_1....,S_r$，滿足任兩條線段不相交（可以端點重合），轉移到$dp[S_1][j]+...+dp[S_r][j]$。另一種轉移方法則是取$i$，那麼就會直接等價於$dp[i][min(str[i],j-wei[i])]$的情形了，其中$str$代表那個線段的強度，$wei$則是代表重量。顯然第一種轉移沒辦法直接轉，這裡我們可以再用一個DP，因為當$i,j$確定時，對於所有包含在$i$內的線段$k$（$k\neq i$），取他的話等於價值增加了$dp[k][j]$，也就是會是固定的，因此這裡就可以轉換成簡單的問題：數線上有$m$條線段，每條線段都有他的價值，求取好幾條線段使得他們兩兩不相交（可以端點重合）的話價值總和的最大值。這顯然可以先對每條線段的右端點排序、離散化，然後令$dp2[i]=$只考慮線段座標落於$[1,x]$之類的線段時所能獲得的最大價值，則轉移是顯然的。

總結來說，可以先把所有線段按照右端點由小到大排序，一樣時按左端點由大到小排序，那麼上面說的DP過程就可以按照$1,2,...$的順序來做了。並且在作一條線段的DP值時，找出有哪些線段被他包含在裡面，假設有$k$條好了，那麼就可以在$O(klogk+Sk)$的複雜度內求出這條線段的所有DP值了，其中$S$是箱子們的最大強度。

code :

[CF 482E] ELCA

作法：

這題我的作法根官方解只有後半部不一樣，就是在算答案的那部份。前面幾步一樣就是當我們要處理連續的好幾個詢問時，把整棵樹重建（因為可能有一些點被拔到其他地方了），先把那些重要的點找出來，之後叫他們黑點，其餘的則為白點。並且把黑點構成的樹建出來，稱他為新樹，原本題目給的則為原樹。我們要維護的值有兩個東西，就如官方解裡寫的$path$值和$ch$值。首先看如何求$path$值，令$d[x]=(size[fa[x]]-size[x])\cdot val[fa[x]]$，其中$size[x]$為$x$（在原樹）子樹的大小，$fa[x]$則代表$x$在原樹的父節點，$val[]$則是那個節點上標的值，則$x$的$path$值就是由$x$開始一路往上走，走到$1$之前把所有的節點的$d$值加起來（對了，我還有多把$1$標成黑點，這樣新樹的根也是$1$了，不用再區分）。由這件事就可以得到$path$值的算法：如果對每條新樹中的邊都紀錄這條邊上經過的所有點的$d$值總和，那麼一個黑點的$path$值就可以一路沿著祖先的邊走上去並加總得到了。具體來說，假設$x\rightarrow y$是新樹中的一條父親指向孩子的邊，並且令$y$沿著原樹的父親走上去經過的路徑為$y=s_1,...,s_{r-1},s_r=x$，那麼就讓$x\rightarrow y$這條邊上紀錄的值等於$d[s_1]+...+d[s_{r-1}]$（之後叫他$dsum$值）。

再來則是$ch$值（在我的code裡是叫作$pnum$），對於原樹中的一個點$x$，容易得出他的$ch$值會等於$\displaystyle size[x]^2-(\sum_{i}size[i]^2)$，其中$i$跑遍所有$x$的子節點。在建圖的時候可以先對原樹DFS一次，求出每個點的$ch$值，重點是當我們把一個點拔掉和接回去的時候要如何更新每個黑點的$ch$值。如果每次操作完都重新算一次所有黑點的$ch$值的話複雜度會是好的（黑位黑點不多），但不能重算所有黑白點的，因此只能對新樹DFS一次。所以就可以得到對於每條$x\rightarrow y$的邊，我們必須紀錄$size[s_{r-1}]$是多少（$s_i$同上面的記號）（之後叫他這條邊的$ssz$值），這樣才能在新樹中DFS時算出每個黑點的$ch$值。因此每條新樹中的邊會紀錄$dsum$值和$ssz$值。但光這樣還不夠算出黑點的$ch$值，因為在原樹中有可能黑點有一個子樹是全部都是白的，我們當然也要知道他的大小的平方和，因此對每個黑點$x$還要紀錄一個值$sz2sum$，代表：若$t_1,...,t_z$為$x$在原樹中所有全白子樹們的大小，則其為$t_1^2+...+t_z^2$，這樣就能在重新DFS時算出每個點的$ch$值了。

整理一下上面的算法，在處理每次詢問時我們要維護好的值有：每條新樹邊上的$dsum$值、$ssz$值，還有每個黑點的$size$值、$val$值（這兩個在維護前面那些東西時會需要）、$sz2sum$值、新樹中的父節點、$pnum$值（這是在詢問結束後再對新樹DFS計算）。當拔掉一個節點$y$的子樹時，會影響到的東西有：從$y$沿著新樹邊走上去的所有邊上的兩個值，和路上經過節點的$size$值，並且要記得順便計算$y$的$path$值是多少。那些數的變動值不難由定義得出，這邊就省略。在接回去的時候影響到的東西也是那些，所以照做一次就可以了，而在接上去時這條新產生的邊的$dsum$值和$ssz$值顯然分別會是$d[y]$和$size[y]$。最後記得再DFS一次求$pnum$。至於此次詢問是改一個點$x$的值的話，會影響到的則是所有$x$連到他孩子的邊上的$dsum$值，變動大小也不難推出。

這樣傳上去之後WA第三筆，我辛苦的把他的樹畫出來模擬後發現我漏了好幾個很容易忘記的東西，一個是當我們拔去$y$所在的子樹時，記$y$的父親為$f$，那麼$f$的$sz2sum$值必須要增加！因為此時$f$多了一棵全白的子樹，他原本是用來連接$y$的，現在$y$沒了當然要加回他的$sz2sum$中。另外則是我在DFS計算$pnum$值的時候，如果此時這個點是新樹的葉節點，那麼就直接 return （因為在原樹建完，處理詢問之前會有一次DFS，把每個黑點的$pnum$值都算好了，而在新樹中的葉節點的$pnum$值顯然在這好幾次詢問中都會保持相同）。這樣會有個很不明顯的問題，就是有可能一個黑點在新樹中的子節點都被拔光了，自己成為了葉節點，那麼在算他的$pnum$值就直接 return 了，這不是我們想要的。解決這個問題的方法就是當我們發現把一個點拔掉之後會讓他父親成為葉節點時，就趕快把他的$pnum$值算好就好了（其實就是$size$值平方扣掉$sz2sum$值）。

code :

[CF 482D] Random Function and Tree

作法：

令$dp[x][b]$代表以$x$為根的子樹中塗了個數的奇偶性為$b$的節點有幾種塗法，首先算出「選出這棵子樹要塗色的集合」有幾種方法，再來算考慮黑白色時有幾種方法。不難用一次DP算出這棵子樹塗上奇數（或偶數）個點時有幾種塗法（不考慮黑白的問題），但對於某一種塗法來說，從左邊塗過來根從右邊塗過來可能不一樣，也可能一樣。而所求就會是剛才求出的值的兩倍，再扣掉「從左塗和從右塗會一樣」的不考慮黑白的塗法數，因此接下來要想辦法算出後者的值。假設$x$的子樹為$T_1,...,T_r$，並且這種塗法分別在每個子樹裡塗了$a_1,...,a_r$個點。那麼從左邊塗過來的話，$T_i$的根節點的顏色就和$a_1+...+a_{i-1}$的奇偶性有關（注意到當根節點顏色確定，整棵子樹的顏色就確定了），從右邊塗過來則是和$a_{i+1}+...+a_r$的奇偶性有關。因此當兩種塗法一樣時，代表對於所有$a_i>0$，$a_1+...+a_{i-1}$和$a_{i+1}+...+a_r$的奇偶性相同，又等價於對於所有$a_i>0$，$a_1+...+a_{i-1}+a_{i+1}+...+a_r$為偶數，也就是所有$a_i>0$的$i$都必須和$a_1+...+a_r$的雞偶性相同。不難得到滿足這種條件的$a_i$只有兩種可能，一種是全部都是偶數，另一種是$a_1,...,a_r$中每個數不是奇數就是$0$，並且裡面有奇數個奇數。這兩個也都不難用DP對子節點掃一次得出，因此就完成轉移了。

code :

[CF 482C] Game with Strings

作法：

首先考慮一定會對的DP方法：設$dp[S][i]$代表當目前猜的位置的二進制表示為$S$，且所選的答案為第$i$個字串時，期望還要再猜幾次。計算這個DP值的方法並不難，如果$S$裡的這些位置已經可以唯一確定第$i$個字串的話，他的DP值就是0，否則$\displaystyle dp[S][i]=1+\frac{1}{k}\sum_{j} dp[S| (2^j)][i]$，其中$j$滿足他是還沒被猜過的位置，$k$是還沒被猜過的位置個數。最後答案就是$\displaystyle \frac{1}{n}\sum_{i=0}^{n-1} dp[0][i]$。但這樣時間和空間都會爆掉，所以需要改進。

事實上我們可以把這些DP值的第2維壓起來，也就是令$dp2[S]=dp[S][0]+...+dp[S][n-1]$，而因為當$S$能唯一辨別第$i$個字串時$dp[S][i]=0$，也就是我們可以把剛才的轉移式改寫成：若$S$能唯一辨別第$i$個字串，則$\displaystyle dp[S][i]=\frac{1}{k}\sum_{j} dp[S| (2^j)][i]$（其實他就是$0=0+...+0$）。那麼由這條式子就可以推出$dp2$的轉移式了，他會是$\displaystyle dp2[S]=num[S]+\frac{1}{k}\sum_{j} dp[S| (2^j)]$，其中$num[S]$代表$S$辨別不出來的字串的個數。

所以問題轉換為要如何求出所有的$num[S]$，考慮任兩個字串$s_i,s_j$，設$s_i$和$s_j$共同的部份的集合為$S0$，那麼所有$S0$的子集合都沒辦法辨識出$s_i$和$s_j$。因此如果對於每個$i$，找出所有$j$對應的$S0$（當然$j\neq i$），那麼所有這些集合的子集合的聯集就是所有沒辦法辨識出$s_i$的集合。可以用DFS來處理這個問題，設$in[S]$代表$S$這個集合已經在剛才那些集合的聯集裡了，那麼所有$S$的子集合也會在裡面，因此當我們多加入一個集合，準備把他的所有子集合的$in$值設成$1$的時候，就直接DFS下去，並且遇到$in$值已經是$1$的數就直接return 就好了，這樣複雜度會是$O(n2^m)$，其中$m$是字串的長度。

但這樣傳上去TLE了，後來看解才知道，其實可以令$d[S]$代表「用$S$沒辦法辨識出的字串集合」，那麼當我們找到$s_i$和$s_j$的$S0$時，讓$d[S0]|=(2^i)$根$(2^j)$，這樣就得到了初步的$d$值們，但我們還要求，如果$S2$是$S1$的子集合，且$S1$不能辨識$i$，那麼$S2$也不行，而這只要按照數字大到小，把$d[S]$的值拿去 $or$ 上所有$d[S']$的值就可以了，其中$S'$是包含$S$且他們只差一個bit的集合。最後看$d[S]$有幾位是$1$就知道他不能辨別多少字串了。

code :

[CF 547E] Mike and Friends

作法：

因為題目要問的東西就是$s_k$在$s_l,...,s_r$裡出現了幾次，所以如果按照$s_1,...,s_n$把所有字串接在一起，並在中間插入沒看過的字元（例如$\$$），那麼問題就變成了詢問一個字串在某個區間裡出現了幾次。設整串接起來的字串為$S$，首先先建出$S$的後綴數組，那麼當遇到一個詢問$l,r,k$時，查詢$s_k$在$S$裡出現的位置，假設為$sa[L],...,sa[R]$，並且可以把「在$s_l$到$s_r$中間出現」的條件等價成「出現的位置落在某個區間中」，假設那個區間為$[L2,R2]$好了（有可能長度$\leq 0$，這個可以先判掉），那麼問題就變成詢問$sa$陣列在$[L,R]$之間有幾個數介於$[L2,R2]$之間，並且所有數字都$\leq 4\cdot 10^5$，因此就可以用持久化線段樹來作了。而我們必須預處理出每個$s_i$所對應的$[L,R]$，不然每次詢問才去後綴數組裡詢問就太慢了。

code :