Problem A - Rational Resistance (by TreapKing)
你有很多很多個電阻為\(1\)的電阻器，你可以反覆做這樣的操作：1. 把一個電阻為\(1\)的電阻器拿在手上。
2. 拿一個電阻為\(1\)的電阻器跟你手上的電阻器串聯。
3. 拿一個電阻為\(1\)的電阻器跟你手上的電阻器並聯。
給你兩整數\(a, b\)，問你要湊出一個電阻為\(\frac{a}{b}\)的電阻器最少要用幾個電阻為\(1\)的電阻器？
保證輸入有解。
註：兩個電阻分別為\(x, y\)的電阻，串連後的電阻是\(x+y\)，並連後電阻是\(\frac{1}{ \frac{1}{x} + \frac{1}{y}}\)。
題解：
可以發現一個電阻為\(\frac{a}{b}\)的電阻器，加上一個電阻器之後的電阻會變成\(\frac{a+b}{a}\)或\(\frac{a}{a+b}\)，手畫了幾步之後感覺每一組\(a, b\)都只會出現一次，也就是每一組\(a, b\)都只存在唯一一個湊法，不用考慮用最少個電阻器的問題。所以就得到了一個做法：一直把小的數字當作\(a\)，大的數字當作\(a+b\)，然後把\(\frac{a}{a+b}\)變成\(\frac{a}{b}\)之類的，然後會發現這件事情長的跟輾轉相除法很像，於是就產生了下面的code。
這樣做的複雜度就跟輾轉相除法一樣，我只知道至少是\(O(lgN)\)啦。
code：http://codeforces.com/contest/343/submission/15429853
Problem B - Alternating Current (by TreapKing)
給你兩個兩端都黏死的電線的每個交叉點是哪一條在上面，問你可不可以在不拆掉左右黏死的部分，把纏繞的部分拆掉。
像這張圖，輸入就會是-++-，只要把中間的兩個紅色在上的翻好，再把兩個藍色在上的翻好就拆完了(覺得自己翻的很爛....可以考慮自己去讀原題QQ)。
題解：
總覺得這題有強烈的既視感，好像是以前在ioicamp寫過。
思考一陣後會發現，兩個相鄰的++或--就可以把他拆開來，也就是直接消掉一個++或--。如果這樣可以把整個序列消完就是Yes，消不完就是No。
然後會發現這個東西其實跟括弧匹配蠻像的，所以可以用stack做。
這樣做的複雜度是\(O(N)\)。
Problem C - Read Time (by TreapKing)
可以想成有\(N\)個人分別站在\(h_1, h_2, ... , h_N\)的位子上，有\(M\)個地方要探查(探查不用花時間，其實就是被人踩過)，分別是\(p_1, p_2, .., p_M\)，每個人一單位時間可以走一單位長度而且每個人的移動互相獨立，問你最少要花多少時間才能探查到所有需要探查的點？也就是所有需要被踩到的點都被至少一個人踩到要花多少時間。
題解：
看到Note寫的東西就覺得可以二分搜答案，經過思考後會發現如果a人在左邊b人在右邊，那麼讓a負責的部分完全在b負責的部分的左邊一定不會比較糟。所以二分搜答案後，可以強迫讓最左邊的人負責最左邊的幾個點，並把他負責的部分盡量往右推，下一個人就從還沒被探查過的點開始探查，安排每個人負責的區域的細節就直接看code吧。這樣做的複雜度會是\(O((N+M)lgC)\)，\(C\)是數值範圍。
code：http://codeforces.com/contest/343/submission/15437104
code：http://codeforces.com/contest/343/submission/15437104
Problem D - Water Tree (by TreapKing)
給你一棵樹，一開始每個點的點權都是\(0\)，支援以下三種操作：
1. 把一個點\(v\)以及他的子樹的點權改成\(1\)。
2. 把一個點\(v\)以及他的祖先的點權改成\(0\)。
3. 詢問一個點的點權。
題解：
跟子樹操作還有對祖先們的操作就應該想到樹壓平(壓平後，一個子樹會對應到一個區間，對一個點的祖先們的操作可以去問一個點的子樹)。對於每個點，他的點權決定於他最後一次被改到是被誰改的，如果最後一次動到它是操作1那它的點權就會是\(1\)，反之就會是\(0\)。
所以我們可以開兩個線段樹分別對應兩種操作，第一顆線段樹支援區間改值跟單點詢問，第二顆線段樹支援單點修改跟區間詢問最大值，如果第\(i\)個操作是1號操作，就把那個子樹所對應的區間的值改成\(i\)(線段樹1)，如果第\(i\)個操作是2號操作的話，就把樹壓平後的隨便一個\(v\)出現的位子的值改成\(i\)(線段樹2)。對於第3種操作，就看(\(v\)的子樹在線段樹1的值(最後一次把\(v\)改成\(1\)的操作))跟(\(v\)的子樹的最大值(最後一次把\(v\)改成\(0\)的操作))誰比較大，就知道\(v\)的權重是多少了。
這樣預處理\(O(N)\)，每一次操作都是\(O(lgN)\)，所以總複雜度是\(O(N+QlgN)\)。
另解(By Yanger)：
樹壓平之後，每次詢問其實就是看，那個節點所代表的區間內是否全部為1。於是我們可以開一棵線段樹，支援區間修改與查詢，直接維護一個區間AND起來的值。對於題目中的各種操作，
操作1 --> 把該點對應的區間改成1，在此因為
操作2 --> 把那個點在區間上隨便挑一個點改成0
操作3 --> 詢問該點對應的整個區間取 AND
複雜度：
樹壓平&線段樹初始化 O(N)、每次操作都是O(lgN)，所以總複雜度為 O(N + QlgN) 。
Problem E - Pumping Stations (by TreapKing)
給你一個\(N\)個點的帶權無向圖，請你找一個\(1\)~\(N\)的排列，讓相鄰兩項的最大流的和盡量大。
題解：
這題想了一陣之後一點頭緒也沒有，就直接看tutorial惹。
這題用到了一個東西叫做Gomory-Hu Tree，這個樹就是對於任意一個帶權無向圖\(G\)，都可以找到一個\(G\)的Gomory-Hu Tree \(T\)，\(T\)的點集和\(G\)的點集一樣，而對於任意點對\((u, v)\)，在\(G\)上\((u, v)\)的最大流等於在\(T\)上\((u, v)\)的最大流(也就是在\(T\)上，\(u\)~\(v\)路徑上的最小值)，而且對於任意一個\(T\)上的邊\((u, v)\)，\((u, v)\)在\(G\)上的最小割等於\((u, v)\)在\(T\)上的最小割。
先假設我們不知道為什麼變出了一顆對於輸入的Gomory-Hu Tree，那麼這題的答案就會是那顆Gomory-Hu Tree的邊權和，原因是對於\(T\)上邊權最小的邊(如果有多個就隨便選一個)，只用這個邊一次一定不會比較糟，那麼我們可以把這個邊兩端的子樹的答案算完之後，再把兩邊所形成的序列直接串起來，這樣就只會用到這條邊一次了。一直遞迴下去，每個邊就會恰被用一次。
現在問題就在於要怎麼找Gomory-Hu Tree，甚至連它存不存在都是個問題，查了一陣資料後發現他一定存在，而且好像是只要在滿足它的性質(相鄰兩點切開來就是原圖最小割)的前提下，胡亂接一接好像都會是對的，但原理我其實不是那麼了解。不過在這個前提下就生出了一個做法：把點照\(0\)~\((n-1)\)的順序一個一個放到樹上，然後想辦法判斷下個點該接在哪個點上&接上去的邊權是多少，一開始先假設通通都接在\(0\)上面。\(0\)當然就直接放上去，\(1\)就接在\(0\)上，然後因為最小割的性質，剩下的點就會基於他在原圖上的\(0-1\)最小割的位子(看他在\(0\)的那一邊還是\(1\)的那一邊)被切成兩邊，所以有些點會不可能接在\(0\)上，他就應該接在\(1\)上，然後一直做下去就會生出一顆Gomory-Hu Tree了，我也不知道為什麼這樣是對的就是了.......，不過看懂做法之後，感受一陣就會覺得對對的xD，例如被\(0, 1\)切來的兩部分，如果\(u, v\)分屬不同邊，他們的最大流絕對不會超過\(0, 1\)的最大流之類的。
參考資料：
我看懂找Gomory-Hu的原理的地方：
我看懂實作的地方，往下拉一點點會有文字描述的實作方法跟pseudo-code：
後來的code很醜而且落落長(200行)，順便推個kutengine大大的code，在status隨機戳的時候戳到他的code，找Gomory-Hu Tree的部分很短(雖然他是用Ford-Fulkerson)，找答案序列的部分我也是參(ㄓㄠˋ)考(ㄔㄠ)他的code寫的。
沒有留言:
張貼留言