這題是有趣的題目
有很漂亮的O(n)解法
-> dfs兩次
第一次求出該節點以下的 1. 和, 2. 平方和, 3. 節點數
接下來就可以求出每個節點的距離平方和了
因為（距離加一）平方＝距離平方＋2*距離和＋1
http://codepad.org/lt6iItAv
2012年4月27日 星期五
2012年4月26日 星期四
tioj 1445 機器人組裝大賽
這是我第一次寫次小生成樹！
我的想法是這樣的：
先找出最小生成樹，做成一棵樹。
枚舉每個節點，使他遍歷這棵樹一遍，
對於每個有另一不屬於這棵樹的邊的節點
ANS = MIN( ANS , VMST + DIS[i][j] - 此路徑中最大的邊 )
原因如下：
上述作法相當於 -> 枚舉加入所有不屬於樹的邊，並將形成了環中的最大邊拔掉，求出權重和
http://codepad.org/oOGCuYQa
我的想法是這樣的：
先找出最小生成樹，做成一棵樹。
枚舉每個節點，使他遍歷這棵樹一遍，
對於每個有另一不屬於這棵樹的邊的節點
ANS = MIN( ANS , VMST + DIS[i][j] - 此路徑中最大的邊 )
原因如下：
上述作法相當於 -> 枚舉加入所有不屬於樹的邊，並將形成了環中的最大邊拔掉，求出權重和
http://codepad.org/oOGCuYQa
2012年4月21日 星期六
tioj 1333 番茄小豆湯
Dancing Links( Knuth實在太罩了 )
其實我從來都沒有寫過link，結果第一次就寫了dancing links
感覺起來真的超級複雜的＝＝
寫了80 行，又多又醜真是太糟糕了QQ
先講講概念再來說實作好了XD
概念：
先討論Links, 平常人在用Links時，他是用指標來互相只來只去的一種資料結構。普通人主要是用他的快速刪除機制，而當一個程式設計師把一個點刪除時，為了安全與保險，通常會把它的left跟right都指向自己或NULL，因為他們覺得有一個外面的東西可以連進去是危險的。
但是Dancing Links實在是超級活躍的～，他用到的概念是這樣的，他反其道而行，故意讓自己的左右維持不變，這時你就可以快速的把被刪掉的東西UNDO囉！XD
不要以為這只是個耍耍廢的常識，這可是2000年Knuth教授發表的超強論文中的關鍵所在阿！有了基礎後就要進入應用了。這個性質（刪去用復原）感覺就非常的DFS，很有回溯的味道，他超棒的用處就在於加快暴搜速度，大概看一下這個題目（也就是所謂的精準覆蓋），你會發現他越到後面，其實有很多行列根本完全不需要去尋找，卻要一直去花那可憐的n^2，這時心中就冒出一種想法，乾脆把它刪掉吧！Dancing Links就如此的誕生了～（在Knuth的腦中XD），你就不斷的在搜尋時將他刪除刪除刪除，之後再將他補回補回補回，就可以進行回溯法了～
實作：
有了概念後，一切都只剩下如何實作了，說到實作就快崩壞＝＝，居然寫了快100行，我會把code放在後面，但是還是不要看比較好，我直接講作法，簡單易懂。首先要討論如何去記錄，有些人會把每一個node當成是某一個只是個node的東西（存取位置不具有上下左右的，像這個），但我把它寫成陣列，接下來就是要連接每一個點了，如果是0的話，其實可以直接跳過去，不需要連接以增快速度，像下圖這個矩陣，就可以轉為下下圖。
喔對，忘記說一件事情，為了達到快速的效率，我們使用的是十字Link List，所以需要四個東西R[][]，L[][]，U[][]，D[][]（上下左右），然後為了其中使用上的方便，我們會多增加一個S[]，代表每列有幾個點。再來就是，除了下圖這些點，還需要多m個點（矩陣為n*m），代表著整列，並要加上一個header，也就是一切的總指揮（類似），建完圖後大致就如下下圖所示。（這樣我就寫了30行，真是有點難建）
其實我從來都沒有寫過link，結果第一次就寫了dancing links
感覺起來真的超級複雜的＝＝
寫了80 行，又多又醜真是太糟糕了QQ
先講講概念再來說實作好了XD
概念：
先討論Links, 平常人在用Links時，他是用指標來互相只來只去的一種資料結構。普通人主要是用他的快速刪除機制，而當一個程式設計師把一個點刪除時，為了安全與保險，通常會把它的left跟right都指向自己或NULL，因為他們覺得有一個外面的東西可以連進去是危險的。
L[R[x]] = L[x]; R[L[x]] = R[x];
但是Dancing Links實在是超級活躍的～，他用到的概念是這樣的，他反其道而行，故意讓自己的左右維持不變，這時你就可以快速的把被刪掉的東西UNDO囉！XD
L[R[x]] = x; R[L[x]] = x;
實作：
有了概念後，一切都只剩下如何實作了，說到實作就快崩壞＝＝，居然寫了快100行，我會把code放在後面，但是還是不要看比較好，我直接講作法，簡單易懂。首先要討論如何去記錄，有些人會把每一個node當成是某一個只是個node的東西（存取位置不具有上下左右的，像這個），但我把它寫成陣列，接下來就是要連接每一個點了，如果是0的話，其實可以直接跳過去，不需要連接以增快速度，像下圖這個矩陣，就可以轉為下下圖。
喔對，忘記說一件事情，為了達到快速的效率，我們使用的是十字Link List，所以需要四個東西R[][]，L[][]，U[][]，D[][]（上下左右），然後為了其中使用上的方便，我們會多增加一個S[]，代表每列有幾個點。再來就是，除了下圖這些點，還需要多m個點（矩陣為n*m），代表著整列，並要加上一個header，也就是一切的總指揮（類似），建完圖後大致就如下下圖所示。（這樣我就寫了30行，真是有點難建）
再來要講的就是刪除列跟插入列了，除了原本的兩式可以把整列跳掉，還要順便把那列為1的row一同砍掉。而輸入就是刪除的反操作。最後就只剩下DFS內容了，內容很簡單，先找出有最少1的列（使分支度降低），將此列滿足（用for）將每種都跑過一遍，並將跟所選row有重疊的row一併刪除，如此遞迴下去，及得所求。
http://codepad.org/kqDiKX4V
許許多多的參考資料都可以在網路上取得～
2012年4月20日 星期五
tioj 1515 似曾相識
首先要先對名詞有點概念：
- suffix：hello, ello, llo, lo, o 皆為hello的後綴
- sa[i]（後綴數組）：問某個名次是第幾個後綴
- ra[i]（排名數組）：問某個後綴是第幾名
- lcp( i, j ) ： 問第 i 個後綴與第 j 個後綴的最長共同前綴
- LCP( i, j ) ： 問第 i 名與第 j 名的最長共同前綴
- height[i] : 問第 i 名跟第 i -1 名的最長共同前綴
- h[i] : 問第 i 個後綴與排在第 i 個後綴前一名最長共同前綴
大致記一記之後，就要進入演算法的部份了。
1. SA_MAKER ( Doubling Algorithm ):
概念：當你有某字串的前半排名與後半排名，你便可以得到他的排名。故你先一次求得每單一字母的排名（用Counting），接著用一變二，二變四，四變八...，logn快速求得，故他稱為doubling algorithm。
實作：
int ws[MAXN], wv[MAXN], wa[MAXN], wb[MAXN];
bool cmp( int *r, int a, int b, int l, int n )
{ return r[a] == r[b] && r[a+l] == r[b+l]; }
void SA_maker( char* str, int* sa, int n, int m ){
int i, p = 0, *x = wa, *y = wb;
for( i = 0 ; i < m ; i++ ) ws[i] = 0;
for( i = 0 ; i < n ; i++ ) ws[ (x[i] = (int)str[i]) ]++;
for( i = 1 ; i < m ; i++ ) ws[i] += ws[i-1];
for( i = 0 ; i < n ; i++ ) sa[ --ws[x[i]] ] = i;
for( int l = 1 ; p < n ; l*=2, m = p ){
// sort the second element
for( i = n-l, p = 0 ; i < n ; i++ ) y[p++] = i;
for( i = 0 ; i < n ; i++ ) if( sa[i] >= l ) y[p++] = sa[i]-l;
for( i = 0 ; i < n ; i++ ) wv[i] = x[y[i]];
// sort the first element
for( i = 0 ; i < m ; i++ ) ws[i] = 0;
for( i = 0 ; i < n ; i++ ) ws[wv[i]]++;
for( i = 1 ; i < m ; i++ ) ws[i] += ws[i-1];
for( i = n-1 ; i >= 0 ; i-- ) sa[ --ws[wv[i]] ] = y[i];
// Get value
swap( x, y ); x[sa[0]] = 0;
for( i = 1, p = 1 ; i < n ; i++ )
x[sa[i]] = cmp( y, sa[i], sa[i-1], l, n ) ? p-1 : p++ ;
}
}
Reference:
m：排名值的最大值+1 sa[i]=j：第 i 名是第 j 個後綴
x[i]=j：第 i 個後綴的排名值
y[i]=j：第 i 名是第 j 個後綴（照第二元素排名）
ws[i]=j：第 i 個值的最後一個排名＋1 = j
wv[i]=j：第 i 名的先前排名值（照第二元素排名）
講解：
！這個函數有使用限制， s 的最後一個元素必須為零！
（也就是得到的sa數組要從第1個數起）
首先先得到一個個字母的排序，存在 sa[] 當中。ws[]是用來存當前的某個數值的名次。x[] 是存此位置的ranking相對值。（並非絕對的1, 2, 3, 4...，而是像1, 2, 5, 12之類的）
接下來就進入doubling的步驟：1. 排序第二元素，第一迴圈（超出去的就直接是最大的），第二迴圈（剩下的就跟sa值一樣），第三迴圈（方便之後使用）2. 排序第一元素（最終排序），此時作法與外頭對單一字母排序的方法類似，唯一差別在於要從後面開始放進來，因為y[i]是以排序過的。而且排名是從大的開是進來（--ws[wv[i]] ）。3. 得到排名值，如果一樣的話排名值相同，他使用的cmp是特製過的，他看起來會取到不該取的值，但是因為最後一個值是零，所以如果兩個相等的話，他不會超過最後一個值。
2. H_maker（LCP Theorem）:
定理1：LCP( i, j ) = min{ LCP( k-1, k ), i+1~j }
定理2：h[i] >= h[i-1]-1，當 i > 1且 ra[i] > 1
證明困難，實作簡單。
實作：
int sa[MAXN], ra[MAXN];
void H_maker( char *s, int *h, int n ){
SA_maker( s, sa, n+1, 128 );
for( int i = 1 ; i <= n ; i++ ) ra[sa[i]] = i;
for( int i = 1 ; i <= n ; i++ ){
if( ra[i] == 0 ){ h[i] = 0; continue; }
if( i == 0 || h[i-1] <= 1 ) h[i] = 0;
else h[i] = h[i-1]-1;
int x = sa[ra[i]-1], y = sa[ra[i]];
while( max(x,y)+h[i] < n && s[x+h[i]] == s[y+h[i]] ) h[i]++;
}
}
bool cmp( int *r, int a, int b, int l, int n )
{ return r[a] == r[b] && r[a+l] == r[b+l]; }
void SA_maker( char* str, int* sa, int n, int m ){
int i, p = 0, *x = wa, *y = wb;
for( i = 0 ; i < m ; i++ ) ws[i] = 0;
for( i = 0 ; i < n ; i++ ) ws[ (x[i] = (int)str[i]) ]++;
for( i = 1 ; i < m ; i++ ) ws[i] += ws[i-1];
for( i = 0 ; i < n ; i++ ) sa[ --ws[x[i]] ] = i;
for( int l = 1 ; p < n ; l*=2, m = p ){
// sort the second element
for( i = n-l, p = 0 ; i < n ; i++ ) y[p++] = i;
for( i = 0 ; i < n ; i++ ) if( sa[i] >= l ) y[p++] = sa[i]-l;
for( i = 0 ; i < n ; i++ ) wv[i] = x[y[i]];
// sort the first element
for( i = 0 ; i < m ; i++ ) ws[i] = 0;
for( i = 0 ; i < n ; i++ ) ws[wv[i]]++;
for( i = 1 ; i < m ; i++ ) ws[i] += ws[i-1];
for( i = n-1 ; i >= 0 ; i-- ) sa[ --ws[wv[i]] ] = y[i];
// Get value
swap( x, y ); x[sa[0]] = 0;
for( i = 1, p = 1 ; i < n ; i++ )
x[sa[i]] = cmp( y, sa[i], sa[i-1], l, n ) ? p-1 : p++ ;
}
}
m：排名值的最大值+1 sa[i]=j：第 i 名是第 j 個後綴
x[i]=j：第 i 個後綴的排名值
y[i]=j：第 i 名是第 j 個後綴（照第二元素排名）
ws[i]=j：第 i 個值的最後一個排名＋1 = j
wv[i]=j：第 i 名的先前排名值（照第二元素排名）
講解：
！這個函數有使用限制， s 的最後一個元素必須為零！
（也就是得到的sa數組要從第1個數起）
為了使每個logn裡之要花費 n 的時間，這邊使用的是Radix Sort，而且是不太一樣的Radix Sort，本來我寫的是用Vector做的Radix Sort，因為用Vector，速度極慢，這種寫法是在網路上東看西看發現的。
首先先得到一個個字母的排序，存在 sa[] 當中。ws[]是用來存當前的某個數值的名次。x[] 是存此位置的ranking相對值。（並非絕對的1, 2, 3, 4...，而是像1, 2, 5, 12之類的）
接下來就進入doubling的步驟：1. 排序第二元素，第一迴圈（超出去的就直接是最大的），第二迴圈（剩下的就跟sa值一樣），第三迴圈（方便之後使用）2. 排序第一元素（最終排序），此時作法與外頭對單一字母排序的方法類似，唯一差別在於要從後面開始放進來，因為y[i]是以排序過的。而且排名是從大的開是進來（--ws[wv[i]] ）。3. 得到排名值，如果一樣的話排名值相同，他使用的cmp是特製過的，他看起來會取到不該取的值，但是因為最後一個值是零，所以如果兩個相等的話，他不會超過最後一個值。
2. H_maker（LCP Theorem）:
定理1：LCP( i, j ) = min{ LCP( k-1, k ), i+1~j }
定理2：h[i] >= h[i-1]-1，當 i > 1且 ra[i] > 1
證明困難，實作簡單。
實作：
int sa[MAXN], ra[MAXN];
void H_maker( char *s, int *h, int n ){
SA_maker( s, sa, n+1, 128 );
for( int i = 1 ; i <= n ; i++ ) ra[sa[i]] = i;
for( int i = 1 ; i <= n ; i++ ){
if( ra[i] == 0 ){ h[i] = 0; continue; }
if( i == 0 || h[i-1] <= 1 ) h[i] = 0;
else h[i] = h[i-1]-1;
int x = sa[ra[i]-1], y = sa[ra[i]];
while( max(x,y)+h[i] < n && s[x+h[i]] == s[y+h[i]] ) h[i]++;
}
}
2012年4月17日 星期二
tioj 1446 H遊戲秘笈
我打這邊的目的完全是為了防止 J睿 嗆我。
這次我完全是被 tioj 表，我 wa 了半天跑去找shik大神
他重傳了我的code就AC了，我重傳了某一次RE的code
也就瞬間AC了，請不要嗆我，這一切都是tioj的錯XDDD
這只是個sort題，我了解的，請不要嗆我XDDD
我寫了一個Trie版，跑很快XD
可是估算了一下會MLE就不傳了XD
Trie: http://codepad.org/Hy38MsZV
Sort: http://codepad.org/zEVSvoaI
這次我完全是被 tioj 表，我 wa 了半天跑去找shik大神
他重傳了我的code就AC了，我重傳了某一次RE的code
也就瞬間AC了，請不要嗆我，這一切都是tioj的錯XDDD
這只是個sort題，我了解的，請不要嗆我XDDD
我寫了一個Trie版，跑很快XD
可是估算了一下會MLE就不傳了XD
Trie: http://codepad.org/Hy38MsZV
Sort: http://codepad.org/zEVSvoaI
2012年4月13日 星期五
tioj 1253 炮打皮皮
由定理：二分圖最大配對＝最小點覆蓋。
這題就可以轉成求二分圖的最大匹配。
因為是二分圖，所以可以寫的很小很可愛XD
http://codepad.org/yPUbb2XL
這題就可以轉成求二分圖的最大匹配。
因為是二分圖，所以可以寫的很小很可愛XD
http://codepad.org/yPUbb2XL
2012年4月6日 星期五
tioj 1210 圖論 之 簡單圖測試
先想一下再來討論接下來的內容
其實題目就是給一個 di 的集合，問可否形成一簡單圖。
1. 對任意圖 sum of di 必為二的倍數（理由過於簡單自己想）
2. 對任意簡單圖，任一 di 必 <= ( n-1 ) 。
接下來的討論都是建構在以上兩假設成立的情況。
有兩種判斷方式
第一個是Erdős–Gallai theorem ( Online proof <- 較嚴謹?! )
定理：
在 di 有大到小排列過後，此序列為簡單圖
若且為若對於任意的 1<= k <= n-1，sum(1~k) di <= k(k-1) + sum(k+1~n) min( di, k )
證明：
（->）k(k-1)+sum(k+1~n) min( di, k ) 為最大上限，前項代表的就是前面k個點，每個都互相連接，後項則為除那些k點外的點與此k點最大的連結數量（min的原因是點數(k)有限）。
（<-）我們用反證法，若此序列無法畫成簡單圖，則一定可以找到某一k使得sum(1~k) > k(k-1) + sum(k+1~n) min( di, k )。
至於為什麼要排序過的原因其實是，此式子最最基本的想法應該是要判斷每一種分法，但是若有一種分法，他左邊的某一元素小於右邊的，則你將他們對調，會使得此不等是更不容易成立，故直接 O(n) 看過排序後的序列，不但更省時而且是對的。
我覺得我的證明比他的好XD
第二個是 Havel 定理
定理：
有一個度序列 x = {d1, d2, d3, d4 ... } 且d1>=d2>=d3>=...，若且為若此度序列可畫為簡單圖，則另一度序列x' = { d2-1, d3-1, d4-1, ... d(d1)-1, d(d1+1), ... dn }可畫為簡單圖。
證明：
（<-）若 x' 為可圖序列，加上一點d1，並與其他的 d1 個點相連，則此圖仍為簡單圖。
（->）若 G 中存在 ( v1, v2 ) & ( v1, v3 ) & ( v1, v4 ) ...，將這些邊都去掉並拔掉 v1 後，不會影響他的簡單圖性質。如果G不如上述，亦即存在某( v1, vi )不屬於G，但( v1, vj )屬於G（其中 i<j）
因為 di >= dj 故必定可以找到一個點 k ，( vi, vk ) 屬於G，但( vj, vk ) 不屬於G，即可將邊做一點調換，但不改變度序列，即可回到上述的情況。
O( n ) 算法： http://codepad.org/LoHkJa4K
其實題目就是給一個 di 的集合，問可否形成一簡單圖。
1. 對任意圖 sum of di 必為二的倍數（理由過於簡單自己想）
2. 對任意簡單圖，任一 di 必 <= ( n-1 ) 。
接下來的討論都是建構在以上兩假設成立的情況。
有兩種判斷方式
第一個是Erdős–Gallai theorem ( Online proof <- 較嚴謹?! )
定理：
在 di 有大到小排列過後，此序列為簡單圖
若且為若對於任意的 1<= k <= n-1，sum(1~k) di <= k(k-1) + sum(k+1~n) min( di, k )
證明：
（->）k(k-1)+sum(k+1~n) min( di, k ) 為最大上限，前項代表的就是前面k個點，每個都互相連接，後項則為除那些k點外的點與此k點最大的連結數量（min的原因是點數(k)有限）。
（<-）我們用反證法，若此序列無法畫成簡單圖，則一定可以找到某一k使得sum(1~k) > k(k-1) + sum(k+1~n) min( di, k )。
至於為什麼要排序過的原因其實是，此式子最最基本的想法應該是要判斷每一種分法，但是若有一種分法，他左邊的某一元素小於右邊的，則你將他們對調，會使得此不等是更不容易成立，故直接 O(n) 看過排序後的序列，不但更省時而且是對的。
我覺得我的證明比他的好XD
第二個是 Havel 定理
定理：
有一個度序列 x = {d1, d2, d3, d4 ... } 且d1>=d2>=d3>=...，若且為若此度序列可畫為簡單圖，則另一度序列x' = { d2-1, d3-1, d4-1, ... d(d1)-1, d(d1+1), ... dn }可畫為簡單圖。
證明：
（<-）若 x' 為可圖序列，加上一點d1，並與其他的 d1 個點相連，則此圖仍為簡單圖。
（->）若 G 中存在 ( v1, v2 ) & ( v1, v3 ) & ( v1, v4 ) ...，將這些邊都去掉並拔掉 v1 後，不會影響他的簡單圖性質。如果G不如上述，亦即存在某( v1, vi )不屬於G，但( v1, vj )屬於G（其中 i<j）
因為 di >= dj 故必定可以找到一個點 k ，( vi, vk ) 屬於G，但( vj, vk ) 不屬於G，即可將邊做一點調換，但不改變度序列，即可回到上述的情況。
O( n ) 算法： http://codepad.org/LoHkJa4K
訂閱：
文章 (Atom)