简要题意
给定一个长度为 \(n\) 的只由数字 \(0\) 到 \(9\) 组成的字符串 \(s\) ,求 \(s\) 中有多少个子串满足 所有数字出现次数的最大值小于等于出现的不同数字的数量 ,其中 \(n \le 10^5\) 。
分析
题目拿到手,先想暴力解法。我们可以直接枚举 \(s\) 的所有子串,并统计子串中数字 \(i\) 出现的次数(记为 \(cnt_i\) ),以及子串中出现的数字个数(记为 \(sum\) )。再记 \(maxn=\max(cnt_i)\) ,比较 \(maxn \le sum\) 并记录答案即可。
for(int i=1;i<=n;i++){
memset(cnt,0,sizeof(cnt));
maxn=0;
sum=0;
for(int j=i;j<=n;j++){
int pos=a[j];
if(!cnt[pos]) sum++;
cnt[pos]++;
maxn=max(maxn,cnt[pos])
if(sum>=maxn) ans++;
}
}
显然,这种 \(O(n^2)\) 的时间复杂度是过不去 \(n \le 10^5\) 的。所以我们考虑优化。
优化
显然,所有的数字个数不会超过 \(10\) ,所以 \(sum \le 10\) ,而 \(maxn \le 10^5\) ,所以可以得知符合条件的子串的长度一定不会大于 \(100\) (每个数字各出现 \(10\) 次)。所以,我们可以将
for(ll j=i;j<=n;j++)
改成
for(ll j=0;j+i<=n&&j<=100;j++)
这样就可以将我们的时间复杂度优化到 \(O(n\times 100)\) ,轻松 AC 。
完整代码
#include<bits/stdc++.h>
#define ll long long
#define ma 214514
using namespace std;
ll read(){
char ch=getchar();
ll x=0,f=1;
while('0'>ch||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while('0'<=ch&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
ll t;
ll n;
ll cnt[10];
ll maxn;
ll a[ma];
ll ans=0;
ll sum=0;
char x;
int main(){
t=read();
while(t--){
n=read();
memset(cnt,0,sizeof(cnt));
ans=0,sum=0;
for(ll i=1;i<=n;i++){
x=getchar();
a[i]=x-'0';//读入时转化成字符读入,防止读入一长串数字
}
for(ll i=1;i<=n;i++){
memset(cnt,0,sizeof(cnt));
maxn=0;
sum=0;
for(ll j=0;j+i<=n&&j<=100;j++){
ll pos=a[j+i];
if(!cnt[pos]) sum++;
cnt[pos]++;
maxn=max(maxn,cnt[pos]);
if(sum>=maxn) ans++;
}
}
printf("%lld\n",ans);
}
return 0;
}
标签:子串,10,ch,CF1748B,题解,ll,le,maxn
From: https://www.cnblogs.com/mukar/p/17057348.html