526互联

Diverse Substrings

发布时间 2023-07-24 11:27:11作者: o-Sakurajimamai-o

# Diverse Substrings

## 题面翻译

定义一个数字串是**多变的**当且仅当其中所有数字的重复次数均不超过其中不同数字的种类数。

给定一个由 $0$ 到 $9$ 组成的长为 $n$ 的数字串 $s$，求其不同的**多变的**子串 $s_{[l,r]}$ 的个数。

## 题目描述

A non-empty digit string is diverse if the number of occurrences of each character in it doesn't exceed the number of distinct characters in it.

For example:

- string "7" is diverse because 7 appears in it $ 1 $ time and the number of distinct characters in it is $ 1 $ ;
- string "77" is not diverse because 7 appears in it $ 2 $ times and the number of distinct characters in it is $ 1 $ ;
- string "1010" is diverse because both 0 and 1 appear in it $ 2 $ times and the number of distinct characters in it is $ 2 $ ;
- string "6668" is not diverse because 6 appears in it $ 3 $ times and the number of distinct characters in it is $ 2 $ .

You are given a string $ s $ of length $ n $ , consisting of only digits $ 0 $ to $ 9 $ . Find how many of its $ \frac{n(n+1)}{2} $ substrings are diverse.

A string $ a $ is a substring of a string $ b $ if $ a $ can be obtained from $ b $ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Note that if the same diverse string appears in $ s $ multiple times, each occurrence should be counted independently. For example, there are two diverse substrings in "77" both equal to "7", so the answer for the string "77" is $ 2 $ .

## 输入格式

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the string $ s $ .

The second line of each test case contains a string $ s $ of length $ n $ . It is guaranteed that all characters of $ s $ are digits from $ 0 $ to $ 9 $ .

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

## 输出格式

For each test case print one integer — the number of diverse substrings of the given string $ s $ .

## 样例 #1

### 样例输入 #1

```
7
1
7
2
77
4
1010
5
01100
6
399996
5
23456
18
789987887987998798
```

### 样例输出 #1

```
1
2
10
12
10
15
106
```

## 提示

In the first test case, the diverse substring is "7".

In the second test case, the only diverse substring is "7", which appears twice, so the answer is $ 2 $ .

In the third test case, the diverse substrings are "0" ( $ 2 $ times), "01", "010", "1" ( $ 2 $ times), "10" ( $ 2 $ times), "101" and "1010".

In the fourth test case, the diverse substrings are "0" ( $ 3 $ times), "01", "011", "0110", "1" ( $ 2 $ times), "10", "100", "110" and "1100".

In the fifth test case, the diverse substrings are "3", "39", "399", "6", "9" ( $ 4 $ times), "96" and "996".

In the sixth test case, all $ 15 $ non-empty substrings of "23456" are diverse.

//由于题目要求,可以得到,每个数都有一个最大的限制范围,考虑最差情况,如果每个数都不同
//那么只需要100位即可,因为,每个数的大小最多不能超过9,如果到100,那么一定会有一个数会成为第11个数
//所以从i位开始,只需要枚举之后的最多i+100位就可以了
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,a[N],res,num,ans,m,f[11];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        res=0;
        cin>>n>>s;
        for(int i=0;i<min(n,(int)(i+101));i++){
            num=0;memset(f,0,sizeof f);
            for(int j=i;j<min(n,(int)(i+101));j++){
                if(f[s[j]-'0']==0) num++;
                f[s[j]-'0']++;
                bool a=false;
                for(int k=0;k<10;k++) if(f[k]>num) a=true;
                if(!a) res++;
            }
        }
        cout<<res<<endl;
    }
    return 0;
}