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.

Run a for loop from 0 to N-1. Record the new data in the map in each iteration and remove the leftmost data. If the value in the map for the removed data becomes 0, decrement number--, indicating that one distinct number has been removed from the subinterval. If the value for the newly added number in the map becomes 1, increment number++, meaning a new distinct number has been added. During each iteration, check if the number equals M, and if it does, increment the answer by +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