作法：
我們先觀察：對於一個排列，要怎麼判斷他是否可以在有限的交換次數內換回來。我們知道一個排列可以拆成很多圈，因此只要把這些圈分開研究就可以了。首先我們可以證明：對於每個圈，他能夠換完並且滿足限制的充要條件為：圈上的只能換一次的人數$\leq 2$。從右推到左不難，只要構造出一種換法就可以了。至於從左推到右，首先我們可以數歸出：對於一個大小為$k$的圈，至少要換$k-1$次才能把所有數歸位。而當作一次交換動作時，相應的兩個人的限制值都會減$1$，也就推得了所有人的限制值總和必須$\geq 2k-2$，所以至多有兩個人只能換$1$次。
另外再注意到，其實重要的只有有多少人能換一次，和有多少人能換兩次而已。因為我們可以任意交換兩人的 index 和限制值而不影響答案。因此現在問題變成：給定$x,y$（代表輸入中有$x$個$1$和$y$個$2$），找出滿足以下條件的$1,...,x+y$的排列個數：排列中的每個圈至多有兩個$1,..,x$之中的數。而這可以先想到一個DP的作法，也就是令$dp[x][y]$為所求的答案，那麼有邊界$dp[x][y]=(x+y)!$當$x\leq 2$。再來看要怎麼求$dp[x][y]$，考慮$x$這個數所在的圈，分成兩種可能：這個圈有$1$個或$2$個$1,...,x$之中的數。枚舉這個圈中用到了幾個$x+1,...,x+y$之間的數就可以得到轉移式：
$\displaystyle dp[x][y]=\sum_{i=0}^{y}dp[x-1][y-i]\frac{y!}{(y-i)!}+$$\displaystyle (x-1)\sum_{i=0}^{y}dp[x-2][y-i]\frac{y!}{(y-i)!}\cdot (i+1)$
可以先寫個程式算出這個DP表格，觀察前幾項可以發現：$\displaystyle dp[x][y]=dp[x][0]\cdot \frac{(x+y)!}{x!}$，所以只要遞推出$dp[x][0]$再計算答案就可以了。至於上面這條的證明就只要直接代入轉移式數歸，然後把組合級數化簡就可以了，詳細過程在這裡省略。
code :
2015年8月8日 星期六
[HOJ 283] Grid coloring
作法：
當$k=1$時作法是顯然的。接下來我們構造只要兩種顏色就可以滿足$\frac{3}{4}$以上的方法。首先把第一列按照不違反左右限制的方法塗完。並且最左邊行和最右邊行的格子的塗法為滿足他和他上面那個格子的限制為準。剩下的格子由上往下一列一列填，同列時由左往右填。假設當前格子為$A$，左邊格子為$B$，上面格子為$C$，右上方格子為$D$，那麼$B$會透過$A$左邊界的條件來限制$A$要放什麼，$C$則是透過上邊界，$D$則是得往下走再往左走來限制。如果這三個限制條件是一樣的話就直接放上那個顏色即可，否則一定有兩個限制條件的顏色一樣，選那個顏色塗即可。而證明也不難，只要發現到連續使用兩次上述塗法至多會跑出一個不合法的地方就可以了。
這題原本是codeforces的題目，官方解和我的不太一樣，也可以參考看看。
code :
當$k=1$時作法是顯然的。接下來我們構造只要兩種顏色就可以滿足$\frac{3}{4}$以上的方法。首先把第一列按照不違反左右限制的方法塗完。並且最左邊行和最右邊行的格子的塗法為滿足他和他上面那個格子的限制為準。剩下的格子由上往下一列一列填，同列時由左往右填。假設當前格子為$A$，左邊格子為$B$，上面格子為$C$，右上方格子為$D$，那麼$B$會透過$A$左邊界的條件來限制$A$要放什麼，$C$則是透過上邊界，$D$則是得往下走再往左走來限制。如果這三個限制條件是一樣的話就直接放上那個顏色即可，否則一定有兩個限制條件的顏色一樣，選那個顏色塗即可。而證明也不難，只要發現到連續使用兩次上述塗法至多會跑出一個不合法的地方就可以了。
這題原本是codeforces的題目，官方解和我的不太一樣，也可以參考看看。
code :
[HOJ 282] Empire disruption
作法：
首先注意到，對於每個計劃的相鄰兩個給定的城市，只要$x+y$的值比兩個城市之間的距離左右還大，那麼這兩個城市佔領的區域就會重疊。並且當兩相鄰城市佔領的區域重疊時，他們所佔領的總城市數就會是這兩個城市之間的城市數（含端點）加上$x+y$（不考慮左右邊界的話）。因此我們可以按照詢問的$x+y$值從小到大排序，每次如果發現有相鄰城市佔領的區域重疊了，就把他們黏起來。於是現在會變成有很多被黏起來的相鄰的城市們，我們需要知道總共有幾陀，還有這些城市區間內部的城市數量是多少。而這只要對於每一陀被黏起來的的城市，假設他最左和最右的城市分別是$X$和$Y$好了，那麼就用兩個陣列$le,ri$紀錄好$ri[X]=Y$，還有$le[Y]=X$就可以了。實作上我是將所有的兩個相鄰的給定城市之間的距離 sort ，還有詢問當然按照$x+y$值sort，並且當遇到一個詢問時把所有該黏起來的城市黏起來就可以了。最後要記得考慮超出邊界的問題，這只要用$a[1],a[n]$和當次詢問的$x,y$值就可以判斷了。
code :
首先注意到，對於每個計劃的相鄰兩個給定的城市，只要$x+y$的值比兩個城市之間的距離左右還大，那麼這兩個城市佔領的區域就會重疊。並且當兩相鄰城市佔領的區域重疊時，他們所佔領的總城市數就會是這兩個城市之間的城市數（含端點）加上$x+y$（不考慮左右邊界的話）。因此我們可以按照詢問的$x+y$值從小到大排序，每次如果發現有相鄰城市佔領的區域重疊了，就把他們黏起來。於是現在會變成有很多被黏起來的相鄰的城市們，我們需要知道總共有幾陀，還有這些城市區間內部的城市數量是多少。而這只要對於每一陀被黏起來的的城市，假設他最左和最右的城市分別是$X$和$Y$好了，那麼就用兩個陣列$le,ri$紀錄好$ri[X]=Y$，還有$le[Y]=X$就可以了。實作上我是將所有的兩個相鄰的給定城市之間的距離 sort ，還有詢問當然按照$x+y$值sort，並且當遇到一個詢問時把所有該黏起來的城市黏起來就可以了。最後要記得考慮超出邊界的問題，這只要用$a[1],a[n]$和當次詢問的$x,y$值就可以判斷了。
code :
2015年7月25日 星期六
[HOJ 278] Many Prizes
作法：
我們只要知道一個人最好是可以到多少，還有最差可以到多少，就可以分別對兩個答案二分搜了。首先看一個人最好可以到多少，最佳情形當然是他剛好一直遇到比他弱的，所以一直贏，直到沒有人比弱為止開始一直輸。假設現在比他弱的人有$x$個，那麼不難得出下一輪比他弱的只會剩$\left \lfloor \frac{x-1}{2} \right \rfloor $個，因此只要一直除下去直到這數字變$0$為止，就知道他可以連續贏幾場了。並且一個人的最差狀況則是一直輸，最後再一直贏，也可以用類似的方法求出會先輸幾場才開始一直贏。
code :
我們只要知道一個人最好是可以到多少，還有最差可以到多少，就可以分別對兩個答案二分搜了。首先看一個人最好可以到多少，最佳情形當然是他剛好一直遇到比他弱的，所以一直贏，直到沒有人比弱為止開始一直輸。假設現在比他弱的人有$x$個，那麼不難得出下一輪比他弱的只會剩$\left \lfloor \frac{x-1}{2} \right \rfloor $個，因此只要一直除下去直到這數字變$0$為止，就知道他可以連續贏幾場了。並且一個人的最差狀況則是一直輸，最後再一直贏，也可以用類似的方法求出會先輸幾場才開始一直贏。
code :
[HOJ 272] 出納員的僱用
作法：
考慮二分搜答案，那麼問題就會變成是否恰好僱用$X$個人並滿足條件。記我們在每個小時僱用的人為$x_1,...,x_{24}$，將他循環延長$7$個，也就是變成$x_1,...,x_{31}$，其中$x_i=x_{i+24}$，那麼我們就可以列出一些條件：首先當然是僱用的人數不能超過給的人數，也就是$x_i\leq num[i]$，其中$num$代表這個時間可以請的人數。還有剛才提到的$x_i=x_{i+24}$，並且因為能夠在某個時間$i$工作的人們開始工作的時間可能會是$i-7,...,i$，也就是這些時間請的人數必須$\geq$需要的人數，因此可以列出$x_{i-7}+...+x_i\geq need[i]$，其中$need$陣列一樣以 $24$ 一循環。不難將這些條件改為前綴和的條件，也就是令$S_i=x_1+...+x_i$，那麼$x_i=x_{i+24}$的條件可以改寫為$S_{i+24}=S_i+X$，其中$X$是前面我們二分搜的值（也就是$x_1+...+x_{24}=S_{24}$），剩下的條件則是顯然的。這樣就可以用差分約束解他了，把圖建出來用 Bellman-Ford 判他有沒有負圈就可以了。
code :
考慮二分搜答案，那麼問題就會變成是否恰好僱用$X$個人並滿足條件。記我們在每個小時僱用的人為$x_1,...,x_{24}$，將他循環延長$7$個，也就是變成$x_1,...,x_{31}$，其中$x_i=x_{i+24}$，那麼我們就可以列出一些條件：首先當然是僱用的人數不能超過給的人數，也就是$x_i\leq num[i]$，其中$num$代表這個時間可以請的人數。還有剛才提到的$x_i=x_{i+24}$，並且因為能夠在某個時間$i$工作的人們開始工作的時間可能會是$i-7,...,i$，也就是這些時間請的人數必須$\geq$需要的人數，因此可以列出$x_{i-7}+...+x_i\geq need[i]$，其中$need$陣列一樣以 $24$ 一循環。不難將這些條件改為前綴和的條件，也就是令$S_i=x_1+...+x_i$，那麼$x_i=x_{i+24}$的條件可以改寫為$S_{i+24}=S_i+X$，其中$X$是前面我們二分搜的值（也就是$x_1+...+x_{24}=S_{24}$），剩下的條件則是顯然的。這樣就可以用差分約束解他了，把圖建出來用 Bellman-Ford 判他有沒有負圈就可以了。
code :
[HOJ 247][IOI 2008] Islands
作法：
首先當然是把所有連通塊分開看，這題簡單來說就是要找水母圖上的最長路（無向的），我們先找出這張水母圖的圈在哪裡，找法從隨便一個點開始沿著他唯一連出去的邊一直走，走到重複的點為止，就找到一個圈了。水母圖上的最長路分兩種，一種是沒有經過圈上的邊的，一種則是有的。對於前者，我們可以枚舉水母圈上的點，考慮這個點連往非水母圈的邊的那些點們，會形成一棵子樹，對這個子樹求最長路徑就可以了。至於經過水母圈上的邊的路徑，因為顯然如果我們已經決定好路徑和水母圈的交集的兩端點的話，剩下就取這個端點往他的子樹方向走過去的最長路就可以了，因此在回傳子樹內部的最長路時要順便回傳子樹根往下走的最長路。於是我們現在有圈上每個點往樹方向走下去的最長路了（以下稱為$val$值），還有圈上每條邊的長度，要求的是「兩點之間的距離$+$兩點的$val$值」的最大值。考慮把圈壓成序列，也就是如果原本圈上的點為$A_1,...,A_k$，考慮序列$A_1,...,A_k,A_{k+1},...,A_{2k-1}$，其中$A_{i+k}=A_i$，並且相鄰點的距離就和原本圈上連接這兩點的距離相等，記$dis[i]$代表$A_1$往右走到$A_i$的距離，和$val[i]$代表$A_i$的 val 值（最長路長），那麼我們要求的東西就是：$(i,j)$滿足$dis[i]-dis[j]+val[i]+val[j]$最大，其中$i-j<k$。因此當固定$i$的時候，我們需要的東西就會是$max\{ val[j]-dis[j] \}$，其中$j=i-k+1,...,i-1$。於是這就可以用 deque 優化在線性的時間內求出來了。
最後我傳上去 MLE 了，載測資來看發現那兩筆是DFS會到$10^6$層左右的，後來我把DFS改成自己用 stack 作才過的，感覺 IOI 沒必要這樣卡記憶體阿OAO......
code :
首先當然是把所有連通塊分開看，這題簡單來說就是要找水母圖上的最長路（無向的），我們先找出這張水母圖的圈在哪裡，找法從隨便一個點開始沿著他唯一連出去的邊一直走，走到重複的點為止，就找到一個圈了。水母圖上的最長路分兩種，一種是沒有經過圈上的邊的，一種則是有的。對於前者，我們可以枚舉水母圈上的點，考慮這個點連往非水母圈的邊的那些點們，會形成一棵子樹，對這個子樹求最長路徑就可以了。至於經過水母圈上的邊的路徑，因為顯然如果我們已經決定好路徑和水母圈的交集的兩端點的話，剩下就取這個端點往他的子樹方向走過去的最長路就可以了，因此在回傳子樹內部的最長路時要順便回傳子樹根往下走的最長路。於是我們現在有圈上每個點往樹方向走下去的最長路了（以下稱為$val$值），還有圈上每條邊的長度，要求的是「兩點之間的距離$+$兩點的$val$值」的最大值。考慮把圈壓成序列，也就是如果原本圈上的點為$A_1,...,A_k$，考慮序列$A_1,...,A_k,A_{k+1},...,A_{2k-1}$，其中$A_{i+k}=A_i$，並且相鄰點的距離就和原本圈上連接這兩點的距離相等，記$dis[i]$代表$A_1$往右走到$A_i$的距離，和$val[i]$代表$A_i$的 val 值（最長路長），那麼我們要求的東西就是：$(i,j)$滿足$dis[i]-dis[j]+val[i]+val[j]$最大，其中$i-j<k$。因此當固定$i$的時候，我們需要的東西就會是$max\{ val[j]-dis[j] \}$，其中$j=i-k+1,...,i-1$。於是這就可以用 deque 優化在線性的時間內求出來了。
最後我傳上去 MLE 了，載測資來看發現那兩筆是DFS會到$10^6$層左右的，後來我把DFS改成自己用 stack 作才過的，感覺 IOI 沒必要這樣卡記憶體阿OAO......
code :
[HOJ 251][IOI 2008] Pyramid Base
作法：
首先考慮二分搜答案，因為如果能夠在預算內放入邊長$x$的正方形，那顯然可以放入邊長$x-1$的正方形。當確定一個邊長時，我們想要知道他可不可行，而只要注意到：我們只要決定好正方形的左上角就可以了，並且對於平面上的某個障礙物來說，考慮那些「用來當正方形左上角的話會和這個障礙物有交集的格子」，不難發現這些格子形成一個長方形（其座標不難求），因此就可以想成：如果左上角放在這個長方形裡，就要多花（這個長方形的 cost ）元。並且我們想知道這個平面上花費最少的格子是否在預算之中。因此就轉換為經典問題了：給定平面上的一些長方形，每個長方形都把內部的格子同加某個值，求整個平面的最小值是多少。這就顯然可以用掃描線+線段樹做了。
但這樣傳上去TLE了，畢竟$O(nlog^2n)$對$n\leq 400000$來說太大了。但注意到剩下只有$B=0$的情形，因此可以思考另外一種算法。考慮對於每個左界$i$，都找出最大的右界$j$，使得存在一個空的正方形，他的左右界分別為$i$和$j$。注意到如果我們把$i$到$j$這幾排全部壓成一排，並且「有和$i$到$j$交集的障礙物」都被壓成一排中的區間，那麼就變成詢問這一排中有最多連續幾個格子沒有障礙物了。因此我們可以把有交集到的障礙物的兩個$y$座標看成「把這兩數之間的所有數的位置的值都$+1$」，並且詢問的是這個數列裡有最多多少個連續的$0$，因此可以用線段樹做。這樣我們得到了$O(n^2logn)$的算法，也就是對於每個左界$i$直接一個一個往右擴展，當多遇到一個障礙物的左界，就在該區間$+1$的地方$+1$，直到查詢出來的值無法在兩邊界之間形成正方形為止。但只要注意到：如果存在一個正方形的左右邊界是$i,j$，那麼也存在左右邊界是$i+1,j$的。因此就可以改成用雙指標掃過去一次就可以了。複雜度降為$O(nlogn)$
最後提一下，這裡的線段樹必須支援：區間加$1$，區間減$1$和查詢最大連續的$0$數量，作法和「求$n$個矩形在平面上的覆蓋面積」時掃描線所用的線段樹類似，可以參考這篇。
code :
首先考慮二分搜答案，因為如果能夠在預算內放入邊長$x$的正方形，那顯然可以放入邊長$x-1$的正方形。當確定一個邊長時，我們想要知道他可不可行，而只要注意到：我們只要決定好正方形的左上角就可以了，並且對於平面上的某個障礙物來說，考慮那些「用來當正方形左上角的話會和這個障礙物有交集的格子」，不難發現這些格子形成一個長方形（其座標不難求），因此就可以想成：如果左上角放在這個長方形裡，就要多花（這個長方形的 cost ）元。並且我們想知道這個平面上花費最少的格子是否在預算之中。因此就轉換為經典問題了：給定平面上的一些長方形，每個長方形都把內部的格子同加某個值，求整個平面的最小值是多少。這就顯然可以用掃描線+線段樹做了。
但這樣傳上去TLE了，畢竟$O(nlog^2n)$對$n\leq 400000$來說太大了。但注意到剩下只有$B=0$的情形，因此可以思考另外一種算法。考慮對於每個左界$i$，都找出最大的右界$j$，使得存在一個空的正方形，他的左右界分別為$i$和$j$。注意到如果我們把$i$到$j$這幾排全部壓成一排，並且「有和$i$到$j$交集的障礙物」都被壓成一排中的區間，那麼就變成詢問這一排中有最多連續幾個格子沒有障礙物了。因此我們可以把有交集到的障礙物的兩個$y$座標看成「把這兩數之間的所有數的位置的值都$+1$」，並且詢問的是這個數列裡有最多多少個連續的$0$，因此可以用線段樹做。這樣我們得到了$O(n^2logn)$的算法，也就是對於每個左界$i$直接一個一個往右擴展，當多遇到一個障礙物的左界，就在該區間$+1$的地方$+1$，直到查詢出來的值無法在兩邊界之間形成正方形為止。但只要注意到：如果存在一個正方形的左右邊界是$i,j$，那麼也存在左右邊界是$i+1,j$的。因此就可以改成用雙指標掃過去一次就可以了。複雜度降為$O(nlogn)$
最後提一下，這裡的線段樹必須支援：區間加$1$，區間減$1$和查詢最大連續的$0$數量，作法和「求$n$個矩形在平面上的覆蓋面積」時掃描線所用的線段樹類似，可以參考這篇。
code :
2015年7月22日 星期三
[HOJ 223] H. 項鍊
作法：
$m=1$時是顯然的，$m=2$不難自己構造出來，詳細可以參考 code 。但$m=3$以上的構造就很困難了，我的作法是直接 DFS 下去，剛好因為滿足這種條件的數列蠻多的，所以可以在時限內找到。比較正常的作法應該是把他轉成尤拉迴路問題：考慮一張有$n^{m-1}$個點的有向圖，每個點都代表一個長度為$m-1$字元集$1~n$的字串，並且如果某個點$A$可以經由「在後面加上一個數並丟掉最前面的數」轉換成$B$，那麼就從$A$連到$B$一條邊。這樣邊的總數會是$n^m\leq 3\cdot 10^5$，對這張圖求尤拉迴路就可以了。
code :
$m=1$時是顯然的，$m=2$不難自己構造出來，詳細可以參考 code 。但$m=3$以上的構造就很困難了，我的作法是直接 DFS 下去，剛好因為滿足這種條件的數列蠻多的，所以可以在時限內找到。比較正常的作法應該是把他轉成尤拉迴路問題：考慮一張有$n^{m-1}$個點的有向圖，每個點都代表一個長度為$m-1$字元集$1~n$的字串，並且如果某個點$A$可以經由「在後面加上一個數並丟掉最前面的數」轉換成$B$，那麼就從$A$連到$B$一條邊。這樣邊的總數會是$n^m\leq 3\cdot 10^5$，對這張圖求尤拉迴路就可以了。
code :
[HOJ 220] E. code
作法：
如果題目沒有$i\neq j$的條件的話，式子就可以寫成$\displaystyle (\sum_{i=1}^{n} n\% i)(\sum_{i=1}^{m} m\% i)$，因此這部份可以先分開算再乘起來。至於要怎麼計算$\displaystyle \sum_{i=1}^{n} n\% i$，一樣是把商一樣的區間合併起來看，因為$n$除以從$i$一直到$n/(n/i)$（這裡是整數除法）的這些數都會得到一樣的商，所以在這個區間裡$n\% i$會是一個等差數列，可以合併起來一起算。最後則是要扣掉$i=j$的部份，也就是要計算$\displaystyle \sum_{i=1}^{min(n,m)} (n\% i)(m\% i)$，這一樣可以用剛才的技巧，只不過區間的右端點必須取成$min(m/(m/i),n/(n/i))$而已。這部份則會變成一個二次函數在一個區間裡的所有函數值的總和，而這東西不難用$\displaystyle \sum k^2$的公式求得。
code :
如果題目沒有$i\neq j$的條件的話，式子就可以寫成$\displaystyle (\sum_{i=1}^{n} n\% i)(\sum_{i=1}^{m} m\% i)$，因此這部份可以先分開算再乘起來。至於要怎麼計算$\displaystyle \sum_{i=1}^{n} n\% i$，一樣是把商一樣的區間合併起來看，因為$n$除以從$i$一直到$n/(n/i)$（這裡是整數除法）的這些數都會得到一樣的商，所以在這個區間裡$n\% i$會是一個等差數列，可以合併起來一起算。最後則是要扣掉$i=j$的部份，也就是要計算$\displaystyle \sum_{i=1}^{min(n,m)} (n\% i)(m\% i)$，這一樣可以用剛才的技巧，只不過區間的右端點必須取成$min(m/(m/i),n/(n/i))$而已。這部份則會變成一個二次函數在一個區間裡的所有函數值的總和，而這東西不難用$\displaystyle \sum k^2$的公式求得。
code :
[HOJ 218] C. osu!
作法：
首先找出圓和四條邊界的交點（如果有的話），那麼可以得到相鄰交點中間形成的弧同在矩形內部或外部，因此可以直接選這段弧的中點判斷他是在內部還外部，在內部的話就把答案加上對應的值就可以了。另外要注意圓和邊界完全沒有交點的情形，而這只要一開始就加入兩個假的斷點（$\frac{\pi}{2}$和$-\frac{\pi}{2}$）就可以了。
code :
首先找出圓和四條邊界的交點（如果有的話），那麼可以得到相鄰交點中間形成的弧同在矩形內部或外部，因此可以直接選這段弧的中點判斷他是在內部還外部，在內部的話就把答案加上對應的值就可以了。另外要注意圓和邊界完全沒有交點的情形，而這只要一開始就加入兩個假的斷點（$\frac{\pi}{2}$和$-\frac{\pi}{2}$）就可以了。
code :
[HOJ 201] TRAMPOLIN
作法：
首先我們可以把相鄰的同高度的大樓黏起來，並且紀錄好黏起來的這陀大樓原本有幾棟，而如果原本黏起來的大樓中有可以瞬移的大樓，那麼黏起來後的也可以瞬移。因此現在問題轉化為相鄰高度皆不同的問題。首先如出發點往左邊或右邊走都沒辦法達到能夠瞬移的大樓，那麼答案就是往左走或往右走的經過大樓數比較多的那個，反之假設起點可以走到某個可瞬移的大樓，那麼對於所有的制高點（旁邊沒有比他高的大樓的大樓），如果他往左（或往右）走下去之後會可以遇到能瞬移的，那麼我們就可以從起點那邊瞬移到這個制高點，走完這段後再順移回去。因此我們可以先找出所有的這樣的路徑，把他們標記成全部都可以走到。最後只要再選一個制高點然後走到底就好，枚舉看要走哪條路徑可以增加更多被走到的大樓。
code :
首先我們可以把相鄰的同高度的大樓黏起來，並且紀錄好黏起來的這陀大樓原本有幾棟，而如果原本黏起來的大樓中有可以瞬移的大樓，那麼黏起來後的也可以瞬移。因此現在問題轉化為相鄰高度皆不同的問題。首先如出發點往左邊或右邊走都沒辦法達到能夠瞬移的大樓，那麼答案就是往左走或往右走的經過大樓數比較多的那個，反之假設起點可以走到某個可瞬移的大樓，那麼對於所有的制高點（旁邊沒有比他高的大樓的大樓），如果他往左（或往右）走下去之後會可以遇到能瞬移的，那麼我們就可以從起點那邊瞬移到這個制高點，走完這段後再順移回去。因此我們可以先找出所有的這樣的路徑，把他們標記成全部都可以走到。最後只要再選一個制高點然後走到底就好，枚舉看要走哪條路徑可以增加更多被走到的大樓。
code :
[HOJ 187] 小學老師
作法：
首先觀察有哪些數字的$f$值會變成$i$，會發現這就等價於這個數是$1,...,i-1$的倍數，但不是$i$的倍數。因此可以想像$10^{17}$範圍內的數字的$f$值都不會太大，因為$1,...,n$的最小公倍數成長的速度非常快。可以預處理出最大的$f$值只會到$41$，因此對於所求的值，對於每一項$L(i)$來說，可以先把他換成$L(f(i))+1$，這樣就只需要知道$[A,B]$之間有幾個數的$f$值等於$i$了（$i=1,...,41$），而這顯然用前面的等價條件就可以算了。
code :
首先觀察有哪些數字的$f$值會變成$i$，會發現這就等價於這個數是$1,...,i-1$的倍數，但不是$i$的倍數。因此可以想像$10^{17}$範圍內的數字的$f$值都不會太大，因為$1,...,n$的最小公倍數成長的速度非常快。可以預處理出最大的$f$值只會到$41$，因此對於所求的值，對於每一項$L(i)$來說，可以先把他換成$L(f(i))+1$，這樣就只需要知道$[A,B]$之間有幾個數的$f$值等於$i$了（$i=1,...,41$），而這顯然用前面的等價條件就可以算了。
code :
2015年7月20日 星期一
[HOJ 160] 紅色警戒區
作法：
首先對於每個圓，求出他和其他所有圓的交點，那麼對於相鄰交點形成的弧上的任意點來說，他們的狀態都是一樣的，也就是他們同為邊界或同不為邊界（或是說交點們就是「斷點」）。因此只要取這段弧上的中點，去判斷他是否落在某個圓內部就可以了。另外要注意到，這樣會沒辦法判斷一個圓被另一個圓包住的情形，此時裡面的圓沒有任何斷點，因此要先對每個圓都加入$\frac{\pi }{2}$和$-\frac{\pi}{2}$這兩個斷點（以極角表示斷點）才能自動把他判掉。最後還要處理兩個圓重和的情形，在一開始就直接把重複的丟掉就可以了。
code :
首先對於每個圓，求出他和其他所有圓的交點，那麼對於相鄰交點形成的弧上的任意點來說，他們的狀態都是一樣的，也就是他們同為邊界或同不為邊界（或是說交點們就是「斷點」）。因此只要取這段弧上的中點，去判斷他是否落在某個圓內部就可以了。另外要注意到，這樣會沒辦法判斷一個圓被另一個圓包住的情形，此時裡面的圓沒有任何斷點，因此要先對每個圓都加入$\frac{\pi }{2}$和$-\frac{\pi}{2}$這兩個斷點（以極角表示斷點）才能自動把他判掉。最後還要處理兩個圓重和的情形，在一開始就直接把重複的丟掉就可以了。
code :
[HOJ 164] 森森砍你的臉
作法：
考慮枚舉正方形左上角右下角所在的對角線，首先我們可以預處理出每個格子的$X$值和$Y$值，$X[i][j]$代表從$(i,j)$這格往右往下長度$X[i][j]$以內的格子都是$1$（或是$(i,j),...,(i,j+X[i][j]-1)$均為$1$，往下同理），$Y[i][j]$則是代表往左往上的，並且兩者都是取最大的值。那麼當我們枚舉一條對角線時，記這條對角線上第$i$格的$X,Y$值分別為$x[i],y[i]$，那我們想找的就是所有二元組$(i,j)$的數量（$i\leq j$），滿足$x[i]\geq j-i+1$，且$y[j]\geq j-i+1$。注意到這條式子中，不管怎麼樣當$i>j$時他一定會成立，因此我們可以把$i\leq j$這個條件拿掉，再扣掉多算到的部份就可以了。將上式移項得$i+x[i]\geq j+1$，$i\geq j+1-y[j]$，那麼就可以轉換成簡單的問題了：考慮平面上的$n$個紅點和$n$個藍點，其中第$i$個紅點的座標為$(i+x[i],i)$，第$i$個藍點的座標為$(i+1,i+1-y[i])$，求滿足「紅點的兩座標均$\geq$藍點的兩座標」的（紅點、藍點）的個數（或是說紅點包住藍點的點對數量）。這可以先把所有點按照$x$座標排序，再用個 BIT 查詢每個紅點包住了幾個藍點就可以了。
code :
考慮枚舉正方形左上角右下角所在的對角線，首先我們可以預處理出每個格子的$X$值和$Y$值，$X[i][j]$代表從$(i,j)$這格往右往下長度$X[i][j]$以內的格子都是$1$（或是$(i,j),...,(i,j+X[i][j]-1)$均為$1$，往下同理），$Y[i][j]$則是代表往左往上的，並且兩者都是取最大的值。那麼當我們枚舉一條對角線時，記這條對角線上第$i$格的$X,Y$值分別為$x[i],y[i]$，那我們想找的就是所有二元組$(i,j)$的數量（$i\leq j$），滿足$x[i]\geq j-i+1$，且$y[j]\geq j-i+1$。注意到這條式子中，不管怎麼樣當$i>j$時他一定會成立，因此我們可以把$i\leq j$這個條件拿掉，再扣掉多算到的部份就可以了。將上式移項得$i+x[i]\geq j+1$，$i\geq j+1-y[j]$，那麼就可以轉換成簡單的問題了：考慮平面上的$n$個紅點和$n$個藍點，其中第$i$個紅點的座標為$(i+x[i],i)$，第$i$個藍點的座標為$(i+1,i+1-y[i])$，求滿足「紅點的兩座標均$\geq$藍點的兩座標」的（紅點、藍點）的個數（或是說紅點包住藍點的點對數量）。這可以先把所有點按照$x$座標排序，再用個 BIT 查詢每個紅點包住了幾個藍點就可以了。
code :
[HOJ 199] KAMPANJA
作法：
考慮$d[A][B]$代表從$1$走到$A$走到$B$再走回$A$的路上最少可以經過幾個節點，那麼所求的答案就是$d[2][2]$。首先我們可以用 Floyd 求出任兩點之間的最短路（之後記為$dis[][]$），就可以先得到$d[A][B]$的一些初始值，並且由第一個範測可以觀察到：如果我們任取四個點$A,B,X,Y$，那麼$1\rightarrow X\rightarrow Y\rightarrow 1$實際上可以用$1\rightarrow A\rightarrow B\rightarrow X\rightarrow Y\rightarrow A\rightarrow B\rightarrow 1$來達成，也就是我們可以用$d[A][B]+dis[B][X]+dis[X][Y]+dis[Y][A]-1$來更新$d[X][Y]$的值。注意到上式中當$X,Y,A,B$不全相等時，$dis[B][X]+dis[X][Y]+dis[Y][A]-1\geq 0$，這就類似在求最短路的過程，因此我們可以直接套用 Dijkstra 求得答案。注意到這裡的 Dijkstra 不是用 priority_queue 優化的，而是優化前的「每次掃一遍所有的節點看誰目前距離最小，拿他來鬆弛其他人」，前者複雜度會變成$O(n^4logn)$，後者則是$O(n^4)$（因為這張圖是稠密圖）。
code :
考慮$d[A][B]$代表從$1$走到$A$走到$B$再走回$A$的路上最少可以經過幾個節點，那麼所求的答案就是$d[2][2]$。首先我們可以用 Floyd 求出任兩點之間的最短路（之後記為$dis[][]$），就可以先得到$d[A][B]$的一些初始值，並且由第一個範測可以觀察到：如果我們任取四個點$A,B,X,Y$，那麼$1\rightarrow X\rightarrow Y\rightarrow 1$實際上可以用$1\rightarrow A\rightarrow B\rightarrow X\rightarrow Y\rightarrow A\rightarrow B\rightarrow 1$來達成，也就是我們可以用$d[A][B]+dis[B][X]+dis[X][Y]+dis[Y][A]-1$來更新$d[X][Y]$的值。注意到上式中當$X,Y,A,B$不全相等時，$dis[B][X]+dis[X][Y]+dis[Y][A]-1\geq 0$，這就類似在求最短路的過程，因此我們可以直接套用 Dijkstra 求得答案。注意到這裡的 Dijkstra 不是用 priority_queue 優化的，而是優化前的「每次掃一遍所有的節點看誰目前距離最小，拿他來鬆弛其他人」，前者複雜度會變成$O(n^4logn)$，後者則是$O(n^4)$（因為這張圖是稠密圖）。
code :
2015年7月18日 星期六
[HOJ 128] Matching
作法：
我們一樣往KMP的方向想，首先我們會需要 fail 函數，回顧他的定義，$fail[i]$代表說「當已經匹配好$1,...,i$時，如果$i+1$失配，那麼要轉換成已經匹配好$1,...,fail[i]$的情形」，而這裡的匹配的定義根一般字串匹配不一樣，是要兩個子序列的「相對大小關係」一樣時則叫作匹配。因此回顧我們在算 fail 函數時的方法，假設當前要決定$i$的 fail 值，令$fail[i-1]=j$，那麼首先我們要判斷「$1,...,i$的長度為$j+1$的後綴」是否和「長度$j+1$的前綴」匹配（再次強調這裡匹配的定義不一樣），而這等價於：「在$x[i-j],...,x[i-1]$之中比$x[i]$小的數的個數」等於「在$x[1],...,x[j]$中比$x[j+1]$小的數的個數」，其中$x$為要求$fail$函數的陣列。因此就可以維護一個 BIT 來查詢所求的答案（因為會支援加數字和刪數字）。如果發現失配了就一樣沿著 fail 往回跳，直到長度變$0$或是匹配成功為止。由這裡就可以發現，其實 fail 函數建立的過程幾乎一樣，只是變成要多維護兩個 BIT ，並用 BIT 來查詢是否匹配成功而已。在和原數列匹配的過程也一模一樣（本來在原本的寫法中建 fail 函數和匹配的過程的程式碼就幾乎一樣了），失配就沿 fail 往前跳，維護好兩個 BIT 即可。最後要記得當找到一個地方成功匹配了模版串時也要沿 fail 往前跳，跟原本的 KMP 一樣。
code :
我們一樣往KMP的方向想，首先我們會需要 fail 函數，回顧他的定義，$fail[i]$代表說「當已經匹配好$1,...,i$時，如果$i+1$失配，那麼要轉換成已經匹配好$1,...,fail[i]$的情形」，而這裡的匹配的定義根一般字串匹配不一樣，是要兩個子序列的「相對大小關係」一樣時則叫作匹配。因此回顧我們在算 fail 函數時的方法，假設當前要決定$i$的 fail 值，令$fail[i-1]=j$，那麼首先我們要判斷「$1,...,i$的長度為$j+1$的後綴」是否和「長度$j+1$的前綴」匹配（再次強調這裡匹配的定義不一樣），而這等價於：「在$x[i-j],...,x[i-1]$之中比$x[i]$小的數的個數」等於「在$x[1],...,x[j]$中比$x[j+1]$小的數的個數」，其中$x$為要求$fail$函數的陣列。因此就可以維護一個 BIT 來查詢所求的答案（因為會支援加數字和刪數字）。如果發現失配了就一樣沿著 fail 往回跳，直到長度變$0$或是匹配成功為止。由這裡就可以發現，其實 fail 函數建立的過程幾乎一樣，只是變成要多維護兩個 BIT ，並用 BIT 來查詢是否匹配成功而已。在和原數列匹配的過程也一模一樣（本來在原本的寫法中建 fail 函數和匹配的過程的程式碼就幾乎一樣了），失配就沿 fail 往前跳，維護好兩個 BIT 即可。最後要記得當找到一個地方成功匹配了模版串時也要沿 fail 往前跳，跟原本的 KMP 一樣。
code :
[HOJ 149] 改建路徑
作法：
我們考慮一個非常樸素的DP：設$dp[i][j]$代表目前已把前$i$個數弄成非嚴格遞增了，則第$i$個數的值為$j$的最小花費，那麼顯然可以寫出轉移式：$dp[i][j]=min\{dp[i-1][k]+|a[i]-j|,k=1,...,j\}$。想像一下$dp[i]$的函數圖形，那麼他就是由$dp[i-1]$先取前綴 min ，再加上$|x-a[i]|$這個函數所形成的圖形（前綴 min 的意思就是前面轉移式中的$min\{ dp[i-1][k],k=1,...,j \}$）。不難發現他其實會形成一個下凸包，並且轉折的點只會出現在$x$座標為原本$a$數列裡出現過的值，並且每次加上$|x-a[i]|$這個函數時，可以看成$a[i]$左邊的斜率全部$-1$，右邊的斜率全部$+1$，因此就可以用線段樹來維護斜率們（所以在這之前要先離散化$a[i]$），並且取前綴 min 的操作可以等價成：把斜率$>0$的部份都設成$0$（因為他會一直維持他是下凸包的良好性質），這也不難在線段樹上做到。最後我們想知道的是$dp[n]$這個函數圖形的最小值是多少，但線段樹中只有紀錄每個區間的斜率，因此只要再多紀錄函數在$0$的值是多少就可以了（而他顯然會是所有$a[i]$的和），從左到右掃一遍就可以獲得$dp[n]$圖形的每個轉折點的座標，取$y$座標最小的點就是答案了。
最後，在「把斜率$>0$的部份都設成$0$」的操作其實可以很簡潔的完成，我們可以對每個線段樹區間都維護他的最小值，那麼就可以直接從根走下去，發現如果當前節點的右孩子的最小值$>0$（其實也只有可能是$1$），就把右孩子全部$-1$，往左孩子遞迴，反之則往右孩子遞迴就可以了。
code :
我們考慮一個非常樸素的DP：設$dp[i][j]$代表目前已把前$i$個數弄成非嚴格遞增了，則第$i$個數的值為$j$的最小花費，那麼顯然可以寫出轉移式：$dp[i][j]=min\{dp[i-1][k]+|a[i]-j|,k=1,...,j\}$。想像一下$dp[i]$的函數圖形，那麼他就是由$dp[i-1]$先取前綴 min ，再加上$|x-a[i]|$這個函數所形成的圖形（前綴 min 的意思就是前面轉移式中的$min\{ dp[i-1][k],k=1,...,j \}$）。不難發現他其實會形成一個下凸包，並且轉折的點只會出現在$x$座標為原本$a$數列裡出現過的值，並且每次加上$|x-a[i]|$這個函數時，可以看成$a[i]$左邊的斜率全部$-1$，右邊的斜率全部$+1$，因此就可以用線段樹來維護斜率們（所以在這之前要先離散化$a[i]$），並且取前綴 min 的操作可以等價成：把斜率$>0$的部份都設成$0$（因為他會一直維持他是下凸包的良好性質），這也不難在線段樹上做到。最後我們想知道的是$dp[n]$這個函數圖形的最小值是多少，但線段樹中只有紀錄每個區間的斜率，因此只要再多紀錄函數在$0$的值是多少就可以了（而他顯然會是所有$a[i]$的和），從左到右掃一遍就可以獲得$dp[n]$圖形的每個轉折點的座標，取$y$座標最小的點就是答案了。
最後，在「把斜率$>0$的部份都設成$0$」的操作其實可以很簡潔的完成，我們可以對每個線段樹區間都維護他的最小值，那麼就可以直接從根走下去，發現如果當前節點的右孩子的最小值$>0$（其實也只有可能是$1$），就把右孩子全部$-1$，往左孩子遞迴，反之則往右孩子遞迴就可以了。
code :
[HOJ 156] Xor路徑和
作法：
首先我們當然可以只看和$1,n$連通的分量就好了。考慮隨便取一條$1$走到$n$的路徑，設其 xor 值為$X$，然後隨便取一個圖中的圈，假設他邊的 xor 值為$Y$，那麼就存在一條從$1$走到$n$的路徑，使得其 xor 值為$X\; xor\; Y$。因為只要在走原本的路徑時，走到一半分出去走到圈上的某一個點，繞完一圈後再沿原路走回來，再繼續走到$n$就可以了。因此我們的想法為：隨便取一條$1$走到$n$的路徑，並且找出所有圖中的圈，那麼只要想辦法用這條路徑的 xor 值加上隨便取幾個圈湊出最大的 xor 值就可以了。但這樣顯然會遇到圖中的圈太多的問題，但其實我們可以只保留那些「沒辦法被之前找到的圈的值 xor 出來的圈」就可以了，具體來說，如果有個圈$C$的 xor 值為$X$，並且存在其他圈$C_1,...,C_r$其 xor 值分別為$X_1,...,X_r$，那麼當$X=X_1\; xor \; ... \; xor \; X_r$時$C$就沒有用了，因為如果取到他的話就可以直接把他換成$C_1,...,C_r$（或是說我們取的圈的值都是線性獨立的）。再來注意到，我們考慮一條一條把邊加到圖中，那麼當某條邊$AB$加進去並且形成了新的圈時，我們隨便取一條$A$到$B$的路徑，和新加的這條邊組成了一個圈，那麼（不難證明）在這個圖中所有新形成的圈的 xor 值都可以用這個新的圈的 xor 值和舊的那些圈的值 xor 出來，因此我們就可以獲得至多$m$個圈的 xor 值，並且要想辦法把他刪成線性獨立的（這樣就會不超過 $60$ 個了）。
我們先看要怎麼知道這些圈的 xor 值是多少，事實上我們可以在維護 disjoint set 的時候順便維護這個點沿著他父親走到根，路上經過的邊的 xor 值是多少，只要修改一下 find 的過程就可以了，詳細可以參考 code 。再來則是我們想把$m$個數（向量）刪成線性獨立的$\leq 60$個，這只要直接高斯消去就可以了，細節在此省略。有了這些線性獨立的向量後，剩下的問題是：給定一個數$x$（也就是我們任意取的$1$走到$n$的路徑的 xor 值），我們要想辦法用這些向量 xor 一個數，使得他和$x$的 xor 值盡量大。我們可以考慮由高到低一位一位確定答案，舉例來說，$x$的二進制為$110101$，並且我們已經知道能湊出的盡量大的值為$101***$（後面代表還沒確定），那麼接下來我們想知道能不能用那些向量湊出形如$0110**$的向量，就能確定答案的下一位了。確定這個的方法只要把所有已有的向量的最後兩位砍掉，並且去處理「給定一些向量，是否有辦法湊出給定的某個向量」的問題就可以了，作法當然就直接高斯消去就可以了。
code :
首先我們當然可以只看和$1,n$連通的分量就好了。考慮隨便取一條$1$走到$n$的路徑，設其 xor 值為$X$，然後隨便取一個圖中的圈，假設他邊的 xor 值為$Y$，那麼就存在一條從$1$走到$n$的路徑，使得其 xor 值為$X\; xor\; Y$。因為只要在走原本的路徑時，走到一半分出去走到圈上的某一個點，繞完一圈後再沿原路走回來，再繼續走到$n$就可以了。因此我們的想法為：隨便取一條$1$走到$n$的路徑，並且找出所有圖中的圈，那麼只要想辦法用這條路徑的 xor 值加上隨便取幾個圈湊出最大的 xor 值就可以了。但這樣顯然會遇到圖中的圈太多的問題，但其實我們可以只保留那些「沒辦法被之前找到的圈的值 xor 出來的圈」就可以了，具體來說，如果有個圈$C$的 xor 值為$X$，並且存在其他圈$C_1,...,C_r$其 xor 值分別為$X_1,...,X_r$，那麼當$X=X_1\; xor \; ... \; xor \; X_r$時$C$就沒有用了，因為如果取到他的話就可以直接把他換成$C_1,...,C_r$（或是說我們取的圈的值都是線性獨立的）。再來注意到，我們考慮一條一條把邊加到圖中，那麼當某條邊$AB$加進去並且形成了新的圈時，我們隨便取一條$A$到$B$的路徑，和新加的這條邊組成了一個圈，那麼（不難證明）在這個圖中所有新形成的圈的 xor 值都可以用這個新的圈的 xor 值和舊的那些圈的值 xor 出來，因此我們就可以獲得至多$m$個圈的 xor 值，並且要想辦法把他刪成線性獨立的（這樣就會不超過 $60$ 個了）。
我們先看要怎麼知道這些圈的 xor 值是多少，事實上我們可以在維護 disjoint set 的時候順便維護這個點沿著他父親走到根，路上經過的邊的 xor 值是多少，只要修改一下 find 的過程就可以了，詳細可以參考 code 。再來則是我們想把$m$個數（向量）刪成線性獨立的$\leq 60$個，這只要直接高斯消去就可以了，細節在此省略。有了這些線性獨立的向量後，剩下的問題是：給定一個數$x$（也就是我們任意取的$1$走到$n$的路徑的 xor 值），我們要想辦法用這些向量 xor 一個數，使得他和$x$的 xor 值盡量大。我們可以考慮由高到低一位一位確定答案，舉例來說，$x$的二進制為$110101$，並且我們已經知道能湊出的盡量大的值為$101***$（後面代表還沒確定），那麼接下來我們想知道能不能用那些向量湊出形如$0110**$的向量，就能確定答案的下一位了。確定這個的方法只要把所有已有的向量的最後兩位砍掉，並且去處理「給定一些向量，是否有辦法湊出給定的某個向量」的問題就可以了，作法當然就直接高斯消去就可以了。
code :
2015年7月6日 星期一
[HOJ 329] Construct?!
作法：
假設我們交換的兩數分別為$x,y$，那麼對於那些數值不是落在$x,y$之間的數，交換之後並不會影響這些數和$x,y$之間的逆序數對數，不管這些數落在交換的兩位置的左右還是中間。對於那些數值落在$x,y$之間的數，只有當他的位子落在交換的兩數字位置之間才會影響逆序數對的數量。由此就可以推出，我們交換的兩個數一定是左邊大右邊小的，才可以讓交換後逆序數對減少越多。假設交換的兩數位置分別為$i,j$，數字則為$x,y$，那麼逆序數對的變化就會等於$2\times $位子落在$i,j$之間的介於$x,y$之間數的個數$+1$（還要加上交換的兩數形成的逆序數對）。這樣就可以轉化為平面上點集的問題了：把$(i,a[i])$看成座標平面上的點，那麼我們要的就是一個矩形的左上角和右下角，使得這個矩形內包含最多的點。考慮所有「左上方沒有點」的點，那麼不難知道所求矩形的左上角一定是取其中的某個點是最好的。同理所求的右下角是取「右下方沒有點」的點是最好的。我們可以$O(n)$找出所有的這樣的點（之後分別叫他們$X$陣列和$Y$陣列），所以現在我們得到了一個樸素的算法：在這些點之間枚舉左上角和右下角，計算其中包含了多少點。但這樣太慢了，我們反過來考慮一個點對哪些矩形有貢獻，對於某個點$P$，考慮所有落在$P$左上方的$X$陣列中的點，和落在$P$右下方的$Y$陣列中的點，那麼任取前者中的一個點和後者中的一個點形成的矩形都可以包住這個點，因此如果我們幫$X$陣列中的數編號$1,...,n_x$，$Y$陣列則編號$1,...,n_y$，那麼一個矩形就可以表示成一個平面上的點，以左上角的編號和右下角的編號來表示。並且我們把每個矩形內的點數寫在他對應的點上，那麼就可以用以下方式來得到所有點的數值：枚舉每個原題中的點，找出他對哪些矩形有貢獻，而被貢獻的這些矩形們的集合對應到的點就會形成一個矩形區域，並且我們需要把這個矩形區域中的點值都$+1$。於是這樣就轉換為新的問題了：平面上有好幾個矩形，問被最多矩形覆蓋的點被覆蓋了幾次，而這可以用個掃描線來做，只需要維護一個最大值線段樹，並支援區間加值操作就可以了。
code :
假設我們交換的兩數分別為$x,y$，那麼對於那些數值不是落在$x,y$之間的數，交換之後並不會影響這些數和$x,y$之間的逆序數對數，不管這些數落在交換的兩位置的左右還是中間。對於那些數值落在$x,y$之間的數，只有當他的位子落在交換的兩數字位置之間才會影響逆序數對的數量。由此就可以推出，我們交換的兩個數一定是左邊大右邊小的，才可以讓交換後逆序數對減少越多。假設交換的兩數位置分別為$i,j$，數字則為$x,y$，那麼逆序數對的變化就會等於$2\times $位子落在$i,j$之間的介於$x,y$之間數的個數$+1$（還要加上交換的兩數形成的逆序數對）。這樣就可以轉化為平面上點集的問題了：把$(i,a[i])$看成座標平面上的點，那麼我們要的就是一個矩形的左上角和右下角，使得這個矩形內包含最多的點。考慮所有「左上方沒有點」的點，那麼不難知道所求矩形的左上角一定是取其中的某個點是最好的。同理所求的右下角是取「右下方沒有點」的點是最好的。我們可以$O(n)$找出所有的這樣的點（之後分別叫他們$X$陣列和$Y$陣列），所以現在我們得到了一個樸素的算法：在這些點之間枚舉左上角和右下角，計算其中包含了多少點。但這樣太慢了，我們反過來考慮一個點對哪些矩形有貢獻，對於某個點$P$，考慮所有落在$P$左上方的$X$陣列中的點，和落在$P$右下方的$Y$陣列中的點，那麼任取前者中的一個點和後者中的一個點形成的矩形都可以包住這個點，因此如果我們幫$X$陣列中的數編號$1,...,n_x$，$Y$陣列則編號$1,...,n_y$，那麼一個矩形就可以表示成一個平面上的點，以左上角的編號和右下角的編號來表示。並且我們把每個矩形內的點數寫在他對應的點上，那麼就可以用以下方式來得到所有點的數值：枚舉每個原題中的點，找出他對哪些矩形有貢獻，而被貢獻的這些矩形們的集合對應到的點就會形成一個矩形區域，並且我們需要把這個矩形區域中的點值都$+1$。於是這樣就轉換為新的問題了：平面上有好幾個矩形，問被最多矩形覆蓋的點被覆蓋了幾次，而這可以用個掃描線來做，只需要維護一個最大值線段樹，並支援區間加值操作就可以了。
code :
2015年5月14日 星期四
[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 :
訂閱：
文章 (Atom)