紅白彩帶 題解｜APCS 2019 年 2 月中高級 第 2 題

前置知識

這題的核心（塗一格紅只會讓它左右兩段紅色區段合併成一段）下面會從頭講；要先會的是兩個工具，同一個主題兩邊都有的，對照著讀會更快上手：

  • 計數陣列：語法書 6.7——要帶走的是「值的範圍不大時，開一個陣列 cnt[v] 記每種值出現幾次，要找最小值就從小往大掃到第一個非零的格子」。這題「紅色區段長度不超過 \(10000\)」這句限制就是在暗示這條路。
  • multiset（最後的「另一種做法」會用到）：NTUCPC Guide〈Set 與 Map〉——元素永遠排好序、允許重複，begin() 是最小、rbegin() 是最大，erase(find(x)) 只拿掉一個 \(x\)。吳邦一《AP325》把本題放在第 7 章 7.4.2 併查集一節當習題 Q-7-11（教材 PDF 第 270～271 頁；Python 版第 7 章（III）），同一節也說「這一題不使用併查集也可以通過」——下面教的就是不用併查集的做法。

簡潔題意

彩帶有 \(n\) 格，\(1\) 是紅、\(0\) 是白；連續的紅格算一段「紅色區段」。依序把 \(k\) 個指定的白格塗紅（位置從 \(1\) 數起、互不相同）。初始狀態和每次塗完之後，都把「最長的紅色區段長度」加進第一個總和、「最短的」加進第二個總和，沒有任何紅格時兩個都算 \(0\)；最後輸出兩個總和（\(1 \le n \le 100000\)，\(0 \le k \le \min(n, 20000)\)，\(k = 0\) 時第三行是空行，任何時刻紅色區段長度都不超過 \(10000\)）。（APCS 逐筆給分。）

先照字面做：每塗一格就重掃一次

最直覺的做法是把彩帶存進陣列，每塗完一格就從頭掃一遍：遇到紅格就往右數到白格為止，得到一段的長度，擂台法同時記最長和最短。初始狀態也要掃一次。

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

const int MAX_N = 100000;
int color[MAX_N + 2];            // color[i] = 第 i 格是不是紅色（0 白、1 紅）
int n, k;
long long sumMax = 0, sumMin = 0;

void tally() {                   // 把目前的最長、最短紅色區段長度加進總和
    int longest = 0, shortest = 0;
    int i = 1;
    while (i <= n) {
        if (color[i] == 0) {
            i++;
            continue;
        }
        int j = i;                           // 從 i 開始往右數這一段有幾格紅
        while (j <= n && color[j] == 1) j++;
        int len = j - i;
        if (len > longest) longest = len;
        if (shortest == 0 || len < shortest) shortest = len;
        i = j;
    }
    sumMax += longest;
    sumMin += shortest;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> color[i];
    tally();                                 // 初始狀態也要算
    for (int t = 0; t < k; t++) {
        int x;
        cin >> x;
        color[x] = 1;
        tally();
    }
    cout << sumMax << endl << sumMin << endl;
    return 0;
}

兩個細節：「最短」的擂台初值不能用 \(0\) 直接比小，所以用 shortest == 0 代表「還沒看過任何一段」；沒有紅格時 longest、shortest 都維持 \(0\)，剛好就是題目要的。

這個寫法每次掃 \(n\) 格，一共掃 \(k + 1\) 次，最壞 \(20001 \times 100000 \approx 2 \times 10^9\) 次——本站時限 \(2\) 秒，\(k = 20000\) 的測資實測 \(1.3\) 到 \(3.2\) 秒，有的過、有的超時。答案是對的，只是慢。

不重掃：塗一格只會動到它左右的兩段

塗第 \(x\) 格時，整條彩帶只有一個地方變了：如果第 \(x - 1\) 格是紅的，它左邊貼著一段紅色區段；如果第 \(x + 1\) 格是紅的，右邊也貼著一段；塗完之後這兩段（有幾段算幾段）和第 \(x\) 格合併成一段，長度是「左邊那段的長度 \(+ 1 +\) 右邊那段的長度」。其他段完全不受影響。

所以要做的只有「查左右兩段多長」和「登記合併後的新長度」。查長度的方法：把每一段的長度記在它的左右兩端那兩格，len[l] = len[r] = 這一段的長度。第 \(x - 1\) 格如果是紅的，它一定是左邊那段的右端，len[x - 1] 就是左段的長度；同理 len[x + 1] 是右段的長度。合併後的新段左端是 \(x - \text{left}\)、右端是 \(x + \text{right}\)，把新長度寫到這兩格就登記完了（中間那些格的 len 是舊值沒關係，不會再被讀到——會被讀到的永遠只有兩端）。範例 2 的四個狀態見圖 1。

圖 1：範例 2 的四個狀態，每段紅色區段的長度記在它的左右兩端；塗第 7 格時左邊 len[6]=2、右邊 len[8]=1，合併成 4

接下來是「每個狀態的最長和最短」。最長很簡單：長度只會因為合併而變大、永遠不會變小，所以用擂台變數 longest 一路取最大值就對了。最短就沒這麼好——新塗的一格如果左右都是白的，就冒出一段長度 \(1\) 的新段，最短立刻掉到 \(1\)；下一步它又可能被合併掉，最短又彈回去。這裡就用到題目的限制「紅色區段長度不超過 \(10000\)」：開一個計數陣列 cnt[L] 記「目前長度為 \(L\) 的段有幾段」，合併時把舊的兩段長度各減一、新長度加一；要找最短就從 \(L = 1\) 往上掃，第一個 cnt[L] > 0 的就是答案，掃完都是 \(0\) 就表示沒有紅格、答案 \(0\)。

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

const int MAX_N = 100000;
const int MAX_LEN = 10000;       // 題目保證紅色區段長度不超過 10000
int color[MAX_N + 2];            // color[i] = 第 i 格是不是紅色；第 0 格和第 n + 1 格永遠是白的
int len[MAX_N + 2];              // 只在每段紅色區段的「兩端」有效：記這一段有幾格
int cnt[MAX_LEN + 1];            // cnt[L] = 目前長度為 L 的紅色區段有幾段
int n, k;
int longest = 0;                 // 目前最長的紅色區段（只會變長，擂台就夠）
int sumMax = 0, sumMin = 0;

void tally() {                   // 把目前的最長、最短長度加進總和
    int shortest = 0;
    for (int L = 1; L <= MAX_LEN; L++) {     // 從短的往長的找，第一個有段的長度就是最短
        if (cnt[L] > 0) {
            shortest = L;
            break;
        }
    }
    sumMax += longest;
    sumMin += shortest;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> color[i];
    int i = 1;
    while (i <= n) {                         // 先把初始狀態的每一段紅色區段登記起來
        if (color[i] == 0) {
            i++;
            continue;
        }
        int j = i;
        while (j <= n && color[j] == 1) j++;
        int L = j - i;                       // 第 i 格到第 j - 1 格是一段
        len[i] = L;
        len[j - 1] = L;
        cnt[L]++;
        if (L > longest) longest = L;
        i = j;
    }
    tally();                                 // 初始狀態也要算
    for (int t = 0; t < k; t++) {
        int x;
        cin >> x;
        int left = 0, right = 0;             // 左右兩邊貼著的紅色區段各有多長（沒有就是 0）
        if (color[x - 1] == 1) left = len[x - 1];
        if (color[x + 1] == 1) right = len[x + 1];
        if (left > 0) cnt[left]--;           // 舊的兩段消失
        if (right > 0) cnt[right]--;
        int L = left + 1 + right;            // 合併成一段新的
        cnt[L]++;
        color[x] = 1;
        len[x - left] = L;                   // 新的一段：左端是 x - left、右端是 x + right
        len[x + right] = L;
        if (L > longest) longest = L;
        tally();
    }
    cout << sumMax << endl << sumMin << endl;
    return 0;
}

幾個細節：

  • 陣列多開兩格、從 \(1\) 用起（語法書 6.3），第 \(0\) 格和第 \(n + 1\) 格永遠是 \(0\)，所以 color[x - 1]、color[x + 1] 在 \(x = 1\) 或 \(x = n\) 時不用特判。
  • 每次塗色是 \(O(1)\)，找最短最多掃 \(10000\) 格，\(k + 1\) 個狀態最多 \(2 \times 10^8\) 次簡單比較，本站實測 \(0.06\) 秒。
  • 總和用 int 就夠：每個狀態的最長最多 \(10000\)，\(k + 1 \le 20001\) 個狀態，總和不超過 \(20001 \times 10000 \approx 2 \times 10^8\)，離 int 的 \(2147483647\) 還很遠（估算方法見語法書 2.9）；不想算就用 long long，兩種都對。

測過再交：範例沒有「沒紅格」和「兩邊都合併」

範例 1 塗一格把左右兩段接起來、範例 2 有單獨冒出一段和接在一段旁邊；沒蓋到的是：一開始一格紅都沒有（總和要算 \(0\)、而且 \(k = 0\) 時第三行是空行）、塗完才出現第一段、合併之後最短往上跳、以及最大的 \(k\)（驗速度和找最短的掃描）。

輸入 正確輸出 這一筆在測什麼
3 0／0 0 0／（空行） 0／0 沒有紅格：兩個總和都是 \(0\)，\(k = 0\) 的空行不能讓程式卡住
4 2／1 0 0 1／2 3 7／6 塗第 \(3\) 格時左邊一段長 \(2\)、右邊一段長 \(1\)，合併成 \(4\)：\(1 + 2 + 4\) 與 \(1 + 1 + 4\)
5 2／0 0 0 0 0／3 1 2／2 一開始全白：初始狀態算 \(0\)，塗了才冒出長度 \(1\) 的段
6 1／1 1 1 0 1 1／4 9／8 合併後最短從 \(2\) 跳到 \(6\)：找最短不能只往下找
用程式造：\(n = 100000\)、\(k = 20000\)，一開始第 \(1\) 到 \(9999\) 格是紅的，先依序塗第 \(10001\) 到 \(20000\) 格、再塗第 \(20002\) 到 \(30001\) 格 200000000／100019997 最大測資：兩段各長到 \(10000\)，每一步都在找最短，驗速度

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

另一種做法：用 `multiset` 記所有段的長度

不想依賴「長度不超過 \(10000\)」這條限制，就把所有段的長度放進 multiset<int>：begin() 是最短、rbegin() 是最長，合併時 erase(find(left))、erase(find(right)) 各拿掉一個舊長度（直接 erase(left) 會把所有同長度的段一起刪光）、再 insert 新長度。查左右段多長的方法和上面一模一樣。

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

const int MAX_N = 100000;
int color[MAX_N + 2];            // color[i] = 第 i 格是不是紅色；第 0 格和第 n + 1 格永遠是白的
int len[MAX_N + 2];              // 只在每段紅色區段的「兩端」有效：記這一段有幾格
multiset<int> lengths;           // 目前每一段紅色區段的長度，同長度的段各算一個
int n, k;
int sumMax = 0, sumMin = 0;

void tally() {                   // 最短在最前面、最長在最後面；沒有紅格就都是 0
    if (lengths.empty()) return;
    sumMax += *lengths.rbegin();
    sumMin += *lengths.begin();
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> color[i];
    int i = 1;
    while (i <= n) {                         // 先把初始狀態的每一段紅色區段登記起來
        if (color[i] == 0) {
            i++;
            continue;
        }
        int j = i;
        while (j <= n && color[j] == 1) j++;
        int L = j - i;
        len[i] = L;
        len[j - 1] = L;
        lengths.insert(L);
        i = j;
    }
    tally();
    for (int t = 0; t < k; t++) {
        int x;
        cin >> x;
        int left = 0, right = 0;
        if (color[x - 1] == 1) left = len[x - 1];
        if (color[x + 1] == 1) right = len[x + 1];
        if (left > 0) lengths.erase(lengths.find(left));    // 只拿掉「一個」這種長度
        if (right > 0) lengths.erase(lengths.find(right));
        int L = left + 1 + right;
        lengths.insert(L);
        color[x] = 1;
        len[x - left] = L;
        len[x + right] = L;
        tally();
    }
    cout << sumMax << endl << sumMin << endl;
    return 0;
}

每次塗色是 \(O(\log n)\)，本站實測 \(0.03\) 秒。兩種做法都是滿分；計數陣列版用到題目給的限制、什麼容器都不用，multiset 版則是長度沒有上限也能用。學過併查集的人也可以把「合併兩段」交給併查集做，不過這題相鄰的段只會在塗色那一格接起來，記兩端長度就夠了。

常犯錯誤
  • 忘了初始狀態也要加進總和：範例 1 自己就會抓到——印 3、1，正確是 4、2。
  • 沒有紅格時直接取 multiset 的 begin()／rbegin()（或計數版找不到就亂用變數）：兩個範例都過，本站計分測資有 \(4\) 筆一開始全白，程式直接當掉；自測表第 \(1\)、\(3\) 列現形。
  • 段的長度只記在一端（例如只記左端）：從右邊接上來時讀到的是舊值——範例 2 印 10、5，正確是 11、6；計分測資掛 \(8\) 筆。
  • 合併時忘了把舊的兩段長度從計數陣列扣掉：最短永遠停在被合併掉的舊長度——範例 2 印 11、4；自測表第 \(2\) 列印 7、3；計分測資掛 \(5\) 筆。
  • 每塗一格就整條重掃：答案全對，但 \(k = 20000\) 的測資本站實測 \(1.3\) 到 \(3.2\) 秒，時限 \(2\) 秒，會掉好幾筆。