主題

ZeroJudge - f637: DF-expression 解題心得

Not In My Back Yard | 2021-02-03 00:00:12 | 巴幣 0 | 人氣 154

題目連結:


題目大意:
一個 n × n (n 為 2 的某一冪次)二維的黑白圖片(只有黑和白兩種像素)有一種壓縮方式稱為深度優先圖像表示式(Depth-First Expression,在本題簡稱為 DF-express),其定義為:
DF-express(n):
  一:如果此圖片為全白,則以一個 0 表示;
  二:否則,如果此圖面為全白,則以一個 1 表示;
  三:以上皆非,則將此圖片平分成左上、右上、左下、右下這四個正方形子區域(每個為 (n ÷ 2) × (n ÷ 2) 大),而此圖片表示法即為一個 2 與左上、右上、左下、右下四個區域各自的 DF-express 所依序串接起來。

輸入有兩列,第一列給定一個合法的 DF-express S (S 長度 < 1100000 且只由 「0」 、 「1」 、 「2」 三種字元組成),而第二列給定一正整數 n (1 ≦ n ≦ 1024 , 且 n 必為 2 的冪次),代表壓縮前的圖片之大小。試問,根據 S 之內容,原先的 n × n 應有多少像素為「黑」?



範例輸入:
範例輸入 #1
2200101020110
4

範例輸入 #2
2020020100010
8


範例輸出:
範例輸出 #1
7

範例輸出 #2
17


解題思維:
本題可以直接照著原本的遞迴式去判斷給定的 DF-express S 每一個數字是如何產出的。

以範例輸入 #2 的 S =「2020020100010」 、 n = 8 為例。
2020020100010
可以看到現在的是 2 ,所以我們切分此 8 × 8 為 4 個 4 × 4 方塊。

2020020100010
遇到了 0 ,所以剛剛切出來的左上 4 × 4 全為白。

2020020100010
接著是 2 ,所以右上的 4 × 4 需要繼續切成 4 個 2 × 2 。

2020020100010
接著是 0 ,所以右上 4 × 4 其左上的 2 × 2 全為白。

2020020100010
接著是 0 ,所以右上 4 × 4 其右上的 2 × 2 全為白。

2020020100010
接著是 2 ,所以右上 4 × 4 其左下的 2 × 2 切為四個 1 × 1。

2020020100010
接著是 0 ,所以右上 4 × 4 其左下的 2 × 2 的左上之 1 × 1 為白。

2020020100010
接著是 1 ,所以右上 4 × 4 其左下的 2 × 2 的右上之 1 × 1 為黑。

2020020100010
接著是 0 ,所以右上 4 × 4 其左下的 2 × 2 的左下之 1 × 1 為白。

2020020100010
接著是 0 ,所以右上 4 × 4 其左下的 2 × 2 的右下之 1 × 1 為白。

2020020100010
接著是 0 ,所以右上 4 × 4 其右下的 2 × 2 全為白。

2020020100010
接著是 1 ,所以左下 4 × 4 全為黑。

2020020100010
接著是 0 ,所以右下 4 × 4 全為白。

因此「黑」像素總面積為 4 × 4 + 1 × 1 = 17 。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作