2015年8月8日 星期六

各種code分享

裡面放了我寫過的Online Judge的 code ,還有一些模板,之後應該會比較少增加東西了。
連結

[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 :

[HOJ 283] Grid coloring

作法:

當$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 :