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