B. Diverse Substrings (2024.1.22灵茶)

本文主要是介绍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()
{IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}

这篇关于B. Diverse Substrings (2024.1.22灵茶)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---