CF1748B-Diverse Substrings

长度为n的字符串，求出子串（只能从头尾依次删字符来得到子串）中，相同字符出现的最高次数小于等于不同字符的个数，这样的子串的个数 以1~n个字符作为起点，枚举终点的位置来判断每种情况是否符合要求（Complexity:O(n 2 )） 根据题目，只会出现'0'~'9'，所以符合题目要求的子串最长为100，相同字符出现的最高次数不超过10，所以枚举终点时，相同字符出现的最高次数超过10，就退出循环，接着下一个起点继续枚举终点的情况(Complexity:O(n×10 2 ))

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 void solve()
 4 {
 5     int n, ans=0;
 6     cin>>n;
 7     string s;
 8     cin>>s;
 9     for(int i=0; i<s.size(); i++){
10         //起点为i，枚举终点，需要维护这段子串中，相同字符出现的最高次数，不同字符的个数，以及每个字符已经出现的次数（当该次数超过10时，退出这次循环） 
11         int fr[10]={0}, max_fr=0, num_distinct=0;
12         for(int j=i; j<s.size() && (++fr[s[j]-'0'])<=10; j++){
13             max_fr=max(max_fr, fr[s[j]-'0']);
14             if(fr[s[j]-'0']==1) //如果这个字符出现次数变成1，说明这个字符是之前没有出现过的字符，所以num_distinct+=1 
15                 num_distinct++;
16             if(max_fr<=num_distinct)
17                 ans++;
18         }
19     }
20     cout<<ans<<'\n';
21 }
22 int main(void)
23 {
24     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
25     int T=1;
26     cin>>T;
27     while(T--)solve();
28     return 0;
29 }