前置知識

這題是「遞迴定義直接翻成遞迴函式」的練習，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 遞迴：NTUCPC Guide〈遞迴〉——終止條件、以及「假裝函式已經寫好，直接拿來用」；吳邦一《AP325》第 1 章 1.2「實作遞迴定義」的 P-1-1 合成函數教的就是本題用的技巧（用一個全域的讀取位置一路往後讀），本題是它的習題 Q-1-5（教材 PDF 第 16～24 頁；Python 版第 1 章）。
• 二維陣列：語法書 13.1（想把影像真的畫出來才需要）。

簡潔題意

一張 \(n \times n\) 的黑白影像（\(n\) 是 \(2\) 的次方、\(n \le 1024\)）用遞迴方式編成一串字：整塊全白寫 0、全黑寫 1，否則寫 2 再依序接上左上、右上、左下、右下四個等大子正方形的編碼。給編碼字串（長度 \(< 1.1 \times 10^6\)）和 \(n\)，求黑色像素的數量。

依正確通過的測試資料筆數給分，其中：

• 子題組 1（\(10\) 分）：\(n = 2\)。
• 子題組 2（\(20\) 分）：\(n = 4\)。
• 子題組 3（\(70\) 分）：無額外限制。

先拿下 10 分：n = 2 的影像只有兩層

\(n = 2\) 時編碼只有兩種長相：整張同色（一個字 0 或 1），或 2 後面接四個字、每個字就是一個像素。整張 1 答案是 \(4\)，否則數後面四個字裡有幾個 1：

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    int n;
    cin >> s >> n;                        // 子題組 1：n = 2
    int black = 0;
    if (s == "1") {
        black = 4;                        // 整張全黑：2 × 2 = 4 個像素
    } else {
        for (char c : s)                  // "0" 一個字；或 "2" 後面四個字各是一個像素
            if (c == '1') black++;
    }
    cout << black << '\n';
    return 0;
}

\(n \ge 4\) 時一個 1 可能代表一整塊 \(2 \times 2\) 甚至更大，數字數就錯了——兩個範例都會 WA，這是正常的，逐筆給分之下子題組 1 的 \(10\) 分穩穩到手。

從 10 分到 100 分：照定義寫一個「讀一塊」的函式

編碼的定義本身就是遞迴的：「一塊的編碼」要嘛是一個 0／1，要嘛是 2 加上「四塊小一號的編碼」。寫一個函式 read(side)，負責從字串目前的位置讀完一塊邊長 side 的影像、回傳它有幾個黑像素：

• 讀到 0：整塊白，回傳 \(0\)。
• 讀到 1：整塊黑，回傳 \(side \times side\)——不是 \(1\)。
• 讀到 2：接下來依序是四塊邊長 \(side / 2\) 的影像，呼叫自己四次把它們讀完，四個回傳值相加。

字串從頭到尾每個字只讀一次，用一個全域變數 pos 記「讀到第幾個字」，每讀一個字就往前推——四次遞迴呼叫自然會接續讀下去，不用算每一塊的編碼有多長。

#include <bits/stdc++.h>
using namespace std;

string s;
int pos = 0;                              // 目前讀到字串的第幾個字

// 從 pos 開始讀完一塊邊長 side 的影像，回傳黑色像素數
int read(int side) {
    char c = s[pos];
    pos++;                                // 這個字讀掉了
    if (c == '0') return 0;               // 整塊白
    if (c == '1') return side * side;     // 整塊黑：side × side 個像素
    int half = side / 2;                  // '2'：依序讀左上、右上、左下、右下
    int black = 0;
    for (int i = 0; i < 4; i++)
        black += read(half);
    return black;
}

int main() {
    int n;
    cin >> s >> n;
    cout << read(n) << '\n';
    return 0;
}

每個字讀一次、常數時間，\(O(|s|)\)；遞迴深度只有 \(\log_2 n \le 10\) 層。\(n = 1024\) 的全黑答案是 \(1048576\)，int 夠。不需要把影像畫出來——但真的想畫也行：讀到 0／1 時把對應的 \(side \times side\) 格子填色，最後數格子，\(1024^2\) 約一百萬格也跑得完。

測過再交：範例的「1」都只代表小塊

兩個範例裡的 1 最多代表 \(2 \times 2\)。沒蓋到的：整張一個字、1 代表一大塊、\(n = 1\)、每個 2 都切到最底。

五筆都親眼看過正確，這題就穩了。