今天無聊，做起CSC3270四道數據結構習作。
PKU1182 食物链
依據路徑壓縮，可以對x-->y帶三種標號﹕ label(x) = 0 (x 與 y 同類), 1 (x 吃 y), 2 (y 吃 x)。
計算路徑計縮時必須先取x的根點, rx。 對於find(x)一遍後，最多只有這種結構﹕x-->y-->rx。假設它是合法的，那麼label(x)的更新必然是(label(x) + label(y))%3 (可用簡單向量理解)，然後對x進行路徑壓縮。
要判斷x y的關係，先尋找它們的根rx及ry。如果rx == ry，可以直接判同類(label(x) = label(y))或者x吃y ((label(x) - label(y) + 3) % 3 == 1 及 x != y)。
若rx != ry 顯然不會有矛盾。這意味著可以通過并合兩者來構造新的樹。對於x-->rx-->ry<--y，若果認為x跟y是同類的話，必有label(x) + label(rx) = 0 + label(y)。若果認為x吃y的話則有label(x) + label(rx) = 1 + label(y)。繼乎直接更新label和進行普通union就成。
PKU2481 Cows
如果任何可以強於[Si, Ei]的牛[Sj, Ej]，必須有Sj <= Si和 Ei <= Ej。可以想到當我們從最大的E值開始，相同E值的依最小S值來處理線段的話，保証處理當前線段時，所有強於它的線段都已經處理過了(並且不強於它的線段沒有被處理過)。此刻強於線段i的已處理線段必然都有<=Si的值。因此我們可以憑已處理並少於等於Si的S值進行統計並計算答案。然後把Si加進表中。這裡我們直接使用樹狀數組。對於重覆的[S, E]值，我們直接用上一個處理線段的值，因兩者有相等答案。緊記亦需把它加進數組中。
PKU2777 Count Color
純粹普通線段樹應用。一種顏色可用一個位元來記著。
PKU1442 Black Box
用最大堆及最小堆。每次把新的數放進最大堆。只要當前最大堆的大小超過counter，便把它放到最小堆內。最大堆永遠保持首counter小的數。最小堆的最小值便是答案，記得把它放會最大堆中。
2010年5月21日 星期五
2009年7月16日 星期四
PKU 1466 Boys and Girls
想不到這道是若干年後被改難然後翻炒…
題意說給出N人，每人會對某幾個人有關係，問最多可以選多少人，使得這群人互相不會有關係。
如果把沒有關係的人連一條邊，題目正好就是求Maximum Clique。不過這道題給的不是這條邊，而是赤裸裸的告訴你這是二分圖。明顯地求Maximum Independent Set。輕輕用簡單的二分圖匹配就搞定了。
至於難版的那個，只是沒有這般赤裸裸而已…
題意說給出N人，每人會對某幾個人有關係，問最多可以選多少人，使得這群人互相不會有關係。
如果把沒有關係的人連一條邊，題目正好就是求Maximum Clique。不過這道題給的不是這條邊，而是赤裸裸的告訴你這是二分圖。明顯地求Maximum Independent Set。輕輕用簡單的二分圖匹配就搞定了。
至於難版的那個，只是沒有這般赤裸裸而已…
PKU3680 Intervals
如此這般，開始寫中文。
以後頹題難題只要解了就寫。
先說這道題，大意就是給定一堆Open Intervals，要保証選取某些Intervals使實數軸上的數字不會被覆蓋超過
次，並且把選取的Intervals的獲利總數最大化。
好的，看起來很複雜對吧？不難發現用任何DP方法都應該得不到正確的結果。於是我們從題意直接著手。就取Sample最後一例說明吧。
把Intervals(不按比例)畫出來會成這個樣子﹕
1: |-----------------------------------------|
2: |--------------|
3: |---------------|
----------------------------------------------
1 100 150 200 10萬
假設第i區間取次Xi，從Sample我們可得X1, X2, X3。
把Intervals作離散化，可以得到以下4道不等式。同色Intervals代表屬同一不等式。
X1 + X2 <= K .....(1)
X1 + X2 + X3 <= K .....(2)
X1 + X3 <= K ..... (3)
X1 <= K ..... (4)
一般來說處理不等式都不好辦，我們嘗試引入鬆弛量(不是熊) Slack Variables，讓不等試變等式。
X1 + X2 + Y1 = K .....(1)
X1 + X2 + X3 + Y2 = K .....(2)
X1 + X3 + Y3 = K ..... (3)
X1 + Y4 = K ..... (4)
若果讓第i式與第i+1式相減(不包括i = 4)，按植樹原理可以得3式﹕
(2) - (1): X3 + Y2 = Y1
(3) - (2): Y3 = X2 + Y2
(4) - (3): Y4 = X3 + Y3
補上(1)及(4)，可得以下5式﹕
X1 + X2 + Y1 = K
X3 + Y2 = Y1
Y3 = X2 + Y2
Y4 = X3 + Y3
K = X1 + Y4 (我把這式倒轉了)
你可以發現，左式相加，就是右式，恰好得到了F=F這個結論。 我們再想深一層，如果套用 F_in = F_out，就是網絡流的守衡定律﹗(Flow Conservation) 若左式是代表入流量，右式便正好了是代表出流量。式子間的關係就可以靠變量來連繫了(比如出流式3聯繫了入流式2)。由此我們可以看式子就是點，變數就是 邊。假如變數X在第i式是出流，在第j式是入流，圖裡便有一條邊 i---->j。相通了這相的東西後，你可以利用變數Xi和Yi來構出一張圖。不過你會發現一件事﹕
(1) Constant怎樣處理？
(2) Source和Sink在哪？
想到這裡，你便猜到Constant的出入流正是對應Source和Sink。
好了。圖是出來了。問題是網絡中的Capacity到底是怎樣？
我們可以這樣分類﹕
Xi: 它代表選或不選第i個interval，故此Capacity頂多是1。
Yi: 它是調節不等式的變數，其值有修正不等式作用，故Capacity可取任意 (即無限)。
常數﹕就是Source / Sink的Capacity。
因 為這題不是要我們選最多的Intervals，而是把獲利最大化，我們便要考慮最小費用流(Min Cost Flow)。費用從何而定？當然費用就是選取Xi與否。故代表Xi的費用就是-Ci，基於最小費用流下我們可以得最小的負數費用(最後把它再負一次便 成)。最後構圖如下﹕
顯然易見，費用流得出最小費用為-100301，取絕對值便是答案。
問題來了﹕構圖不易。
留意以下觀察。
(1) 不失一般性，假設第i個interval的超始點必不多於第i+1個。構建式子時，若第P式開始出現變量Xi，Xi最後出現在式子Q，肯定Xi不會無故於P至Q式之間消失。因為Interval是連續嘛…
(2) 利用兩連續式相減，P式子減去P-1式子時必然利剩下Xi在左式(這不用証明吧…)。當Q+1式減Q式時，該式子的右邊必然出現Xi(取同樣道理)。至此 若果完全明白的話，你會明白為何第1式必須留下，原因是第一式首次出現的變數沒有上一式可以減，反而式子本身就有它們在了。而最後一式最倒轉也是基於這個 原理。
(3) 假設有N等式。經此構造會有 N-1 兩兩相減式 + 2 首尾式 = N+1 式。其中如果第i式左邊出現Yi，右式因為相減下令Yi出現在第i+1式的右邊。
由此得知，若Xi出現在式子P至Q之間，肯定得出邊 (Q+1)-->P。亦可以發現Source必須接N+1式，1式必須接Sink。因此無需處理複雜式子間關係才能構圖。
問題又來了﹕如何得知式子數？
這 問題是對離散化不熟悉的人最常見的(我也是)。一般構建方法可以記錄Intervals的Start及End，對應+1或-1然後便知變數屬甚麼範圍的式 子。此方正確但難以處理區間邊緣重疊的問題，容易出錯。我的做法是把所有Intervals的起點終點的**唯一數字**排序，那麼這個數字的次序便對應 起點的出現在甚麼式子的左邊，和終結時變數應該會在甚麼式子的右式出現。再以Sample為例，可以如下數字﹕
次序 | 1 2 3 4 5
數字 | 1 100 150 200 100000
取第二Interval為例，X2出現在第1式的左邊和第3式的右邊，故此得出3-->1的邊。
知道這個便是貼模版的時候。你會發覺不對勁﹕負邊用Bellman-Ford會否出現Negative Cycle?答案是否定的。Negative Cycle不會出現在這種構圖中，你可以再慢慢証明。然而當你放心貼上Bellman-Ford的時候，會發現PKU上會說TLE…因此，你可以嘗試用用 SPFA(Shortest Path Faster Algorithm)。然後，又是超時。原因是，SPFA對層圖處理比較慢，所以要加上優化。只要加上SLF(Shortest Label First)即可以極速AC。再加上LLL(Largest Label Last)只是錦上添花，想嘗試寫寫亦無傷大雅。
以後頹題難題只要解了就寫。
先說這道題，大意就是給定一堆Open Intervals，要保証選取某些Intervals使實數軸上的數字不會被覆蓋超過
好的，看起來很複雜對吧？不難發現用任何DP方法都應該得不到正確的結果。於是我們從題意直接著手。就取Sample最後一例說明吧。
把Intervals(不按比例)畫出來會成這個樣子﹕
1: |-----------------------------------------|
2: |--------------|
3: |---------------|
----------------------------------------------
1 100 150 200 10萬
假設第i區間取次Xi，從Sample我們可得X1, X2, X3。
把Intervals作離散化，可以得到以下4道不等式。同色Intervals代表屬同一不等式。
X1 + X2 <= K .....(1)
X1 + X2 + X3 <= K .....(2)
X1 + X3 <= K ..... (3)
X1 <= K ..... (4)
一般來說處理不等式都不好辦，我們嘗試引入鬆弛量(不是熊) Slack Variables，讓不等試變等式。
X1 + X2 + Y1 = K .....(1)
X1 + X2 + X3 + Y2 = K .....(2)
X1 + X3 + Y3 = K ..... (3)
X1 + Y4 = K ..... (4)
若果讓第i式與第i+1式相減(不包括i = 4)，按植樹原理可以得3式﹕
(2) - (1): X3 + Y2 = Y1
(3) - (2): Y3 = X2 + Y2
(4) - (3): Y4 = X3 + Y3
補上(1)及(4)，可得以下5式﹕
X1 + X2 + Y1 = K
X3 + Y2 = Y1
Y3 = X2 + Y2
Y4 = X3 + Y3
K = X1 + Y4 (我把這式倒轉了)
你可以發現，左式相加，就是右式，恰好得到了F=F這個結論。 我們再想深一層，如果套用 F_in = F_out，就是網絡流的守衡定律﹗(Flow Conservation) 若左式是代表入流量，右式便正好了是代表出流量。式子間的關係就可以靠變量來連繫了(比如出流式3聯繫了入流式2)。由此我們可以看式子就是點，變數就是 邊。假如變數X在第i式是出流，在第j式是入流，圖裡便有一條邊 i---->j。相通了這相的東西後，你可以利用變數Xi和Yi來構出一張圖。不過你會發現一件事﹕
(1) Constant怎樣處理？
(2) Source和Sink在哪？
想到這裡，你便猜到Constant的出入流正是對應Source和Sink。
好了。圖是出來了。問題是網絡中的Capacity到底是怎樣？
我們可以這樣分類﹕
Xi: 它代表選或不選第i個interval，故此Capacity頂多是1。
Yi: 它是調節不等式的變數，其值有修正不等式作用，故Capacity可取任意 (即無限)。
常數﹕就是Source / Sink的Capacity。
因 為這題不是要我們選最多的Intervals，而是把獲利最大化，我們便要考慮最小費用流(Min Cost Flow)。費用從何而定？當然費用就是選取Xi與否。故代表Xi的費用就是-Ci，基於最小費用流下我們可以得最小的負數費用(最後把它再負一次便 成)。最後構圖如下﹕
問題來了﹕構圖不易。
留意以下觀察。
(1) 不失一般性，假設第i個interval的超始點必不多於第i+1個。構建式子時，若第P式開始出現變量Xi，Xi最後出現在式子Q，肯定Xi不會無故於P至Q式之間消失。因為Interval是連續嘛…
(2) 利用兩連續式相減，P式子減去P-1式子時必然利剩下Xi在左式(這不用証明吧…)。當Q+1式減Q式時，該式子的右邊必然出現Xi(取同樣道理)。至此 若果完全明白的話，你會明白為何第1式必須留下，原因是第一式首次出現的變數沒有上一式可以減，反而式子本身就有它們在了。而最後一式最倒轉也是基於這個 原理。
(3) 假設有N等式。經此構造會有 N-1 兩兩相減式 + 2 首尾式 = N+1 式。其中如果第i式左邊出現Yi，右式因為相減下令Yi出現在第i+1式的右邊。
由此得知，若Xi出現在式子P至Q之間，肯定得出邊 (Q+1)-->P。亦可以發現Source必須接N+1式，1式必須接Sink。因此無需處理複雜式子間關係才能構圖。
問題又來了﹕如何得知式子數？
這 問題是對離散化不熟悉的人最常見的(我也是)。一般構建方法可以記錄Intervals的Start及End，對應+1或-1然後便知變數屬甚麼範圍的式 子。此方正確但難以處理區間邊緣重疊的問題，容易出錯。我的做法是把所有Intervals的起點終點的**唯一數字**排序，那麼這個數字的次序便對應 起點的出現在甚麼式子的左邊，和終結時變數應該會在甚麼式子的右式出現。再以Sample為例，可以如下數字﹕
次序 | 1 2 3 4 5
數字 | 1 100 150 200 100000
取第二Interval為例，X2出現在第1式的左邊和第3式的右邊，故此得出3-->1的邊。
知道這個便是貼模版的時候。你會發覺不對勁﹕負邊用Bellman-Ford會否出現Negative Cycle?答案是否定的。Negative Cycle不會出現在這種構圖中，你可以再慢慢証明。然而當你放心貼上Bellman-Ford的時候，會發現PKU上會說TLE…因此，你可以嘗試用用 SPFA(Shortest Path Faster Algorithm)。然後，又是超時。原因是，SPFA對層圖處理比較慢，所以要加上優化。只要加上SLF(Shortest Label First)即可以極速AC。再加上LLL(Largest Label Last)只是錦上添花，想嘗試寫寫亦無傷大雅。
訂閱：
文章 (Atom)
