2015年1月27日 星期二

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)