ZeroJudge E289: Beautiful Ribbons

You have a rainbow-colored ribbon, but since it comes from another world, it may have more than just 7 colors (in that world, a rainbow could have as many as 87 colors). You define the beauty of the ribbon by the number of subarrays of length M that contain exactly M distinct colors.

Now you need to write a program to calculate the beauty of a string.

Sample Inputs/Outputs

Thought Process

Since the numbers can be as large as 10^150, use strings to store the ribbon’s numbers. Utilize a map (or dictionary) to keep track of the count of each number in the current subinterval, and declare a variable number to record how many distinct numbers are present in the current subinterval.

跑一個 For迴圈 從 0 到 N-1，並且每次都將新的資料紀錄到 Map 中並且把最左邊的資料做刪除，如果刪除的資料中的 Map 值是 0，那就 number–，代表區段中少了一個不同的數字。並且如果新加入的數字的 Map 值是 1，代表是一個全新的數字 number++，每次迴圈都要判斷 number 是否等於 M，如果有等於的話就將答案 +1。

Sample Code－ZeroJudge E289: Beautiful Ribbons

#include <iostream>
#include <map>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int M, N;
    string num[200000] = {};
    map<string, int>appear;
    cin >> M >> N;
    for (int i = 0; i<N; i++) {
        cin >> num[i];
    }
    int count = 0, last = 0, ans = 0, number = 0;
    for (int i = 0; i<N; i++) {
        const string current = num[i];
        if (count <= M-1) {
            appear[current]++;
            count++;
            if (appear[current] == 1) number++;
            if (number == M) ans++;
        }
        else {
            appear[num[last]]--;
            if (appear[num[last]] == 0) number--;
            appear[current]++;
            if (appear[current] == 1) number++;
            last++;
            if (number == M) ans++;
        }
    }
    cout << ans << "\n";
}

//ZeroJudge E289
//Dr. SeanXD