# APCS實作題2019年6月第4題：美麗的彩帶

> 日期：2024年7月11日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=e289)

## 題目

### 問題描述

你有一條彩虹色的彩帶，但是因為它是異世界來的彩帶，所以可能不只七個顏色(異世界有可能有87色的彩虹)，你有一個定義彩帶美麗度的標準，你定義一條彩帶的美麗度為它所擁有的長度為 $m$ 且有 $m$ 種顏色的子區間數量。現在你需要寫一個程式來計算一個字串的美麗度。
<br />

### 輸入說明

第一行有兩個數字 $m$ 和 $n$，代表定義的子區間長度和彩帶長度。
第二行有 $n$ 個數字代表彩帶的顏色。

<br />

### 輸出格式

輸出這條彩帶的美麗度。
<br />

### 範例輸入

3 7
1 2 3 5 4 5 4

### 範例輸出

3

<br />

## Python 程式碼

### 寫法1，配合 set 直接掃過去

很直接的作法，但是效率不好，第10筆測資超時。

m, n = map(int, input().split())  # 讀取子區間長度 m、彩帶長度 n
cs = list(map(int, input().split()))  # 讀取彩帶顏色
ans = 0  # 答案
for i in range(n-m+1):  # 掃過一輪，i = 0 ~ n-m
    sub = cs[i:i+m]  # 子區間
    if len(set(sub)) == m: ans += 1  # 將 sub 轉成 set，計算顏色種類，如果等於 m 則 ans 加 1
print(ans)  # 印出答案

<br /><br />

### 寫法2，固定窗口大小，只處理右端新增、左端出界的項目

第18筆測資費時最久，約為 0.4 s，使用記憶體最多約為 105.6 MB，通過測試。

from collections import Counter  # 使用計數器 Counter

m, n = map(int, input().split())  # 讀取子區間長度 m、彩帶長度 n
cs = list(map(int, input().split()))  # 讀取彩帶顏色
ans = 0  # 答案
cnt = Counter(cs[:m])  # 計數器，先處理 cs[0:m]
if len(cnt) == m: ans += 1  # 如果有 m 種顏色，ans 加 1

for i in range(1, n-m+1):  # 掃過剩下的彩帶
    # 如果出界的彩帶於 cnt 中只有一段，從 cnt 中刪除；如果數量大於1則減1
    if cnt[cs[i-1]] == 1: del cnt[cs[i-1]]
    elif cnt[cs[i-1]] > 1: cnt[cs[i-1]] -= 1
    # 如果新增的彩帶不在 cnt 中，新增此段的顏色，數量為1；反之數量加1
    if cs[i+m-1] not in cnt: cnt[cs[i+m-1]] = 1
    else: cnt[cs[i+m-1]] += 1
    # 如果 cnt 長度等於 m，ans 加1
    if len(cnt) == m: ans += 1
    
print(ans)  # 印出答案

<br /><br />

## C++ 程式碼

### 寫法1，配合 set 直接掃過去

很直接的作法，但是效率不好，第5筆測資超時。

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main() {
    int m, n; cin >> m >> n;  // 讀取子區間長度 m、彩帶長度 n
    vector<int> cs (n, 0);
    for(int i=0; i<n; i++) cin >> cs[i];  // 讀取彩帶顏色 
    int ans = 0;  // 答案
    for(int i=0; i<=n-m; i++) {  // 掃過一輪，i = 0 ~ n-m
        set<int> sub (cs.begin()+i, cs.begin()+i+m);  // 子區間
        if (sub.size() == m) ans++;  // 將 sub 轉成 set，計算顏色種類，如果等於 m 則 ans 加 1
    }
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br /><br />

### 寫法2，固定窗口大小，只處理右端新增、左端出界的項目

最後4筆測資輸入的數值超大，上限為 $10^{150}$，如果用 int 作為 cnt 的 key 值會爆掉，要用 string 作為 key 值。費時最久約為 0.2 s，使用記憶體最多約為 64.5 MB，通過測試。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速，不然最後4筆測資會超時
    int m, n; cin >> m >> n;  // 讀取子區間長度 m、彩帶長度 n
    vector<string> cs (n);
    for(int i=0; i<n; i++) cin >> cs[i];  // 讀取彩帶顏色 
    int ans = 0, num = 0;  // 答案 ans，子區間內顏色種類數量 num
    unordered_map<string, int> cnt;  // 計數器
    for(int i=0; i<m; i++) {  // 先處理 cs[0:m]
        if (cnt[cs[i]] == 0) num++;  // 如果原來 cnt 中 cs[i] 的數量為0，增加一種新的顏色，num 加1
        cnt[cs[i]]++;  // cnt 中對應的顏色數量加1
    }
    if (num == m) ans++;

    for(int i=1; i<=n-m; i++) {  // 掃過剩下的彩帶
        // 如果出界的彩帶於 cnt 中原來只有一段，子區間中少一種顏色，num 減1
        if (cnt[cs[i-1]] == 1) num--;
        cnt[cs[i-1]]--;
        // 如果新增的彩帶不在 cnt 中，新增此段的顏色，num 加1
        if (cnt[cs[i+m-1]] == 0) num++;
        cnt[cs[i+m-1]]++;
        // 如果有 m 種顏色，ans 加 1
        if (num == m) ans++;
    }
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`