B. Diverse Substrings (2024.1.22灵茶)

链接 :?

Problem - 1748B - Codeforces

思路 :?

0-9一共十个字符，由于一个子串是diverse要满足每个字符出现的次数，不超过子串字符种类的数目，所以子串最长的情况也就是0-9每个10个，长度为100,所以可以暴力枚举所有子串 ；

详情请看代码 :?

代码:
?

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;

using namespace std;

inline void solve(){
	int n ; cin >> n ;
	string s ; cin >> s ;
	if(n==1){
		cout << 1 << endl;
		return ;
	}
	LL ans = 0 ;
	for(int i=0;i<n;i++){
		int t[10]{} ;// 每个出现次数 , 初始化为0 
		int cnt = 0 ; // 种类个数
		int ma = 0 ;// 最频繁出现字符出现次数
		for(int j=i;j<n&&(++t[s[j]-'0'])<=10 ;j++){
			ma = max(ma , t[s[j]-'0']);
			if(t[s[j]-'0']==1) cnt ++;
			if(cnt >= ma) ans ++;
		} 
	}
	cout << ans << endl ;
}
 
signed main()
{
    IOS
    int _ = 1;
    cin >> _;
    while(_ --) solve();
    return 0;
}