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

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

其他做法：

後來看題解寫了兩個作法，而且都跟我的作法不一樣。

我在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

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