ZeroJudge 解題筆記：s215.紙膠帶 (Tape)

作者：王一哲
日期：2026年9月1日


ZeroJudge 題目連結：s215.紙膠帶 (Tape)

題目 pdf 檔連結：紙膠帶 (Tape)

解題想法

題目是多筆測資。每筆測資第一列是代表紙膠帶長度的整數 $N$，第二列有 26 個正整數代表每種動物（字母）數量上限，第三列是代表紙膠帶圖案的字串。題目規定一段連續的漂亮紙帶必須符合以下 2 個條件：

1. 紙帶上正好有 3 種動物
2. 紙帶上最多只能有 1 種動物數量超過上限

這題要找符合條件的連續子字串，很適合用滑動視窗 (sliding window) 解題。不過麻煩的地方在於計分方式有 2 種：

1. 紙帶上沒有動物超過數量上限，以 3 種動物的最大數量計分。
2. 紙帶上正好有 1 種物物超過數量上限，以超過上限的數量計分。

為了保證滑動視窗取對範圍，要分別對 2 種計分方式各跑一次滑動視窗，因為可能在一段較短的視窗內正好有 1 種物物超過數量上限，但是這個數量很大，分數反而可能很高。

Python 程式碼

使用時間約為 0.8 s，記憶體約為 10.9 MB，通過測試。

def solve():
    import sys
    
    def get_tokens():
        for line in sys.stdin:
            for token in line.split():
                yield token
        
    tokens = get_tokens()
    
    result = []
    while True:
        try:
            N = int(next(tokens))
            limits = [0] * 26
            for i in range(26):
                limits[i] = int(next(tokens))
            s = next(tokens)
        except StopIteration:
            break
        
        def get_score(max_exceed):
            # 自訂函式，用滑動視窗取連續子字串分數，代入可以有幾個字母超標
            left = 0  # 視窗左端點
            imax = 0  # 最高分數
            curr = set()  # 視窗中的字母索引值
            exceed = set()  # 超標的字母
            cnt = [0] * 26  # 視窗中的字母計數器
            for right in range(N):  # 右端點 0 ~ N-1
                ri_idx = ord(s[right]) - ord('a')  # 右端點字母索引值
                curr.add(ri_idx)  # ri_idx 加入 curr
                cnt[ri_idx] += 1  # ri_idx 數量加 1
                # 如果 ri_idx 超標，ri_idx 加入 exceed
                if cnt[ri_idx] == limits[ri_idx] + 1: exceed.add(ri_idx)
                # 左端點向右滑，直到視窗內字母種類等於 3 且超標數量等於 max_exceed
                while left < right and (len(curr) > 3 or len(exceed) > max_exceed):
                    le_idx = ord(s[left]) - ord('a')  # 左端點字母索引值
                    left += 1
                    cnt[le_idx] -= 1
                    # 如果 le_idx 降回數量上限，exceed 移除 le_idx
                    if cnt[le_idx] == limits[le_idx]: exceed.remove(le_idx)
                    # 如果 le_idx 降回數量歸零，curr 移除 le_idx
                    if cnt[le_idx] == 0: curr.remove(le_idx)
                
                # 依照 max_exceed 計分
                score = 0
                if len(curr) == 3:  # 有 3 種字母才有分數
                    if max_exceed == 1 and len(exceed) == 1:  # 只有一種超標，這個字母數量是分數
                        score = cnt[list(exceed)[0]]
                    elif max_exceed == 0 and len(exceed) == 0:  # 沒有字母超標，curr 之中 3 個字母數量最大值是分數
                        score = max(cnt[idx] for idx in curr)
                # 更新最高分數
                imax = max(imax, score)
            return imax
        # 用兩次滑動視窗找最高分
        ans = max(get_score(0), get_score(1))
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 51 ms，記憶體約為 3.9 MB，通過測試。

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

// 自訂函式，用滑動視窗取連續子字串分數，代入可以有幾個字母超標
int get_score(const int, const int, const string&, const int*);

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N;
    while(cin >> N) {
        int limits[26] = {0};
        for(int i = 0; i < 26; i++) {
            cin >> limits[i];
        }
        string s; cin >> s;
        
        // 用兩次滑動視窗找最高分
        int ans = max(get_score(0, N, s, limits), get_score(1, N, s, limits));
        cout << ans << "\n";
    }
    return 0;
}

// 自訂函式，用滑動視窗取連續子字串分數，代入可以有幾個字母超標
int get_score(const int max_exceed, const int N, const string& s, const int* limits) {
    int left = 0, imax = 0;  // 視窗左端點，最高分數
    unordered_set<int> curr, exceed;  // 視窗中的字母索引值，超標的字母
    int cnt[26] = {0};  // 視窗中的字母計數器
    for(int right = 0; right < N; right++) {  // 右端點 0 ~ N-1
        int ri_idx = s[right] - 'a';  // 右端點字母索引值
        curr.insert(ri_idx);  // ri_idx 加入 curr
        cnt[ri_idx]++;  // ri_idx 數量加 1
        // 如果 ri_idx 超標，ri_idx 加入 exceed
        if (cnt[ri_idx] == limits[ri_idx] + 1) exceed.insert(ri_idx);
        // 左端點向右滑，直到視窗內字母種類等於 3 且超標數量等於 max_exceed
        while(left < right && (curr.size() > 3 || (int)exceed.size() > max_exceed)) {
            int le_idx = s[left] - 'a';  // 左端點字母索引值
            left++;
            cnt[le_idx]--;
            // 如果 le_idx 降回數量上限，exceed 移除 le_idx
            if (cnt[le_idx] == limits[le_idx]) exceed.erase(le_idx);
            // 如果 le_idx 降回數量歸零，curr 移除 le_idx
            if (cnt[le_idx] == 0) curr.erase(le_idx);
        }

        // 依照 max_exceed 計分
        int score = 0;
        if (curr.size() == 3) {  // 有 3 種字母才有分數
            if (max_exceed == 1 && exceed.size() == 1) {  // 只有一種超標，這個字母數量是分數
                score = cnt[*exceed.begin()];
            } else if (max_exceed == 0 && exceed.empty()) {  // 沒有字母超標，curr 之中 3 個字母數量最大值是分數
                for(auto idx : curr) {
                    score = max(score, cnt[idx]);
                }
            }
        }
        // 更新最高分數
        imax = max(imax, score);
    }
    return imax;
}

N, s, limits 放在 main 之外作為全域變數，使用時間約為 49 ms，記憶體約為 3.8 MB，通過測試。

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

int N, limits[26];
string s;

// 自訂函式，用滑動視窗取連續子字串分數，代入可以有幾個字母超標
int get_score(const size_t);

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    while(cin >> N) {
        for(int i = 0; i < 26; i++) {
            cin >> limits[i];
        }
        cin >> s;
        
        // 用兩次滑動視窗找最高分
        int ans = max(get_score(0), get_score(1));
        cout << ans << "\n";
    }
    return 0;
}

// 自訂函式，用滑動視窗取連續子字串分數，代入可以有幾個字母超標
int get_score(const size_t max_exceed) {
    int left = 0, imax = 0;  // 視窗左端點，最高分數
    unordered_set<int> curr, exceed;  // 視窗中的字母索引值，超標的字母
    int cnt[26] = {0};  // 視窗中的字母計數器
    for(int right = 0; right < N; right++) {  // 右端點 0 ~ N-1
        int ri_idx = s[right] - 'a';  // 右端點字母索引值
        curr.insert(ri_idx);  // ri_idx 加入 curr
        cnt[ri_idx]++;  // ri_idx 數量加 1
        // 如果 ri_idx 超標，ri_idx 加入 exceed
        if (cnt[ri_idx] == limits[ri_idx] + 1) exceed.insert(ri_idx);
        // 左端點向右滑，直到視窗內字母種類等於 3 且超標數量等於 max_exceed
        while(left < right && (curr.size() > 3 || exceed.size() > max_exceed)) {
            int le_idx = s[left] - 'a';  // 左端點字母索引值
            left++;
            cnt[le_idx]--;
            // 如果 le_idx 降回數量上限，exceed 移除 le_idx
            if (cnt[le_idx] == limits[le_idx]) exceed.erase(le_idx);
            // 如果 le_idx 降回數量歸零，curr 移除 le_idx
            if (cnt[le_idx] == 0) curr.erase(le_idx);
        }

        // 依照 max_exceed 計分
        int score = 0;
        if (curr.size() == 3) {  // 有 3 種字母才有分數
            if (max_exceed == 1 && exceed.size() == 1) {  // 只有一種超標，這個字母數量是分數
                score = cnt[*exceed.begin()];
            } else if (max_exceed == 0 && exceed.empty()) {  // 沒有字母超標，curr 之中 3 個字母數量最大值是分數
                for(auto idx : curr) {
                    score = max(score, cnt[idx]);
                }
            }
        }
        // 更新最高分數
        imax = max(imax, score);
    }
    return imax;
}