完美彩帶 題解｜APCS 2019 年 6 月中高級 第 4 題

前置知識

這題的核心（固定長度的視窗往右滑一格，只有一格進來、一格出去）下面會從頭講；要先會的是：

• 滑動視窗：NTUCPC Guide〈雙指針〉——要帶走的是「視窗往右移時，只更新進來那格和出去那格的影響，不重算整個視窗」。吳邦一《AP325》第 3 章的「滑動視窗」一節就是在講這個，例題 P-3-9 最多色彩帶、P-3-10 全彩彩帶 和本題是同一系列，習題 Q-3-12 就是本題（教材 PDF 第 105～117 頁；Python 版第 3 章）。
• map：NTUCPC Guide〈Set 與 Map〉——顏色編號到 \(10^9\)、不能拿來當陣列索引，map<int, int> count 用顏色當索引記出現次數。

簡潔題意

彩帶有 \(n\) 格，每格一個顏色編號，整條彩帶恰好出現 \(m\) 種顏色。長度剛好 \(m\) 的連續一段，如果每種顏色都恰好出現一次，就是一段「完美彩帶」。求有幾段（不同起點分開算）（\(2 \le m \le n \le 200000\)，顏色編號 \(0\) 到 \(10^9\)）。（APCS 逐筆給分。）

關鍵的一句話：視窗長度是 m，所以「m 種顏色」就是「每種恰好一次」

一段長度 \(m\) 的視窗裡有 \(m\) 格，如果裡面出現了全部 \(m\) 種顏色，每種就只能各占一格——「每種顏色恰好出現一次」和「視窗裡有 \(m\) 種不同的顏色」是同一件事。所以只要能數出每個視窗裡「有幾種顏色」，數到 \(m\) 的就是完美彩帶。範例的七個視窗見圖 1。

先照字面做：每個視窗各自數

最直覺的寫法：每個起點 \(l\) 各開一個 set，把 \(m\) 格丟進去，size() 是 \(m\) 就加一。

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

const int MAX_N = 200000;
int a[MAX_N + 1];                // a[i] = 第 i 格的顏色

int main() {
    int m, n;
    cin >> m >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int answer = 0;
    for (int l = 1; l + m - 1 <= n; l++) {       // 每一段 [l, l + m - 1] 各自檢查
        set<int> colors;                         // 這一段出現過的顏色
        for (int i = l; i <= l + m - 1; i++) colors.insert(a[i]);
        if ((int)colors.size() == m) answer++;   // m 格裡有 m 種顏色 ＝ 每種恰好一次
    }
    cout << answer << endl;
    return 0;
}

答案是對的，但每個視窗都要看 \(m\) 格，總共 \((n - m + 1) \times m\) 次：\(m = 100000\)、\(n = 200000\) 時是 \(10^{10}\) 次，本站實測 \(60\) 秒都跑不完。

不重數：視窗滑一格，只有一格進來、一格出去

視窗從 \([l, l + m - 1]\) 滑到 \([l + 1, l + m]\)，裡面 \(m - 1\) 格都沒變，只有第 \(l + m\) 格進來、第 \(l\) 格出去。用 count[c] 記視窗裡顏色 \(c\) 出現幾次、kinds 記目前有幾種顏色：

• 第 \(i\) 格進來：count[a[i]]++，如果加完變成 \(1\)，表示這種顏色本來沒有，kinds++。
• 第 \(i - m\) 格出去：count[a[i - m]]--，如果減完變成 \(0\)，表示這種顏色沒了，kinds--。
• 視窗湊滿 \(m\) 格之後（\(i \ge m\)），kinds == m 就加一。

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

const int MAX_N = 200000;
int a[MAX_N + 1];                // a[i] = 第 i 格的顏色

int main() {
    int m, n;
    cin >> m >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    map<int, int> count;                         // count[c] = 視窗裡顏色 c 出現幾次
    int kinds = 0;                               // 視窗裡有幾種不同的顏色
    int answer = 0;
    for (int i = 1; i <= n; i++) {
        count[a[i]]++;                           // 右端：第 i 格進來
        if (count[a[i]] == 1) kinds++;           // 這種顏色本來沒有，現在有了
        if (i > m) {                             // 左端：第 i - m 格出去，視窗維持 m 格
            count[a[i - m]]--;
            if (count[a[i - m]] == 0) kinds--;   // 這種顏色沒了
        }
        if (i >= m && kinds == m) answer++;      // 視窗 [i - m + 1, i] 剛好 m 種顏色
    }
    cout << answer << endl;
    return 0;
}

幾個細節：

• 兩個邊界要分開想：第一次「有格子出去」是 \(i = m + 1\)（第 \(1\) 格出去），所以是 i > m；第一次「視窗湊滿」是 \(i = m\)，所以是 i >= m。少一個等號就會漏掉第一個視窗、多一個等號會把不存在的第 \(0\) 格拿去扣。
• 顏色編號到 \(10^9\)，不能開那麼大的陣列當計數表（\(4 \times 10^9\) 位元組，遠超記憶體限制），所以用 map。
• 每格進來一次、出去一次，\(O(n \log m)\)，本站實測 \(0.11\) 秒。

測過再交：範例只有一種 m

範例 \(m = 4\) 的三段完美彩帶都在中間；沒蓋到的是：\(n = m\) 只有一個視窗、每個視窗都完美（答案 \(n - m + 1\)）、重複的顏色出去之後 kinds 要正確減回來、很大的顏色編號、以及 \(m\) 很大的測資（驗速度）。

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

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

const int MAX_N = 200000;
int a[MAX_N + 1];                // a[i] = 第 i 格的顏色

int main() {
    int m, n;
    cin >> m >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    map<int, int> lastSeen;                      // lastSeen[c] = 顏色 c 上一次出現在第幾格（沒出現過就是 0）
    int start = 1;                               // 以第 i 格結尾、沒有重複顏色的最長一段，從第 start 格開始
    int answer = 0;
    for (int i = 1; i <= n; i++) {
        if (lastSeen[a[i]] + 1 > start) start = lastSeen[a[i]] + 1;   // 上次出現的位置之前都不能要
        lastSeen[a[i]] = i;
        if (i - start + 1 >= m) answer++;        // 不重複的一段至少 m 格 ⇒ 最後 m 格恰好是一段完美彩帶
    }
    cout << answer << endl;
    return 0;
}