這題感覺我的作法爛爛的，建議先理解官方解還有dreamoon的code，都寫的蠻清楚的@@
作法：
首先考慮一個會有問題的作法：對於每個點，往他上下左右四個方向最近的點分別連一條邊（如果沒有點就不用連），然後直接對這張圖二塗色。而這樣隨便都能構一個出現奇環的測資讓他爛掉，因此我們可以考慮先把圈都拔光，具體來說，我們考慮一種比較特別的圈，如果沿著這樣的圈一直走的話，走的方向依序是「橫直橫直......」，也就是每走一個點都會轉$90$度。顯然這樣的圈的點數為偶數，那麼沿著這個圈一路途上紅藍交錯的顏色，就可以把這個圈上的所有點砍掉了，因為塗完後他讓每條鉛直線和水平線上的紅藍點數增加的個數相同。因此只要把這種圈都砍完之後，剩下的圖就可以用剛才提到的那個演算法了：直接把圖建出來二塗色，因為此時已經沒有圈了（容易證明，當不存在剛才那種「特別的圈」時，原本的圖裡也不會有圈），所以直接塗就可以了。
所以重點在於要如何找圈然後把他拔掉，首先考慮直接DFS的算法，也就是走到一個點的時候，考慮所有和他同行（或同列，只會是其中一個，因為我們要找的是剛才提到的特別的圈）的點DFS下去，當找到一條回邊，也就是形成了一個圈時，就沿著父親一直走上去，並沿路塗色，塗完後直接中斷這次的DFS，一直 return 回去直到當前的點的答案還沒被決定為止，然後之後在DFS的時候就可以完全無視那些已經被塗過色的點了。這個算法還有需要注意的地方，因為當我們最一開始DFS的時候一定是先選一個方向去DFS，也就是假設從這個點出發是先走橫的，這樣之後DFS的過程就知道現在這個點的下一步是走橫的還是直的。而如果結束DFS的時候根節點還沒有被塗色，就要去DFS起點是走直的的情況，否則之後在以其他點當根DFS的時候，當戳到了這個還沒被塗色的舊根節點時會誤以為這是一條回邊，這時沿著父親走就會爛掉。
顯然這個算法複雜度會爛掉，於是我只好用 linked list 優化 DFS ，這東西在TIOJ 1220也有用到類似的東西（雖然我當時的解不是那樣做的），具體來說就是：對每個$x$座標維護一條 linked list ，代表當前的$x$座標等於他的點中還剩下這些點。對每個$y$座標一樣也有一條 linked list 。由這裡可以看出每個原圖中的點$P$會對應到兩個在 linked list 中的節點$nx,ny$（其中$nx$是被放在「$x$座標的lonked list」中的節點，$ny$則是$y$座標的），並且讓$nx$代表走到$P$時下一步是要走鉛直方向的，$ny$則是代表走到$P$時下一步是要走水平方向的。
建好 linked list 後就可以DFS了，當走到一個點$P$時，假設他現在要走的是直的方向，那麼就先把他對應的$nx$拔掉，然後去他的$x$座標這條 linked list 裡找後繼節點，當找到一個後繼節點$Q$時就直接把$Q$對應的$nx$拔掉再DFS下去，一樣當找到一個圈的時候就一樣沿路塗色並一直 return 。但這樣做會有問題，會發現根本找不到圈，因為當一個點被走到時他所對應的$nx,ny$都已經被拔掉了，之後當然就不會有任何邊走向他了。解決方法是當在DFS時，假設現在是$P$找到了他的後繼節點$Q$（和剛剛一樣），那麼在DFS下去之前先不要把$Q$的$nx$拔掉，等到DFS出來之後再拔掉，因為如果有圈形成的話他的回邊一定是連向$Q$的$nx$的。最後還要注意到剛才用 linked list 優化之前的那個細節，也就是根節點要記得擴展完，因此當最一開始DFS進去是選$x$方向的 linked list 的話，出來之後發現根節點還沒被塗色，就要試試看選$y$方向的。
code :
2015年5月31日 星期日
[CF 547C] Mike and Foam
作法：
首先可以把問題化為：支援一個資料結構，可以加入和刪除數，並且詢問目前裡面有幾個數和給定的某個數互質。設當前詢問的數是$x$，其因數由為$d_1,...,d_r$，那麼$x$和所有當前裡面的數的 gcd 值只有可能是$x$的因數，因此設目前總共有$a_i$的數和$x$的 gcd 等於$i$，則只有$x$的因數的$a$值非$0$，而我們想求的就是$a_1$。單一個$a_i$的值不容易求，但如果令$num_i$代表目前這些數裡面有幾個數是$i$的倍數，顯然可以在加入和刪除一個數時維護好$num_i$的陣列，那麼考慮$num_{d_i}$，他其實就會等於所有滿足$d_i | d_j$ 的$a_{d_j}$ 的總和，也就是如果令$A_i=\{ d_j | d_j\%d _i=0 \}$，那麼$\displaystyle num_{d_i}=\sum_{t\in A_i}a_t$，因此現在要用已知的$num_{d_i}$們的式子來求出$a_1$。再來就有點類似莫比烏斯反演的概念了，那東西的詳細可以參考維基，其實和這題一樣本質上來說就是排容原理。不妨設$d_1,...,d_k$就是$x$的所有質因數（不包含$1$），那麼考慮集合$A_1,...,A_k$，跟他們的宇集$\{ d_1,...,d_r \}$，並且以下記$|S|$代表$S$中所有元素的$a$值的和。可以得到$A_1\bigcup A_2\bigcup ... \bigcup A_k$包含了所有$x$的非$1$的因數，因此用宇集扣掉他之後就只剩下$1$，也就是我們要求扣掉之後的集合內元素的權值和（雖然他只有一個元素）。這時就可以用排容了，首先宇集的權值和就是$num_1$，再來要扣掉$|A_1|,...,|A_k|$，由上面的結論可以知道$|A_i|$就是$num_{d_i}$，直接代入即可。再來要加回長的像$|A_i\bigcap A_j|$的這種東西，這裡就是莫比烏斯變換關鍵的地方，因為$d_i$和$d_j$是兩個$x$的不同的質因數，所以他們互質，而回到$A_i$的定義，他裡面蒐集了所有是$d_i$倍數的$x$的因數，所以由$d_i,d_j$互質就可以得到$|A_i\bigcap A_j|=num_{i\cdot j}$，因為他們的交集就代表著滿足他是$d_i,d_j$倍數的$x$的因數，所以是滿足他是$d_i\cdot d_j$倍數的$x$的因數，所以就可以化簡成$num_{i\cdot j}$了。到了好幾個$A$交集在一起時一樣可以融合起來變成一個$num$值，於是這樣就成功求出答案了。
而實作的方法又轉了個彎，因為注意到上面那條式子裡面，我們會用到的$num$值的下標都是「沒有平方因子的數」(square-free)，或是說把他質因數分解的話會分成好幾個不同的質數的一次方相乘，而$num$值前面的係數則和當前下標的質因數個數有關，若個數為奇數則為$-1$，若為偶數則為$1$，這東西就是莫比烏斯函數，因此在計算上我們只要先把$x$的所有因數找出來，求出所有因數的$num$值乘上其莫比烏斯函數的值的總和就可以了。
code :
首先可以把問題化為：支援一個資料結構，可以加入和刪除數，並且詢問目前裡面有幾個數和給定的某個數互質。設當前詢問的數是$x$，其因數由為$d_1,...,d_r$，那麼$x$和所有當前裡面的數的 gcd 值只有可能是$x$的因數，因此設目前總共有$a_i$的數和$x$的 gcd 等於$i$，則只有$x$的因數的$a$值非$0$，而我們想求的就是$a_1$。單一個$a_i$的值不容易求，但如果令$num_i$代表目前這些數裡面有幾個數是$i$的倍數，顯然可以在加入和刪除一個數時維護好$num_i$的陣列，那麼考慮$num_{d_i}$，他其實就會等於所有滿足$d_i | d_j$ 的$a_{d_j}$ 的總和，也就是如果令$A_i=\{ d_j | d_j\%d _i=0 \}$，那麼$\displaystyle num_{d_i}=\sum_{t\in A_i}a_t$，因此現在要用已知的$num_{d_i}$們的式子來求出$a_1$。再來就有點類似莫比烏斯反演的概念了，那東西的詳細可以參考維基，其實和這題一樣本質上來說就是排容原理。不妨設$d_1,...,d_k$就是$x$的所有質因數（不包含$1$），那麼考慮集合$A_1,...,A_k$，跟他們的宇集$\{ d_1,...,d_r \}$，並且以下記$|S|$代表$S$中所有元素的$a$值的和。可以得到$A_1\bigcup A_2\bigcup ... \bigcup A_k$包含了所有$x$的非$1$的因數，因此用宇集扣掉他之後就只剩下$1$，也就是我們要求扣掉之後的集合內元素的權值和（雖然他只有一個元素）。這時就可以用排容了，首先宇集的權值和就是$num_1$，再來要扣掉$|A_1|,...,|A_k|$，由上面的結論可以知道$|A_i|$就是$num_{d_i}$，直接代入即可。再來要加回長的像$|A_i\bigcap A_j|$的這種東西，這裡就是莫比烏斯變換關鍵的地方，因為$d_i$和$d_j$是兩個$x$的不同的質因數，所以他們互質，而回到$A_i$的定義，他裡面蒐集了所有是$d_i$倍數的$x$的因數，所以由$d_i,d_j$互質就可以得到$|A_i\bigcap A_j|=num_{i\cdot j}$，因為他們的交集就代表著滿足他是$d_i,d_j$倍數的$x$的因數，所以是滿足他是$d_i\cdot d_j$倍數的$x$的因數，所以就可以化簡成$num_{i\cdot j}$了。到了好幾個$A$交集在一起時一樣可以融合起來變成一個$num$值，於是這樣就成功求出答案了。
而實作的方法又轉了個彎，因為注意到上面那條式子裡面，我們會用到的$num$值的下標都是「沒有平方因子的數」(square-free)，或是說把他質因數分解的話會分成好幾個不同的質數的一次方相乘，而$num$值前面的係數則和當前下標的質因數個數有關，若個數為奇數則為$-1$，若為偶數則為$1$，這東西就是莫比烏斯函數，因此在計算上我們只要先把$x$的所有因數找出來，求出所有因數的$num$值乘上其莫比烏斯函數的值的總和就可以了。
code :
2015年5月30日 星期六
[CF 487E] Tourists
作法：
這題的官方解大部份講的蠻清楚的，主要就是要先知道那個引理，然後把原圖的BCC樹建出來，對每塊縮完後的BCC（或是單一一個割點）維護那塊目前的最小值，然後對BCC樹作樹鍊剖分，讓他可以支援「修改點權與詢問某條路徑上點權最小值」這兩件事。但官方解裡提到的「只要更新其祖先的那塊BCC的值就好了」寫的不太清楚，這裡詳細解釋一下。
以下圖舉例，右邊是用BCC縮完點後的圖，其中紅色是割點，黑色的是一塊BCC。對於每個BCC都維護一個 multiset ，裡面裝的值是「在這個BCC內的點，除了他的祖先以外的所有點的值」，並且這坨BCC在新的樹當中的「點權」就會是這個 multiset 裡最小的數，割點在新的樹裡的點權則和原圖中的一樣。例如在下圖中，$2,3,4,5$這坨BCC在新的圖中他的點權就會是$2,3,4$的點權的最小值，$2,6,7$那坨則是$6,7$點權的最小值，其他以此類推。這樣就能在$O(logn)$的時間內完成修改了。具體方法是，如果改的點是割點的話，會動到的新圖中的點權有割點本身，還有他的父親BCC（如果他有父親的話一定是一坨BCC）。而如果改的點不是割點的話就只會動到他所屬的BCC的權值而已。
code :
這題的官方解大部份講的蠻清楚的，主要就是要先知道那個引理，然後把原圖的BCC樹建出來，對每塊縮完後的BCC（或是單一一個割點）維護那塊目前的最小值，然後對BCC樹作樹鍊剖分，讓他可以支援「修改點權與詢問某條路徑上點權最小值」這兩件事。但官方解裡提到的「只要更新其祖先的那塊BCC的值就好了」寫的不太清楚，這裡詳細解釋一下。
以下圖舉例，右邊是用BCC縮完點後的圖，其中紅色是割點，黑色的是一塊BCC。對於每個BCC都維護一個 multiset ，裡面裝的值是「在這個BCC內的點，除了他的祖先以外的所有點的值」，並且這坨BCC在新的樹當中的「點權」就會是這個 multiset 裡最小的數，割點在新的樹裡的點權則和原圖中的一樣。例如在下圖中，$2,3,4,5$這坨BCC在新的圖中他的點權就會是$2,3,4$的點權的最小值，$2,6,7$那坨則是$6,7$點權的最小值，其他以此類推。這樣就能在$O(logn)$的時間內完成修改了。具體方法是，如果改的點是割點的話，會動到的新圖中的點權有割點本身，還有他的父親BCC（如果他有父親的話一定是一坨BCC）。而如果改的點不是割點的話就只會動到他所屬的BCC的權值而已。
code :
[CF 487D] Conveyor Belts
作法：
因為他的輸送帶的方向只有左右上，所以分塊顯然可以做，只是複雜度有點高。官方解中提到的線段樹的作法沒有寫的很清楚，這裡詳細講一下。
假設線段樹的某個節點的區間為$[L,R]$，則這個節點裡放的資訊為：考慮$(L,1),(R,m)$形成的矩形，則從每個$x$座標為$R$的格子開始走，走出這塊矩形時的第一個格子是哪格，或是會形成無窮回圈。也就是這個節點裡存了$m$個格子的座標（所以是$m$個pair）。那麼就可以由$[a,b]$和$[b+1,c]$的資訊推出$[a,c]$的資訊了，因此可以用線段樹把每個節點的資訊都先處理好。至於如何回答詢問，假設詢問的點為$(x,y)$首先把線段$[1,x]$用線段樹拆解成好幾個線段，那麼只要從最後一個拆出來線段開始，利用線段樹上已經處理好的資訊就可以直接跳到下一個線段的起點$x$座標，或是得知他會走出左右邊界，或是形成無窮回圈了。而修改是顯然的。
code :
因為他的輸送帶的方向只有左右上，所以分塊顯然可以做，只是複雜度有點高。官方解中提到的線段樹的作法沒有寫的很清楚，這裡詳細講一下。
假設線段樹的某個節點的區間為$[L,R]$，則這個節點裡放的資訊為：考慮$(L,1),(R,m)$形成的矩形，則從每個$x$座標為$R$的格子開始走，走出這塊矩形時的第一個格子是哪格，或是會形成無窮回圈。也就是這個節點裡存了$m$個格子的座標（所以是$m$個pair）。那麼就可以由$[a,b]$和$[b+1,c]$的資訊推出$[a,c]$的資訊了，因此可以用線段樹把每個節點的資訊都先處理好。至於如何回答詢問，假設詢問的點為$(x,y)$首先把線段$[1,x]$用線段樹拆解成好幾個線段，那麼只要從最後一個拆出來線段開始，利用線段樹上已經處理好的資訊就可以直接跳到下一個線段的起點$x$座標，或是得知他會走出左右邊界，或是形成無窮回圈了。而修改是顯然的。
code :
2015年5月27日 星期三
[CF 491C] Deciphering
作法：
首先遇處理出把每個字母換成另外一個字母的$k\cdot k$種可能，算出他可以得幾分，那麼這樣就可以轉換成新的問題：有$k$個點，任兩個點之間都連一條有向邊，並且每條有向邊都有權重，對每個點都選一條起點為他的有向邊，滿足每個點恰被當成選到的邊的終點一次，求這些邊的總和的最大值。而這就是經典的二分圖最大權完美匹配問題，因為「對每個點選唯一的要走到的點」就類似於對每個點選一個匹配點。構造新的圖為左右分別有$k$個點，並且如果原圖中$i$連到$j$的權重為$w$，則在左邊第$i$個點和右邊第$j$個點之間連權重$w$的邊，求最大權完美匹配就是答案了。
首先遇處理出把每個字母換成另外一個字母的$k\cdot k$種可能，算出他可以得幾分，那麼這樣就可以轉換成新的問題：有$k$個點，任兩個點之間都連一條有向邊，並且每條有向邊都有權重，對每個點都選一條起點為他的有向邊，滿足每個點恰被當成選到的邊的終點一次，求這些邊的總和的最大值。而這就是經典的二分圖最大權完美匹配問題，因為「對每個點選唯一的要走到的點」就類似於對每個點選一個匹配點。構造新的圖為左右分別有$k$個點，並且如果原圖中$i$連到$j$的權重為$w$，則在左邊第$i$個點和右邊第$j$個點之間連權重$w$的邊，求最大權完美匹配就是答案了。
code :
[CF 494E] Sharti
作法：
詳細的作法在官方解已經講的很清楚了，這裡講一下為什麼 grundy number 長那樣的證明。
首先考慮$k$是無限大的情形，也就是這個遊戲可以選擇任意大的正方形，我們要證明當只有$(i,j)$有石頭的時候其 grundy number $g_{i,j}=min(lowbit(i),lowbit(j))$。當$i=1$或$j=1$時是顯然的，以下用數學歸納法，假設以$(1,1)$為左上角，$(x,y)$為右下角的矩形中，除了$(x,y)$以外的格子的 grundy number 都知道了，並且設$(x,y)$這格的理論值為$2^i$，那麼我們要證明兩件事：「只有$(x,y)$有石頭這個狀態」的後繼狀態中的 grundy number 裡沒有出現$2^i$，還有有出現$0,1,...,2^i-1$。
首先是沒有出現$2^i$，因為他的後繼狀態是一個正方形的每格裡都有一個石頭，除了$(x,y)$那格，因此這個命題就可以等價為：考慮一張方格表，上面寫上每個格子的理論上的 grundy number ，則任意圈一塊正方形把裡面的所有數全部 xor 起來都不會是$0$。用反證法，如果某一塊正方形內所有的數 xor 起來等於$0$，因為格子中的數都是$2$的冪次，所以等於是這塊正方形中每種數字都出現了兩次。首先看如何計算某塊區域中有多少個$2^i$，設$a_i$為這塊區域中$x,y$座標均被$2^i$整除的格子的數量，那麼這塊區域中的$2^i$的數量就會是$a_i-a_{i+1}$，而因為對於每個$i$，這塊正方形中的$2^i$都是偶數個，所以所有$a_i$的奇偶性相同，當$i$足夠大時$a_i$顯然$=0$，因此所有$a_i$都是偶數。假設這塊正方形的邊長是$2^x\cdot y$，其中$y$是奇數，那麼不難證明$a_y$是奇數，矛盾。
再來是證明出現了$0,1,...,2^i-1$（其中$0$是顯然的），這可以用數歸解決，假設現在$(1,1)$和$(2^r,2^r)$形成的正方形內部都是對的，那麼現在要推到$(2^{r+1},2^{r+1})$以內都是對的。把$(1,1)(2^{r+1},2^{r+1})$這個正方形切成四塊，那麼對於任意一個落在左下角那塊的格子$(x,y)$來說，考慮$(x-2^r,y)$，可以得到$(x-2^r,y)$能夠到達的後繼狀態的 grundy number $(x,y)$都能到達，所以$(x,y)$的 grundy number 和$(x-2^r,y)$的一樣。對於其他三塊也可以這樣處理，除了$(2^{r+1},2^{r+1})$這一格，我們要證明他的 grundy number 是$2^{r+1}$。在計算他的後繼狀態的值時，因為整張表格是沿對角線對稱的，所以兩邊的 xor 值會抵消，只剩下對角線上的，此時就化為一維的問題了，也就是證明當有個數列$b$滿足$b_i=lowbit(i),i=1,2,...,2^{r+1}-1$的話，令集合$S=\{ b_i\bigoplus ...\bigoplus b_{2^{r+1}-1} | 1\leq i<2^{r+1}\}$，則$S$裡出現了$1,2,...,2^{r+1}-1$（其中$\bigoplus $代表 xor 運算）。這件事的證明可以對$r$數歸，還算蠻顯然的所以略去，因此這樣成功證完$k$是無限大的情形了。
當$k$不是無限大時其實也類似，一樣也是先考慮每個格子的理論值形成的表，證明用邊長$\leq k$的正方形蓋下去的話所有的值 xor 起來不會是$0$。這次要注意到的是，假設$t$滿足$2^t\leq k<2^{t+1}$，那麼整張表其實是由$(1,1),(2^t,2^t)$形成的正方形裡面的值一直複製來的，證法和剛才類似，這裡省略。至於後繼狀態出現了$0,1,...,2^i-1$就變得很顯然了，因為每一格都可以對應回正方形$(1,1)(2^t,2^t)$內的其中一格，所以顯然是對的。
code :
詳細的作法在官方解已經講的很清楚了，這裡講一下為什麼 grundy number 長那樣的證明。
首先考慮$k$是無限大的情形，也就是這個遊戲可以選擇任意大的正方形，我們要證明當只有$(i,j)$有石頭的時候其 grundy number $g_{i,j}=min(lowbit(i),lowbit(j))$。當$i=1$或$j=1$時是顯然的，以下用數學歸納法，假設以$(1,1)$為左上角，$(x,y)$為右下角的矩形中，除了$(x,y)$以外的格子的 grundy number 都知道了，並且設$(x,y)$這格的理論值為$2^i$，那麼我們要證明兩件事：「只有$(x,y)$有石頭這個狀態」的後繼狀態中的 grundy number 裡沒有出現$2^i$，還有有出現$0,1,...,2^i-1$。
首先是沒有出現$2^i$，因為他的後繼狀態是一個正方形的每格裡都有一個石頭，除了$(x,y)$那格，因此這個命題就可以等價為：考慮一張方格表，上面寫上每個格子的理論上的 grundy number ，則任意圈一塊正方形把裡面的所有數全部 xor 起來都不會是$0$。用反證法，如果某一塊正方形內所有的數 xor 起來等於$0$，因為格子中的數都是$2$的冪次，所以等於是這塊正方形中每種數字都出現了兩次。首先看如何計算某塊區域中有多少個$2^i$，設$a_i$為這塊區域中$x,y$座標均被$2^i$整除的格子的數量，那麼這塊區域中的$2^i$的數量就會是$a_i-a_{i+1}$，而因為對於每個$i$，這塊正方形中的$2^i$都是偶數個，所以所有$a_i$的奇偶性相同，當$i$足夠大時$a_i$顯然$=0$，因此所有$a_i$都是偶數。假設這塊正方形的邊長是$2^x\cdot y$，其中$y$是奇數，那麼不難證明$a_y$是奇數，矛盾。
再來是證明出現了$0,1,...,2^i-1$（其中$0$是顯然的），這可以用數歸解決，假設現在$(1,1)$和$(2^r,2^r)$形成的正方形內部都是對的，那麼現在要推到$(2^{r+1},2^{r+1})$以內都是對的。把$(1,1)(2^{r+1},2^{r+1})$這個正方形切成四塊，那麼對於任意一個落在左下角那塊的格子$(x,y)$來說，考慮$(x-2^r,y)$，可以得到$(x-2^r,y)$能夠到達的後繼狀態的 grundy number $(x,y)$都能到達，所以$(x,y)$的 grundy number 和$(x-2^r,y)$的一樣。對於其他三塊也可以這樣處理，除了$(2^{r+1},2^{r+1})$這一格，我們要證明他的 grundy number 是$2^{r+1}$。在計算他的後繼狀態的值時，因為整張表格是沿對角線對稱的，所以兩邊的 xor 值會抵消，只剩下對角線上的，此時就化為一維的問題了，也就是證明當有個數列$b$滿足$b_i=lowbit(i),i=1,2,...,2^{r+1}-1$的話，令集合$S=\{ b_i\bigoplus ...\bigoplus b_{2^{r+1}-1} | 1\leq i<2^{r+1}\}$，則$S$裡出現了$1,2,...,2^{r+1}-1$（其中$\bigoplus $代表 xor 運算）。這件事的證明可以對$r$數歸，還算蠻顯然的所以略去，因此這樣成功證完$k$是無限大的情形了。
當$k$不是無限大時其實也類似，一樣也是先考慮每個格子的理論值形成的表，證明用邊長$\leq k$的正方形蓋下去的話所有的值 xor 起來不會是$0$。這次要注意到的是，假設$t$滿足$2^t\leq k<2^{t+1}$，那麼整張表其實是由$(1,1),(2^t,2^t)$形成的正方形裡面的值一直複製來的，證法和剛才類似，這裡省略。至於後繼狀態出現了$0,1,...,2^i-1$就變得很顯然了，因為每一格都可以對應回正方形$(1,1)(2^t,2^t)$內的其中一格，所以顯然是對的。
code :
2015年5月25日 星期一
[CF 494D] Birthday
作法：
首先觀察到我們有兩種方法來計算題目所求的值，令$ \displaystyle g(u)=\sum_{i=1}^{n} d(u,i)^2 $，那麼$\displaystyle f(u,v)=g(u)-2\cdot \sum_{x\notin S(v)} d(u,x)^2=2\cdot \sum_{x\in S(v)} d(u,x)^2 - g(u)$
首先先想辦法求出$g(u)$，如果我們只要知道特定一個$u$的$g$值的話，就直接對以$u$為根建立有根樹並DP就好了，DP時對每個節點$x$紀錄三個值：以$x$為根的子樹的大小，以$x$為根的子樹中的所有點走到$x$的距離和，還有以$x$為根的子樹中的所有點走到$x$的距離平方和，這三個東西的遞推式子算是顯然的（以後簡稱他們叫作三個DP值）。但我們需要對每個$u$都算出他的$g$值，如果對每個點都DFS一次顯然會太慢。這時只要注意到，實際上對兩個不同的點DFS的時候，會有很多點的那三個值是一模一樣的，更具體來說，如果現在對$X$和$Y$作DFS，那麼對於任何一個點$u$，如果從$X$走到$u$的路徑上的最後一條邊等於從$Y$走到$u$的路徑上的最後一條邊，則兩次的DFS在$u$求出的值是一樣的，因為這兩次的$u$的子樹是一模一樣的。這啟發了我們可以對每個點分別計算「當他的父節點是他的某個鄰居時，他的三個DP值會是多少」。嚴謹來說，定義對於相鄰的兩點$u,v$，定義$T(u,v)$代表砍掉$(u,v)$這條邊後以$u$為根的子樹，那麼把這棵子樹對應的三個DP值算出來。這樣只有$O(n)$個值要算，並且也不難得知這些值的$O(n)$或是$O(nlogn)$的算法，因此這裡成功解決了遇處理每個點的$g$值的部份。
有了每個點的$g$值之後，再回到題目要求的式子。當$u$不在以$v$為根的子樹內時，那麼第二條和所求等價的式子會很好算，因為我們可以把$d(u,x)$拆成$d(u,v)+d(v,x)$，這樣所求就可以由剛才求出的$T(v,fa[v])$的三個DP值計算出來了，其中$fa[v]$代表$v$的父節點（題目給的是以$1$為根的有根樹）。至於$u$落在$v$的子樹內的情形則使用第一條和所求等價的式子，此時對應的子樹就會是$T(fa[v],v)$，因此算法也根剛才類似了。另外注意到這個算法的回答詢問複雜度會是$O(logn)$，因為會需要求兩點之間的距離。
code :
首先觀察到我們有兩種方法來計算題目所求的值，令$ \displaystyle g(u)=\sum_{i=1}^{n} d(u,i)^2 $，那麼$\displaystyle f(u,v)=g(u)-2\cdot \sum_{x\notin S(v)} d(u,x)^2=2\cdot \sum_{x\in S(v)} d(u,x)^2 - g(u)$
首先先想辦法求出$g(u)$，如果我們只要知道特定一個$u$的$g$值的話，就直接對以$u$為根建立有根樹並DP就好了，DP時對每個節點$x$紀錄三個值：以$x$為根的子樹的大小，以$x$為根的子樹中的所有點走到$x$的距離和，還有以$x$為根的子樹中的所有點走到$x$的距離平方和，這三個東西的遞推式子算是顯然的（以後簡稱他們叫作三個DP值）。但我們需要對每個$u$都算出他的$g$值，如果對每個點都DFS一次顯然會太慢。這時只要注意到，實際上對兩個不同的點DFS的時候，會有很多點的那三個值是一模一樣的，更具體來說，如果現在對$X$和$Y$作DFS，那麼對於任何一個點$u$，如果從$X$走到$u$的路徑上的最後一條邊等於從$Y$走到$u$的路徑上的最後一條邊，則兩次的DFS在$u$求出的值是一樣的，因為這兩次的$u$的子樹是一模一樣的。這啟發了我們可以對每個點分別計算「當他的父節點是他的某個鄰居時，他的三個DP值會是多少」。嚴謹來說，定義對於相鄰的兩點$u,v$，定義$T(u,v)$代表砍掉$(u,v)$這條邊後以$u$為根的子樹，那麼把這棵子樹對應的三個DP值算出來。這樣只有$O(n)$個值要算，並且也不難得知這些值的$O(n)$或是$O(nlogn)$的算法，因此這裡成功解決了遇處理每個點的$g$值的部份。
有了每個點的$g$值之後，再回到題目要求的式子。當$u$不在以$v$為根的子樹內時，那麼第二條和所求等價的式子會很好算，因為我們可以把$d(u,x)$拆成$d(u,v)+d(v,x)$，這樣所求就可以由剛才求出的$T(v,fa[v])$的三個DP值計算出來了，其中$fa[v]$代表$v$的父節點（題目給的是以$1$為根的有根樹）。至於$u$落在$v$的子樹內的情形則使用第一條和所求等價的式子，此時對應的子樹就會是$T(fa[v],v)$，因此算法也根剛才類似了。另外注意到這個算法的回答詢問複雜度會是$O(logn)$，因為會需要求兩點之間的距離。
code :
2015年5月23日 星期六
[CF 497E] Subsequences Return
作法：
這題的官方解中已經把前面DP的部份講的很清楚了，這裡紀錄一下後面我在求那些矩陣的方法，和官方解的不太一樣。首先$A_{0,x}$是顯然的，也就是最原始的轉移，他會是一個對角線上都是$1$，還有上面數來第$x$列都是$1$的矩陣。再來我們要想辦法在比較快的時間內求出$A_{m,x}$，首先我們知道$A_{m,0}=A_{m-1,0}\times A_{m-1,1}\times ... \times A_{m-1,k-1}$，還有$A_{m,1}=A_{m-1,1}\times A_{m-1,2}\times ... \times A_{m-1,k-1}\times A_{m-1,0}$，觀察這兩條式子可以發現他們只差在前後的$A_{m-1,0}$，也就是如果我們預先算好了$A_{m-1,0}$的反矩陣$I_{m-1,0}$的話，就可以直接用$O(k^3)$的時間從$A_{m,0}$算出$A_{m,1}$了，因此我們再對每個$A_{m,x}$紀錄他的反矩陣$I_{m,x}$就可以了，並且其遞推式和$A$的遞推式很像。至於邊界的部份（也就是$I_{0,x}$）其實長的也蠻好看的，因為$A_{0,x}$的樣子很特殊。可以得到$I_{0,x}$的樣子是：在主對角線上都是$1$，而在上面數來第$x$排的每個數，除了主對角線上的那個數是$1$以外都是$-1$（記得在賦值時要寫$MOD-1$）。
code :
這題的官方解中已經把前面DP的部份講的很清楚了，這裡紀錄一下後面我在求那些矩陣的方法，和官方解的不太一樣。首先$A_{0,x}$是顯然的，也就是最原始的轉移，他會是一個對角線上都是$1$，還有上面數來第$x$列都是$1$的矩陣。再來我們要想辦法在比較快的時間內求出$A_{m,x}$，首先我們知道$A_{m,0}=A_{m-1,0}\times A_{m-1,1}\times ... \times A_{m-1,k-1}$，還有$A_{m,1}=A_{m-1,1}\times A_{m-1,2}\times ... \times A_{m-1,k-1}\times A_{m-1,0}$，觀察這兩條式子可以發現他們只差在前後的$A_{m-1,0}$，也就是如果我們預先算好了$A_{m-1,0}$的反矩陣$I_{m-1,0}$的話，就可以直接用$O(k^3)$的時間從$A_{m,0}$算出$A_{m,1}$了，因此我們再對每個$A_{m,x}$紀錄他的反矩陣$I_{m,x}$就可以了，並且其遞推式和$A$的遞推式很像。至於邊界的部份（也就是$I_{0,x}$）其實長的也蠻好看的，因為$A_{0,x}$的樣子很特殊。可以得到$I_{0,x}$的樣子是：在主對角線上都是$1$，而在上面數來第$x$排的每個數，除了主對角線上的那個數是$1$以外都是$-1$（記得在賦值時要寫$MOD-1$）。
code :
[CF 497D] Gears
作法：
當兩個多邊形碰撞時，一定是一個多邊形的其中一個頂點碰到另一個多邊形的線段，並且顯然當有頂點碰到別人的線段時他們一定相撞了。因此我們只要對兩個多邊形的其中一個枚舉頂點，另一個枚舉邊，然後想辦法$O(1)$判斷這個點會不會跑到這條線段上就可以了。這裡要用相對運動來看會好做很多。假設現在要判斷的是$A$上的一條線段和$B$上的一個頂點$X$是否會在運動的時候碰到，想像站在$P$點看所有東西，並且面對的方向是跟著$A$一起轉的，也就是當$A$順時針旋轉了$\theta $度之後面對的方向也跟著順時針轉$\theta $度，那麼我們看到的$A$上的這條線段會是永遠不動的。設時間$0$時$Q$的座標為$(a,b)$，$X$的座標為$(x,y)$，那麼可以知道$X$被旋轉了$\theta $度之後他在時間$0$的座標系上的座標會是$M_{-\theta}\begin{bmatrix}x-a\\y-b\end{bmatrix}+\begin{bmatrix}a\\ b\end{bmatrix}$，其中$M_{\theta}$代表的是可以將一個點以原點為中心逆時針旋轉$\theta $的矩陣。但此時我們的座標系已經順時針旋轉$\theta $度了，所以這時候看到的$X$點的座標必須要逆時針旋轉$\theta $度才是對的，也就是等於$M_{\theta}(M_{-\theta}\begin{bmatrix}x-a\\y-b\end{bmatrix}+\begin{bmatrix}a\\ b\end{bmatrix})=\begin{bmatrix}x-a\\y-b\end{bmatrix}+M_{\theta}\begin{bmatrix}a\\ b\end{bmatrix}$，由這個式子就可以看出這是一個以$(x-a,y-b)$為圓心，半徑為$\sqrt{a^2+b^2}$的圓了，因此只要寫個線段和圓是否有相交的函式就可以了。
code :
當兩個多邊形碰撞時，一定是一個多邊形的其中一個頂點碰到另一個多邊形的線段，並且顯然當有頂點碰到別人的線段時他們一定相撞了。因此我們只要對兩個多邊形的其中一個枚舉頂點，另一個枚舉邊，然後想辦法$O(1)$判斷這個點會不會跑到這條線段上就可以了。這裡要用相對運動來看會好做很多。假設現在要判斷的是$A$上的一條線段和$B$上的一個頂點$X$是否會在運動的時候碰到，想像站在$P$點看所有東西，並且面對的方向是跟著$A$一起轉的，也就是當$A$順時針旋轉了$\theta $度之後面對的方向也跟著順時針轉$\theta $度，那麼我們看到的$A$上的這條線段會是永遠不動的。設時間$0$時$Q$的座標為$(a,b)$，$X$的座標為$(x,y)$，那麼可以知道$X$被旋轉了$\theta $度之後他在時間$0$的座標系上的座標會是$M_{-\theta}\begin{bmatrix}x-a\\y-b\end{bmatrix}+\begin{bmatrix}a\\ b\end{bmatrix}$，其中$M_{\theta}$代表的是可以將一個點以原點為中心逆時針旋轉$\theta $的矩陣。但此時我們的座標系已經順時針旋轉$\theta $度了，所以這時候看到的$X$點的座標必須要逆時針旋轉$\theta $度才是對的，也就是等於$M_{\theta}(M_{-\theta}\begin{bmatrix}x-a\\y-b\end{bmatrix}+\begin{bmatrix}a\\ b\end{bmatrix})=\begin{bmatrix}x-a\\y-b\end{bmatrix}+M_{\theta}\begin{bmatrix}a\\ b\end{bmatrix}$，由這個式子就可以看出這是一個以$(x-a,y-b)$為圓心，半徑為$\sqrt{a^2+b^2}$的圓了，因此只要寫個線段和圓是否有相交的函式就可以了。
code :
[CF 498E] Stairs and Lines
作法：
首先大概可以想到是從左到右一行一行決定的狀態壓縮DP。考慮把 $dp[i][j]$ 定為：只看左邊數來第$1$條到第$i$條鉛直線，並且在第$i$條鉛直線上的有塗色和沒塗色的狀態壓起來為$j$，此時的方法數。那麼我們就可以先對七種不同的高度預處理出有哪些轉移，也就是先處理好狀態$j_1$轉移到狀態$j_2$有幾種方法，具體來說只要枚舉他們之間的橫線的狀況就好了，如果對於某種橫線的取法是可行的那麼就在這兩個狀態的轉移方法數上加$1$。這樣每行都有最多$2^7=128$種狀態，每個狀態最多也是$128$種轉移，所以如果直接做的話時間會爆掉。而這只要在多注意到我們可以用矩陣乘法來取代轉移過程，因此把DP的過程改成快速冪就可以了。
code :
首先大概可以想到是從左到右一行一行決定的狀態壓縮DP。考慮把 $dp[i][j]$ 定為：只看左邊數來第$1$條到第$i$條鉛直線，並且在第$i$條鉛直線上的有塗色和沒塗色的狀態壓起來為$j$，此時的方法數。那麼我們就可以先對七種不同的高度預處理出有哪些轉移，也就是先處理好狀態$j_1$轉移到狀態$j_2$有幾種方法，具體來說只要枚舉他們之間的橫線的狀況就好了，如果對於某種橫線的取法是可行的那麼就在這兩個狀態的轉移方法數上加$1$。這樣每行都有最多$2^7=128$種狀態，每個狀態最多也是$128$種轉移，所以如果直接做的話時間會爆掉。而這只要在多注意到我們可以用矩陣乘法來取代轉移過程，因此把DP的過程改成快速冪就可以了。
code :
2015年5月21日 星期四
[CF 545E] Paths and Trees
作法：
首先把所有在最短路徑上的邊都找出來，並且定好方向（方向為到源點距離小的連到到源點距離大的），那麼可以知道其實最短路徑樹就是這些邊的一個有向生成樹，並且顯然一棵有向生成樹一定會是最短路徑樹（因為從原點到每個點經過的邊都是最好的邊）。而題目要求的是權值和最小的最短路徑樹，因此就等價於這張圖的最小有向生成樹（MDST）。回顧DMST的作法，第一步是先幫每個非源點的節點選擇權值最小的入邊，如果這些邊沒有形成環就結束了。而很幸運的因為這些都是最短路徑樹上的邊，所以顯然不會形成環，因此直接這樣取就會形成一棵樹了。
code :
首先把所有在最短路徑上的邊都找出來，並且定好方向（方向為到源點距離小的連到到源點距離大的），那麼可以知道其實最短路徑樹就是這些邊的一個有向生成樹，並且顯然一棵有向生成樹一定會是最短路徑樹（因為從原點到每個點經過的邊都是最好的邊）。而題目要求的是權值和最小的最短路徑樹，因此就等價於這張圖的最小有向生成樹（MDST）。回顧DMST的作法，第一步是先幫每個非源點的節點選擇權值最小的入邊，如果這些邊沒有形成環就結束了。而很幸運的因為這些都是最短路徑樹上的邊，所以顯然不會形成環，因此直接這樣取就會形成一棵樹了。
code :
[CF 500G] New Year Running
作法：
這題我的作法是按照官方解的作法寫的，這裡大概提一些官方解裡比較沒有寫到的東西，還有我的實作方法。
首先是求出兩條路徑的共同部份（對了，我的記號是記兩條路徑分別是$u_1$~$v_1$和$u_2$~$v_2$），還有之後需要用到的重要的數字$f_1,f_2,t_1,t_2,t_3,t_4,dis$，其中$f_1,f_2$分別代表兩條路徑的兩倍長，$dis$則代表兩條路徑共同部份的長度，$t_1,t_2,t_3,t_4$則和題解中的定義一樣。這裡先假設在$u_1,v_1,u_2,v_2$中沒有任何一點是另一點的祖先，這種情形的算法可以直接套到一般情形上。至於為什麼我目前也不是很清楚，不過大概可以想成：如果$X$是$Y$的祖先，那麼可以把$X$替換成另一個虛擬節點$Z$，然後把$X$接到$Z$底下，並且在他們之間連一條長度為$0$的邊，這樣不會影響到我們要求的任何東西。有了這件事之後，可以發現給定的這四個點形成的圖形只會有以下兩種：
再來則是轉換後的數論問題，第一部份是要能夠求出以下問題的答案：給定$a,b,c,d\geq 0$，求出在所有滿足$ax+b=cy+d$的整數$(x,y)$中，當$ax+b$為最小的非負值的時候其值是多少。移項變成$ax-cy=d-b$，因此可以直接套用擴展歐幾里得算法求出一組$(x,y)$的解，再把他調整成讓$ax+b$值最小的解。而在調整的時候如果是用慢慢加的會TLE，要算好要加幾倍再一次加上去才可以，看code應該比較好理解。
再來則是第二部份，也就是求$g$函數的值的部份，我覺得他寫的怪怪的所以自己弄了一個作法。這裡我的記號和他不太一樣，$g(a,b,y,M)$會回傳最小的非負整數$x$，使得$a\leq (x\cdot y)\mod M\leq b$，並且$a,b$滿足$0\leq a\leq b<M$。想像$x$從$0$開始慢慢往上加，那麼$x\cdot y$就會一直$+y$，當他加到$\geq a$的時候，如果他的值$\leq b$，那麼顯然此時的$x$就是最小的解了，直接回傳就可以了，也就是第一步是先確認$\geq a$的最小的$y$的倍數是否可行，如果可以的話就直接回傳。如果不行的話，那麼就代表$a$和$b$之間沒有任何$y$的倍數（包含$a,b$），這件事等一下會用到。那麼此時引入另一個變數$r$，把方程式改寫成$a\leq x\cdot y-M\cdot r\leq b$，也就是我們要求滿足上式的二元組$(x,r)$中，$x$的最小值是多少（當然$r$也要$\geq 0$）。而可以看出$r$越小$x$就越小，所以其實也可以先找出$r$的最小值再推出所求的值。再把這條式子反過來變成$-b\leq r\cdot M-x\cdot y\leq -a$，這時候因為$a,b$之間沒有$y$的倍數，所以可以把這條式子直接模$y$，把最左邊和最右邊都變成介於$0$到$y-1$的數字而不會反號（也就是變成$((-b)\% y+y)\% y$）。也就是現在變成了一個新的問題：求最小的$r$使得$A\leq (r\cdot M)\mod y\leq B$，其中$A$和$B$是剛才提到的值。注意到我們可以把$M$改成$M\% y$，也就是變成了$A\leq (r\cdot (M\% y))\mod y\leq B$，因此這樣就可以遞迴下去處理了，他的過程就和輾轉相除法類似，所以複雜度會是$log$級別的。另外還要注意到，如果此時$M\% y = 0$的話遞迴下去可能會有問題，不過不難發現此時一定無解，所以直接回傳就可以了。
另外在使用這個函式之前還會有些問題。回到官方解中我們要解決的那條式子，此時他形如$yf_2+a\leq xf_1\leq yf_2+b$，要求出最小的非負的$x$是多少。如果直接把$a$和$b$拿去模掉$f_2$然後丟$g$函式的話會有問題，因為有可能$a$和$b$之間有$f_1$的倍數，模下去之後就沒了之類的，因此我們先判斷$x=0$或$y=0$的時候這條式子有沒有解，如果有就直接回傳，沒有的話才用$g$函數來算。
對了，出題者在下面的留言說因為他作過了這題（也就是求$g$函數的值的裸題）所以才會的，可以在傳這題之前用來測測看$g$函數有沒有寫對。
code :
2015年5月20日 星期三
[CF 506C] Mr. Kitayuta vs. Bamboos
作法：
這題我是完全照著官方詳解的第二種作法寫的，看了很久一直看不懂第一種作法，這裡就紀錄一下大概怎麼實作的。
在二分搜一個值的時候，一開始所有竹子都同高，只是縮短的速率不一樣。我們可以把所有竹子分成三類，第一類為那些「一直不理他到最後一天高度還是$\geq $他的$h$值」的竹子，我們可以完全不用理他，因為永遠不用把他拉長。至於第二種竹子則是「一直不理他直到最後一天高度會$<$他的$h$值，但不會$<0$」，第三種則是最後一天結束會$<0$的。我們可以先用貪心處理第三種竹子，把他們全部都變第二種之後，剩下的拉長操作的次數就可以依照任意順序對竹子們使用了。貪心的詳細一點來說就是，對每個第三種的竹子都算出「如果一直不理他，那到哪一天他的高度會$<0$」，那麼就只要把他們丟入一個priority_queue中，每次取天恕最小的那跟竹子出來把他拉長，並用一個陣列$num$紀錄每個竹子被拉長了幾次，那麼就可以用$\left \lfloor \frac{h_0+num[i]\cdot p}{a[i]} \right \rfloor+1$算出不理他的話第幾天會$<0$了（其中$h_0$是此次二分搜的值，也是所有竹子的初始高度）。而我的寫法不太一樣，是把第二種和第三種合併處理，也就是一樣都對他們計算上式的值並且丟進priority_queue裡面，只不過所有第二種竹子算出來的值都會$>m$，因為他們在最後一天並不會$<0$，而這也不影響第三種竹子的處理，因為第三種竹子一定會比第二種竹子早出隊，並且保證當 pop 出來的是第二種竹子的時候，所有的第三種竹子都處理完畢了。另外只要再判一下現在被拉長的這個竹子是否已經變成第一種竹子了就好了，如果還沒的話就繼續丟進priority_queue中。當所有程序結束時，priority_queue為空若且唯若此次是成功的。
code :
2015年5月18日 星期一
[CF 504E] Misha and LCP on Tree
作法：
這題我是寫hash的作法，官方解裡有提到用樹鍊剖分 + 後綴數組的作法，雖然他講的沒有很清楚，不過官方解的code寫的很好懂，建議可以參考看看。
首先二分搜答案，只要先求出「這條路徑上的第$t$個點是誰」，就可以把問題轉化成判斷樹上的兩條路徑代表的字串是否相等，因此我們需要求出這兩個字串的hash值，也就是我們需要計算樹上任意一條路徑的hash值。而這可以分成「沿著路競走一路往上」、「沿著路徑走一路往下」、「沿著路徑走先往上再往下」幾種情形，所以對於前兩種情形，我們就必須在每個節點 $i$ 紀錄兩種hash值，兩個hash值都是從 $i$ 走到根所對應的字串的hash值，不過一個是$s[root]+...+s[i]\cdot X^{dep[i]}$，一個是$s[root]\cdot X^{dep[i]}+...+s[i]$，其中 $s$ 為原始字串，$dep[i]$ 為這個點的深度，並且$dep[root]=0$，這兩個值都可以在DFS時順便算好。再來則是如何求出所求的hash值，首先前兩種情況是顯然的，至於第三種情況，我們要先找到兩個點的LCA，在把兩段的hash值合併，而合併的式子稍微推一下就可以了。
但這樣傳上去TLE了，畢竟是$O(Qlog^2n)$的解，官方解也說hash的解太慢了需要優化。首先就是官方解提到的「離線作詢問$k$級祖先」，因為離線處理「詢問節點$x$的$k$級祖先」可以做到$O(n+Q)$，方法也不難，在DFS時維護一個stack就可以了。具體作法是，先把所有詢問讀進來，求出每條路徑兩端點的LCA，並且對每個詢問都紀錄兩個值 $l,r$ ，代表當前這個詢問的解的區間，在每個階段對每個詢問跑一次，如果這個詢問的區間長度已經是$1$了那就略過，至於不是的話，等於是現在我們要詢問長度$mid=\frac{l+r}{2}$是否可行，所以此時可以知道這個詢問會需要知道「誰的幾級祖先是誰」，所以就可以把所有這些東西紀錄下來。跑完所有詢問一次之後DFS一次處理剛才所需要的答案，然後就可以再跑一次所有詢問計算此時的兩個hash值，並且判斷他們兩個是否相等了。
但這樣傳上去還是TLE了，後來我測了一下，發現光預處理每個詢問裡兩點LCA的部份就已經花了$4$秒了，所以我把求LCA的部份也改成離線的作法，離線作LCA可以做到$O((n+Q)\alpha (n))$，詳細作法可以查查LCA的 tarjan 算法。苦苦的改完後竟然還TLE了......最後發現是因為取模太慢了，把 「$ret=(ret\% MOD+MOD)\% MOD$」的外面那層改成用「如果小於 $0$ 就加MOD」就壓線過了，這題的時限太恐怖了OAO
後來我去看別人的作法，這份code跑的速度最快，他的作法是樹鍊剖分套hash，寫的也蠻好懂的，建議也可以參考看看。
code :
2015年5月17日 星期日
[CF 506E] Mr. Kitayuta's Gift
作法：
關於這題的官方解，前面寫的還蠻清楚的，不過後面有跳過一些東西，所以這裡只把後半部的詳細解釋一下。對了，我習慣用$n$代表字串長度，而題目裡的多加字母的個數則用$m$表示。從官方解中的第一張大圖開始（有$O(n^2)$個紅綠節點的那張圖），因為每條鍊是獨立的，所以我們可以分開計算每條鍊上的答案再加起來。而單看一條鍊時，現在上面有一些紅綠交錯的節點，這時可以發現其實他們排列的順序其實不影響答案，只和他是幾個紅點幾個綠點組成的有關，所以可以任意交換位置，才能變成官方解圖中「先全部都是紅再全部都是綠」的鍊。因此這時候我們得到了很多種很類似的鍊，並且我們知道每種鍊的倍率，也就是每種鍊分別有幾條（或是說當我們算完每條鍊的答案之後他們分別要乘以多少，加起來才是答案）。假設第$i$種鍊有$i$個紅點，那麼可以推出此時有$\left \lceil \frac{n-i}{2} \right \rceil$個綠點，如下圖。（這裡舉$n=6$當例子）
最後還有詳解最後一部份的「扣掉違反規則的字串個數」，先回去看第一張官方解的大圖，看那些代表$dp[i][i+1]$的節點們，如果有綠色的節點，那麼就代表從起點走到這個節點的長度為$K-1$的路徑都是不滿足條件的。於是我們可以把「代表$dp[i][i+1]$的綠節點們」當成終點，所以這時候也可以把所有的路徑都拆開，並且一樣用DP求出「有$x$個黑點的路徑」分別有幾條，再作一次上述的步驟就可以了。而這兩次不一樣的地方在於：如果這次有$x$個黑點，那麼白點的個數會是$\left \lceil \frac{n-2-i}{2} \right \rceil$，還有這次從終點到終點的轉移只有$25$種，第一次作的時候是有$26$種的。
code :
[CF 509C] Sums of Digits
作法：
首先可以把問題化簡成：給定一個數$S$和一個正整數$n$，求出數字和為恰為$S$且比$n$大的最小正整數是多少。考慮將所求的數字和$n$從最高位開始往下比，找到第一位兩個數不同的位置，假設為 $i$ ，那麼就代表在第 $i$ 位之前所求的數字和$n$對應的位置都是一樣的，至於第$i$位和他之後要怎麼放，假設$S$扣掉第$1$位到第$i-1$位的值後剩下的值為$S2$，那麼就代表第$i$位以後一直到個位數的總和要恰好是$S2$，並且還得滿足第$i$位的值$\geq $ $n$ 的第 $i$ 位的值 $+1$ ，當然還有第$i$位以後的數都要介於$0$和$9$之間，因此就可以先列出一個關於$S2$的不等式，不管$S2$太大或是太小都沒辦法在剩下的位子裡面放完需要的數字總和的數。具體來說，假設$n$的第$i$位的值為$x$，並且第$i+1$位一直到個位還有$y$個位子，那麼$S2$就必須滿足$x+1 \leq S2 \leq 9\cdot (y+1)$。並且剩下的問題不難得知只要往個位數的方向放儘量多的$9$就可以了，也就是從個位數開始往左一直放$9$，直到$S2$被用完為止，但記得要注意到如果$S2$太大，也有可能最後要加到第$i$位身上，畢竟他最大還是可以到$9$，不一定只能放$x+1$。最後只要注意到，當兩個數的第一個不一樣的位置越靠近個位的話，算出來的新的值就會越小，所以只要從小到大枚舉$i$，一找到一個解就趕快回傳就可以了。
code :
首先可以把問題化簡成：給定一個數$S$和一個正整數$n$，求出數字和為恰為$S$且比$n$大的最小正整數是多少。考慮將所求的數字和$n$從最高位開始往下比，找到第一位兩個數不同的位置，假設為 $i$ ，那麼就代表在第 $i$ 位之前所求的數字和$n$對應的位置都是一樣的，至於第$i$位和他之後要怎麼放，假設$S$扣掉第$1$位到第$i-1$位的值後剩下的值為$S2$，那麼就代表第$i$位以後一直到個位數的總和要恰好是$S2$，並且還得滿足第$i$位的值$\geq $ $n$ 的第 $i$ 位的值 $+1$ ，當然還有第$i$位以後的數都要介於$0$和$9$之間，因此就可以先列出一個關於$S2$的不等式，不管$S2$太大或是太小都沒辦法在剩下的位子裡面放完需要的數字總和的數。具體來說，假設$n$的第$i$位的值為$x$，並且第$i+1$位一直到個位還有$y$個位子，那麼$S2$就必須滿足$x+1 \leq S2 \leq 9\cdot (y+1)$。並且剩下的問題不難得知只要往個位數的方向放儘量多的$9$就可以了，也就是從個位數開始往左一直放$9$，直到$S2$被用完為止，但記得要注意到如果$S2$太大，也有可能最後要加到第$i$位身上，畢竟他最大還是可以到$9$，不一定只能放$x+1$。最後只要注意到，當兩個數的第一個不一樣的位置越靠近個位的話，算出來的新的值就會越小，所以只要從小到大枚舉$i$，一找到一個解就趕快回傳就可以了。
code :
2015年5月14日 星期四
[CF 512E] Fox And Polygon
作法：
這題我是看了這篇裡講的作法才會做的，詳細的作法在這篇comment裡，這裡大概講一下是怎麼做的。
我們能夠把任何對角線配置都轉換成其中一個端點在$1$的樣子就可以了，也就是所有對角線會是$1-3,1-4,...,1-(n-1)$（稱這樣子的對角線配置為標準型），因為這樣就可以從原本的對角線配置 -> 標準型 -> 目標對角線配置。而要讓對角線們成為標準型也很簡單，因為如果存在一條對角線$1-i$，但不存在$1-(i+1)$，那麼找一條對角線$1-j$使得$1-(i-1),...,1-(j-1)$都沒有對角線，則$i$一定和$j$有連線，只要把這條對角線換過來就可以讓其中一個端點在$1$的對角線增加一條，於是在$n-3$步以內就可以達到標準型了。
code :
這題我是看了這篇裡講的作法才會做的，詳細的作法在這篇comment裡，這裡大概講一下是怎麼做的。
我們能夠把任何對角線配置都轉換成其中一個端點在$1$的樣子就可以了，也就是所有對角線會是$1-3,1-4,...,1-(n-1)$（稱這樣子的對角線配置為標準型），因為這樣就可以從原本的對角線配置 -> 標準型 -> 目標對角線配置。而要讓對角線們成為標準型也很簡單，因為如果存在一條對角線$1-i$，但不存在$1-(i+1)$，那麼找一條對角線$1-j$使得$1-(i-1),...,1-(j-1)$都沒有對角線，則$i$一定和$j$有連線，只要把這條對角線換過來就可以讓其中一個端點在$1$的對角線增加一條，於是在$n-3$步以內就可以達到標準型了。
code :
[IOICamp Judge 16] 叫我轉珠王
題目敘述：
給定一個$n\times m$的棋盤，其中有一些格子是障礙格，求有幾種哈密頓圈可以完整覆蓋所有非障礙格。輸入有$T$筆測資，其中$T\leq 100$，$n,m\leq 12$，時限 $5$ 秒。
作法：
這題也是插頭DP的經典題，和這篇的作法幾乎一樣。而這次我改用$8$進制寫寫看，畢竟多筆測資可能是要來卡時限的。這題在轉移的部份就比較沒那麼麻煩了，因為要求的是哈密頓圈，所以沒有哪裡是起點哪裡是終點的區別。而必須注意到的是上面那題是在最右下角的格子時才把兩條最終的路徑接起來，而這裡必須要在「最後一格非障礙格」時作這件事，而這格位於哪裡可以預先處理好。在轉移時一樣不能把相同連通分量的兩條線連起來，除非當前格是最後一格非障礙格。但這樣傳上去後TLE了，把 map 改成 unordered_map 才AC @@。
給定一個$n\times m$的棋盤，其中有一些格子是障礙格，求有幾種哈密頓圈可以完整覆蓋所有非障礙格。輸入有$T$筆測資，其中$T\leq 100$，$n,m\leq 12$，時限 $5$ 秒。
作法：
這題也是插頭DP的經典題，和這篇的作法幾乎一樣。而這次我改用$8$進制寫寫看，畢竟多筆測資可能是要來卡時限的。這題在轉移的部份就比較沒那麼麻煩了，因為要求的是哈密頓圈，所以沒有哪裡是起點哪裡是終點的區別。而必須注意到的是上面那題是在最右下角的格子時才把兩條最終的路徑接起來，而這裡必須要在「最後一格非障礙格」時作這件事，而這格位於哪裡可以預先處理好。在轉移時一樣不能把相同連通分量的兩條線連起來，除非當前格是最後一格非障礙格。但這樣傳上去後TLE了，把 map 改成 unordered_map 才AC @@。
code :
[HOJ 123][TIOJ 1810] 漫遊小鎮 / 小鎮DP
作法：
這題是標準的插頭DP題，需要把連通性壓入狀態表示中，在上一篇中提到的是簡單的版本。因為那題只要求用多個哈密頓圈覆蓋，而這題則是限定用一條哈密頓鍊覆蓋。另外還有要求是從左上角走到左下角，因此這時候能拼的拼圖總共有9種：
其中上面三種只能拼在左上角和左下角，並且左上角和左下角一定要用這三種拼圖來拼。但兩題不只有差這樣而已，如果一樣直接DP的話，$n=3$ 時會得出答案為 $3$ （多出來的路徑就是下面的左圖）。也就是在DP最後一格時，誤把同一個連通分量的兩條線接起來了。
左圖和右圖的情形在狀態表示中都是$0011$，但左圖的情形不能轉移，右圖的情形則可以，因此這樣的狀態表示會造成誤判，必須細分。所以此時只好把線的「連通性」納入狀態表示中，也就是在左圖的$0011$中，其實兩個$1$是連通的，而右圖的$0011$的兩個$1$則是不連通的。所以此時我們要想辦法把連通性壓入狀態中。對於一個狀態中的$1$代表的那條線來說，如果沿著他往回走，那麼有幾種可能：一種是走回這個狀態表示中的另外一個$1$，一種是走回左上角，一種是走回左下角。而「走回左下角」的情形在還沒有轉移左下角那格之前是不存在的。而轉移到左下角那格之前每個狀態會恰有一個$1$代表從左上角走過來的線。因此我們就可以用以下的方法表示狀態：如果這格的線是走回左上或左下角的，那麼就把這格位子的值設為$1$，而如果是走回這個狀態的另一條線的情形，就把這一對連通的線的值都設為$2$，如果有第三組就設為$3$，以此類推。這樣因為$n\leq 10$（TIOJ的數字範圍），也就是一個狀態最多有$11$個位子，用到最多數字的情形是類似$12233445566$的樣子，因此我們可以用$7$進制來表示一個儲存了連通訊息的狀態（當然沒有線的話就是$0$）。（註：事實上用$8$進制會更快，在編碼解碼的過程可以用位元運算加速。）
但這樣的表示還不夠，因為可能有很多重複的狀態，例如$12233000$和$13322000$兩個是一模一樣的狀態，所以對每個狀態我們可以把他「標準化」，把他改成「在所有其他和他等價的狀態表示中字典序最小的狀態表示法」，這只要$O(n)$掃過去就可以做到了，細節在此省略（這東西好像叫作最小表示法）。這樣可以用排列組合稍微算一下，會得到一個階段中的節點數量最多只會有幾萬個，再乘上$n^2$得到總狀態數最多幾百萬，還在可以接受的範圍內（好像還有一種表示法叫括號表示法，不過我還沒研究）。
有了狀態表示法後，轉移的部份也蠻麻煩的。首先當然要滿足不能在邊界放有線撞到邊界的拼圖，還有兩塊拼圖之間必須同時有線或無線。假設現在在轉移某個格子的某個狀態，記當前格的左邊界的狀態值為$x$，上邊界的狀態值為$y$，那麼會分成好幾種可能：
1. $x=y=0$
2. $x=0 , y\neq 0$
3. $x\neq 0,y=0$
4. $x,y\neq 0$
因為 2. 和 3. 幾乎一樣，所以等等就略過 3 的討論。對於 1. 來說，勢必要鋪上 ┏ 這塊拼圖，而轉移後的狀態的計算方法可以先在對應的兩個位子填上$7$，然後進行一次標準化得到。對於 2. 來說，可以鋪上 ┃ 和 ┗ 這兩種拼圖，而新的狀態就只要把對應的位子改成$y$就可以了，並且不用重新標準化。4. 則是最麻煩的，這時必須要放上 ┛ 。首先當 $x=y$ 時不可以放，否則就會把已經連通的分量再連起來，形成一個圈。但有個特例要判，就是如果當前格是右下角的話，那麼就可以轉移了，因為此時是把兩個$1$連起來，才能形成最後的一條哈密頓鍊。至於$x\neq y$時又分成幾種情形，如果$x=1$的話，當放上了這塊拼圖之後，另外一個值為$y$的位置就會變成$1$，因為這時候那條線就變成可以走到左上（或左下）角了，同理如果$y=1$的話，則是另一個值為$x$的位置要換成$1$。如果是$x$和$y$都不為$1$，那麼這時候就把$x$和$y$的另一個位置的值都改成同一個數就可以了。以上這些屬於 4. 的情形都必須要重新標準化一次。
實作方法有很多種，一種是預先編碼，把每種狀態都和一個$id$值對應，那麼就可以用$dp[i][j][k]$代表當前格是$(i,j)$，並且此時為第$k$個狀態的方法數，但這樣會有很多無效的狀態。我寫的方法則是直接把$dp$陣列改成 map，用壓縮過後的七進制的那個數字直接當成狀態的 index ，這樣可以在一邊DP時把新的有效的狀態加入 map 裡，不會有無效的狀態在裡面。不過不管是用哪種方法，都必須要寫兩個函式對一個$7$（或$8$）進制的數做編碼和解碼。
最後，這裡也有關於插頭DP的文章，寫的很詳細，不過我還沒全部看完@@
code :
這題是標準的插頭DP題，需要把連通性壓入狀態表示中，在上一篇中提到的是簡單的版本。因為那題只要求用多個哈密頓圈覆蓋，而這題則是限定用一條哈密頓鍊覆蓋。另外還有要求是從左上角走到左下角，因此這時候能拼的拼圖總共有9種：
但這樣的表示還不夠，因為可能有很多重複的狀態，例如$12233000$和$13322000$兩個是一模一樣的狀態，所以對每個狀態我們可以把他「標準化」，把他改成「在所有其他和他等價的狀態表示中字典序最小的狀態表示法」，這只要$O(n)$掃過去就可以做到了，細節在此省略（這東西好像叫作最小表示法）。這樣可以用排列組合稍微算一下，會得到一個階段中的節點數量最多只會有幾萬個，再乘上$n^2$得到總狀態數最多幾百萬，還在可以接受的範圍內（好像還有一種表示法叫括號表示法，不過我還沒研究）。
有了狀態表示法後，轉移的部份也蠻麻煩的。首先當然要滿足不能在邊界放有線撞到邊界的拼圖，還有兩塊拼圖之間必須同時有線或無線。假設現在在轉移某個格子的某個狀態，記當前格的左邊界的狀態值為$x$，上邊界的狀態值為$y$，那麼會分成好幾種可能：
1. $x=y=0$
2. $x=0 , y\neq 0$
3. $x\neq 0,y=0$
4. $x,y\neq 0$
因為 2. 和 3. 幾乎一樣，所以等等就略過 3 的討論。對於 1. 來說，勢必要鋪上 ┏ 這塊拼圖，而轉移後的狀態的計算方法可以先在對應的兩個位子填上$7$，然後進行一次標準化得到。對於 2. 來說，可以鋪上 ┃ 和 ┗ 這兩種拼圖，而新的狀態就只要把對應的位子改成$y$就可以了，並且不用重新標準化。4. 則是最麻煩的，這時必須要放上 ┛ 。首先當 $x=y$ 時不可以放，否則就會把已經連通的分量再連起來，形成一個圈。但有個特例要判，就是如果當前格是右下角的話，那麼就可以轉移了，因為此時是把兩個$1$連起來，才能形成最後的一條哈密頓鍊。至於$x\neq y$時又分成幾種情形，如果$x=1$的話，當放上了這塊拼圖之後，另外一個值為$y$的位置就會變成$1$，因為這時候那條線就變成可以走到左上（或左下）角了，同理如果$y=1$的話，則是另一個值為$x$的位置要換成$1$。如果是$x$和$y$都不為$1$，那麼這時候就把$x$和$y$的另一個位置的值都改成同一個數就可以了。以上這些屬於 4. 的情形都必須要重新標準化一次。
實作方法有很多種，一種是預先編碼，把每種狀態都和一個$id$值對應，那麼就可以用$dp[i][j][k]$代表當前格是$(i,j)$，並且此時為第$k$個狀態的方法數，但這樣會有很多無效的狀態。我寫的方法則是直接把$dp$陣列改成 map，用壓縮過後的七進制的那個數字直接當成狀態的 index ，這樣可以在一邊DP時把新的有效的狀態加入 map 裡，不會有無效的狀態在裡面。不過不管是用哪種方法，都必須要寫兩個函式對一個$7$（或$8$）進制的數做編碼和解碼。
最後，這裡也有關於插頭DP的文章，寫的很詳細，不過我還沒全部看完@@
code :
2015年5月13日 星期三
[ZJ a228] 就少一個插座用很不方便
作法：
這題是輪廓線DP的最簡單的題型（插頭DP好像是專指要把輪廓線上的連通性壓成狀態的DP，不過名詞似乎沒那麼重要），這裡大概提一下輪廓線DP一般的想法。首先我們知道，「多段圖的決策問題」是最好DP的東西，具體來說就是，想像現在有好幾陀節點，第 $i$ 陀節點只有連往第 $i+1$ 陀節點的邊，問起點走到終點總共有多少條路徑。這顯然可以一陀一陀算，第 $i$ 陀所有節點的答案只和第 $i-1$ 陀所有節點的答案有關，並且轉移式是顯然的。也就是當我們現在要DP的圖是多段圖時，只要確定好每陀中有哪些節點，還有知道這些節點會連向哪些節點（也就是這個狀態可以轉移到哪些狀態，或稱為這個節點的所有決策），那麼就可以簡單的DP了。至於原本的問題我們也可以把他看成一個多段圖決策問題，假設現在已經有一條路徑滿足題目要求了，那麼考慮把所有格子拆開，每個格子只會是以下六種可能之一：
或是空白的（圖中的障礙），因此我們可以把這個問題看成「拼拼圖」的問題，考慮從上而下，從左而右一塊一塊把拼圖放上去（如果這格是障礙格那就只能放沒有線的拼圖），因此我們可以用「當前要放拼圖的格子」來劃分多段圖的每個階段，並且每個節點的決策就是放上一塊拼圖。至於每一陀中到底有哪些節點，總不能把當前格之前的所有格子的每一種放法都開一個節點。而觀察下圖可以發現，如果當前格是綠色叉叉所在的格子，那麼會對之後狀態有影響的只有「紅色的邊上是否有線通過」，不管紅線以上的路徑長成什麼歪來歪去的樣子。
因此我們可以用一個長$m+1$的$01$字串代表一個狀態。而在轉移時還要注意一些事情，以上圖為例，當前格就不能放下第 $1,3,4,5$ 種拼圖，因為第 $1,4,5$ 種拼圖的左邊有線，但這個狀態相應的位子沒有線，所以不能放。而第 $3,4,5$ 種拼圖的上面沒有線，但當前狀態相應的位子有線，所以也不能放。最後也要注意到：如果當前格在盤面的右邊界，那麼就不可以放右邊有線的拼圖，同理在下邊界時也不能放下面有線的拼圖。
code :
這題是輪廓線DP的最簡單的題型（插頭DP好像是專指要把輪廓線上的連通性壓成狀態的DP，不過名詞似乎沒那麼重要），這裡大概提一下輪廓線DP一般的想法。首先我們知道，「多段圖的決策問題」是最好DP的東西，具體來說就是，想像現在有好幾陀節點，第 $i$ 陀節點只有連往第 $i+1$ 陀節點的邊，問起點走到終點總共有多少條路徑。這顯然可以一陀一陀算，第 $i$ 陀所有節點的答案只和第 $i-1$ 陀所有節點的答案有關，並且轉移式是顯然的。也就是當我們現在要DP的圖是多段圖時，只要確定好每陀中有哪些節點，還有知道這些節點會連向哪些節點（也就是這個狀態可以轉移到哪些狀態，或稱為這個節點的所有決策），那麼就可以簡單的DP了。至於原本的問題我們也可以把他看成一個多段圖決策問題，假設現在已經有一條路徑滿足題目要求了，那麼考慮把所有格子拆開，每個格子只會是以下六種可能之一：
或是空白的（圖中的障礙），因此我們可以把這個問題看成「拼拼圖」的問題，考慮從上而下，從左而右一塊一塊把拼圖放上去（如果這格是障礙格那就只能放沒有線的拼圖），因此我們可以用「當前要放拼圖的格子」來劃分多段圖的每個階段，並且每個節點的決策就是放上一塊拼圖。至於每一陀中到底有哪些節點，總不能把當前格之前的所有格子的每一種放法都開一個節點。而觀察下圖可以發現，如果當前格是綠色叉叉所在的格子，那麼會對之後狀態有影響的只有「紅色的邊上是否有線通過」，不管紅線以上的路徑長成什麼歪來歪去的樣子。
因此我們可以用一個長$m+1$的$01$字串代表一個狀態。而在轉移時還要注意一些事情，以上圖為例，當前格就不能放下第 $1,3,4,5$ 種拼圖，因為第 $1,4,5$ 種拼圖的左邊有線，但這個狀態相應的位子沒有線，所以不能放。而第 $3,4,5$ 種拼圖的上面沒有線，但當前狀態相應的位子有線，所以也不能放。最後也要注意到：如果當前格在盤面的右邊界，那麼就不可以放右邊有線的拼圖，同理在下邊界時也不能放下面有線的拼圖。
code :
[CF 513F] Scaygerboss
作法：
首先做個顯然的簡化，把問題化為$k$男$k$女的問題。因此現在問題變成，要安排$k$個位子，讓每個位子都放進一男一女，並且使得最大走路時間最少。而這顯然可以二分搜，因此現在問題變成給定一個時間上限 T，判斷是否可以完成要求。建立最大流模型，假設總共有$num$個空格，那麼考慮由$k$男$k$女，還有$num$個格子和$num$個虛擬節點，還有源點匯點構成的圖，如果 $i$ 女可以花費$\leq T$的時間走到第 $j$ 個空格，那麼就從 $i$ 女建到第 $j$ 個虛擬節點的邊，容量為$1$。並且對第 $i$ 個虛擬節點建到第 $i$ 個空格的容量為$1$的邊，還有如果 $i$ 男可以花費$\leq T$的時間走到第 $j$ 個空格，那麼就從第 $j$ 個空格建到 $i$ 男的邊，容量也是$1$。最後讓源點連往所有女生，所有男生連往匯點，容量也都是$1$。那麼從源點到匯點的最大流$=k$若且唯若存在一組解。這樣因為節點的總數為$O(n^2)$，邊的總數為$O(n^4)$，而 Dinic 算法據說在所有邊容量都為$1$的圖中的複雜度為$O(min(E^{\frac{3}{2}},EV^{\frac{2}{3}}))$，其中$E,V$分別為圖的邊數和點數（這篇comment講的），因此再加上二分搜可以得到總複雜度為$O(n^6logn)$（二分搜時每次都重建圖），對於$n=22$來說還是很大，不過應該是常數小所以很驚險的用 2683ms AC了。
code :
首先做個顯然的簡化，把問題化為$k$男$k$女的問題。因此現在問題變成，要安排$k$個位子，讓每個位子都放進一男一女，並且使得最大走路時間最少。而這顯然可以二分搜，因此現在問題變成給定一個時間上限 T，判斷是否可以完成要求。建立最大流模型，假設總共有$num$個空格，那麼考慮由$k$男$k$女，還有$num$個格子和$num$個虛擬節點，還有源點匯點構成的圖，如果 $i$ 女可以花費$\leq T$的時間走到第 $j$ 個空格，那麼就從 $i$ 女建到第 $j$ 個虛擬節點的邊，容量為$1$。並且對第 $i$ 個虛擬節點建到第 $i$ 個空格的容量為$1$的邊，還有如果 $i$ 男可以花費$\leq T$的時間走到第 $j$ 個空格，那麼就從第 $j$ 個空格建到 $i$ 男的邊，容量也是$1$。最後讓源點連往所有女生，所有男生連往匯點，容量也都是$1$。那麼從源點到匯點的最大流$=k$若且唯若存在一組解。這樣因為節點的總數為$O(n^2)$，邊的總數為$O(n^4)$，而 Dinic 算法據說在所有邊容量都為$1$的圖中的複雜度為$O(min(E^{\frac{3}{2}},EV^{\frac{2}{3}}))$，其中$E,V$分別為圖的邊數和點數（這篇comment講的），因此再加上二分搜可以得到總複雜度為$O(n^6logn)$（二分搜時每次都重建圖），對於$n=22$來說還是很大，不過應該是常數小所以很驚險的用 2683ms AC了。
code :
[CF 513E1,E2] Subarray Cuts
作法：
首先把題目改為：求 $\pm (s_1-s_2) \pm (s_2-s_3) \pm ... \pm (s_{k-1}-s_k)$ 的最大值，因為可以簡單證明前式達到最大值若且唯若題目要求的式子達到最大值，具體來說是因為如果上式中其中一項是負的話，就顯然不會是最大值了，因此最大值發生在每項都是正的情形，也就和加了絕對值沒兩樣了。而轉換成 maximize 這個函式的話就可以用DP了：記 $dp[i][j][c]$ 代表在$a_1,a_2,...,a_i$中取 $j$ 段連續的數，假設他們的和分別為$s_1,...,s_j$，則其值為$\pm (s_1-s_2) \pm (s_2-s_3) \pm ... \pm (s_{j-1}-s_j) + c\cdot s_j$ 的最大值，其中$c = 1,-1$（實作上是用 $0$ 來代表 $c=-1$，因此這裡都把下標寫為$-1$）。但這邊要注意到 $j=k$ 時會不太一樣，他的值應該要是$\pm (s_1-s_2) \pm (s_2-s_3) \pm ... \pm (s_{k-1}-s_k)$（不管 $c$ 為多少），而這可以在轉移的時候多加留意就好了。
因此再來要看如何轉移，首先$dp[i][j][c]$當然可以轉移到$dp[i-1][j][c]$，也就是$s_j$裡面不包含$a_i$的情形。而如果有包含，那麼就可以轉移到$dp[i-r][j-1][-1]+(c+1)\cdot (a_{i-r+1}+...+r_i)$，或是$dp[i-r][j-1][1]+(c-1)\cdot (a_{i-r+1}+...+r_i)$。這邊要注意到這是$j\neq 1$且$j\neq k$時的轉移式，當$j=1$時轉移到$dp[i-r][j-1][-1]$的總和那項的前面係數必須是 $c$，而轉移到$dp[i-r][j-1][1]$ 的係數也一樣是$c$。至於$j=k$時兩個係數則分別為$1$和$-1$，這些都可以由前面$dp$值的定義得出。因此這樣就得到了一個$O(n^2k)$的算法了，直接DP就可以了，code 為下面的第一份 code。
接下來我們要想辦法把他改進成$O(nk)$的，而對於這種轉移式通常就是維護某種前綴的$max$值，使得到時候在算好幾個數的$max$值的時候可以直接$O(1)$得知。這裡以$dp[i][j][1]$為例，當他想轉移到$dp[i-r][j-1][-1]$時，我們會需要以下所有數的$max$值：
$\begin{cases}dp[i-1][j-1][-1]+2a_i\\dp[i-2][j-1][-1]+2(a_{i-1}+a_i)\\dp[i-3][j-1][-1]+2(a_{i-2}+a_{i-1}+a_i)\\ \;\;\;\;\;\;\;\;\;\;\;\;\; \vdots\end{cases}$
因此可以想到直接令一個陣列$g[i][j]$等於上面那一陀值，那麼就可以得到$g$的轉移式為；$g[i][j]=max(g[i-1][j],dp[i-1][j-1][-1])+2\cdot a_i$，因此可以在一算完$dp[i][j][-1]$的時候就馬上計算$g[i+1][j+1]$的值，這樣之後要算$dp[i+1][j+1][1]$時就可以$O(1)$轉移了。
但上面只是其中一個情形，也就是「要算$dp[i][j][1]$且他想要轉移到$dp[i-r][j-1][-1]$時所得到的值」，實際上我們總共會需要$8$個$g$陣列，因為還要有「要算$dp[i][j][-1]$」時所需要的值，還有不要忘了前面的轉移式中有$c-1$和$c+1$，也就是上面那陀$max$中右邊累加和的係數也可能有其他值，因此必須對每種情形都紀錄一個$g$陣列。不過他們的轉移都一樣，所以可以直接用個 for 把所有的$g$值一起更新。
code(E1):
首先把題目改為：求 $\pm (s_1-s_2) \pm (s_2-s_3) \pm ... \pm (s_{k-1}-s_k)$ 的最大值，因為可以簡單證明前式達到最大值若且唯若題目要求的式子達到最大值，具體來說是因為如果上式中其中一項是負的話，就顯然不會是最大值了，因此最大值發生在每項都是正的情形，也就和加了絕對值沒兩樣了。而轉換成 maximize 這個函式的話就可以用DP了：記 $dp[i][j][c]$ 代表在$a_1,a_2,...,a_i$中取 $j$ 段連續的數，假設他們的和分別為$s_1,...,s_j$，則其值為$\pm (s_1-s_2) \pm (s_2-s_3) \pm ... \pm (s_{j-1}-s_j) + c\cdot s_j$ 的最大值，其中$c = 1,-1$（實作上是用 $0$ 來代表 $c=-1$，因此這裡都把下標寫為$-1$）。但這邊要注意到 $j=k$ 時會不太一樣，他的值應該要是$\pm (s_1-s_2) \pm (s_2-s_3) \pm ... \pm (s_{k-1}-s_k)$（不管 $c$ 為多少），而這可以在轉移的時候多加留意就好了。
因此再來要看如何轉移，首先$dp[i][j][c]$當然可以轉移到$dp[i-1][j][c]$，也就是$s_j$裡面不包含$a_i$的情形。而如果有包含，那麼就可以轉移到$dp[i-r][j-1][-1]+(c+1)\cdot (a_{i-r+1}+...+r_i)$，或是$dp[i-r][j-1][1]+(c-1)\cdot (a_{i-r+1}+...+r_i)$。這邊要注意到這是$j\neq 1$且$j\neq k$時的轉移式，當$j=1$時轉移到$dp[i-r][j-1][-1]$的總和那項的前面係數必須是 $c$，而轉移到$dp[i-r][j-1][1]$ 的係數也一樣是$c$。至於$j=k$時兩個係數則分別為$1$和$-1$，這些都可以由前面$dp$值的定義得出。因此這樣就得到了一個$O(n^2k)$的算法了，直接DP就可以了，code 為下面的第一份 code。
接下來我們要想辦法把他改進成$O(nk)$的，而對於這種轉移式通常就是維護某種前綴的$max$值，使得到時候在算好幾個數的$max$值的時候可以直接$O(1)$得知。這裡以$dp[i][j][1]$為例，當他想轉移到$dp[i-r][j-1][-1]$時，我們會需要以下所有數的$max$值：
$\begin{cases}dp[i-1][j-1][-1]+2a_i\\dp[i-2][j-1][-1]+2(a_{i-1}+a_i)\\dp[i-3][j-1][-1]+2(a_{i-2}+a_{i-1}+a_i)\\ \;\;\;\;\;\;\;\;\;\;\;\;\; \vdots\end{cases}$
因此可以想到直接令一個陣列$g[i][j]$等於上面那一陀值，那麼就可以得到$g$的轉移式為；$g[i][j]=max(g[i-1][j],dp[i-1][j-1][-1])+2\cdot a_i$，因此可以在一算完$dp[i][j][-1]$的時候就馬上計算$g[i+1][j+1]$的值，這樣之後要算$dp[i+1][j+1][1]$時就可以$O(1)$轉移了。
但上面只是其中一個情形，也就是「要算$dp[i][j][1]$且他想要轉移到$dp[i-r][j-1][-1]$時所得到的值」，實際上我們總共會需要$8$個$g$陣列，因為還要有「要算$dp[i][j][-1]$」時所需要的值，還有不要忘了前面的轉移式中有$c-1$和$c+1$，也就是上面那陀$max$中右邊累加和的係數也可能有其他值，因此必須對每種情形都紀錄一個$g$陣列。不過他們的轉移都一樣，所以可以直接用個 for 把所有的$g$值一起更新。
code(E1):
2015年5月11日 星期一
[CF 528E] Triangles 3000
作法：
我的作法和這篇講的第二個作法一樣，而實作的方法在那篇裡已經寫的很清楚了，這裡大概提一下他的證明。借用一下上面那篇裡面的圖，先無視掉$L_2$，我們關心的是在什麼時候「由$L_0,L_1,L_3$圍成的三角形」會被算成$-1$倍。首先注意到，對於任意四條直線$L_0,L_1,L_2,L_3$來說，如果現在要算$L_1,L_2,L_3$圍成的三角形面積，那麼他就是由其他3個三角形（$L_0,L_1,L_2$，$L_0,L_2,L_3$，$L_0,L_1,L_3$）的面積取兩個相加再扣掉另一個得來的，而扣掉的那個三角形一定會是「和$L_1,L_2,L_3$圍成的三角形有唯一的重合邊」的三角形，而滿足這件事的三角形也顯然是唯一的。因此回到無視掉$L_2$的圖，由上面的結論可以得到，如果有某一條$L_2$會使得在計算$L_1,L_2,L_3$圍成的三角形面積時，三角形$L_0,L_1,L_3$會被算成$-1$倍，那麼就代表三角形$L_1,L_2,L_3$必須和三角形$L_0,L_1,L_3$恰有一條邊重合。因此如果記$L_1,L_3$的交點為$P$，並且稱$P$把$L_1,L_3$分成了上下兩半部，那麼就可以推出$L_2$只能交$L_1$於上半部，交$L_3$於下半部，或是交$L_1$於下半部，交$L_3$於上半部。有了這件事之後就不難得到由$L_0$轉向$L_2$的夾角會介於$L_0$轉向$L_1$的夾角和$L_0$轉向$L_3$的夾角之間了。
code :
我的作法和這篇講的第二個作法一樣，而實作的方法在那篇裡已經寫的很清楚了，這裡大概提一下他的證明。借用一下上面那篇裡面的圖，先無視掉$L_2$，我們關心的是在什麼時候「由$L_0,L_1,L_3$圍成的三角形」會被算成$-1$倍。首先注意到，對於任意四條直線$L_0,L_1,L_2,L_3$來說，如果現在要算$L_1,L_2,L_3$圍成的三角形面積，那麼他就是由其他3個三角形（$L_0,L_1,L_2$，$L_0,L_2,L_3$，$L_0,L_1,L_3$）的面積取兩個相加再扣掉另一個得來的，而扣掉的那個三角形一定會是「和$L_1,L_2,L_3$圍成的三角形有唯一的重合邊」的三角形，而滿足這件事的三角形也顯然是唯一的。因此回到無視掉$L_2$的圖，由上面的結論可以得到，如果有某一條$L_2$會使得在計算$L_1,L_2,L_3$圍成的三角形面積時，三角形$L_0,L_1,L_3$會被算成$-1$倍，那麼就代表三角形$L_1,L_2,L_3$必須和三角形$L_0,L_1,L_3$恰有一條邊重合。因此如果記$L_1,L_3$的交點為$P$，並且稱$P$把$L_1,L_3$分成了上下兩半部，那麼就可以推出$L_2$只能交$L_1$於上半部，交$L_3$於下半部，或是交$L_1$於下半部，交$L_3$於上半部。有了這件事之後就不難得到由$L_0$轉向$L_2$的夾角會介於$L_0$轉向$L_1$的夾角和$L_0$轉向$L_3$的夾角之間了。
code :
[CF 528D] Fuzzy Search
作法：
蠻經典的 FFT 題。（以下使用 0 base ）因為只要注意到， $T$ 不能放在 $i$ 位置的充要條件是：存在 $j$ 滿足 $S[i+j]$ 的前後 $k$ 個之中沒有字母 $T[ j ]$ 。因此首先把每個字母分開考慮，對於每個字母 $c$ 可以先 $O( |S| )$ 處理出「哪些位置的前後 $k$ 個之中沒有 $c$ 」，這只要先算出「前 $i$ 個字母中有幾個 $c$ 」就可以 $ O( 1 ) $ 知道一個區間裡是否有 $c$ 了。假設所有上面所說的位置為 $a_1$ ~ $a_k$ ，還有 $T$ 中的所有 $c$ 的出現位置 $b_1$ ~ $b_r$ ，那麼考慮一個多項式 $f( x ) = x^{a_1} + x^{a_2} + ... + x^{a_k}$ ，還有$ g( x ) = x^{ m-1-b_1 } + x^{ m-1-b_2 } + ... + x^{ m-1-b_r } $（其中 $m = | T |$），那麼如果 $f( x ) * g( x )$ 的 $x^i$ 係數不為 $0$ 的話，就代表把 $T$ 放在 $i - m + 1$ 位置時是不合法的。因此只要作四次多項式乘法，把他全部加起來，然後去看冪次 $m-1$ ~ $n-1$ 中有幾個係數為$0$的項就可以了。
code :
蠻經典的 FFT 題。（以下使用 0 base ）因為只要注意到， $T$ 不能放在 $i$ 位置的充要條件是：存在 $j$ 滿足 $S[i+j]$ 的前後 $k$ 個之中沒有字母 $T[ j ]$ 。因此首先把每個字母分開考慮，對於每個字母 $c$ 可以先 $O( |S| )$ 處理出「哪些位置的前後 $k$ 個之中沒有 $c$ 」，這只要先算出「前 $i$ 個字母中有幾個 $c$ 」就可以 $ O( 1 ) $ 知道一個區間裡是否有 $c$ 了。假設所有上面所說的位置為 $a_1$ ~ $a_k$ ，還有 $T$ 中的所有 $c$ 的出現位置 $b_1$ ~ $b_r$ ，那麼考慮一個多項式 $f( x ) = x^{a_1} + x^{a_2} + ... + x^{a_k}$ ，還有$ g( x ) = x^{ m-1-b_1 } + x^{ m-1-b_2 } + ... + x^{ m-1-b_r } $（其中 $m = | T |$），那麼如果 $f( x ) * g( x )$ 的 $x^i$ 係數不為 $0$ 的話，就代表把 $T$ 放在 $i - m + 1$ 位置時是不合法的。因此只要作四次多項式乘法，把他全部加起來，然後去看冪次 $m-1$ ~ $n-1$ 中有幾個係數為$0$的項就可以了。
code :
[CF 543D] Road Improvement
作法：
首先容易得出以某個點為根的算法：如果記每個點的子樹的取法數為 $dp[ x ]$ ，那麼 $dp[ x ] =\prod ( dp[ s ] + 1 )$ ，其中$s$跑遍所有$x$的子節點。而當我們算出整棵樹以 $x$ 為根時每個點的 $dp$ 值了，如果現在想要轉移到整棵樹以某個 $x$ 的子節點 $s$ 的 $dp$ 值，那麼其實會變動的 $dp$ 值只有兩個，也就是$x$和$s$的值，並且不難知道他們新的 $dp$ 值的算法，因此只要再對原圖做一次 DFS ，每次要往下走時把 $dp$ 值更新成以他為根時的所有點的 $dp$ 值，走回來時再把 $dp$ 值還原就可以了。
但這樣有個很不明顯的陷阱，就是當在換根的時候 $dp[ x ]$ 的新的值會是 $\frac{dp[ x ]}{dp[ s ] + 1} $，因此如果$dp[ x ]$和$dp[ s ] + 1$都是$MOD $的倍數，那麼就不知道新的 $dp$ 值到底是多少了！因此只好對於每個 $dp$ 值，都紀錄一個「這個數是 $MOD$ 的幾次方的倍數」才可以正確的計算 $dp$ 值。
code :
首先容易得出以某個點為根的算法：如果記每個點的子樹的取法數為 $dp[ x ]$ ，那麼 $dp[ x ] =\prod ( dp[ s ] + 1 )$ ，其中$s$跑遍所有$x$的子節點。而當我們算出整棵樹以 $x$ 為根時每個點的 $dp$ 值了，如果現在想要轉移到整棵樹以某個 $x$ 的子節點 $s$ 的 $dp$ 值，那麼其實會變動的 $dp$ 值只有兩個，也就是$x$和$s$的值，並且不難知道他們新的 $dp$ 值的算法，因此只要再對原圖做一次 DFS ，每次要往下走時把 $dp$ 值更新成以他為根時的所有點的 $dp$ 值，走回來時再把 $dp$ 值還原就可以了。
但這樣有個很不明顯的陷阱，就是當在換根的時候 $dp[ x ]$ 的新的值會是 $\frac{dp[ x ]}{dp[ s ] + 1} $，因此如果$dp[ x ]$和$dp[ s ] + 1$都是$MOD $的倍數，那麼就不知道新的 $dp$ 值到底是多少了！因此只好對於每個 $dp$ 值，都紀錄一個「這個數是 $MOD$ 的幾次方的倍數」才可以正確的計算 $dp$ 值。
code :
2015年5月9日 星期六
[CF 543C] Remembering Strings
作法：
我一開始的想法是，對於每個字串，我們可以選一個位置把他改掉，使得這個字串一定可以滿足條件，因為字串的個數小於字母的個數。而對於每一行來說，我們可以做的決策就是選一些字串並且把那個位置改成星號，代表等一下一定會變得不一樣的意思，並且可以算出這樣的決策會讓哪些字串變得滿足條件。有了轉移就可以位元 DP 了，記 $dp[ i ][ j ]$ 代表只考慮前 $i$ 行，並且已滿足條件的字串集合為 $j$ 時至少需要花費多少。但這樣每一行都會有 $O( 2^n )$ 種決策，會讓複雜度爆掉，於是我就卡到比賽結束了......後來去看詳解才知道，其實我們可以把決策都拆開，例如假設一行裡面有 $6$ 個 $a $，其中一個決策是把 4 個 $a$ 換成星號，那麼就可以把他拆成 $4 $種決策，每種分別是把對應位置的 $a $換成星號。而如果是把 $5$ 個 $a$ 換成星號的決策，就會讓 $6$ 個字串都變成符合條件的，總共有 $6$ 種取法，但他們的功能都一樣，所以只要取會讓花費最少的那個方案就好了。而像取好幾個 $a$ 和好幾個 $b$ 的決策，也可以把他拆成取好幾個 $a$ 和取好幾個 $b$ ，這樣剩下的決策總數就剩下 $O( m )$ 了（對於那些達到相同功能的決策都取他們的 $min$ 值），所以就可以在 $O( m^2 2^n )$ 的時間內DP完了。而至於為什麼這裡的DP可以這樣拆，是因為狀態在轉移時是從 $j$ 轉移到 $j | x$ ，其中 $x$ 代表這次決策可以造成哪些字串變成符合條件的。
code :
我一開始的想法是，對於每個字串，我們可以選一個位置把他改掉，使得這個字串一定可以滿足條件，因為字串的個數小於字母的個數。而對於每一行來說，我們可以做的決策就是選一些字串並且把那個位置改成星號，代表等一下一定會變得不一樣的意思，並且可以算出這樣的決策會讓哪些字串變得滿足條件。有了轉移就可以位元 DP 了，記 $dp[ i ][ j ]$ 代表只考慮前 $i$ 行，並且已滿足條件的字串集合為 $j$ 時至少需要花費多少。但這樣每一行都會有 $O( 2^n )$ 種決策，會讓複雜度爆掉，於是我就卡到比賽結束了......後來去看詳解才知道，其實我們可以把決策都拆開，例如假設一行裡面有 $6$ 個 $a $，其中一個決策是把 4 個 $a$ 換成星號，那麼就可以把他拆成 $4 $種決策，每種分別是把對應位置的 $a $換成星號。而如果是把 $5$ 個 $a$ 換成星號的決策，就會讓 $6$ 個字串都變成符合條件的，總共有 $6$ 種取法，但他們的功能都一樣，所以只要取會讓花費最少的那個方案就好了。而像取好幾個 $a$ 和好幾個 $b$ 的決策，也可以把他拆成取好幾個 $a$ 和取好幾個 $b$ ，這樣剩下的決策總數就剩下 $O( m )$ 了（對於那些達到相同功能的決策都取他們的 $min$ 值），所以就可以在 $O( m^2 2^n )$ 的時間內DP完了。而至於為什麼這裡的DP可以這樣拆，是因為狀態在轉移時是從 $j$ 轉移到 $j | x$ ，其中 $x$ 代表這次決策可以造成哪些字串變成符合條件的。
code :
[CF 543B] Destroying Roads
作法：
破壞掉最多的路，也就是要留下最少的路。如果兩條最短路沒有相交，那麼顯然把其他邊都砍掉是最好的。而如果有相交的話，讓兩條最短路相交成 $H$ 字型會是最好的，因為如果兩條路徑重合的部份分成了很多段，那麼中間就會出現類似一個圈的東西（大概會長的像├O┤），那麼把中間那個圈改成只取比較短的那條就好了。因此只要枚舉兩個點當 $H$ 的中繼點，計算 $H$ 的總長就可以了。但這題有一些陷阱，首先是如果兩條路徑一模一樣的話不能去枚舉 $H$ 的兩個中繼點，否則長度會算到太長。還有必須把 $s2$ 和 $t2$ 交換再算一次，因為有可能當中繼點是 $i , j$ 時， $i$ 連到 $s1$ 和 $t2$ 是比較好的選擇。
code :
破壞掉最多的路，也就是要留下最少的路。如果兩條最短路沒有相交，那麼顯然把其他邊都砍掉是最好的。而如果有相交的話，讓兩條最短路相交成 $H$ 字型會是最好的，因為如果兩條路徑重合的部份分成了很多段，那麼中間就會出現類似一個圈的東西（大概會長的像├O┤），那麼把中間那個圈改成只取比較短的那條就好了。因此只要枚舉兩個點當 $H$ 的中繼點，計算 $H$ 的總長就可以了。但這題有一些陷阱，首先是如果兩條路徑一模一樣的話不能去枚舉 $H$ 的兩個中繼點，否則長度會算到太長。還有必須把 $s2$ 和 $t2$ 交換再算一次，因為有可能當中繼點是 $i , j$ 時， $i$ 連到 $s1$ 和 $t2$ 是比較好的選擇。
code :
[CF 526G] Spiders Evil Plan
作法：
我寫的作法跟這篇寫的一樣，這裡大概提一下實作的方法跟證明。
首先當然是找出重心，然後預處理出每個點往下走到葉子的最長距離，還有他應該要往哪個子節點走才可以走到最遠的葉子。這樣就可以用一個 priority_queue 來處理「一直把路徑拔掉」的操作了。具體來說，priority_queue 裡面放的是所有現在候選的鍊的深度最淺的點，還有這條鍊的長度，當我們把一條鍊從 priority_queue 裡面拿出來時，就沿著這條鍊走下去，並且對於走到的每一個點 $X$ ，假設他沿著鍊往下走的點為 $Y$ ，那麼就把 $X$ 除了 $Y$ 以外的所有子節點 $Z$ 都加入 priority_queue 中，並且可以知道 $Z$ 所代表的鍊長為 $d[ Z ] + dis[ X ] [ Z ]$ ，其中 $d$ 代表每個點往下走到葉子的最長距離， $dis$ 則是兩點之間的距離。而再處理詢問時，我們還要知道前 $2y$ 條鍊的總長度是多少，所以會需要一個前綴和陣列，還有一個點是落在第幾條鍊上。另外當詢問的 $x$ 沒有落在前 $2y$ 條鍊上時，會必須要沿著 $x$ 往上走，走到第一個落在前 $2y$ 條鍊上的點，而這個部份就可以用類似在找 LCA 的倍增法處理，所以要先預處理好每個點的 $2^k$ 級祖先是誰。
至於證明，當前 $2y$ 條鍊已經包含 $x$ 了的話是顯然的，以下只考慮不包含 $x$ 的情形。事實上對於一次的詢問，有一個貪心的算法是：以 $x$ 為根建出這棵樹，然後依次取 $2y$ 次葉節點，使得每次多取一個葉節點時可以讓總長增加的最多，這樣會是最好的選法。但是當我們所有選的鍊都是落在 $x$ 的同一個子節點 $y$ 底下時，這樣就會變成總共有 $2y + 1$ 個葉節點，不符合要求，因此必須把其中一條捨棄掉，加入一條 $x$ 往 $y$ 以外的子節點連過去並且連到最遠葉子的路徑。那麼回到現在這張以重心為根的圖，會得到以 $x$ 為根時貪心所選的 $2y$ 條鍊都會是往 $x$ 的祖先的方向（否則以重心為根的前 $2y$ 條鍊會選到 $x$），所以必須捨棄掉其中一條，並加上 $d[ x ]$ ，這就和上面的算法一致了。
code :
我寫的作法跟這篇寫的一樣，這裡大概提一下實作的方法跟證明。
首先當然是找出重心，然後預處理出每個點往下走到葉子的最長距離，還有他應該要往哪個子節點走才可以走到最遠的葉子。這樣就可以用一個 priority_queue 來處理「一直把路徑拔掉」的操作了。具體來說，priority_queue 裡面放的是所有現在候選的鍊的深度最淺的點，還有這條鍊的長度，當我們把一條鍊從 priority_queue 裡面拿出來時，就沿著這條鍊走下去，並且對於走到的每一個點 $X$ ，假設他沿著鍊往下走的點為 $Y$ ，那麼就把 $X$ 除了 $Y$ 以外的所有子節點 $Z$ 都加入 priority_queue 中，並且可以知道 $Z$ 所代表的鍊長為 $d[ Z ] + dis[ X ] [ Z ]$ ，其中 $d$ 代表每個點往下走到葉子的最長距離， $dis$ 則是兩點之間的距離。而再處理詢問時，我們還要知道前 $2y$ 條鍊的總長度是多少，所以會需要一個前綴和陣列，還有一個點是落在第幾條鍊上。另外當詢問的 $x$ 沒有落在前 $2y$ 條鍊上時，會必須要沿著 $x$ 往上走，走到第一個落在前 $2y$ 條鍊上的點，而這個部份就可以用類似在找 LCA 的倍增法處理，所以要先預處理好每個點的 $2^k$ 級祖先是誰。
至於證明，當前 $2y$ 條鍊已經包含 $x$ 了的話是顯然的，以下只考慮不包含 $x$ 的情形。事實上對於一次的詢問，有一個貪心的算法是：以 $x$ 為根建出這棵樹，然後依次取 $2y$ 次葉節點，使得每次多取一個葉節點時可以讓總長增加的最多，這樣會是最好的選法。但是當我們所有選的鍊都是落在 $x$ 的同一個子節點 $y$ 底下時，這樣就會變成總共有 $2y + 1$ 個葉節點，不符合要求，因此必須把其中一條捨棄掉，加入一條 $x$ 往 $y$ 以外的子節點連過去並且連到最遠葉子的路徑。那麼回到現在這張以重心為根的圖，會得到以 $x$ 為根時貪心所選的 $2y$ 條鍊都會是往 $x$ 的祖先的方向（否則以重心為根的前 $2y$ 條鍊會選到 $x$），所以必須捨棄掉其中一條，並加上 $d[ x ]$ ，這就和上面的算法一致了。
code :
[CF 538H] Summer Dichotomy
這題的兩個官方解都還蠻精湛的，特別是第二個，把他轉換成 2-SAT 真是太神奇了OAO，建議兩個都看看，相比之下我的解就爛爛的也比較難寫=ㄦ= 。
作法：
首先當給定的圖不是二部圖時無解。一開始可以把原圖轉換成剩下一堆點和一堆互斥的連接兩點的線段，實際作法也蠻顯然的所以這裡略過。當然如果轉換後出現一個老師要求的學生數集合是空集也顯然無解。我們先處理整張圖裡沒有邊的情形，再把類似的想法套到一般的圖上。
如果現在整張圖裡沒有邊，那麼問題就等價於：有一堆線段，目標要取兩個點 X , Y ，使得所有線段均包含 $X$ 或 $Y$ ，且 $t \leq X+Y \leq T$ 。我們先無視 $t$ 和 $T$ 的限制，之後再考慮進來。可以假設 $X \leq Y$ ，那麼 $X$ 必須要 $\leq $所有線段的右端點，否則就會有線段沒有被 $X$ 和 $Y$ 碰到。假設所有線段右端點的最小值為 $R0$ ，所以有 $X \leq R0$ ，也就是等一下我們會考慮 $X$ 從 $R0$ 開始慢慢往左邊跑。如果有一條線段的左端點 $> R0$ ，那麼他之後永遠都不會被 $X$ 碰到，所以就直接把他丟給 $Y$ 去處理（等等 $Y$ 必須要被這條線段包含）。也就是當 $X = R0$ 時，設所有被 $X$ 碰到的線段集合為 $SX$ ，剩下的線段集合為 $SY$ ，那麼 $Y$ 一定要落在 $SY$ 中所有線段的交集裡。如果此時 $SY$ 的交集為空集那麼無解（等等會說明），否則假設現在 $SY$ 的交集為 $[ L , R ]$ ，如果 $R0 + L $ ~ $ R0 + R$ 之間存在一個數介於 $[ t , T ]$ 之間那就找到解了，否則有可能這些數都比 $T$ 大，或是這些數都比 $t$ 小。當 $X$ 慢慢往左移時，假設 $SX$ 中擁有左端點最大值的線段為 $[ L1 , R1 ] $，那麼 $X$ 在往左移到 $< L1$ 之前 $SX$ 和 $SY$ 都不會改變，也就是我們能再確認一下 $L1 + L $ ~ $ R0 + R$ 之間是否有一個數介於 $[ t , T ]$ 之間。如果 $X$ 想要往左移到 $< L1$ 的地方，那麼這時就必須要把 $[ L1 , R1 ]$ 丟給右邊處理，也就是從 $SX$ 中移除 $[ L1 , R1 ]$ ，並在 $SY$ 中加入 $[ L1 , R1 ]$ ，然後繼續重複上述過程（當 $[ L1 , R1 ]$ 被丟到右邊時，$X$ 的往左可移動範圍就變大了）。而這邊就可以注意到，對於 $SY$ 來說，他裡面的線段數量會越來越多，也就是 $SY$ 中所有線段的交集會越來越小，因此當 $x = R0$ 時 $SY$ 交集就已經是空集合的時候就直接無解了。另外還可以注意到，如果前面我們發現到 $R0 + L $ ~ $ R0 + R$ 之間的所有數都比 $t$ 小，那麼之後也是無解的，因為 $[ L , R ]$ 只會越來越往裡面縮，而 $X$ 則是往越來越小的方向跑，也就是不管怎麼樣我們之後找到的解的兩數和一定都會比$ t $小，所以就可以直接判掉了。
再來我們要改進上面的算法來解決原本的問題(原圖為一堆互斥的線段)。假設有一對互相仇視的老師 $[ l , r ]$ 和 $[ l2 , r2 ]$ ，並且 $l \leq l2$ ，那麼可以分成幾種情形：
1. $r < l2$
2. $l2 \leq r $且$ r2 \geq r$
3. $l2 \leq r $且$ r2 < r$
對於第1種情形，可以得到 $[ l , r ]$ 一定是要被放在 $SX$ 裡的，還有 $[ l2 , r2 ]$ 一定要被放在 $SY$ 裡。而對於第2種情形，可以簡單的證明如果存在一個解，使得 $[ l , r ]$ 包含 $Y$ 且 $[ l2 , r2 ]$ 包含 $X$ ，那麼 $[ l , r ]$ 和 $[ l2 , r2 ]$ 都包含了 $X$ 和 $Y$ ，也就是我們也可以直接把 $[ l , r ]$ 丟給 $SX$ ， $[ l2 , r2 ]$ 丟給 $SY$ 。而這裡跟剛剛不一樣的點在於，當之後我們要從 $SX$ 裡拿線段出來丟到 $SY$ 時，前兩種情況的 $[ l , r ]$ 都是不可以被丟到 $SY$ 的，否則就會和條件矛盾，因此要作個標記，當準備要把這種線段丟棄時，就代表 $X$ 不能再往左邊了，就必須要直接 break 掉。至於第3種情形比較麻煩，當我們算出前一段所說的點 $R0$ 時，如果 $R0 \geq l2$ ，那麼這時可以把 $[ l , r ]$ 或 $[ l2 , r2 ]$ 丟到 $SY$ ，因為當 $X = R0$ 時 $X$ 可以負責 $[ l , r ]$ 或 $[ l2 , r2 ]$ ，但此時對 $X$ 來說負責哪條線段其實沒差，所以我們可以先把 $[ l , r ]$ 丟到 $SY$ 裡。或是此時 $R0$ 已經 $< l2$ 了，那麼就勢必要把 $[ l , r ]$ 丟進 $SX$ ，把 $[ l2 , r2 ]$ 丟進 $SY$ ，並且把 $[ l , r ]$ 標記為不可移除，這種情況比較好處理。如果是上一種情況，並且當我們打算在 $SX$ 中移除掉 $[ l2 , r2 ]$ 時，這時作的動作就會變成把 $[ l2 , r2 ]$ 從 $SX$ 丟進 $SY$ ，然後把 $[ l , r ]$ 從 $SY$ 丟進 $SX$ ，因為必須要滿足題目條件。這樣也有機會讓 $X$ 的可移動範圍變大，並且也可以符合題目的條件，所以是沒有問題的。
因此最終的算法和原本的算法只差在會需要判蠻多條件的，至於要怎麼輸出解，我們會需要一個函式把原圖中的一整個連通塊的顏色都反過來，而這只要對於一個 $( l , r , l2 , r2 )$ 多紀錄原始連通塊中的任意一個點就可以了。
code :
作法：
首先當給定的圖不是二部圖時無解。一開始可以把原圖轉換成剩下一堆點和一堆互斥的連接兩點的線段，實際作法也蠻顯然的所以這裡略過。當然如果轉換後出現一個老師要求的學生數集合是空集也顯然無解。我們先處理整張圖裡沒有邊的情形，再把類似的想法套到一般的圖上。
如果現在整張圖裡沒有邊，那麼問題就等價於：有一堆線段，目標要取兩個點 X , Y ，使得所有線段均包含 $X$ 或 $Y$ ，且 $t \leq X+Y \leq T$ 。我們先無視 $t$ 和 $T$ 的限制，之後再考慮進來。可以假設 $X \leq Y$ ，那麼 $X$ 必須要 $\leq $所有線段的右端點，否則就會有線段沒有被 $X$ 和 $Y$ 碰到。假設所有線段右端點的最小值為 $R0$ ，所以有 $X \leq R0$ ，也就是等一下我們會考慮 $X$ 從 $R0$ 開始慢慢往左邊跑。如果有一條線段的左端點 $> R0$ ，那麼他之後永遠都不會被 $X$ 碰到，所以就直接把他丟給 $Y$ 去處理（等等 $Y$ 必須要被這條線段包含）。也就是當 $X = R0$ 時，設所有被 $X$ 碰到的線段集合為 $SX$ ，剩下的線段集合為 $SY$ ，那麼 $Y$ 一定要落在 $SY$ 中所有線段的交集裡。如果此時 $SY$ 的交集為空集那麼無解（等等會說明），否則假設現在 $SY$ 的交集為 $[ L , R ]$ ，如果 $R0 + L $ ~ $ R0 + R$ 之間存在一個數介於 $[ t , T ]$ 之間那就找到解了，否則有可能這些數都比 $T$ 大，或是這些數都比 $t$ 小。當 $X$ 慢慢往左移時，假設 $SX$ 中擁有左端點最大值的線段為 $[ L1 , R1 ] $，那麼 $X$ 在往左移到 $< L1$ 之前 $SX$ 和 $SY$ 都不會改變，也就是我們能再確認一下 $L1 + L $ ~ $ R0 + R$ 之間是否有一個數介於 $[ t , T ]$ 之間。如果 $X$ 想要往左移到 $< L1$ 的地方，那麼這時就必須要把 $[ L1 , R1 ]$ 丟給右邊處理，也就是從 $SX$ 中移除 $[ L1 , R1 ]$ ，並在 $SY$ 中加入 $[ L1 , R1 ]$ ，然後繼續重複上述過程（當 $[ L1 , R1 ]$ 被丟到右邊時，$X$ 的往左可移動範圍就變大了）。而這邊就可以注意到，對於 $SY$ 來說，他裡面的線段數量會越來越多，也就是 $SY$ 中所有線段的交集會越來越小，因此當 $x = R0$ 時 $SY$ 交集就已經是空集合的時候就直接無解了。另外還可以注意到，如果前面我們發現到 $R0 + L $ ~ $ R0 + R$ 之間的所有數都比 $t$ 小，那麼之後也是無解的，因為 $[ L , R ]$ 只會越來越往裡面縮，而 $X$ 則是往越來越小的方向跑，也就是不管怎麼樣我們之後找到的解的兩數和一定都會比$ t $小，所以就可以直接判掉了。
再來我們要改進上面的算法來解決原本的問題(原圖為一堆互斥的線段)。假設有一對互相仇視的老師 $[ l , r ]$ 和 $[ l2 , r2 ]$ ，並且 $l \leq l2$ ，那麼可以分成幾種情形：
1. $r < l2$
2. $l2 \leq r $且$ r2 \geq r$
3. $l2 \leq r $且$ r2 < r$
對於第1種情形，可以得到 $[ l , r ]$ 一定是要被放在 $SX$ 裡的，還有 $[ l2 , r2 ]$ 一定要被放在 $SY$ 裡。而對於第2種情形，可以簡單的證明如果存在一個解，使得 $[ l , r ]$ 包含 $Y$ 且 $[ l2 , r2 ]$ 包含 $X$ ，那麼 $[ l , r ]$ 和 $[ l2 , r2 ]$ 都包含了 $X$ 和 $Y$ ，也就是我們也可以直接把 $[ l , r ]$ 丟給 $SX$ ， $[ l2 , r2 ]$ 丟給 $SY$ 。而這裡跟剛剛不一樣的點在於，當之後我們要從 $SX$ 裡拿線段出來丟到 $SY$ 時，前兩種情況的 $[ l , r ]$ 都是不可以被丟到 $SY$ 的，否則就會和條件矛盾，因此要作個標記，當準備要把這種線段丟棄時，就代表 $X$ 不能再往左邊了，就必須要直接 break 掉。至於第3種情形比較麻煩，當我們算出前一段所說的點 $R0$ 時，如果 $R0 \geq l2$ ，那麼這時可以把 $[ l , r ]$ 或 $[ l2 , r2 ]$ 丟到 $SY$ ，因為當 $X = R0$ 時 $X$ 可以負責 $[ l , r ]$ 或 $[ l2 , r2 ]$ ，但此時對 $X$ 來說負責哪條線段其實沒差，所以我們可以先把 $[ l , r ]$ 丟到 $SY$ 裡。或是此時 $R0$ 已經 $< l2$ 了，那麼就勢必要把 $[ l , r ]$ 丟進 $SX$ ，把 $[ l2 , r2 ]$ 丟進 $SY$ ，並且把 $[ l , r ]$ 標記為不可移除，這種情況比較好處理。如果是上一種情況，並且當我們打算在 $SX$ 中移除掉 $[ l2 , r2 ]$ 時，這時作的動作就會變成把 $[ l2 , r2 ]$ 從 $SX$ 丟進 $SY$ ，然後把 $[ l , r ]$ 從 $SY$ 丟進 $SX$ ，因為必須要滿足題目條件。這樣也有機會讓 $X$ 的可移動範圍變大，並且也可以符合題目的條件，所以是沒有問題的。
因此最終的算法和原本的算法只差在會需要判蠻多條件的，至於要怎麼輸出解，我們會需要一個函式把原圖中的一整個連通塊的顏色都反過來，而這只要對於一個 $( l , r , l2 , r2 )$ 多紀錄原始連通塊中的任意一個點就可以了。
code :
2015年5月7日 星期四
[CF 538G] Berserk Robot
這題官方解是先轉成一維的問題，我的作法是直接作，雖然本質上好像沒有差很多，不過我還得枚舉一個變數的值，感覺比官方解的麻煩多了......
作法：
一開始大概可以先想到奇偶性的問題：如果走了 $i$ 步停在 $( x , y )$ ，那麼 $i$ 和 $x + y$ 的奇偶性一定要一樣，這件事可以先在讀入條件時過濾掉顯然不可能的解。以下把每個指令都看成一個向量（$U$ 就是 $( 0 , 1 )$ ，以此類推），並且記 $S_i$ 為前 $i$ 個指令的向量和，另外記 $S_L = ( p , q )$ 。首先每個條件告訴我們的東西其實是一個等式： $k ( p , q ) + S_i = ( x , y )$ ，其中如果輸入為 $t , x , y$ 的話，那麼上式的 $ k$ 就等於 $\left \lfloor \frac{t}{L} \right \rfloor$ ，$i$ 等於 $t % L$ 。觀察這條式子可以發現，如果確定好 $( p , q )$ 的值時，就代表現在每個條件都變成了 $S_i = ( ?? , ?? )$ 的型式了，此時處理方法就會變得很簡單：把所有的 $S_i$ 按照 $i$ 值由小到大排序，如果相鄰等式的奇偶性沒有滿足的話就無解，或是相鄰兩個等式要求的 $S_i$ 座標的曼哈頓距離太大了(超過兩式的 $S$ 的下標差值)就無解，反之可以簡單的構造出一組解（先一堆 $U/D$ 再一堆 $R/L$ ，如果還有多的步數就一直加 $LR$ 之類的）。而由上面的處理方法可以反過來得到 $p , q$ 的限制條件，具體來說，首先把所有的等式都改寫成 $S_i = ( a \cdot p + b , c \cdot p + d )$ 這種樣子( 其中$ a = c = -k , b = x , d = y$ )，所以可以用 $5$ 個變數$( i , a , b , c , d )$來代表一個等式(當然 $4$ 個也可以，因為 $a = c$ ，不過我覺得用 $5$ 個比較直觀)。把所有的等式按照 $i$ 由小到大排序，不過還要注意到在這之前還得加上兩個潛在的條件：$S_0 = ( 0 \cdot p + 0 , 0 \cdot q + 0 )$ ，還有 $S_L = ( 1 \cdot p + 0 , 1 \cdot q + 0 )$ 。將等式們排序後，看兩條相鄰的等式 $S_i $和 $S_j$ ，假設他們的$4$個係數分別為$ a1 , b1 , c1 , d1$ 和 $a2 , b2 , c2 , d2$ ，那麼這樣就得到了一個條件：$| ( a1 - a2 ) \cdot p + ( b1 - b2 ) | + | ( c1 - c2 ) \cdot q + ( d1 - d2 ) | \leq | j - i |$ ，更一般的可以寫成 $| a \cdot p + b | + | c \cdot q + d | \leq e$ ，也就是現在我們獲得了很多這樣子的關於 $p$ 和 $q$ 的限制條件，要找出一組可能的 $( p , q )$ 或是輸出無解。（對了，如果相鄰兩等式的 $a$ 值一樣的話，條件就會變成 $| b | + | d | \leq e$ ，這個可以直接判掉，所以之後可以不用考慮條件中 $a=0$ 或 $c=0$ 的情形。）
如果考慮對某一個限制條件枚舉 $p$ 的話，顯然 $p$ 要滿足 $| a \cdot p + b | \leq e$ ，所以可以先解出 $p$ 的範圍。當確定 $p$ 的值時，所有的條件就變成 $| c \cdot q + d | \leq f$ 的型式了，於是只要再對每個條件都跑一次，把所有的 $q$ 要滿足的不等式交集起來就好了，但這樣複雜度會爆掉。不過其實可以發現，因為當 $p$ 變動 1 的時候 $a \cdot p + b$ 會變動 $a$ ，所以滿足 $| a \cdot p + b | \leq e$ 的 $p$ 值大概不會超過 $\frac{2e}{a}$ 個（因為當 $p$ 改變那麼多時 $a \cdot p + b$ 就至少會從 $-e$ 跳到 $e$ 了），也就是我們有 $p$ 要枚舉的個數上限了，但這件事還不夠，因為如果 $e$ 很大的話複雜度還是爆掉的。但是事實上 $e$ 不會總是那麼大！觀察所有條件的 $e$ 值的由來，是由兩個相鄰等式的 $S$ 的下標相減得到的，所以就可以得到所有 $e$ 值的總和 $\leq L$ ，所以我們只要取 $e$ 值最小的那個等式枚舉 $p$ 的值就好了。這樣的話假設共有 $x$ 條等式，那麼 $e$ 的最小值 $\leq L / x$ ，所以這樣子的複雜度就會是 $O( x ) \cdot O( L / x ) = O( L )$ ！就成功解決了這個問題了。類似的梗也出現在 CF 526-E Transmitting Levels。
但這樣傳上去之後爛掉了OAO，後來我發現是因為忘記判斷相鄰兩個等式之間的奇偶條件了......也就是當我們得到一條 $| ( a1 - a2 ) \cdot p + ( b1 - b2 ) | + | ( c1 - c2 ) \cdot q + ( d1 - d2 ) | \leq | j - i |$ 這樣的條件時，奇偶性的條件其實就會等價於「左式和右式的奇偶性一樣」。我的解決方法是：因為當在枚舉 $p$ 時會再把所有條件跑過一遍，那麼只要在那時候多回傳「 $q$ 是否可以是奇數」和「 $q$ 是否可以是偶數」這兩件事就好了。另外一個小細節是，我們會需要解形如 $a \leq k \cdot x \leq b$ 的等式，其中 $a , b , k$ 給定，這要把 $a$ 和 $b$ 的正負分開處理才可以，因為「 / 」這個運算子是往 $0$ 的方向捨去的。
code :
作法：
一開始大概可以先想到奇偶性的問題：如果走了 $i$ 步停在 $( x , y )$ ，那麼 $i$ 和 $x + y$ 的奇偶性一定要一樣，這件事可以先在讀入條件時過濾掉顯然不可能的解。以下把每個指令都看成一個向量（$U$ 就是 $( 0 , 1 )$ ，以此類推），並且記 $S_i$ 為前 $i$ 個指令的向量和，另外記 $S_L = ( p , q )$ 。首先每個條件告訴我們的東西其實是一個等式： $k ( p , q ) + S_i = ( x , y )$ ，其中如果輸入為 $t , x , y$ 的話，那麼上式的 $ k$ 就等於 $\left \lfloor \frac{t}{L} \right \rfloor$ ，$i$ 等於 $t % L$ 。觀察這條式子可以發現，如果確定好 $( p , q )$ 的值時，就代表現在每個條件都變成了 $S_i = ( ?? , ?? )$ 的型式了，此時處理方法就會變得很簡單：把所有的 $S_i$ 按照 $i$ 值由小到大排序，如果相鄰等式的奇偶性沒有滿足的話就無解，或是相鄰兩個等式要求的 $S_i$ 座標的曼哈頓距離太大了(超過兩式的 $S$ 的下標差值)就無解，反之可以簡單的構造出一組解（先一堆 $U/D$ 再一堆 $R/L$ ，如果還有多的步數就一直加 $LR$ 之類的）。而由上面的處理方法可以反過來得到 $p , q$ 的限制條件，具體來說，首先把所有的等式都改寫成 $S_i = ( a \cdot p + b , c \cdot p + d )$ 這種樣子( 其中$ a = c = -k , b = x , d = y$ )，所以可以用 $5$ 個變數$( i , a , b , c , d )$來代表一個等式(當然 $4$ 個也可以，因為 $a = c$ ，不過我覺得用 $5$ 個比較直觀)。把所有的等式按照 $i$ 由小到大排序，不過還要注意到在這之前還得加上兩個潛在的條件：$S_0 = ( 0 \cdot p + 0 , 0 \cdot q + 0 )$ ，還有 $S_L = ( 1 \cdot p + 0 , 1 \cdot q + 0 )$ 。將等式們排序後，看兩條相鄰的等式 $S_i $和 $S_j$ ，假設他們的$4$個係數分別為$ a1 , b1 , c1 , d1$ 和 $a2 , b2 , c2 , d2$ ，那麼這樣就得到了一個條件：$| ( a1 - a2 ) \cdot p + ( b1 - b2 ) | + | ( c1 - c2 ) \cdot q + ( d1 - d2 ) | \leq | j - i |$ ，更一般的可以寫成 $| a \cdot p + b | + | c \cdot q + d | \leq e$ ，也就是現在我們獲得了很多這樣子的關於 $p$ 和 $q$ 的限制條件，要找出一組可能的 $( p , q )$ 或是輸出無解。（對了，如果相鄰兩等式的 $a$ 值一樣的話，條件就會變成 $| b | + | d | \leq e$ ，這個可以直接判掉，所以之後可以不用考慮條件中 $a=0$ 或 $c=0$ 的情形。）
如果考慮對某一個限制條件枚舉 $p$ 的話，顯然 $p$ 要滿足 $| a \cdot p + b | \leq e$ ，所以可以先解出 $p$ 的範圍。當確定 $p$ 的值時，所有的條件就變成 $| c \cdot q + d | \leq f$ 的型式了，於是只要再對每個條件都跑一次，把所有的 $q$ 要滿足的不等式交集起來就好了，但這樣複雜度會爆掉。不過其實可以發現，因為當 $p$ 變動 1 的時候 $a \cdot p + b$ 會變動 $a$ ，所以滿足 $| a \cdot p + b | \leq e$ 的 $p$ 值大概不會超過 $\frac{2e}{a}$ 個（因為當 $p$ 改變那麼多時 $a \cdot p + b$ 就至少會從 $-e$ 跳到 $e$ 了），也就是我們有 $p$ 要枚舉的個數上限了，但這件事還不夠，因為如果 $e$ 很大的話複雜度還是爆掉的。但是事實上 $e$ 不會總是那麼大！觀察所有條件的 $e$ 值的由來，是由兩個相鄰等式的 $S$ 的下標相減得到的，所以就可以得到所有 $e$ 值的總和 $\leq L$ ，所以我們只要取 $e$ 值最小的那個等式枚舉 $p$ 的值就好了。這樣的話假設共有 $x$ 條等式，那麼 $e$ 的最小值 $\leq L / x$ ，所以這樣子的複雜度就會是 $O( x ) \cdot O( L / x ) = O( L )$ ！就成功解決了這個問題了。類似的梗也出現在 CF 526-E Transmitting Levels。
但這樣傳上去之後爛掉了OAO，後來我發現是因為忘記判斷相鄰兩個等式之間的奇偶條件了......也就是當我們得到一條 $| ( a1 - a2 ) \cdot p + ( b1 - b2 ) | + | ( c1 - c2 ) \cdot q + ( d1 - d2 ) | \leq | j - i |$ 這樣的條件時，奇偶性的條件其實就會等價於「左式和右式的奇偶性一樣」。我的解決方法是：因為當在枚舉 $p$ 時會再把所有條件跑過一遍，那麼只要在那時候多回傳「 $q$ 是否可以是奇數」和「 $q$ 是否可以是偶數」這兩件事就好了。另外一個小細節是，我們會需要解形如 $a \leq k \cdot x \leq b$ 的等式，其中 $a , b , k$ 給定，這要把 $a$ 和 $b$ 的正負分開處理才可以，因為「 / 」這個運算子是往 $0$ 的方向捨去的。
code :
2015年5月6日 星期三
[CF 536E] Tavas on the Path
作法：
樹鍊剖分的練習題。首先考慮如果題目是一維的情形，那麼可以想到離線處理，按照詢問的 $l$ 值由大到小處理，一開始整條鍊上的值都是 $0$ ，並且當處理到一個詢問時，把所有的邊長 $\geq l$ 的邊的位置的值都改成 $1$ ，然後對他做詢問。而這裡顯然可以用線段樹來處理這種東西，對於每個節點紀錄關於這個區間 $[ L , R ]$ 的$4$個值：區間最左邊有幾個連續的 $1$（更嚴謹來說，是滿足 $L$ ~ $L + i - 1$ 全部都是 $1$ 的最大 $i$ 值），還有右端點的類似的值，還有這個區間中除了最左和最右兩段 $1$ 以外的價值總和（價值就是題目給的 $f$ 值），還有一個 $bool$ 代表這個區間裡是否都是 $1$ 。舉例來說，如果區間內的 $01$ 序列為 $11100110011101$ ，那麼以上$4$個值分別為 $3 , 1 , f[ 2 ] + f[ 3 ] , 0$ 。這樣就可以支援修改和查詢操作了。而套到樹鍊剖分上就只差在還要把詢問的鍊拆解成好幾次的詢問而已。
code :
樹鍊剖分的練習題。首先考慮如果題目是一維的情形，那麼可以想到離線處理，按照詢問的 $l$ 值由大到小處理，一開始整條鍊上的值都是 $0$ ，並且當處理到一個詢問時，把所有的邊長 $\geq l$ 的邊的位置的值都改成 $1$ ，然後對他做詢問。而這裡顯然可以用線段樹來處理這種東西，對於每個節點紀錄關於這個區間 $[ L , R ]$ 的$4$個值：區間最左邊有幾個連續的 $1$（更嚴謹來說，是滿足 $L$ ~ $L + i - 1$ 全部都是 $1$ 的最大 $i$ 值），還有右端點的類似的值，還有這個區間中除了最左和最右兩段 $1$ 以外的價值總和（價值就是題目給的 $f$ 值），還有一個 $bool$ 代表這個區間裡是否都是 $1$ 。舉例來說，如果區間內的 $01$ 序列為 $11100110011101$ ，那麼以上$4$個值分別為 $3 , 1 , f[ 2 ] + f[ 3 ] , 0$ 。這樣就可以支援修改和查詢操作了。而套到樹鍊剖分上就只差在還要把詢問的鍊拆解成好幾次的詢問而已。
code :
2015年5月5日 星期二
[HOJ 151] 塗色問題
作法：
經典的樹鍊剖分，這是我第一次寫樹鍊剖分，實際上也沒有說很難寫，只要把該紀錄的東西都紀錄起來就可以了。我的寫法是對於每個點，首先要找出他的子節點中，其子樹大小最大的點是誰，這是樹鍊剖分所需要的，然後紀錄他所在的鍊的編號，還有他所在的鍊的深度最淺的點是誰，還有他在這條鍊上是從上面數下來第幾個。並且對每條鍊紀錄他的大小（開線段樹時要用），還有因為要求 LCA 而需要的每個點的深度值和 $2^k$ 級祖先節點。上面所說的東西可以用兩個 DFS 全部算出來。另外我這邊的線段樹是用指標實作的，用陣列版本的話會變成要開很多個 vector ，因為每條鍊的大小都不一樣，並且總共可能最多會有 $O( n )$ 條鍊，所以只好用 vector ，這似乎會讓 code 醜醜的就沒寫這種版本了。
code :
經典的樹鍊剖分，這是我第一次寫樹鍊剖分，實際上也沒有說很難寫，只要把該紀錄的東西都紀錄起來就可以了。我的寫法是對於每個點，首先要找出他的子節點中，其子樹大小最大的點是誰，這是樹鍊剖分所需要的，然後紀錄他所在的鍊的編號，還有他所在的鍊的深度最淺的點是誰，還有他在這條鍊上是從上面數下來第幾個。並且對每條鍊紀錄他的大小（開線段樹時要用），還有因為要求 LCA 而需要的每個點的深度值和 $2^k$ 級祖先節點。上面所說的東西可以用兩個 DFS 全部算出來。另外我這邊的線段樹是用指標實作的，用陣列版本的話會變成要開很多個 vector ，因為每條鍊的大小都不一樣，並且總共可能最多會有 $O( n )$ 條鍊，所以只好用 vector ，這似乎會讓 code 醜醜的就沒寫這種版本了。
code :
[CF 542F] Quest
作法：
這題我的作法是 greedy ，但DP也可以做，DP的作法可以參考官方詳解。
我們從花費時間少的問題看起，假設有個問題的花費時間為 $1$ ，那麼如果現在打算取他，這時候再拿一個花費時間為 $1$ 的放在這個問題的另一個分支會是最好的選擇，否則如果拿的問題是花費時間為 $t > 1$ 的問題，那麼這個時間 $1$ 的問題就失去優勢了，這時他就等價於一個花費時間為 $t$ 的問題了。並且我們知道當決定好要取時間 $1$ 的兩個問題時，一定是取價值最大的兩個，因此就得到了這樣的算法：按照花費時間由小到大看，如果當前這個花費時間 $t$ 有 $\geq 2$ 個問題，那就不斷把價值最大的兩個問題融合起來，變成一個花費時間為 $t+1$ 的問題，並且他的價值是兩個小問題的價值和。而如果只有一個問題，那就直接把他改成花費時間為 $t+1$ 的。這樣一直做下去直到所有東西都變成花費時間為 $T$ 的，取裡面的最大值就是答案了。比賽時我的理解方式其實是「把兩個問題融合起來變成一個新的問題」，因此是用 priority_queue 實作，後來想想其實把每個花費時間的問題都用一個 vector 裝起來去處理就可以了，那樣也蠻好寫的。
code :
這題我的作法是 greedy ，但DP也可以做，DP的作法可以參考官方詳解。
我們從花費時間少的問題看起，假設有個問題的花費時間為 $1$ ，那麼如果現在打算取他，這時候再拿一個花費時間為 $1$ 的放在這個問題的另一個分支會是最好的選擇，否則如果拿的問題是花費時間為 $t > 1$ 的問題，那麼這個時間 $1$ 的問題就失去優勢了，這時他就等價於一個花費時間為 $t$ 的問題了。並且我們知道當決定好要取時間 $1$ 的兩個問題時，一定是取價值最大的兩個，因此就得到了這樣的算法：按照花費時間由小到大看，如果當前這個花費時間 $t$ 有 $\geq 2$ 個問題，那就不斷把價值最大的兩個問題融合起來，變成一個花費時間為 $t+1$ 的問題，並且他的價值是兩個小問題的價值和。而如果只有一個問題，那就直接把他改成花費時間為 $t+1$ 的。這樣一直做下去直到所有東西都變成花費時間為 $T$ 的，取裡面的最大值就是答案了。比賽時我的理解方式其實是「把兩個問題融合起來變成一個新的問題」，因此是用 priority_queue 實作，後來想想其實把每個花費時間的問題都用一個 vector 裝起來去處理就可以了，那樣也蠻好寫的。
code :
[CF 542E] Playing on Graph
作法：
首先可以觀察到，如果圖中有三角形的話就是無解，因為不管怎麼樣這個三角形的三條邊都沒辦法消失。有了這個之後就可以進一步推到圖裡面沒有奇圈，因為當還存在一個奇圈時，如果圈上有兩個端點連了一條邊，那麼一定會分出一個比較小的奇圈，可以由數歸知道此時原圖無解，否則圈上的點兩兩不連邊，那麼我們遲早會選兩個圈上的點，把他們融合，這時候不難得到融合後一定會出現一個比較小的奇圈，也是由數歸得到此時無解，因此當原圖不是二部圖時就無解。
而當原圖為二部圖時顯然是有解的，因為由二部圖的定義，我們可以把節點群分為兩陀，使得同陀內的點兩兩不連邊，那麼這時只要把同一陀的點全部都融合起來就可以了，但當然他不會總是會是最佳的解，只是確定此時一定可以融合成一條鍊而已。再來則是當原圖不連通時，我們可以分別對每個連通塊求出他的答案再加起來，這就相當於把每個連通快都融合成一條鍊時，在把所有的鍊黏起來，不難知道這樣會是整張圖的最佳解，因此接下來只要考慮圖連通的情形，
假設現在已經把所有點都融合好形成一條練了，那麼每個新的圖中的節點都可以看成是由好幾個舊的圖中的點融合在一起得到的。例如 $A$ 和 $B$ 融合之後的新節點再去和 $C$ 融合，那麼所得到的節點就可以看成 $ABC$ 三點融合在一起的點，並且必須滿足這$3$個點兩兩之間沒有連邊。因此如果我們把新得到的圖的所有節點都「展開」回舊的圖的節點，就會變成長的像類似下面這張圖的東西
其中落在同一陀裡的點兩兩之間沒有連邊，他們在新的圖中會融合成一個點。而這張圖就類似我們在找單源最短路時，以某個點為源點所畫出來的層次圖（把所有點按照他和源點的距離分成不同的幾組），而事實上用任意一個點為源點畫出來的層次圖的確可以滿足這邊的條件，因為現在的圖是二部圖，所以可以保證這樣子分組不會讓同組中的任兩個點相鄰。因此就得到了這題的演算法：對於每個連通分量，對於裡面的每個點都做一次BFS，求出離他最遠點的距離，而在這些距離中的最大值就是這個連通分量的答案，再把所有連通分量的答案加起來即可。
code :
首先可以觀察到，如果圖中有三角形的話就是無解，因為不管怎麼樣這個三角形的三條邊都沒辦法消失。有了這個之後就可以進一步推到圖裡面沒有奇圈，因為當還存在一個奇圈時，如果圈上有兩個端點連了一條邊，那麼一定會分出一個比較小的奇圈，可以由數歸知道此時原圖無解，否則圈上的點兩兩不連邊，那麼我們遲早會選兩個圈上的點，把他們融合，這時候不難得到融合後一定會出現一個比較小的奇圈，也是由數歸得到此時無解，因此當原圖不是二部圖時就無解。
而當原圖為二部圖時顯然是有解的，因為由二部圖的定義，我們可以把節點群分為兩陀，使得同陀內的點兩兩不連邊，那麼這時只要把同一陀的點全部都融合起來就可以了，但當然他不會總是會是最佳的解，只是確定此時一定可以融合成一條鍊而已。再來則是當原圖不連通時，我們可以分別對每個連通塊求出他的答案再加起來，這就相當於把每個連通快都融合成一條鍊時，在把所有的鍊黏起來，不難知道這樣會是整張圖的最佳解，因此接下來只要考慮圖連通的情形，
假設現在已經把所有點都融合好形成一條練了，那麼每個新的圖中的節點都可以看成是由好幾個舊的圖中的點融合在一起得到的。例如 $A$ 和 $B$ 融合之後的新節點再去和 $C$ 融合，那麼所得到的節點就可以看成 $ABC$ 三點融合在一起的點，並且必須滿足這$3$個點兩兩之間沒有連邊。因此如果我們把新得到的圖的所有節點都「展開」回舊的圖的節點，就會變成長的像類似下面這張圖的東西
其中落在同一陀裡的點兩兩之間沒有連邊，他們在新的圖中會融合成一個點。而這張圖就類似我們在找單源最短路時，以某個點為源點所畫出來的層次圖（把所有點按照他和源點的距離分成不同的幾組），而事實上用任意一個點為源點畫出來的層次圖的確可以滿足這邊的條件，因為現在的圖是二部圖，所以可以保證這樣子分組不會讓同組中的任兩個點相鄰。因此就得到了這題的演算法：對於每個連通分量，對於裡面的每個點都做一次BFS，求出離他最遠點的距離，而在這些距離中的最大值就是這個連通分量的答案，再把所有連通分量的答案加起來即可。
code :
[CF 542D] Superhero's Job
作法：
假設某個數 n 的質因數分解為 $p_1^{a_1} \cdot ... \cdot p_k^{a_k}$ ，那麼首先不難得到那個函數的值其實就是 $( 1 + p_1^{a_1} ) \cdot ... \cdot ( 1 + p_k^{a_k} )$ ，只要把這條式子展開獲得的每一項就都是一個滿足條件的 $n$ 的因數。因此問題轉化為有幾種方法可以把 $A$ 表成上述的型式。我的方法是先遇處理出所有 $A$ 的因數裡面形如 $1 + p^x$ 的數（以下簡稱這種數是「好的」），找 $A$ 的因數就只要用單純的 $\sqrt{A}$ 的方法就可以了，至於找到一個因數時要如何判斷他是否是好的 ，我的作法是對於每個小於 $10^6$ 的質數 $p$ ，先處理好由他形成的好數有哪些（因為他們不會太多），這樣在判斷一個數是否為好數時，首先看他有沒有出現在前面遇處理好的好數裡，有的話就代表有，而沒有的話則還有一種可能，就是他是由 $> 10^6$ 的質數形成的好數，但此時這個質數平方就會超過 $10^{12}$ 了，因此他只有可能是質數$+1$，因此這時候只要判斷詢問的這個數減一是不是質數就可以了。對於所有找到的好數，用一個 map<int,vector<int> > 把他們裝起來，其中由同一個質數形成的好數放在同一個 vector 裡面（因此前面遇處理好數們的時候必須用 map ，多紀錄這個好數是由哪個質數構成的，查詢時直接回傳即可），於是此時問題就簡化為：現在有很多個 vector ，問從不同 vector 取出一些數讓他們乘起來等於 $A$ 的方法數有幾種。
這時再多觀察到一件事：如果我們想用一些數來乘出 $A$ ，那麼中間乘到一半的數們一定都會是 $A$ 的因數，所以這個問題就可以用DP處理了！記 $dp[ i ][ j ]$ 代表當只考慮第 $1$ ~ $i$ 個 vector 時，有幾種方法可以乘出 $j $，其中 $j$ 是 $A$ 的一個因數。邊界為 $dp[ 0 ] [ 1 ] = 1$ ，轉移算是顯然的，並且他可以輕鬆的壓成一維的 DP 。另外要注意的是，這邊的 dp 表格其實是一個 map ，因為在 $j$ 的部份會有很大的數。可以得到這個算法的複雜度為 $O(K^2 log K)$ ，其中 $K$ 是 $A$ 的因數數量，而在 $A \leq 10^{12}$ 時 $K$ 不會超過 $7000$ ，所以還不至於 TLE 。
另外我看到的最短的code是直接DFS，比我的作法簡單多了QQ，也很好理解，不過似乎不保證複雜度就是了，時間 1887ms / 2s 也是很驚險的秒數。
code :
假設某個數 n 的質因數分解為 $p_1^{a_1} \cdot ... \cdot p_k^{a_k}$ ，那麼首先不難得到那個函數的值其實就是 $( 1 + p_1^{a_1} ) \cdot ... \cdot ( 1 + p_k^{a_k} )$ ，只要把這條式子展開獲得的每一項就都是一個滿足條件的 $n$ 的因數。因此問題轉化為有幾種方法可以把 $A$ 表成上述的型式。我的方法是先遇處理出所有 $A$ 的因數裡面形如 $1 + p^x$ 的數（以下簡稱這種數是「好的」），找 $A$ 的因數就只要用單純的 $\sqrt{A}$ 的方法就可以了，至於找到一個因數時要如何判斷他是否是好的 ，我的作法是對於每個小於 $10^6$ 的質數 $p$ ，先處理好由他形成的好數有哪些（因為他們不會太多），這樣在判斷一個數是否為好數時，首先看他有沒有出現在前面遇處理好的好數裡，有的話就代表有，而沒有的話則還有一種可能，就是他是由 $> 10^6$ 的質數形成的好數，但此時這個質數平方就會超過 $10^{12}$ 了，因此他只有可能是質數$+1$，因此這時候只要判斷詢問的這個數減一是不是質數就可以了。對於所有找到的好數，用一個 map<int,vector<int> > 把他們裝起來，其中由同一個質數形成的好數放在同一個 vector 裡面（因此前面遇處理好數們的時候必須用 map ，多紀錄這個好數是由哪個質數構成的，查詢時直接回傳即可），於是此時問題就簡化為：現在有很多個 vector ，問從不同 vector 取出一些數讓他們乘起來等於 $A$ 的方法數有幾種。
這時再多觀察到一件事：如果我們想用一些數來乘出 $A$ ，那麼中間乘到一半的數們一定都會是 $A$ 的因數，所以這個問題就可以用DP處理了！記 $dp[ i ][ j ]$ 代表當只考慮第 $1$ ~ $i$ 個 vector 時，有幾種方法可以乘出 $j $，其中 $j$ 是 $A$ 的一個因數。邊界為 $dp[ 0 ] [ 1 ] = 1$ ，轉移算是顯然的，並且他可以輕鬆的壓成一維的 DP 。另外要注意的是，這邊的 dp 表格其實是一個 map ，因為在 $j$ 的部份會有很大的數。可以得到這個算法的複雜度為 $O(K^2 log K)$ ，其中 $K$ 是 $A$ 的因數數量，而在 $A \leq 10^{12}$ 時 $K$ 不會超過 $7000$ ，所以還不至於 TLE 。
另外我看到的最短的code是直接DFS，比我的作法簡單多了QQ，也很好理解，不過似乎不保證複雜度就是了，時間 1887ms / 2s 也是很驚險的秒數。
code :
[CF 542A] Place Your Ad Here
作法：
簡單重述一次問題為：數線上有一堆紅線和藍線，每條藍線有他的價值，並且當取一紅一藍時獲得的價值為藍線價值乘上兩條線段相交部份的長度，求最大價值還有是哪兩條。我們之後的策略會是：對於每條藍線都求出和他交集最長的紅線的交集部份有多長，然後拿他去更新答案。
對於所有的兩條線段相交的情形可以分成以下四種：紅線包含藍線，紅線只和藍線交於藍線的左段，紅線只和藍線交於藍線的右段，還有藍線包含紅線。而對於這幾種情況都可以用掃描線搭配一個資料結構的方法處理（在這裡是線段樹）。首先看第一和第二種情形，考慮把所有的紅線和藍線都按照左端點由小到大排序，當在計算某條特定藍線 $[ L , R ]$ 的答案時，對於所有滿足左端點 $\leq L$ 的紅線 $[ l , r ]$ ，把線段樹上 $l$ 到 $r$ 之間的值都和 $r$ 取 $max$ ，然後查詢時指需查詢此時 $L$ 的值，拿去和 $R$ 取 min 即可。而要注意到的是：首先要對所有數做離散化，才可以用線段樹（或是不離散化 + 線段樹動態開點應該也是可以），還有線段樹上還必須紀錄造成這個節點最大值的是哪條紅線，因為題目還要求輸出一組解。再來是第三種情形，這只要把所有的線段一起全部左右顛倒就可以了（意思是類似把所有的 $[ L , R ]$ 都改成 $[ -R , -L ]$ 然後求一次答案的概念），而我為了不要再重做一次離散化，就直接把所有的 $[ L , R ]$ 改成 $[ SZ - 1 - R , SZ - 1 - L ]$ 然後重新排序，其中 $SZ$ 為離散後的數字個數。但這樣之後在計算座標差時會有問題（區間長度當然是看離散化前的數值），而解決這個的方法就是當在計算區間長度時，發現此時是第二次求解，那麼就要把當前的 $id$ 值用 $SZ-1$ 扣掉。最後是第四種情形，這次處理的方法比較不一樣，不過主體還是掃描線。把所有紅線和藍線都照右端點排序，當處理到一條藍線 $[ L , R ]$ 時，對於所有滿足右端點 $\leq R$ 的紅線 $[ l , r ]$ ，把線段樹上 $0$ ~ $l$ 的值都和 $r - l$ 取 max （因為此時交集部份長度就等於紅線長，並且要注意到設的值必須是原線段的長度而不是離散化後的線段長度），那麼查詢時只要查詢 $L$ 位置的值就可以了。
code :
簡單重述一次問題為：數線上有一堆紅線和藍線，每條藍線有他的價值，並且當取一紅一藍時獲得的價值為藍線價值乘上兩條線段相交部份的長度，求最大價值還有是哪兩條。我們之後的策略會是：對於每條藍線都求出和他交集最長的紅線的交集部份有多長，然後拿他去更新答案。
對於所有的兩條線段相交的情形可以分成以下四種：紅線包含藍線，紅線只和藍線交於藍線的左段，紅線只和藍線交於藍線的右段，還有藍線包含紅線。而對於這幾種情況都可以用掃描線搭配一個資料結構的方法處理（在這裡是線段樹）。首先看第一和第二種情形，考慮把所有的紅線和藍線都按照左端點由小到大排序，當在計算某條特定藍線 $[ L , R ]$ 的答案時，對於所有滿足左端點 $\leq L$ 的紅線 $[ l , r ]$ ，把線段樹上 $l$ 到 $r$ 之間的值都和 $r$ 取 $max$ ，然後查詢時指需查詢此時 $L$ 的值，拿去和 $R$ 取 min 即可。而要注意到的是：首先要對所有數做離散化，才可以用線段樹（或是不離散化 + 線段樹動態開點應該也是可以），還有線段樹上還必須紀錄造成這個節點最大值的是哪條紅線，因為題目還要求輸出一組解。再來是第三種情形，這只要把所有的線段一起全部左右顛倒就可以了（意思是類似把所有的 $[ L , R ]$ 都改成 $[ -R , -L ]$ 然後求一次答案的概念），而我為了不要再重做一次離散化，就直接把所有的 $[ L , R ]$ 改成 $[ SZ - 1 - R , SZ - 1 - L ]$ 然後重新排序，其中 $SZ$ 為離散後的數字個數。但這樣之後在計算座標差時會有問題（區間長度當然是看離散化前的數值），而解決這個的方法就是當在計算區間長度時，發現此時是第二次求解，那麼就要把當前的 $id$ 值用 $SZ-1$ 扣掉。最後是第四種情形，這次處理的方法比較不一樣，不過主體還是掃描線。把所有紅線和藍線都照右端點排序，當處理到一條藍線 $[ L , R ]$ 時，對於所有滿足右端點 $\leq R$ 的紅線 $[ l , r ]$ ，把線段樹上 $0$ ~ $l$ 的值都和 $r - l$ 取 max （因為此時交集部份長度就等於紅線長，並且要注意到設的值必須是原線段的長度而不是離散化後的線段長度），那麼查詢時只要查詢 $L$ 位置的值就可以了。
code :
2015年5月4日 星期一
[CF 533D] Landmarks
作法：
首先把每個柱子的強度都乘以 $2$ （包括答案），這樣對於一根柱子來說，他會倒塌若且唯若他的強度小於左右兩跟柱子的距離，也就是他必須支撐從他到他左邊柱子的天花板，還有從他到他右邊柱子的天花板，這樣可以讓之後的處理跟理解比較方便。假設我們已經在某個地方放上一個柱子，使得最後沒有全部倒塌的話，假設現在留下來的柱子為原本柱子們的第 $a_1 , ... , a_k$ 根，且新加的柱子落在 $a_i$ 和 $a_{ i+1 }$ 之間，那麼這代表當我們單獨看 $a_1$ ~ $a_i$ 的時候， $a_1$ ~ $a_{ i-1 }$ 均不會倒塌，並且 $a_i$ 除了支撐 $a_{ i-1 }$ ~ $a_i$ 的天花板以外，至少還要有力氣支撐他右邊的天花板，而這對於 $a_{ i+1 } ~ a_k$ 來說也一樣。並且如果新加的柱子和 $a_i$ 的距離為 $x$ ，和 $a_{ i+1 }$ 的距離為 $y$ ，那麼必須要有 $a_i$ 除了支撐左邊以外，能多支撐的天花板長度 $\geq x$ ，還有 $a_{ i+1 }$ 除了支撐右邊以外，能多支撐的天花板長度 $\geq y$ ，兩式加起來可以得到 $a_i$ 可以多支撐的長度加上 $a_{ i+1 }$ 可以多支撐的長度 $\geq a_i$ 和 $a_{ i+1 }$ 的距離。因此這啟發了我們可以對於每根柱子，都計算他的「可多支撐右邊的強度」。更嚴謹的來說，對於每個 $i$ ，考慮所有的子序列 $b_1 , ... , b_r = i$ ，並且滿足如果只剩下 $b_1$ ~ $b_r$ 這些柱子時，他們都不會倒塌，那麼 $i$ 的「可多支撐右邊的強度」就是所有這樣的子序列的 $s[ b_r ] - ( pos[ b_r ] - pos[ b_{ r-1 } ] )$ 的最大值。其中 $s[ i ]$ 代表第 $i$ 根柱子的強度， $pos[ i ]$ 代表第 $i$ 根柱子的位置。
記上面所說的要算的東西為 $dp1[ i ]$ ，那麼首先可以想到一個 $O( n^2 )$ 的顯然的作法，就是在算 $i$ 的時候枚舉要放在他左邊的柱子是哪一根就可以了。而如果我們反過來看，假設現在已經算完 $dp1[ i ]$ 了，那麼對於所有位置小於等於 $pos[ i ] + dp1[ i ]$ 的柱子來說，都可以從 $i$ 轉移過去。並且當 $i$ 可以轉移到 $j$ 的時候，就代表 $dp1[ j ]$ 就必須和 $s[ j ] - pos[ j ] + pos[ i ]$ 取 max 。注意到這個東西只和 $pos[ i ]$ 有關，因此這樣就可以用線段樹來計算 $dp1$ 陣列的值了：每當算完 $dp1[ i ]$ 時，找出他最遠可以轉移到哪根柱子，假設為 $i2$ 好了，那麼就把 $i+1$ ~ $i2$ 的每個值都和 $pos[ i ]$ 取 max ，之後要計算 $dp1[ j ]$ 的時候，只要在線段樹上查詢這個點的值，再把他加上 $s[ j ] - pos[ j ]$ 就可以了。
因此用一樣的方法也可以算出每根柱子的「可多支撐左邊的強度」，把他記為 $dp2[ i ]$ 。這個值的定義和 $dp1$ 很類似，不過這次取的則是形如 $b_1 = i , b_2 , ... , b_r$ 的子序列（他和 $dp1$ 一樣都是第一段中提到的一個重要的值）。有了 $dp1$ 和 $dp2$ 之後就可以求解了，首先判斷是否不用加新的柱子也不會全部倒塌，而這只要存在一個 $i$ ，使得 $dp1[ i ] \geq pos[ n+1 ] - pos[ i ]$，就代表可以直接從第 $i$ 根柱子接到最後一根，此時答案是 $0$ 。否則我們要找的是：對於所有的 $i < j$ ，如果 $dp1[ i ] + dp2[ j ] \geq pos[ j ] - pos[ i ]$ ，並且 $dp1[ i ] > 0 , dp2[ j ] > 0$，那麼 $pos[ j ] - pos[ i ]$ 就會是一個可行的答案，只要把他放在 $pos[ i ]$ 和 $pos[ j ]$ 中間的適當位置就可以了。將上式移項得 $dp1[ i ] + pos[ i ] \geq pos[ j ] - dp2[ j ]$ ， 這啟發了我們可以從右到左枚舉 i ，並且對於可能的右端點 $j$ 們維護一個二元組的 set ： $( pos[ j ] - dp2[ j ] , j )$ ，因為當如果有另外一個 $j2$ 滿足 $pos[ j2 ] - dp2[ j2 ] \geq pos[ j ] - dp2[ j ]$ ，並且 $j2 \geq j$ ，那麼 $j2$ 的二元組就廢掉了，之後不可能成為任何左端點的答案，因此這個 set 裡維護的是第一個值遞增時第二個值遞減的二元組，並且在詢問 $i$ 的答案時只要用個 lower_bound 找 $pos[ j ] - dp2[ j ]$ 值最大且滿足上述條件的二元組就可以了。
另外官方解好像和我的作法一樣，但他把每個步驟都從 $O( nlogn )$ 優化成 $O( n )$ 了，不過我還沒仔細研究他是怎麼做的。
code :
首先把每個柱子的強度都乘以 $2$ （包括答案），這樣對於一根柱子來說，他會倒塌若且唯若他的強度小於左右兩跟柱子的距離，也就是他必須支撐從他到他左邊柱子的天花板，還有從他到他右邊柱子的天花板，這樣可以讓之後的處理跟理解比較方便。假設我們已經在某個地方放上一個柱子，使得最後沒有全部倒塌的話，假設現在留下來的柱子為原本柱子們的第 $a_1 , ... , a_k$ 根，且新加的柱子落在 $a_i$ 和 $a_{ i+1 }$ 之間，那麼這代表當我們單獨看 $a_1$ ~ $a_i$ 的時候， $a_1$ ~ $a_{ i-1 }$ 均不會倒塌，並且 $a_i$ 除了支撐 $a_{ i-1 }$ ~ $a_i$ 的天花板以外，至少還要有力氣支撐他右邊的天花板，而這對於 $a_{ i+1 } ~ a_k$ 來說也一樣。並且如果新加的柱子和 $a_i$ 的距離為 $x$ ，和 $a_{ i+1 }$ 的距離為 $y$ ，那麼必須要有 $a_i$ 除了支撐左邊以外，能多支撐的天花板長度 $\geq x$ ，還有 $a_{ i+1 }$ 除了支撐右邊以外，能多支撐的天花板長度 $\geq y$ ，兩式加起來可以得到 $a_i$ 可以多支撐的長度加上 $a_{ i+1 }$ 可以多支撐的長度 $\geq a_i$ 和 $a_{ i+1 }$ 的距離。因此這啟發了我們可以對於每根柱子，都計算他的「可多支撐右邊的強度」。更嚴謹的來說，對於每個 $i$ ，考慮所有的子序列 $b_1 , ... , b_r = i$ ，並且滿足如果只剩下 $b_1$ ~ $b_r$ 這些柱子時，他們都不會倒塌，那麼 $i$ 的「可多支撐右邊的強度」就是所有這樣的子序列的 $s[ b_r ] - ( pos[ b_r ] - pos[ b_{ r-1 } ] )$ 的最大值。其中 $s[ i ]$ 代表第 $i$ 根柱子的強度， $pos[ i ]$ 代表第 $i$ 根柱子的位置。
記上面所說的要算的東西為 $dp1[ i ]$ ，那麼首先可以想到一個 $O( n^2 )$ 的顯然的作法，就是在算 $i$ 的時候枚舉要放在他左邊的柱子是哪一根就可以了。而如果我們反過來看，假設現在已經算完 $dp1[ i ]$ 了，那麼對於所有位置小於等於 $pos[ i ] + dp1[ i ]$ 的柱子來說，都可以從 $i$ 轉移過去。並且當 $i$ 可以轉移到 $j$ 的時候，就代表 $dp1[ j ]$ 就必須和 $s[ j ] - pos[ j ] + pos[ i ]$ 取 max 。注意到這個東西只和 $pos[ i ]$ 有關，因此這樣就可以用線段樹來計算 $dp1$ 陣列的值了：每當算完 $dp1[ i ]$ 時，找出他最遠可以轉移到哪根柱子，假設為 $i2$ 好了，那麼就把 $i+1$ ~ $i2$ 的每個值都和 $pos[ i ]$ 取 max ，之後要計算 $dp1[ j ]$ 的時候，只要在線段樹上查詢這個點的值，再把他加上 $s[ j ] - pos[ j ]$ 就可以了。
因此用一樣的方法也可以算出每根柱子的「可多支撐左邊的強度」，把他記為 $dp2[ i ]$ 。這個值的定義和 $dp1$ 很類似，不過這次取的則是形如 $b_1 = i , b_2 , ... , b_r$ 的子序列（他和 $dp1$ 一樣都是第一段中提到的一個重要的值）。有了 $dp1$ 和 $dp2$ 之後就可以求解了，首先判斷是否不用加新的柱子也不會全部倒塌，而這只要存在一個 $i$ ，使得 $dp1[ i ] \geq pos[ n+1 ] - pos[ i ]$，就代表可以直接從第 $i$ 根柱子接到最後一根，此時答案是 $0$ 。否則我們要找的是：對於所有的 $i < j$ ，如果 $dp1[ i ] + dp2[ j ] \geq pos[ j ] - pos[ i ]$ ，並且 $dp1[ i ] > 0 , dp2[ j ] > 0$，那麼 $pos[ j ] - pos[ i ]$ 就會是一個可行的答案，只要把他放在 $pos[ i ]$ 和 $pos[ j ]$ 中間的適當位置就可以了。將上式移項得 $dp1[ i ] + pos[ i ] \geq pos[ j ] - dp2[ j ]$ ， 這啟發了我們可以從右到左枚舉 i ，並且對於可能的右端點 $j$ 們維護一個二元組的 set ： $( pos[ j ] - dp2[ j ] , j )$ ，因為當如果有另外一個 $j2$ 滿足 $pos[ j2 ] - dp2[ j2 ] \geq pos[ j ] - dp2[ j ]$ ，並且 $j2 \geq j$ ，那麼 $j2$ 的二元組就廢掉了，之後不可能成為任何左端點的答案，因此這個 set 裡維護的是第一個值遞增時第二個值遞減的二元組，並且在詢問 $i$ 的答案時只要用個 lower_bound 找 $pos[ j ] - dp2[ j ]$ 值最大且滿足上述條件的二元組就可以了。
另外官方解好像和我的作法一樣，但他把每個步驟都從 $O( nlogn )$ 優化成 $O( n )$ 了，不過我還沒仔細研究他是怎麼做的。
code :
[CF 538F] A Heap of Heaps
作法：
首先把數列換成 0-base 的，那麼可以得到節點 $x$ 在構成 $y$ 元樹時的祖先就是 $\left \lfloor \frac{x-1}{y} \right \rfloor$ ，而由這件事就可以得到：當 $y$ 從 $1$ 慢慢變大到 $n-1$ 時， $\left \lfloor \frac{x-1}{y} \right \rfloor$ 的值只會改變 $O( \sqrt{ x } )$ 次，所以就可以把所有 $\left \lfloor \frac{x-1}{y} \right \rfloor$ 值一樣的 $y$ 們和在一起算，這樣就可以在 $O( n \sqrt{ n } )$ 的時間內算完答案了。一樣的技巧也出現在 POI 21 Stage 3 Solar Panels 和 POI 14 Stage 1 Queries ( HOJ 22 駭客 ) 中，詳解分別可以參考這裡和這裡。
code :
首先把數列換成 0-base 的，那麼可以得到節點 $x$ 在構成 $y$ 元樹時的祖先就是 $\left \lfloor \frac{x-1}{y} \right \rfloor$ ，而由這件事就可以得到：當 $y$ 從 $1$ 慢慢變大到 $n-1$ 時， $\left \lfloor \frac{x-1}{y} \right \rfloor$ 的值只會改變 $O( \sqrt{ x } )$ 次，所以就可以把所有 $\left \lfloor \frac{x-1}{y} \right \rfloor$ 值一樣的 $y$ 們和在一起算，這樣就可以在 $O( n \sqrt{ n } )$ 的時間內算完答案了。一樣的技巧也出現在 POI 21 Stage 3 Solar Panels 和 POI 14 Stage 1 Queries ( HOJ 22 駭客 ) 中，詳解分別可以參考這裡和這裡。
code :
2015年5月3日 星期日
[CF 538E] Demiurges Play Again
作法：
把題目要求的兩個數值分開計算，兩個數的算法類似，所以這裡只敘述「目的是要讓最終結果越大越好」的那個人的作法。對每個節點 $x$ 紀錄兩個 $dp$ 值，一個代表「若 $x$ 形成的子樹的子節點編號為 $1$ ~ $k$ ，且此時輪到先手，那麼在雙方採取最佳策略後所可以停留的最大值」，令一個則是輪到後手時的最終停留數字的最大值（假設 $dp[ x ][ 0 ]$ 代表前者，$dp[ x ][ 1 ]$ 代表後者）。首先計算 $dp[ x ][ 0 ]$ ，當 x 是葉子的時候顯然是 $1$ 。當 x 不是葉子的時候，假設他的子節點為 $T_1$ ~ $T_k$ ，並且記 $T_i$ 子樹的葉子數為 $S_i$ ，還有記 $d_i = dp[ T_i ][ 1 ]$ （因為走下去之後是輪到後手），那麼首先要先釐清其實 $d_i$ 代表的意義為：如果先手此時決定走向 $T_i$ ，那麼最後就一定會停留在 $T_i$ 的所有葉子中數值第 $d_i$ 小的節點上。因為我們在DP時是假設這棵子樹的葉子是從 $1$ 開始往上編號的，但事實上如果不是的話，也不影響雙方的最佳策略，因為和兩人的決策有關的只有「這個數是否比那個數大」，而不是每個數真正的數值。現在我們有 $1$ ~ $( S_1 + ... + S_k )$ 這些編號，且目的是要找出一個好的編號方法，讓先手做完決策之後最後到的數值最大。而由前面的結論可以知道，如果我們把 $a_1$ ~ $a_{S_i}$ 這些數分到子樹 $T_i$ 裡面的話（其中 $a_i < a_{ i+1 }$），那麼當先手決定走到 $T_i$ 時最終就會停留在 $a_{d_i}$ ，也就是不管在這個子樹裡放哪些數，都會恰好有 $S_i - d_i$ 個比終點還大但沒辦法走到的點，因此為了不讓那些「被浪費掉的大數值太多」，此時的最好配置方法就是：找出所有子樹中 $S_i - d_i$ 最小的子樹，並且把 $1$ ~ $( S_1 + ... + S_k )$ 中最大的 $S_i$ 個數都分配到這個子樹裡，這樣先手就會決定往這個子樹走，最後就會停留在標號 $( S_1 + ... + S_k ) - ( S_i - d_i )$ 的節點。
至於 $dp[ x ][ 1 ]$ 的算法則不太一樣了，因為後手的目的是要讓走到的數越小越好，因此他會去找每個子樹 $T_i$ 所標的所有數值中，第 $d_i$ 小的數最小會是多少，因此我們要找一個好的配置方法，使得後手不管怎麼樣都會選到一個蠻大的數。此時最好的配置方法為：記所有子樹的 $S_i - d_i + 1$ 的總和為 $S$ ，那麼就把 $1$ ~ $( S_1 + ... + S_k )$ 中最大的 $S$ 個數分配到每個子樹的「第 $d_i$ 小到第 $S_i$ 小的數」裡，這樣後手就會選擇走到 $( S_1 + ... + S_k ) - S + 1$ 所在的子樹了，因為這是所有子樹中，第 $d_i$ 小的數的最小值。
code :
把題目要求的兩個數值分開計算，兩個數的算法類似，所以這裡只敘述「目的是要讓最終結果越大越好」的那個人的作法。對每個節點 $x$ 紀錄兩個 $dp$ 值，一個代表「若 $x$ 形成的子樹的子節點編號為 $1$ ~ $k$ ，且此時輪到先手，那麼在雙方採取最佳策略後所可以停留的最大值」，令一個則是輪到後手時的最終停留數字的最大值（假設 $dp[ x ][ 0 ]$ 代表前者，$dp[ x ][ 1 ]$ 代表後者）。首先計算 $dp[ x ][ 0 ]$ ，當 x 是葉子的時候顯然是 $1$ 。當 x 不是葉子的時候，假設他的子節點為 $T_1$ ~ $T_k$ ，並且記 $T_i$ 子樹的葉子數為 $S_i$ ，還有記 $d_i = dp[ T_i ][ 1 ]$ （因為走下去之後是輪到後手），那麼首先要先釐清其實 $d_i$ 代表的意義為：如果先手此時決定走向 $T_i$ ，那麼最後就一定會停留在 $T_i$ 的所有葉子中數值第 $d_i$ 小的節點上。因為我們在DP時是假設這棵子樹的葉子是從 $1$ 開始往上編號的，但事實上如果不是的話，也不影響雙方的最佳策略，因為和兩人的決策有關的只有「這個數是否比那個數大」，而不是每個數真正的數值。現在我們有 $1$ ~ $( S_1 + ... + S_k )$ 這些編號，且目的是要找出一個好的編號方法，讓先手做完決策之後最後到的數值最大。而由前面的結論可以知道，如果我們把 $a_1$ ~ $a_{S_i}$ 這些數分到子樹 $T_i$ 裡面的話（其中 $a_i < a_{ i+1 }$），那麼當先手決定走到 $T_i$ 時最終就會停留在 $a_{d_i}$ ，也就是不管在這個子樹裡放哪些數，都會恰好有 $S_i - d_i$ 個比終點還大但沒辦法走到的點，因此為了不讓那些「被浪費掉的大數值太多」，此時的最好配置方法就是：找出所有子樹中 $S_i - d_i$ 最小的子樹，並且把 $1$ ~ $( S_1 + ... + S_k )$ 中最大的 $S_i$ 個數都分配到這個子樹裡，這樣先手就會決定往這個子樹走，最後就會停留在標號 $( S_1 + ... + S_k ) - ( S_i - d_i )$ 的節點。
至於 $dp[ x ][ 1 ]$ 的算法則不太一樣了，因為後手的目的是要讓走到的數越小越好，因此他會去找每個子樹 $T_i$ 所標的所有數值中，第 $d_i$ 小的數最小會是多少，因此我們要找一個好的配置方法，使得後手不管怎麼樣都會選到一個蠻大的數。此時最好的配置方法為：記所有子樹的 $S_i - d_i + 1$ 的總和為 $S$ ，那麼就把 $1$ ~ $( S_1 + ... + S_k )$ 中最大的 $S$ 個數分配到每個子樹的「第 $d_i$ 小到第 $S_i$ 小的數」裡，這樣後手就會選擇走到 $( S_1 + ... + S_k ) - S + 1$ 所在的子樹了，因為這是所有子樹中，第 $d_i$ 小的數的最小值。
code :
[CF 538D] Weird Chess
作法：
考慮每個被佔領的格子，那麼他至少會對應到一個有棋子的格子，使得這個棋子佔領了他。因此我們可以對每個被佔領的格子，去枚舉是哪個棋子佔領了他。假設當前的被佔領的格子為 ( x0 , y0 )，當枚舉到某一個棋子 ( x1 , y1 ) 的時候，只要檢查向量 ( x0-x1 , y0-y1 ) 可不可行就可以了，如果可行就把他加到答案裡，而如果對於所有的棋子，那個向量都是不可行的，就代表這個盤面無解。
code :
考慮每個被佔領的格子，那麼他至少會對應到一個有棋子的格子，使得這個棋子佔領了他。因此我們可以對每個被佔領的格子，去枚舉是哪個棋子佔領了他。假設當前的被佔領的格子為 ( x0 , y0 )，當枚舉到某一個棋子 ( x1 , y1 ) 的時候，只要檢查向量 ( x0-x1 , y0-y1 ) 可不可行就可以了，如果可行就把他加到答案裡，而如果對於所有的棋子，那個向量都是不可行的，就代表這個盤面無解。
code :
[CF 512D] Fox And Travelling
作法：
這題簡單來說就是，每次操作可以把圖中一個度 <= 1 的點拔掉，問拔掉 k 個點有幾種順序，對於每個 k 都要輸出答案。首先考慮我們最多能拔幾個點，也就是先不斷的從圖中拔去度 <= 1 的點(類似拓僕排序的過程)，那麼最後剩下來的東西就是不管怎麼樣都沒辦法被拔掉的點們（我記得這東西叫作一個圖的核( core ) ，但網路上查到的都是另一個東西，可能是我記錯了）。因此整張圖就被分成了核和一堆樹了，其中有些樹是黏在核上的，有些樹是沒有黏在核上的。因此我們可以先對每棵樹分別求出「在這棵樹中拔掉 k 個點有幾種方法」的陣列，最後再把他們合併起來就好了。
但在處理單棵樹時，上面提到的那兩種樹的處理方法會不一樣，因為黏在核上的樹的根節點（也就是和核有連邊的那個點）一定要是最後被拔掉的，而沒有黏在核上的則是不必要，也就是我們要處理有根樹和無根樹的問題。先看有根樹的情形，對每個點 x 來說， 算出 dp[ x ][ k ] ( k = 0 ~ x 子樹的 size )，代表在 x 的子樹中拔掉 k 個點有幾種拔法。當 x 是葉子時他們的值是顯然的，而當 x 不是葉子時，假設他的子樹們為 T_1 ~ T_r ，那麼現在等於是要把這 r 個 dp 表格合併成一個 dp[ x ] 。假設我們現在要算 dp[ x ][ k ]，那麼總不能去枚舉所有的 b_1 ~ b_r 使得 b_1 + ... + b_r = k 吧！也就是如果要在 x 的子樹中拔 k 個點，那麼去枚舉每個子樹分別要拔幾個點。這樣複雜度顯然會爛掉，但如果只有兩個子樹，那麼事情就簡單多了，枚舉第一個子樹要砍的點的個數 j ，還有第二個子樹要砍的點的個數 k ，那麼 dp[ x ][ j+k ] 的值就要加上 C( j+k , j ) * dp[ T_1 ][ j ] * dp[ T_2 ][ k ]，其中要乘以 C( j+k , j ) 是因為 T_1 和 T_2 中的點可以輪流拔。因此這啟發了我們可以一棵一棵合併子樹，也就是先合併 T_1 , T_2 ，再把合併後的結果拿去跟 T_3 合併，以此類推。這樣就等於是在合併完 T_1 ~ T_i 時，表格裡存的東西是「在這 i 棵子樹中拔掉 k 個點的方法數」，因此把所有子樹都合併完之後就是我們需要的 dp[ x ] ，不過還必須記得要加上 dp[ x ][ sz ] = dp[ x ][ sz-1 ]，其中 sz 為 x 的子樹的大小，因為那 r 棵子樹的大小加起來剛好會是 sz-1 ，而 sz 的值也是需要的，但因為根永遠是最晚被拔的點，所以他的值就會等於 dp[ x ][ sz-1 ]。這樣看起來在計算 dp[ x ] 的時候複雜度會噴到 O( n^2 )，一次 DP 一棵樹的複雜度是 O(n^3) ，但實際上可以用和 TIOJ 1243 的解一樣的手法把複雜度壓成 O( n^2 )，這裡就不再詳細敘述。
處理完有根樹後再來是無根樹，而無根樹有個很重要的性質，就是如果我們直接把每個點都當成根算一次答案，把他們全部加起來，那麼對於任意一個在樹中拔掉 k 個點的拔法來講，他恰好會被算到 max( n-k , 1 ) 次！( 其中 n 是這棵樹的大小 )，也就是只要再把得到的答案分別乘上 n-k 的模逆元就可以了。最後在把所有有根樹和無根樹的答案合併起來的時候，也是用和在DP時同樣的方法就可以處理了，這樣總複雜度會是 O( n^3 )，不過事實上 O( n^4 )也可以過，也就是在 DP 的部份可以允許一次是 O( n^3 ) 的，畢竟 codeforces 主機跑超快XDD。
code :
這題簡單來說就是，每次操作可以把圖中一個度 <= 1 的點拔掉，問拔掉 k 個點有幾種順序，對於每個 k 都要輸出答案。首先考慮我們最多能拔幾個點，也就是先不斷的從圖中拔去度 <= 1 的點(類似拓僕排序的過程)，那麼最後剩下來的東西就是不管怎麼樣都沒辦法被拔掉的點們（我記得這東西叫作一個圖的核( core ) ，但網路上查到的都是另一個東西，可能是我記錯了）。因此整張圖就被分成了核和一堆樹了，其中有些樹是黏在核上的，有些樹是沒有黏在核上的。因此我們可以先對每棵樹分別求出「在這棵樹中拔掉 k 個點有幾種方法」的陣列，最後再把他們合併起來就好了。
但在處理單棵樹時，上面提到的那兩種樹的處理方法會不一樣，因為黏在核上的樹的根節點（也就是和核有連邊的那個點）一定要是最後被拔掉的，而沒有黏在核上的則是不必要，也就是我們要處理有根樹和無根樹的問題。先看有根樹的情形，對每個點 x 來說， 算出 dp[ x ][ k ] ( k = 0 ~ x 子樹的 size )，代表在 x 的子樹中拔掉 k 個點有幾種拔法。當 x 是葉子時他們的值是顯然的，而當 x 不是葉子時，假設他的子樹們為 T_1 ~ T_r ，那麼現在等於是要把這 r 個 dp 表格合併成一個 dp[ x ] 。假設我們現在要算 dp[ x ][ k ]，那麼總不能去枚舉所有的 b_1 ~ b_r 使得 b_1 + ... + b_r = k 吧！也就是如果要在 x 的子樹中拔 k 個點，那麼去枚舉每個子樹分別要拔幾個點。這樣複雜度顯然會爛掉，但如果只有兩個子樹，那麼事情就簡單多了，枚舉第一個子樹要砍的點的個數 j ，還有第二個子樹要砍的點的個數 k ，那麼 dp[ x ][ j+k ] 的值就要加上 C( j+k , j ) * dp[ T_1 ][ j ] * dp[ T_2 ][ k ]，其中要乘以 C( j+k , j ) 是因為 T_1 和 T_2 中的點可以輪流拔。因此這啟發了我們可以一棵一棵合併子樹，也就是先合併 T_1 , T_2 ，再把合併後的結果拿去跟 T_3 合併，以此類推。這樣就等於是在合併完 T_1 ~ T_i 時，表格裡存的東西是「在這 i 棵子樹中拔掉 k 個點的方法數」，因此把所有子樹都合併完之後就是我們需要的 dp[ x ] ，不過還必須記得要加上 dp[ x ][ sz ] = dp[ x ][ sz-1 ]，其中 sz 為 x 的子樹的大小，因為那 r 棵子樹的大小加起來剛好會是 sz-1 ，而 sz 的值也是需要的，但因為根永遠是最晚被拔的點，所以他的值就會等於 dp[ x ][ sz-1 ]。這樣看起來在計算 dp[ x ] 的時候複雜度會噴到 O( n^2 )，一次 DP 一棵樹的複雜度是 O(n^3) ，但實際上可以用和 TIOJ 1243 的解一樣的手法把複雜度壓成 O( n^2 )，這裡就不再詳細敘述。
處理完有根樹後再來是無根樹，而無根樹有個很重要的性質，就是如果我們直接把每個點都當成根算一次答案，把他們全部加起來，那麼對於任意一個在樹中拔掉 k 個點的拔法來講，他恰好會被算到 max( n-k , 1 ) 次！( 其中 n 是這棵樹的大小 )，也就是只要再把得到的答案分別乘上 n-k 的模逆元就可以了。最後在把所有有根樹和無根樹的答案合併起來的時候，也是用和在DP時同樣的方法就可以處理了，這樣總複雜度會是 O( n^3 )，不過事實上 O( n^4 )也可以過，也就是在 DP 的部份可以允許一次是 O( n^3 ) 的，畢竟 codeforces 主機跑超快XDD。
code :
[CF 514E] Darth Vader and Tree
作法：
設 dp[ x ] 代表距離根 <= x 的節點數量，那麼轉移就是顯然的了。設 a_1 ~ a_n 中有 d_i 個 i ( i = 1 ~ 100 ) ，那麼 dp[ x ] = sigma( d[ i ] * dp[ x - i ] ) + 1，邊界為 dp[ 0 ] = 1，而這個遞迴式顯然可以用矩陣快速冪來加速，因此只要先算出 dp[ 0 ] ~ dp[ 100 ] ，更大的 dp 值就可以用矩陣快速冪算了。
code :
設 dp[ x ] 代表距離根 <= x 的節點數量，那麼轉移就是顯然的了。設 a_1 ~ a_n 中有 d_i 個 i ( i = 1 ~ 100 ) ，那麼 dp[ x ] = sigma( d[ i ] * dp[ x - i ] ) + 1，邊界為 dp[ 0 ] = 1，而這個遞迴式顯然可以用矩陣快速冪來加速，因此只要先算出 dp[ 0 ] ~ dp[ 100 ] ，更大的 dp 值就可以用矩陣快速冪算了。
code :
2015年5月1日 星期五
[CF 516D] Drazil and Morning Exercise
作法：
圍繞這題的東西是「一個點到離他最遠的葉子的距離」，那麼我們首先來看這個東西有什麼性質。假設離某個點 A 最遠的葉節點為 P ，且 A 走到 P 的路上經過的第一個點為 B ，那麼可以推到對於和 A 相鄰的除了 B 以外的點們來說，離他們最遠的葉子都是 P ，證明不難證。而這也就代表了如果以 A 為樹的根的話，那麼會得到 B 不在的所有子樹裡的點，他們的離最遠的葉節點都會是 P 了。但在處理這個問題之前，我們還是要先知道要怎麼求出每個點的離他最遠的葉子距離，而實際上不難證明：如果 A1 A2 為這棵樹的直徑的兩端點 （直徑就是樹上離最遠的兩點），那麼對於每個點，他到 A1 的距離和他到 A2 的距離之一就會是所求的東西。
以下記一個點 x 到離他最遠的葉節點的距離為 val[ x ] ，考慮 val 值最小的點 X ，那麼就可以得到一個重要的性質：把這棵樹以 X 為根建成有根樹，那麼對於每一個點 Y ， Y 的父親的 val 值 < Y 的 val 值。這件事情的證明只要用前面提到的 val 的性質，加上 X 是 val 最小的點就可以簡單的證明了。
有了這個重要的性質之後，這就代表了我們可以枚舉所求點集中深度最淺的那個點，記他為 P 好了，那麼當 P 確定之後，就代表整個點集的最小值確定了，那麼這時候所有「 是 P 的子孫且其 val 值 <= val[ P ] + L 」的點就會是一個滿足題目條件的集合，用這個集合的大小去更新答案。而這就代表我們必須對每個節點都維護一個 multiset ，裡面放的是這個節點和他的子孫的所有 val 值，並且在算 P 的答案的時候必須把所有 val 值太大的從 multiset 裡面移除掉。然後我們還需要合併兩個 multiset ，於是就會馬上想到啟發式合併（注意到當在計算 P 的答案時，如果把某個 val 值移除掉了，那麼也代表之後在算 P 的祖先的答案的時候這個 val 值也是沒有用的，因為 P 的祖先的 val 值比 P 的還要小，因此這個合併不會漏掉任何可能性）。但啟發式合併的複雜度是 O(n * log^2 n) ，我自己寫完傳上去就 TLE 了，把 multiset 改成 map 一樣 TLE ，畢竟會有 50 筆詢問，應該就是用來卡掉 O(n * log^2 n) 解用的。
仔細想想其實可以把這個解改進到 O(nlogn) ，因為事實上對於一個點 Q 的 val 值，我們可以二分搜出他會在處理到哪個點的時候被移除掉！也就是如果 R 是深度最淺的點，滿足 val[ R ] < val[ Q ] - L ，那麼 val[ Q ] 就會在處理 val[ R ] 的時候被移除掉（其實應該不太算二分搜，我在找 R 的作法是類似 LCA 的倍增法，紀錄 2^k 級祖先然後一直往上跳這樣）。因此我們可以換個角度作，既然都知道 Q 會在什麼時候被移除掉了，那這就代表從 Q 一路沿著他的父親走，走到 R 之前的這些點們都會收到 Q 的貢獻。那麼這樣就可以轉換為經典問題了！也就是現在問題變成：對於每個點 Q ，找出他能夠貢獻的點們形成的路徑之後，把這條路徑上的每個點的權值都加上 1 ，最後詢問所有點中的點權最大值為多少。這樣就可以透過樹壓平轉換成簡單的一維問題了！
code :
圍繞這題的東西是「一個點到離他最遠的葉子的距離」，那麼我們首先來看這個東西有什麼性質。假設離某個點 A 最遠的葉節點為 P ，且 A 走到 P 的路上經過的第一個點為 B ，那麼可以推到對於和 A 相鄰的除了 B 以外的點們來說，離他們最遠的葉子都是 P ，證明不難證。而這也就代表了如果以 A 為樹的根的話，那麼會得到 B 不在的所有子樹裡的點，他們的離最遠的葉節點都會是 P 了。但在處理這個問題之前，我們還是要先知道要怎麼求出每個點的離他最遠的葉子距離，而實際上不難證明：如果 A1 A2 為這棵樹的直徑的兩端點 （直徑就是樹上離最遠的兩點），那麼對於每個點，他到 A1 的距離和他到 A2 的距離之一就會是所求的東西。
以下記一個點 x 到離他最遠的葉節點的距離為 val[ x ] ，考慮 val 值最小的點 X ，那麼就可以得到一個重要的性質：把這棵樹以 X 為根建成有根樹，那麼對於每一個點 Y ， Y 的父親的 val 值 < Y 的 val 值。這件事情的證明只要用前面提到的 val 的性質，加上 X 是 val 最小的點就可以簡單的證明了。
有了這個重要的性質之後，這就代表了我們可以枚舉所求點集中深度最淺的那個點，記他為 P 好了，那麼當 P 確定之後，就代表整個點集的最小值確定了，那麼這時候所有「 是 P 的子孫且其 val 值 <= val[ P ] + L 」的點就會是一個滿足題目條件的集合，用這個集合的大小去更新答案。而這就代表我們必須對每個節點都維護一個 multiset ，裡面放的是這個節點和他的子孫的所有 val 值，並且在算 P 的答案的時候必須把所有 val 值太大的從 multiset 裡面移除掉。然後我們還需要合併兩個 multiset ，於是就會馬上想到啟發式合併（注意到當在計算 P 的答案時，如果把某個 val 值移除掉了，那麼也代表之後在算 P 的祖先的答案的時候這個 val 值也是沒有用的，因為 P 的祖先的 val 值比 P 的還要小，因此這個合併不會漏掉任何可能性）。但啟發式合併的複雜度是 O(n * log^2 n) ，我自己寫完傳上去就 TLE 了，把 multiset 改成 map 一樣 TLE ，畢竟會有 50 筆詢問，應該就是用來卡掉 O(n * log^2 n) 解用的。
仔細想想其實可以把這個解改進到 O(nlogn) ，因為事實上對於一個點 Q 的 val 值，我們可以二分搜出他會在處理到哪個點的時候被移除掉！也就是如果 R 是深度最淺的點，滿足 val[ R ] < val[ Q ] - L ，那麼 val[ Q ] 就會在處理 val[ R ] 的時候被移除掉（其實應該不太算二分搜，我在找 R 的作法是類似 LCA 的倍增法，紀錄 2^k 級祖先然後一直往上跳這樣）。因此我們可以換個角度作，既然都知道 Q 會在什麼時候被移除掉了，那這就代表從 Q 一路沿著他的父親走，走到 R 之前的這些點們都會收到 Q 的貢獻。那麼這樣就可以轉換為經典問題了！也就是現在問題變成：對於每個點 Q ，找出他能夠貢獻的點們形成的路徑之後，把這條路徑上的每個點的權值都加上 1 ，最後詢問所有點中的點權最大值為多少。這樣就可以透過樹壓平轉換成簡單的一維問題了！
code :
訂閱：
文章 (Atom)