作法：
首先當$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 :
2015年6月10日 星期三
[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 :
通常這種需要考慮區間最大值的題目，可以先令整個數列的最大值的位置為$x$，那麼所有包含了$x$的區間的最大值都會是$x$，這樣問題就變成要如何找有幾個包含$x$的區間，滿足他裡面的總和模$k$是給定的一個數。處理完這個之後就可以拆成$x$左邊和$x$右邊遞迴下去解了。考慮樸素的作法，就是直接枚舉包含了$x$的區間，這樣複雜度會高達$O(n^2)$，不過仔細想想可以發現，假設現在固定了所求區間的右端點，我們想要知道有幾個左端點可以讓這個區間滿足條件，而把一個區間的數的總和改寫成前綴和相減後就可以得到，這個問題就等價於「在前綴和陣列的某一個區間中有幾個數模$k$是某個特定的數」。這可以透過建立模$k$的餘數的所有出現的位置加上二分搜得到答案。於是現在處理上述問題的複雜度變成了其中一邊的長度再乘上$logn$，不過最差狀況下這樣還是會退化到$O(n^2logn)$，而事實上只要每次都取短的那邊去枚舉就好了，這樣複雜度就會是好的。因為當一個點被枚舉到一次時，他所在的區間就至少縮短了兩倍，因此每個點至多被枚舉到$logn$次，所以總複雜度就會是$O(nlog^2n)$。
code :
2015年6月8日 星期一
[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 :
這題只要觀察到：當$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 :
記總共有$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 :
這題簡單來說就是，給定$n$個字串，還有一個目標字串$S$，要求在這$n$個字串裡選出幾個，使得把他們逐位加起來之後每位都和$S$不一樣。首先當$S$裡沒有$0$的時候顯然什麼都不取就可以了，而如果有一個位子$x$是$0$的話，因為題目保證第$i$個字串的第$i$項會是$1$，那麼就考慮直接取第$x$個字串看看，這樣可以發現：不管之後如何選，$x$那個位子的值只會增不會減，也就是之後可以完全忽略他了。這樣就得到了一個非常簡潔的算法：當還有位子的值和$S$的那個位子的值一樣時，就取對應的那個字串，一直作到滿足目標為止就可以了。
code :
2015年6月7日 星期日
[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 :
這題我是看了官方解的大概才會作的，這裡紀錄一下詳細的作法。
首先在讀入問題時，就可以把「按一次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 :
這題我的作法跟官方解幾乎一樣，但最後輸出答案的時候可能會有問題。因為題目要問的是「最後一塊的數字大小加上切的塊數」的最小值，所以可能可以想到最後一步就是枚舉最後一段的開頭是誰，那麼從$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 :
這題就是個構造題，看了這份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 :
2015年6月6日 星期六
[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 :
這題我的構造跟官方解的一樣，這裡就寫一下我是怎麼想到的。
因為要有橋，所以大概可以想到把橋的兩邊分開構。因為每個點的度都要是$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 :
2015年6月5日 星期五
[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 :
把整個過程反過來，變成原本有很多格子是被佔的，當一格一格移除時詢問此時的答案是多少，那麼顯然答案會是遞增的。假設當前答案為$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 :
首先把每個箱子的進入時間和出去時間畫在數線上，轉換成一條線段，那麼可以到如果有兩個箱子都有出現在台子上，那麼要嘛一個箱子的線段完全包含另一個的，要嘛兩個箱子的線段不相交（端點可以碰到），或是說他會形成一個類似樹形結構的東西，所以大概可以想的到是某種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 :
2015年6月3日 星期三
[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 :
這題我的作法根官方解只有後半部不一樣，就是在算答案的那部份。前面幾步一樣就是當我們要處理連續的好幾個詢問時，把整棵樹重建（因為可能有一些點被拔到其他地方了），先把那些重要的點找出來，之後叫他們黑點，其餘的則為白點。並且把黑點構成的樹建出來，稱他為新樹，原本題目給的則為原樹。我們要維護的值有兩個東西，就如官方解裡寫的$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 :
2015年6月2日 星期二
[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 :
令$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 :
首先考慮一定會對的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 :
因為題目要問的東西就是$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 :
訂閱：
文章 (Atom)