裡面放了我寫過的Online Judge的 code ，還有一些模板，之後應該會比較少增加東西了。
連結
2015年8月8日 星期六
[HOJ 284] PE Lesson
作法：
我們先觀察：對於一個排列，要怎麼判斷他是否可以在有限的交換次數內換回來。我們知道一個排列可以拆成很多圈，因此只要把這些圈分開研究就可以了。首先我們可以證明：對於每個圈，他能夠換完並且滿足限制的充要條件為：圈上的只能換一次的人數$\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 :
我們先觀察：對於一個排列，要怎麼判斷他是否可以在有限的交換次數內換回來。我們知道一個排列可以拆成很多圈，因此只要把這些圈分開研究就可以了。首先我們可以證明：對於每個圈，他能夠換完並且滿足限制的充要條件為：圈上的只能換一次的人數$\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 :
[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 :
[CF 559E] Gerald and Path
作法：
我們把一個路燈想像成一根直立的棍子，長度為他可以照到的範圍，那麼現在就變成我們要決定他們要往左倒還是往右倒，使得總覆蓋區間最大。假設現在我們已經全部決定好了，那麼倒下的棍子們會形成好幾陀連通塊（若兩根棍子有交集則在他們之間連邊，考慮這張圖可以獲得一些連通塊），首先不難發現每個連通塊一定都是由連續的棍子所組成的，因此我們可以考慮先求出$dp[i][j]$，代表「從第$i$根到第$j$根棍子倒下後若形成一個連通塊，那麼這個連通塊有哪些可能的左右端點」，也就是一個$dp[i][j]$其實一個 vector<pair<int,int>>，裡面存了很多條線段。這邊可以再發現，如果有兩條線段是互相包含的關係，那麼顯然外面的一定比裡面的還好，因此我們可以只留下必要的線段就可以了，也就是當左端點遞增時右端點也遞增的線段們。不難得知如果我們已經有了所有的$dp[i][j]$的線段，那麼最後就可以再用個DP求出答案了，因此接下來只要關注如何轉移就可以了。
首先當$i=j$的時候顯然有兩個線段，丟進去即可。假設現在我們要算$dp[i][j]$有哪些線段，我們可以先把一些候選的線段丟進$dp[i][j]$中，最後再一次處理掉剛才所說的「被別人包含的線段」。考慮枚舉斷點$k$，那麼我們現在有$dp[i][k]$的一堆線段，還有$dp[k+1][j]$的一堆線段，我們想要用他們合成出新的線段。我們可以先假設$dp[i][k]$裡的線段是被放在左邊的線段，因為可以等一下把$dp[i][k]$和$dp[k+1][j]$交換再作一次即可。考慮枚舉$dp[i][k]$中的線段，當左邊的線段確定後，因為$dp[k+1][j]$中的線段都是當左端點遞增時右端點也遞增的，因此我們只要想辦法找到$dp[k+1][j]$中「和此左線段有交集的右端點最大的線段」就可以了，這可以用一個 lower_bound 達成。這樣轉移複雜度為$O(n^2logn)$，總複雜度為$O(n^4logn)$，不過在 codeforces 上跑得很快，可能是因為線段數量沒有到每個 dp 陣列都$O(n)$那麼多。
code :
我們把一個路燈想像成一根直立的棍子，長度為他可以照到的範圍，那麼現在就變成我們要決定他們要往左倒還是往右倒，使得總覆蓋區間最大。假設現在我們已經全部決定好了，那麼倒下的棍子們會形成好幾陀連通塊（若兩根棍子有交集則在他們之間連邊，考慮這張圖可以獲得一些連通塊），首先不難發現每個連通塊一定都是由連續的棍子所組成的，因此我們可以考慮先求出$dp[i][j]$，代表「從第$i$根到第$j$根棍子倒下後若形成一個連通塊，那麼這個連通塊有哪些可能的左右端點」，也就是一個$dp[i][j]$其實一個 vector<pair<int,int>>，裡面存了很多條線段。這邊可以再發現，如果有兩條線段是互相包含的關係，那麼顯然外面的一定比裡面的還好，因此我們可以只留下必要的線段就可以了，也就是當左端點遞增時右端點也遞增的線段們。不難得知如果我們已經有了所有的$dp[i][j]$的線段，那麼最後就可以再用個DP求出答案了，因此接下來只要關注如何轉移就可以了。
首先當$i=j$的時候顯然有兩個線段，丟進去即可。假設現在我們要算$dp[i][j]$有哪些線段，我們可以先把一些候選的線段丟進$dp[i][j]$中，最後再一次處理掉剛才所說的「被別人包含的線段」。考慮枚舉斷點$k$，那麼我們現在有$dp[i][k]$的一堆線段，還有$dp[k+1][j]$的一堆線段，我們想要用他們合成出新的線段。我們可以先假設$dp[i][k]$裡的線段是被放在左邊的線段，因為可以等一下把$dp[i][k]$和$dp[k+1][j]$交換再作一次即可。考慮枚舉$dp[i][k]$中的線段，當左邊的線段確定後，因為$dp[k+1][j]$中的線段都是當左端點遞增時右端點也遞增的，因此我們只要想辦法找到$dp[k+1][j]$中「和此左線段有交集的右端點最大的線段」就可以了，這可以用一個 lower_bound 達成。這樣轉移複雜度為$O(n^2logn)$，總複雜度為$O(n^4logn)$，不過在 codeforces 上跑得很快，可能是因為線段數量沒有到每個 dp 陣列都$O(n)$那麼多。
code :
[CF 559D] Randomizer
作法：
題目要求的是任取一個子多邊形的內部格點數期望值，顯然必須先使用 Pick's 定理，因為我們有$A=i+\frac{b}{2}-1$，所以我們只要知道子多邊形的$A$值期望值，和$b$值期望值就可以了。首先看$A$值的期望值，對於每個子多邊形，如果我們用整個多邊形去扣掉他，那麼他就會剩下一堆「頂點是原多邊形中的連續幾個點」的子多邊形。因此我們只要先算好要扣掉部份的期望值，再用原本的整個面積去扣掉就可以了。至於要如何算扣掉的部份，對於一個「頂點是原多邊形上連續幾個點」的子多邊形來說，假設他總共有$i$個頂點，那麼不難算出他總共會被算到$2^{n-i}-1$次，並且總共有$2^n-1-n-C_2^n$種子多邊形，因此有$i$個頂點的子多邊形貢獻為$\displaystyle \frac{2^{n-i}-1}{2^n-1-n-C_2^n}\times $其面積。這樣我們可以先獲得一個$O(n^2)$的算法：直接把每一項都加起來，並且在算「有$i$個頂點的子多邊形的面積總和」時可以用$i-1$個頂點的總和花$O(n)$的時間推過來。但觀察這條式子可以發現，當$i$越來越大時其倍率是指數往下跑的，因此我們可以只計算$i$很小的前幾項就好了，稍微估一下大概可以知道一直算到$i=100$左右就很夠了。
再來則是計算$b$的值，我們可以把每條邊拆開看，每條邊的貢獻會是$gcd(x$座標差$,y$座標差$)$（這樣算才能保證把子多邊形的每個邊的貢獻加起來是我們要的值），並且我們想知道他會被算到幾次。假設以這條邊切開原多邊形，所得到的子多邊形其中一邊有$k$個點，那麼不難得出他被算到的次數為：$(2^{n-2-k}-1)+(2^k-1)$，因此我們可以把他拆成兩邊看，也就是我們把主角放在「原多邊形的一段頂點區間」而不是「邊」，這樣就可以套用剛才的作法了，只要考慮那些「頂點區間夠小」的區間就可以了，也是取到長度$100$左右就很夠了。
code :
題目要求的是任取一個子多邊形的內部格點數期望值，顯然必須先使用 Pick's 定理，因為我們有$A=i+\frac{b}{2}-1$，所以我們只要知道子多邊形的$A$值期望值，和$b$值期望值就可以了。首先看$A$值的期望值，對於每個子多邊形，如果我們用整個多邊形去扣掉他，那麼他就會剩下一堆「頂點是原多邊形中的連續幾個點」的子多邊形。因此我們只要先算好要扣掉部份的期望值，再用原本的整個面積去扣掉就可以了。至於要如何算扣掉的部份，對於一個「頂點是原多邊形上連續幾個點」的子多邊形來說，假設他總共有$i$個頂點，那麼不難算出他總共會被算到$2^{n-i}-1$次，並且總共有$2^n-1-n-C_2^n$種子多邊形，因此有$i$個頂點的子多邊形貢獻為$\displaystyle \frac{2^{n-i}-1}{2^n-1-n-C_2^n}\times $其面積。這樣我們可以先獲得一個$O(n^2)$的算法：直接把每一項都加起來，並且在算「有$i$個頂點的子多邊形的面積總和」時可以用$i-1$個頂點的總和花$O(n)$的時間推過來。但觀察這條式子可以發現，當$i$越來越大時其倍率是指數往下跑的，因此我們可以只計算$i$很小的前幾項就好了，稍微估一下大概可以知道一直算到$i=100$左右就很夠了。
再來則是計算$b$的值，我們可以把每條邊拆開看，每條邊的貢獻會是$gcd(x$座標差$,y$座標差$)$（這樣算才能保證把子多邊形的每個邊的貢獻加起來是我們要的值），並且我們想知道他會被算到幾次。假設以這條邊切開原多邊形，所得到的子多邊形其中一邊有$k$個點，那麼不難得出他被算到的次數為：$(2^{n-2-k}-1)+(2^k-1)$，因此我們可以把他拆成兩邊看，也就是我們把主角放在「原多邊形的一段頂點區間」而不是「邊」，這樣就可以套用剛才的作法了，只要考慮那些「頂點區間夠小」的區間就可以了，也是取到長度$100$左右就很夠了。
code :
[CF 559B] Equivalent Strings
作法：
首先我們可以證明，題目給的等於的定義是一個「等價關係」（equivalence relation），可以對字串的長度用數學歸納法即可，因此不難證明，兩個字串是等價的若且唯若：把兩個字串都換成與他等價的字典序最小的字串，兩字串相等。而這個過程就可以用分治來解決了。
另外，這題有很多人直接寫了$O(n^2)$的解卻過了（也就是直接遞迴檢查$4$種可能的子字串配對），例如這份 code 的寫法，實際上可以證明這樣的複雜度其實是$O(n^{1.57})$的，詳細可以參考這篇 comment 。
code :
首先我們可以證明，題目給的等於的定義是一個「等價關係」（equivalence relation），可以對字串的長度用數學歸納法即可，因此不難證明，兩個字串是等價的若且唯若：把兩個字串都換成與他等價的字典序最小的字串，兩字串相等。而這個過程就可以用分治來解決了。
另外，這題有很多人直接寫了$O(n^2)$的解卻過了（也就是直接遞迴檢查$4$種可能的子字串配對），例如這份 code 的寫法，實際上可以證明這樣的複雜度其實是$O(n^{1.57})$的，詳細可以參考這篇 comment 。
code :
[HOJ 251][IOI 2008] Pyramid Base
作法：
首先考慮二分搜答案，因為如果能夠在預算內放入邊長$x$的正方形，那顯然可以放入邊長$x-1$的正方形。當確定一個邊長時，我們想要知道他可不可行，而只要注意到：我們只要決定好正方形的左上角就可以了，並且對於平面上的某個障礙物來說，考慮那些「用來當正方形左上角的話會和這個障礙物有交集的格子」，不難發現這些格子形成一個長方形（其座標不難求），因此就可以想成：如果左上角放在這個長方形裡，就要多花（這個長方形的 cost ）元。並且我們想知道這個平面上花費最少的格子是否在預算之中。因此就轉換為經典問題了：給定平面上的一些長方形，每個長方形都把內部的格子同加某個值，求整個平面的最小值是多少。這就顯然可以用掃描線+線段樹做了。
但這樣傳上去TLE了，畢竟$O(nlog^2n)$對$n\leq 400000$來說太大了。但注意到剩下只有$B=0$的情形，因此可以思考另外一種算法。考慮對於每個左界$i$，都找出最大的右界$j$，使得存在一個空的正方形，他的左右界分別為$i$和$j$。注意到如果我們把$i$到$j$這幾排全部壓成一排，並且「有和$i$到$j$交集的障礙物」都被壓成一排中的區間，那麼就變成詢問這一排中有最多連續幾個格子沒有障礙物了。因此我們可以把有交集到的障礙物的兩個$y$座標看成「把這兩數之間的所有數的位置的值都$+1$」，並且詢問的是這個數列裡有最多多少個連續的$0$，因此可以用線段樹做。這樣我們得到了$O(n^2logn)$的算法，也就是對於每個左界$i$直接一個一個往右擴展，當多遇到一個障礙物的左界，就在該區間$+1$的地方$+1$，直到查詢出來的值無法在兩邊界之間形成正方形為止。但只要注意到：如果存在一個正方形的左右邊界是$i,j$，那麼也存在左右邊界是$i+1,j$的。因此就可以改成用雙指標掃過去一次就可以了。複雜度降為$O(nlogn)$
最後提一下，這裡的線段樹必須支援：區間加$1$，區間減$1$和查詢最大連續的$0$數量，作法和「求$n$個矩形在平面上的覆蓋面積」時掃描線所用的線段樹類似，可以參考這篇。
code :
首先考慮二分搜答案，因為如果能夠在預算內放入邊長$x$的正方形，那顯然可以放入邊長$x-1$的正方形。當確定一個邊長時，我們想要知道他可不可行，而只要注意到：我們只要決定好正方形的左上角就可以了，並且對於平面上的某個障礙物來說，考慮那些「用來當正方形左上角的話會和這個障礙物有交集的格子」，不難發現這些格子形成一個長方形（其座標不難求），因此就可以想成：如果左上角放在這個長方形裡，就要多花（這個長方形的 cost ）元。並且我們想知道這個平面上花費最少的格子是否在預算之中。因此就轉換為經典問題了：給定平面上的一些長方形，每個長方形都把內部的格子同加某個值，求整個平面的最小值是多少。這就顯然可以用掃描線+線段樹做了。
但這樣傳上去TLE了，畢竟$O(nlog^2n)$對$n\leq 400000$來說太大了。但注意到剩下只有$B=0$的情形，因此可以思考另外一種算法。考慮對於每個左界$i$，都找出最大的右界$j$，使得存在一個空的正方形，他的左右界分別為$i$和$j$。注意到如果我們把$i$到$j$這幾排全部壓成一排，並且「有和$i$到$j$交集的障礙物」都被壓成一排中的區間，那麼就變成詢問這一排中有最多連續幾個格子沒有障礙物了。因此我們可以把有交集到的障礙物的兩個$y$座標看成「把這兩數之間的所有數的位置的值都$+1$」，並且詢問的是這個數列裡有最多多少個連續的$0$，因此可以用線段樹做。這樣我們得到了$O(n^2logn)$的算法，也就是對於每個左界$i$直接一個一個往右擴展，當多遇到一個障礙物的左界，就在該區間$+1$的地方$+1$，直到查詢出來的值無法在兩邊界之間形成正方形為止。但只要注意到：如果存在一個正方形的左右邊界是$i,j$，那麼也存在左右邊界是$i+1,j$的。因此就可以改成用雙指標掃過去一次就可以了。複雜度降為$O(nlogn)$
最後提一下，這裡的線段樹必須支援：區間加$1$，區間減$1$和查詢最大連續的$0$數量，作法和「求$n$個矩形在平面上的覆蓋面積」時掃描線所用的線段樹類似，可以參考這篇。
code :
2015年7月22日 星期三
[HOJ 223] H. 項鍊
作法：
$m=1$時是顯然的，$m=2$不難自己構造出來，詳細可以參考 code 。但$m=3$以上的構造就很困難了，我的作法是直接 DFS 下去，剛好因為滿足這種條件的數列蠻多的，所以可以在時限內找到。比較正常的作法應該是把他轉成尤拉迴路問題：考慮一張有$n^{m-1}$個點的有向圖，每個點都代表一個長度為$m-1$字元集$1~n$的字串，並且如果某個點$A$可以經由「在後面加上一個數並丟掉最前面的數」轉換成$B$，那麼就從$A$連到$B$一條邊。這樣邊的總數會是$n^m\leq 3\cdot 10^5$，對這張圖求尤拉迴路就可以了。
code :
$m=1$時是顯然的，$m=2$不難自己構造出來，詳細可以參考 code 。但$m=3$以上的構造就很困難了，我的作法是直接 DFS 下去，剛好因為滿足這種條件的數列蠻多的，所以可以在時限內找到。比較正常的作法應該是把他轉成尤拉迴路問題：考慮一張有$n^{m-1}$個點的有向圖，每個點都代表一個長度為$m-1$字元集$1~n$的字串，並且如果某個點$A$可以經由「在後面加上一個數並丟掉最前面的數」轉換成$B$，那麼就從$A$連到$B$一條邊。這樣邊的總數會是$n^m\leq 3\cdot 10^5$，對這張圖求尤拉迴路就可以了。
code :
[HOJ 220] E. code
作法：
如果題目沒有$i\neq j$的條件的話，式子就可以寫成$\displaystyle (\sum_{i=1}^{n} n\% i)(\sum_{i=1}^{m} m\% i)$，因此這部份可以先分開算再乘起來。至於要怎麼計算$\displaystyle \sum_{i=1}^{n} n\% i$，一樣是把商一樣的區間合併起來看，因為$n$除以從$i$一直到$n/(n/i)$（這裡是整數除法）的這些數都會得到一樣的商，所以在這個區間裡$n\% i$會是一個等差數列，可以合併起來一起算。最後則是要扣掉$i=j$的部份，也就是要計算$\displaystyle \sum_{i=1}^{min(n,m)} (n\% i)(m\% i)$，這一樣可以用剛才的技巧，只不過區間的右端點必須取成$min(m/(m/i),n/(n/i))$而已。這部份則會變成一個二次函數在一個區間裡的所有函數值的總和，而這東西不難用$\displaystyle \sum k^2$的公式求得。
code :
如果題目沒有$i\neq j$的條件的話，式子就可以寫成$\displaystyle (\sum_{i=1}^{n} n\% i)(\sum_{i=1}^{m} m\% i)$，因此這部份可以先分開算再乘起來。至於要怎麼計算$\displaystyle \sum_{i=1}^{n} n\% i$，一樣是把商一樣的區間合併起來看，因為$n$除以從$i$一直到$n/(n/i)$（這裡是整數除法）的這些數都會得到一樣的商，所以在這個區間裡$n\% i$會是一個等差數列，可以合併起來一起算。最後則是要扣掉$i=j$的部份，也就是要計算$\displaystyle \sum_{i=1}^{min(n,m)} (n\% i)(m\% i)$，這一樣可以用剛才的技巧，只不過區間的右端點必須取成$min(m/(m/i),n/(n/i))$而已。這部份則會變成一個二次函數在一個區間裡的所有函數值的總和，而這東西不難用$\displaystyle \sum k^2$的公式求得。
code :
[HOJ 218] C. osu!
作法：
首先找出圓和四條邊界的交點（如果有的話），那麼可以得到相鄰交點中間形成的弧同在矩形內部或外部，因此可以直接選這段弧的中點判斷他是在內部還外部，在內部的話就把答案加上對應的值就可以了。另外要注意圓和邊界完全沒有交點的情形，而這只要一開始就加入兩個假的斷點（$\frac{\pi}{2}$和$-\frac{\pi}{2}$）就可以了。
code :
首先找出圓和四條邊界的交點（如果有的話），那麼可以得到相鄰交點中間形成的弧同在矩形內部或外部，因此可以直接選這段弧的中點判斷他是在內部還外部，在內部的話就把答案加上對應的值就可以了。另外要注意圓和邊界完全沒有交點的情形，而這只要一開始就加入兩個假的斷點（$\frac{\pi}{2}$和$-\frac{\pi}{2}$）就可以了。
code :
[HOJ 201] TRAMPOLIN
作法：
首先我們可以把相鄰的同高度的大樓黏起來，並且紀錄好黏起來的這陀大樓原本有幾棟，而如果原本黏起來的大樓中有可以瞬移的大樓，那麼黏起來後的也可以瞬移。因此現在問題轉化為相鄰高度皆不同的問題。首先如出發點往左邊或右邊走都沒辦法達到能夠瞬移的大樓，那麼答案就是往左走或往右走的經過大樓數比較多的那個，反之假設起點可以走到某個可瞬移的大樓，那麼對於所有的制高點（旁邊沒有比他高的大樓的大樓），如果他往左（或往右）走下去之後會可以遇到能瞬移的，那麼我們就可以從起點那邊瞬移到這個制高點，走完這段後再順移回去。因此我們可以先找出所有的這樣的路徑，把他們標記成全部都可以走到。最後只要再選一個制高點然後走到底就好，枚舉看要走哪條路徑可以增加更多被走到的大樓。
code :
首先我們可以把相鄰的同高度的大樓黏起來，並且紀錄好黏起來的這陀大樓原本有幾棟，而如果原本黏起來的大樓中有可以瞬移的大樓，那麼黏起來後的也可以瞬移。因此現在問題轉化為相鄰高度皆不同的問題。首先如出發點往左邊或右邊走都沒辦法達到能夠瞬移的大樓，那麼答案就是往左走或往右走的經過大樓數比較多的那個，反之假設起點可以走到某個可瞬移的大樓，那麼對於所有的制高點（旁邊沒有比他高的大樓的大樓），如果他往左（或往右）走下去之後會可以遇到能瞬移的，那麼我們就可以從起點那邊瞬移到這個制高點，走完這段後再順移回去。因此我們可以先找出所有的這樣的路徑，把他們標記成全部都可以走到。最後只要再選一個制高點然後走到底就好，枚舉看要走哪條路徑可以增加更多被走到的大樓。
code :
訂閱：
文章 (Atom)