2016年5月4日 星期三

Codeforces #210 Div.1

比賽連結：http://codeforces.com/contest/360

Problem A - Levko and Array Recovery (by Yangerma)

對一個長度最大為\(5000\)的序列，有兩種操作：區間加值和RMQ。今天依時間順序給你一張操作的紀錄，最多有\(5000\)筆操作，其中對於每個RMQ操作都附有它的答案。要求構造出一個符合所有詢問的原序列（可能無解）。

題解：
首先可以預處理，每個位置在每個時間點，相較於原序列的delta值，直接建表。
每筆RMQ有兩個意義：
\(1.\)它是一個上界
\(2.\)區間中有個值等於它
稍微感受一下就發現\(2\)比\(1\)難很多，所以策略就是先忽略\(2\)只考慮\(1\)。在滿足\(1\)的前提下，任何數字越大對\(2\)而言就一定越好。
於是做法就是，對於序列每個位置，就直接跑過所有詢問，配合delta值的表就可以得到它所有的上界，然後直接讓它等於最小的那一個。
最後再把所有操作跑一遍，看看是不是真的滿足\(2\)，如果不是就無解。

時間複雜度：\(O(NQ)\)


這題很慚愧地卡了一陣子，後來才發現\(NQ\)能做的事情比想像中多很多XD。


Problem B - Levko and Array (by Yanger)

給你一個最長2000的整數序列。對一個序列，定義它的「美麗度」為所有相鄰值的差的最大值（美麗度越低越好）。問若你可以改變數列的\(k\)個值，美麗度最低可以是多少？

題解：
答案顯然有單調性，所以就二分搜吧。
對於每個答案，有些值需要改，有些值不用。考慮不用改的那些值，它們滿足一個充要性質：相鄰兩個之間的斜率（這邊指的是拔掉要改的值之後相鄰，實際index不見得相鄰）的絕對值小於等於答案。所以我們的目標就變成找一個最長子序列滿足上面那個條件。這件事可以
\(O(N*N)\) DP做到：令dp[i]代表以 i 為結尾的最長子序列，求\(dp[i]\)的方法就是就回頭看\(dp[0 ~ i-1]\)看有哪個可以接得上去。
找到最長子序列後就看它是否大於等於n-k，來判斷這個答案O不OK。

時間複雜度：\(O(N*N*log(maxval))\)

code: http://codeforces.com/contest/360/submission/17545531


張貼者： 於 沒有留言:

2016年4月30日 星期六

CodeForces #207 Div.1

比賽連結：http://codeforces.com/contest/356

Problem A - Knight Tournament (by nkhg)

有\(n\)個騎士、\(m\)場對決，原始騎士被編號\(1\)到\(n\)，給你那\(m\)場對決的紀錄，每個紀錄會是\(l,r,x\)指編號\(l\)到\(r\)當中還沒遭到淘汰的騎士決鬥，並且編號\(x\)的騎士勝出。
最後請你對每個騎士輸出他是被誰打敗的（就是他出局的那一回合勝出的是誰），沒有被打敗的人請輸出\(0\)。（保證最後恰一個人獲勝、每個對決紀錄至少有兩個騎士參與）

題解：
我是用線段樹解這題，每次把那回被打敗的人的區間標記為\(x\)，遞迴下去的時候如果那個區間已經被標記過，就不做事，否則就標記上去。仔細想想如果一個騎士被打敗好幾次，那麼一定是在最底層的那個標記被打敗的。（因為覆蓋到同一個點的標記，比較慢來的不可能被遞迴到底層）
時間複雜度：\(O((n+m)\log n)\)


其他做法：
後來看題解寫了兩個作法，而且都跟我的作法不一樣。
我在virtual的時候最先寫了個linked list的錯誤作法，慌亂之下沒有思考比較單純的作法，才會寫到線段樹。

tutorial作法一：
直接用一個set存現在還沒被淘汰的人，決鬥時就lower_bound左界然後一個一個掃過去，反正每個人被看過一次之後就會被拔掉了。（當然\(x\)本身是個例外，不過不影響效率）

tutorial作法二：
根據前一個作法，我們試著對每個騎士維護他的下一個還沒被淘汰的人是誰，然後使用路徑壓縮處理就好了。


Problem B - Xenia and Hamming (by nkhg)

給你兩個字串（保證一樣長），叫你輸出他們的漢明距離。
字串的給法是：
給\(n,m\)、英文小寫字串\(x,y\)，表示字串是\(x\)重複\(n\)次與\(y\)重複\(m\)次。
（\(n,m\le 10^{12}, |x|,|y|\le 10^6\)）

題解：
基於題目的保證，我們知道實際字串長度一定是\(lcm(|x|,|y|)\)的倍數，且配對狀況以\(lcm(|x|,|y|)\)的長度循環，因此只要思考\(lcm(|x|,|y|)\)的狀況再乘上某個倍數就好了。
令\(g=gcd(|x|,|y|)\)，那麼我們發現在\(lcm(|x|,|y|)\)內，\(x\)跟\(y\)當中位置編號對\(g\)同餘的字元一定會配對到恰一次，而對\(g\)不同餘的一定不可能配對到。（理由自己想想看）
這時候因為字元集很小（26），所以直接開一條那麼大的陣列，把對\(g\)餘\(i,0\le i\lt g\)的分別處理一遍就好。
（賽中的bug都是long long，從乘法跟輸入分別WA了一遍）

code: http://codeforces.com/contest/356/submission/16777722


Problem C - Compartments (by nkhg)

火車上有\(n\)個包廂，每個包廂容量最大\(4\)人，現分別有學生\(0\)到\(4\)人，請問最少要讓幾個學生換位置使得每個包廂的學生數量都是\(0,3,4\)其中一個？

題解：
看到官方題解是做了一部分greedy之後，剩的直接枚舉，還寫說"You shouldn't come up with common solution. Else you should just to consider all possible cases."
不過我就是在virtual的時候把所有case寫出來的人XD
作法如下：
*1+2→3
然後會只剩下1或2，分兩邊，只剩下1的(照順序)：
*1+1+1→3
*1+1+4→3+3
*1+3→4
*1+4+4→3+3+3
如果是只剩下2的(也是要照順序)：
*2+2+2→3+3
*2+2→4
*2+4→3+3
*2+3+3→4+4
以上是全部了，我也不知道為什麼我這麼有耐心耶XDD

code: http://codeforces.com/contest/356/submission/16778167
張貼者： 於 沒有留言:

2016年4月25日 星期一

CodeForces #206 Div.1

比賽連結: http://codeforces.com/contest/354

Problem A - Vasya and Robot

給你\(n,\ l,\ q,\ Q_l,\ Q_r\)，有一個長度為\(n\)的序列，有兩種操作可以做：
1. 花\(w_i * l\)的代價把最左邊的東西拿走，如果上一次也是拿最左邊的東西的話，則要額外付出\(Q_l\)的代價。
2. 花\(w_i * r\)的代價把最左邊的東西拿走，如果上一次也是拿最左邊的東西的話，則要額外付出\(Q_r\)的代價。
輸入的數字都是正整數，問你拿完所有東西最少要花多少cost。

題解：
要先發現兩個性質：
1. 原序列可以一刀切成兩個部分，左半邊都是用「拿左邊」的拿法拿的，右半邊都是用「拿右邊」的方法拿的。
2. 因為\(Q_l,\ Q_r\)都是正數，所以如果已經決定好哪些東西要用「拿左邊」的拿法、哪些東西要用「拿右邊」的拿法，那麼交錯拿(左邊右邊輪流拿)一定不會比較糟。
於是就可以\(O(n)\)枚舉兩部分的斷點然後輕鬆\(O(1)\)判斷答案。

code: http://codeforces.com/contest/354/submission/16456436

Problem B - Game with Strings

給你一個\(n \times n\)的字元矩陣，一剛開始你有一個空字串，設你加了一個字母到字串後面後，新字串為S，如果從盤面的最左上角只往右或往下走，沿途的字元串起來之後是S的話，那麼剛剛加字串的行為就是合法的。今天有兩個人要輪流加字母，加字母的規則就像剛剛講的那樣，先手玩家想要讓 ('a'的數量) - ('b'的數量)盡量大，後手玩家則希望最小化剛剛講的那個東西，問你在兩個玩家都用最佳策略的話，誰會贏(平手就輸出平手)。
注意：這個遊戲不等價於兩個人把一個棋子往右移或往下移，然後記錄沿途踩到的字元。
(覺得我翻得好爛，可以考慮自己去看原題OAO)

題解：
這題我是看解答才會做的，解答很不直觀。
正解是狀壓DP，因為矩陣上，所有離角落的曼哈頓距離為某個k的位子會是一條斜線，這題DP的方向就是那條斜線，狀態就是對於某個斜線上的每一個都可以是1或0，先設某個狀態中，那些1所對應到的格子們為「等效格」。在某個狀態代表的意義及要存的東西是「對於所有長得一樣的字串而且結尾是等效格的情況， ('a'的數量) - ('b'的數量) 的最大值」。
真的不太會描述，可以自己去看解答參透一下......。

code: http://codeforces.com/contest/354/submission/16507434

Problem C - Beautiful Arrays

給你一個長度為\(n\)的序列跟一個\(k\)，你可以把每個數字減掉\(0~k\)，要請你最大化所有數字的最大公因數。

題解：
其實不難但我很廢所以我還是看題解才會。
首先因為每個數字可以減掉\(0~k\)，所以如果全域最小值\(\leq k+1\)的話，一定可以讓答案是全域最小值，因為一個數字往下減k會一定可以經過到所有\(\leq k+1\)的數字的倍數。
如果全域最小值\(\gt k\)的話，那麼我們可以枚舉答案，如果我們猜答案是x的話，我們只需要數\( [x, x+k], [2x, 2x+k] \)...當中是不是覆蓋了所有的數字，因為答案比k大，所以不會有要數的區間互相覆蓋的問題，對於每個x，我們需要\(\frac{a_i}{x}\)的時間，而\(\sum\limits_{x=1}^n \frac{n}{x} \sim nlgn\)，所以複雜度會是\(O(nlgn)\)。

code: http://codeforces.com/contest/354/submission/16507434

Problem D - Transferring Paramid

有一個長得很像巴斯卡三角形的東西，編號如下圖：

今天有兩種操作：
1. \(t\ i\ v \quad t=1\)，表示把編號i的格子改成\(v\)。
2. \(t\ i\ v_1\ v_2\ ...\ v_s, \quad t=2\)，表示把所有以編號\(i\)為根的「子樹」(上圖的藍色部分的那種樣子)的數字改掉，必須依序說第一個數字要改成\(v_1\)、第二個數字要改成\(v_2\)......等等。
今天有個\(n\)層的這種三角形，然後有\(k\)個數字要被改到，會給你k個數字分別在第幾列第幾行，問你最少需要用幾個數字才能改到所有位置？比如說，一個\(1\ 3\ 4\)的操作就是花三個數字把編號3的數字改掉。

題解：
這題我也是看題解才會的.....(天啊我根本題解王)。
這題是個方向很奇怪的DP，對應這題操作的長相，狀態\(dp[i][j]\)表示「靠著最右邊且邊長為\(i\)的正三角形，挖掉左邊的邊長為\(j\)的正三角形的區域中，改掉那個區域中的數字最少需要用幾個數字」，其實就是下圖中的藍色部分。
思(ㄎㄢˋ)考(ㄨㄢˊ)一(ㄊㄧˊ)陣(ㄐㄧㄝˇ)後，可以想到一個遞迴式：
\(dp[i][0] = min(dp[i-1][k-1]+\frac{k \times (k+1)}{2}+2+sumUp[i][k+1] \times 3), 0 \leq k \leq i \)
\(dp[i][j] = min(dp[i][j-1], dp[i-1][j-1]+sumUp[i][j+1] \times 3), \forall j \gt 0 \)
其中，\(sumUp[i][j]\)表示右邊數過來第\(i\)個斜線上，由下往上數\(k\)個位子以上，有幾個需要被改的格子。
這樣子的複雜度是\(O(n^2)\)。
然後會發現，因為第二種操作需要用大概\(k^2\)個數字，所以你不可能對一個很高的位子用第二種操作。算一下後會發現高度\(\gt \sqrt{6k}\)的點，一個一個改一定比改整個子三角形還要好，所以DP的時候就不用跑到那麼高，這樣子我們的複雜度就會降到\(O(n\sqrt{k})\)。
官方editorial還有給出一個幫助思考的\(O(n^3)\)的做法，如果不覺得上面的遞迴式很有道理的話也可以去看看。

code: http://codeforces.com/contest/354/submission/16910450


Problem E - Lucky Number Representation

給你一個\(t\)個正整數，問你這個數字能不能表示成6個在十進制下每個digit都是\(0, 4, 7\)的非負整數的和，可以的話給出一組解。

題解：
DP，定義狀態\(dp[i][j]\)為「有沒有辦法湊出最右邊的\(i\)個digit，且下一個位數進位的量值為\(j\)」。自己感受一下應該也會覺得可以DP吧，不太難想到不過細節小麻煩，複雜度沒仔細算但感覺就超級快，數字都小小的。
官方題解有給出一個超精妙的做法，寫得很詳細，有興趣可以自己去看，不過DP解好像比較強就是了......。

code: http://codeforces.com/contest/354/submission/16528901
張貼者： 於 沒有留言:

2016年2月26日 星期五

CodeForces #204 Div.1

比賽連結: http://codeforces.com/contest/351

Problem A - Jeff and Rounding

給你\(2N\)個數字(不一定是整數)，你要做N次操作，每次操作的內容是挑兩個還沒被選過的數字，一個取上高斯，另一個取下高斯，要最小化(一開始的總合)-(操作之後的總和)。

題解：
對於那些整數們，顯然不管發生什麼事他們的大小都不會改變，然後對於那些非整數，會發現你無力改變整數部分，只能把那些零點多的數字改成\(0\)或\(1\)，\(1\)的數量的上下界可以用所有非整數的數量跟\(N\)算出來，所以我們可以枚舉我們要把幾個零點多改成\(1\)，剩下就變成\(0\)，細節就看code吧，因為不喜歡double所以我把輸入轉成整數做。

code: http://codeforces.com/contest/351/submission/16270303

Problem B - Jeff and Furik

給你一個數字都相異的序列，Jeff跟Furik會對著這個序列輪流做操作，Jeff先手，每次Jeff可以隨便挑兩個相鄰的數字然後交換那兩個數字，而每次Furik會擲一個公正硬幣，如果是正面就交換一個相鄰的且左邊比較大的兩個數字，反面的話就交換兩個相鄰且右邊比較大的數字，如果不符合他的要求的話他就會在擲一次硬幣，問你在Jeff盡全力的情況下，序列變回遞增的期望交換次數。

題解：
要先知道逆序數對數就是最少必須被交換的次數之類的，而Jeff毫無理由不讓逆序數對數-1，Furik就隨便他玩，設\(dp_i\)=(逆序數對為\(i\)時的期望次數)，列一下式子就會得到\(dp_i=dp_{i-2}+4\)之類的，又\(dp_1=1, dp_2=4\)，同時可以得到答案會是逆序數對數乘上二，然後如果逆序數對數是奇數就再減一之類的亂七八糟公式。

code: http://codeforces.com/contest/351/submission/16270651

Problem C - Jeff and Brackets

給你\(N, M\)，\(M\)保證是偶數，要做出一個長度為\(NM\)的括弧序列，index是\(0\)~\(NM-1\)，其中第\(i\)個位子當成上括弧的成本是\(a_{imodN}\)，當下括弧的成本是\(b_{imodN}\)，問你做出整個括弧序列的最小成本是多少。

題解：
先把\(N\)改成\(2N\)，\(M\)改成\(M/2\)(以下都用新的\(N, M\)講)，然後做出長度為\(N\)的合法括弧序列的最小成本，DP或greedy之類的，然後我們就得到了一個最小成本跟一個方案，然後用倍增做。先解釋一下為什麼可以倍增，假設有兩個合法且成本最小的括弧序列接在一起，要把他換成最小成本的方法一定是找到一對在不同邊的的")("，然後把他換成"()"，一定不可能需要改變一對"()"的原因是，把"()"換成")("的話一定會讓中間的某個地方爛掉，如果真的要這樣換也一定需要另外一對")("換成"()"讓他變合法。
........)...(...)...(.....
........a...b..c..d.....
a, b, c, d分別表示翻轉對應括弧後，成本變小的量(可以是負的)，如果有某個b+c很大，他也一定要一對a+d來支援，那麼就算我們只找")("，也可以變成換a+b跟c+d。
講得有點混亂，直接講做法的話就是，先做出一個N的括弧序列的答案之後，做出2N, 4N, 8N, 16N.....的答案跟方案，雖然序列長度會變得很大，但是我們其實只有2N種成本，所以只要用2N個數字就可以描述一個方案(有幾個在第i個位子的下括弧之類的)，然後一直找一對最好的")("，把它換成"()"，因為上下括弧獨立所以可以找個別的最好的，因為最多就是換成(((())))之類的，所以更新一定會停止，反正N小小的所以可以亂做一通。最後再用這些二的次方湊出M就好了，用一樣的方法合併兩個序列。
官方tutorial的做法是做出一個轉移矩陣，感覺很神秘。

code: http://codeforces.com/contest/351/submission/16290079

Problem D - Jeff and Removing Periods

Jeff可以對一個序列{a}做以下操作：
1. 找一組(v, t, k)，滿足\(a_v=a_v+k=a_v+2k+...=a_v+tk\)，反白(?)這些數字。
2. 把剛剛反白的數字砍掉，剩下的數字重新由1~n編號。
3. 把剩下的數字照你喜歡的樣子排列。
上面的步驟為一次操作。
一個序列的美麗度的定義是要做幾次操作可以把數列裡的元素全部砍掉。
給你一個長度為N的序列跟M次詢問，每次詢問是一個區間的美麗度。

題解：
首先會發現，可以自由排列剩下的數字是個非常OP的行為，只要可以自由排列，就可以把1, 2, 3, 1, 3, 2, 1, 1, 1排列成1, 1, 1, 1, 1, 2, 2, 3, 3之類的，很顯然的排列之後每個數字就只要一次操作就可以被砍完，這也顯然是答案的下界。思考一陣就會發現美麗度是(相異的數字種類) + x，如果有一個數字一開始可以被一次操作拿完的話x就是0，反之x就是1。區間相異數字是個頗經典的題目，可以把詢問離線照右界排序，數字由左而右一個一個加入，然後數的時候只數每個數字最後一次出現之類的，可以用線段樹或BIT做。至於後面那個問題，其實可以維護每個數字在當前右界中，往左最多可以到哪裡仍然可以被一次拿完，比如說：
2_____2__2__2__2____________|____________2
  a                           c                        b
當右界在b的位子時，左界只要在a右邊，2就可以一口氣被拿完，而2這個數字會在下一個2出現之後改變他的左界情況。如果我們定義\(hd_i\)是第i個數字以一樣的間隔不斷地往前一個同數字跳，跳到哪一個位子會爆炸(上示意圖中，\(hd_c = a\))。那麼對一個l, r詢問，有一個數字能一口氣被拿完<==>存在l<=k<=r使得\(hd_k\)<l，這件事可以用線段樹做，不過要記得加入新的數字之後要把那個數字的前一次出現的hd改掉，比如說新出現了一個2，要把上一個2的hd改掉。然後我們這題就可以做了。
官方tutorial只講說可以用根號作法做，寫lgN覺得開心xDD。

code: http://codeforces.com/contest/351/submission/16346528

Problem E - Jeff and Permutation

給你一個序列，你可以把一些數字改成負的，讓逆序數對數盡量小。

題解：
會發現對於最大的數字，其他數字的正負不影響它，如果有多個一樣大的數字，你一定只會想要讓前面幾個數字是負的，然後後面都是正的，N又小小的，所以就有了一個很開心的做法，細節就直接看code吧，用文字不好解釋。
官方tutorial的做法是個奇怪的DP，有點神秘。

code: http://codeforces.com/contest/351/submission/16296103
張貼者： 於 沒有留言:

2016年2月9日 星期二

CodeForces #202 Div.1

比賽連結：http://codeforces.com/contest/348

Problem A - Mafia (by TreapKing)

有\(N\)個人要玩桌遊，由於規則的關係，每一場會有一個人當不到player，如果第\(i\)個人想要當\(a_i\)次player，請問最少要玩幾次遊戲。
閱讀更多 »
張貼者： 於 沒有留言:

2016年1月24日 星期日

Codeforces #201 Div.1

比賽連結：http://codeforces.com/contest/346/

Problem A - Alice and Bob (by TreapKing)

看題目名稱就知道是一個Alice先手的遊戲了。題目會先給出一個數字都相異的數列，Alice先手，每一次行動是挑兩個數字x, y，然後把 | x - y | 加入數列，但如果 | x - y | 本來就存在就不能加，沒有行動可以做的人就輸了，問誰會贏。

題解：
先想只有兩個數字a, b的情況，那麼下一個操作就能做出a-b(正負先不理他xD)，在下一次會做出b - a-b = 2b-a 或 a-b - a = -b之類的，思考一陣會發現如果是給你a跟b，那麼應該對於所有整數x, y，ax + by應該都做得出來，不過會滿足 | ax + by | <= max(a, b)之類的。然後就會發現所有出現的數字都會是gcd(a, b)的倍數。官方的tuorial是直接提到不管怎麼樣最後數列的長相都一樣，然後就直接令d = gcd{ x[i] }，然後說最後的數列就會是{d, 2d, 3d, ... , max{x[i]} }。細節就看code吧。

code:
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef _DEBUG_
 #define debug(...) printf(__VA_ARGS__)
#else
 #define debug(...) (void)0
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

int main() {
 int n;
 scanf("%d", &n);
 int x = 0, mx = 0;
 for(int i=0; i<n; i++) {
  int tmp;
  scanf("%d", &tmp);
  x = __gcd(x, tmp);
  mx = max(mx, tmp);
 }

 puts((mx/x-n)%2 ? "Alice" : "Bob");
    
    return 0;
}


Problem C - Number Transformation II (by Yanger)

給你兩個正整數a, b (a >= b)，以及n個正整數Xi，今天每步有以下兩種選擇：
1. 在Xi裡面選一個數，讓a變成a - (a%Xi)
2. 使a--
問你最少要多少步可以讓a變成b。
n<= 10^5，所有數值都在10^9以內，但保證a-b <= 10^6。

題解：
首先有個greedy的想法，就是每一步都讓 a 變得越小越好。稍微想一下(其實想了蠻久)就發現很對，因為假設今天在某一步有兩個選擇a1和a2(a1 < a2)，那無論選a2後的下一步有多棒，選a1以後都能用相同的Xi走到那一步。
接下來的問題就變成每次要怎麼找當前最大的步伐了。結論是直接枚舉Xi去試就好。乍看起來很像O(n * (a - b))，但我們可以考慮一種走法：選定一個Xi 之後，就只用它和減一交替來走 (後面的渣渣再用減一處理)，然後發現這種走法裡面每兩步a就會減少Xi。所以其實只要維護好當前「還能用」(不會超過b)的Xi，每步步伐的量級就會是Max(Xi)，當Xi 全部相異的時候這就相當於n。算一算複雜度就會是好的O(a-b)。
有點幹的是題目沒有說Xi會相異，所以要事先把它unique掉。


Problem D - Robot Control (by Yanger)

給一個點數、邊數最多都到10^6的有向圖，以及一個起點s和一個終點t。今天有個機器人要從起點走到終點。它有以下幾種性質：
1. 一踏到曾經踏過的點就會爆炸。
2. 沒路可走了(出度為0)就會爆炸。
3. 有不只一條路(出度大於1)的時候會隨機選一條走。
看起來很GG，但所幸聰明的你可以在它每走到一個有叉路的點的時候給它下指令，叫它走某個特定的邊，它在那個點就不會隨機了。
問你，最少需要幾個指令，可以保證機器人安全從s走到t?

題解：
從起點往下走前途茫茫，於是就想想從終點往回走。首先，一個指向終點的點，如果出度為一，則可以直接視為另一個安全的「終點」。把這些點都找完以後，如果另外有一個點的所有出邊都指向那些終點，那它也可以視為終點。照這樣遞迴找完所有終點以後，就代表，其他指向它們的點都需要一個指令才能安全到達。然後又可以接著做跟剛剛類似的事......
想想才發現這其實就是在反向圖上面做dijstra。而且因為需要的指令數只會在每個「階段」增加1，所以連priority queue都不需要。這樣複雜度就只是把所有邊遍歷一次而已，O(|E|)。詳細實作看code吧。

code: http://codeforces.com/contest/346/submission/15576591

Problem E - Doodle Jump (by Yanger)

給定整數a, n, p，定義數列Ai = a * i % p (0 <= i <= n)。
問Ai排序過後，相鄰值的差是否皆小於等於h ?
其中
1 <= a, p <= 10^9 且a, p互質
1 <= n < p
0 <= h <= 10^9

題解：
學官方舉個例，若a = 5, p = 23，則Ai會長得像這樣(這邊先不考慮n到多少，把全部都先列出來)：
0 5 10 15 20
2 7 12 17 22
4 9 14 19
1 6 11 16 21
3 8 13 18
換行的意思應該很明顯，列出來後會發現我們可以把Ai依照mod 5分成5 群。
有幾個觀察
1. 如果n不足以跑完第一群，最大間隔就直接是5。
2. 否則，第一群相當於把[0, 23) 隔成了幾個長度相等的子區間([0, 5], [5, 10], etc.)和後面的一些渣渣，而後面的數我們可以想像成去「填補」那些子區間。
3. 每一群恰好會填在每個子區間內的同一個相對位置，所以我們只要考慮一個子區間和每群中的一個數就好了。

整體就等同以2的步長在分割 [0, 5]，我們發現它其實是規模變小的原題 (a' = a - p % a, p' = a) 。所以我們可以一直遞迴下去，直到出現1.的情況再直接看答案。這邊其實都沒有考慮到2.中所謂的渣渣，不過經過一些證明可以知道它們根本不重要。

最後看複雜度，當a = p - 1的時候很明顯會慘掉，但因為取a = p - a 走出來其實一模一樣，所以我們每次只要取a' = min(a - p % a, p % a)，就能確保每遞迴一次a就至少會減半。這樣複雜度就會是好好的log了!!

code: http://codeforces.com/contest/346/submission/15824994
張貼者： 於 沒有留言:

2016年1月19日 星期二

Codeforces #200 Div.1

比賽連結：http://codeforces.com/contest/343

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)\)。

code：http://codeforces.com/contest/343/submission/15435531

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

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)\)。

code：http://codeforces.com/contest/343/submission/15441990

另解(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寫的。

張貼者： 於 沒有留言:
訂閱： 文章 (Atom)