Codeforces Round #288 (Div. 2)

 pA --- Pasha and Pixels

題意：最初有一個全白的 $n*m$ 的表格，之後有 $k$ 次操作，每個操作會把某格塗黑 (可能去塗已經塗黑的格子)，問第一次出現大小為 $2*2$ 的黑格是什麼時候？

數據範圍： $1 \le n, m \le 1000$，$1 \le k \le 100,000$

tag：[ 模擬 ]

這種類形 (對表格做顏色改變的操作，問什麼時候會出現什麼 pattern 或總共出現幾次) 的題目很多，我敢說近 $30$ 場內有出現類似的題目，$n$ 和 $m$ 的範圍加大也都可以做，做法本質上是模擬，重點約略有二：

1. 用適當的資料結構存取格子的狀態，以這題來說用一個二維陣列就可以了，可以想想看若 $n$ 和 $m$ 很大的時候該怎麼辦。

2. 每個操作後，只去檢查有包含該操作所影響的格子的 pattern，是否已經滿足。

常見會 fail 的地方就是1. 檢查 pattern 時超過存取的資料結構範圍 2. 某次都去檢查所有可能 pattern。

pB --- Anton and currency you all know

題意：給一個位數為 $n$ 的奇數，請問交換兩個位數所產生的偶數最大值為多少？不可能產生偶數則輸出 $0$。

數據範圍：$2 \le n \le 100,000$

tag：[ adhoc ]

交換兩個位數看看會怎樣的題目也蠻常見的，例如說今年 (2015) Facebook Hackercup R1的第一題。

由於要變成偶數，所以一定是拿個位數和某個偶數去交換，最直覺的方法就是都換換看然後使用 strcmp 去比較大小，但這樣會 TLE，因為 #使用太多次可能很花時間的內建函式，這是很多人寫程式生涯中都會犯過的 bug，我也因為這個 bug challenge成功三份 code。

可改成把所有偶數的位數分成比個位數大和比個位數小去討論。

pC --- Anya and Ghost

題意：有 $m$ 隻鬼魂，第 $i$ 隻會在時間 $w_i$ 出現，恰出現一秒。你要在某些時刻花一秒鐘去點蠟燭，蠟燭可以持續燒 $t$ 秒。你希望每隻鬼魂出現的時段都至少有 $r$ 隻蠟燭是正在燃燒著，請問全程至少有點幾隻蠟燭。(可在負的時間點蠟燭)

數據範圍：所有數字皆介於 $1$ 至 $300$

tag：[ greedy ]

從最早出現的鬼魂開始考慮，可以發現為這隻鬼魂點蠟燭的時間愈晚愈好。

數據範圍小小的，所以用任何方法去模擬都幾乎都可 AC。

如果有注意到在考慮第 $i$ 隻鬼魂時，所為他點的蠟燭一定都在第 $i-1$ 隻鬼魂出現之後 (可以想想看為什麼)的話 code 會更好寫。

pD --- Tanya and Password

題意：給 $n$ 個長度為 $3$ 的由大小寫字母及數字組成的字串，問能否找到長度為 $n+2$ 的字串使得此字串所有長度為 $3$ 的子字串恰是所給定的 $n$ 個字串，若能找到請輸出解

數據範圍： $1 \le n \le 200,000$

tag：[ 圖論 ][ 尤拉路徑 ]

這也是經典的尤拉路徑題，第一次遇到這個模式的題目可能會覺得很難，可是由於這類的題目真的很常出現，之前小月的朋友想要辦場 Codeforces 的比賽時也有問過我出這樣類似的題目如何。

解法就是把所有兩個字母組成的字串視為點，並把所有題目給定字串 $c_1 c_2 c_3$ 想像成由點 $c_1 c_2$ 指向 $c_2 c_3$ 的有向邊，可以發現在這張圖上找到尤拉路徑就能找到一組解。

要注意的是由於這題的 n 很大，請務必使用 O(邊數) 的尤拉路徑求法。

pE --- Athur and Brackets

題意：給出一個長度為 $2n$ 且由 '(' 和 ')' 所構成的合法括弧序列，使得第 $i$ 個左括弧與其所對應到的又括弧距離介於 $l_i$ 和 $r_i$ 之間。

數據範圍：$1 \le n \le 600$

tag：[ dp ] [ 區間型dp ]

看到這是括弧類的題目嘛，再看看數據範圍，很容易就想到作法是 $O(n^3)$ 的 dp 類題目了。(再舉個例子：UVa1626)

這類型的dp的狀態往往都是由所有可能的閉區間 $[i, j] (1\le i \le j \le n)$ 所構成，區間長度愈小的狀態在dp過成的愈底部，以這題來說，一個狀態就是記錄僅看邊號在區間 [i, j] 內的所有括號是否有合法的序列，轉移時則枚舉第i個左括號距離對應的右括號的長度，看看是否存在合法序列，若有的話就把此長度記錄下來。

這類的題目我所寫的 code 架構通常如下：

舉個這題實際的轉移的例子。對於第 $1$ 個至第 $6$ 個左括號來說，若第 $1$ 個左括號和對應的右括號距離為 $7$ 是合法的，且只看第 $2$ 個至第 $4$ 個括號能夠成完整括弧序列，以及只看第 $5$ 個至第 $6$ 個左括號也能構成完整括弧序列，那我們就找到了一種把第 $1$ 個至第 $6$ 個括號構成括弧序列的方法了。

去看了官方BLOG，發現其實這題可以做到 O(n)，作者也沒想到 XD (O(n) 的 code)