【題解】ZeroJudge e289: 美麗的彩帶

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e289
【解題想法】Two Pointers【筆記

  • 數字介於 0 ~ 10150 之間:讀入測資後,以字串形式儲存。
  • 使用unordered_map,加快讀取速度。(因為key不需要排序。)
#include <iostream>
#include <unordered_map>
using namespace std;

string a[200005];
unordered_map < string, int > mp;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int m, n;
    while (cin >> m >> n){
        for (int i = 0; i < n; i++){
            cin >> a[i];
        }
        mp.clear();
        int cnt = 0;
        for (int i = 0; i < m; i++){
            if (!mp[a[i]]) cnt++;
            mp[a[i]]++;
        }
        int ans = (cnt == m);
        for (int L = 0, R = m; R < n; L++, R++){
            mp[a[L]]--;
            if (mp[a[L]] == 0) cnt--;
            if (mp[a[R]] == 0) cnt++;
            mp[a[R]]++;
            ans += (cnt == m);
        }
        cout << ans << "\n";
    }
}

Python 程式碼 (credit: Amy Chou)

while True:
    try:
        m, n = map(int, input().split())
        S = list(map(str, input().split()))
        dic = {}
        color = 0;
        for i in range(m):
            if S[i] not in dic.keys():
                color += 1
            dic[S[i]] = dic.get(S[i], 0) + 1

        if (color == m):
            ans = 1
        else:
            ans = 0

        L = 0
        R = m
        while (R < n):
            dic[S[L]] -= 1
            if (dic[S[L]] == 0):
                color -= 1
            if (dic.get(S[R], 0) == 0):
                color += 1
            dic[S[R]] = dic.get(S[R], 0) + 1
            if (color == m):
                ans += 1
            L += 1
            R += 1

        print(ans)
    except:
        break;
分享本文 Share with friends