1 条题解
-
0
//这道题最容易想到的思路肯定是暴力枚举,对每个区间中每个字母出现的次数,进行统计,目前的第一个目前就如果统计区间内字母出现的次数 //如果每一次循环重新统计肯定超时,所以肯定得要用前缀和,如果只是单纯的统计出现的次数,那么还是没法用到具体的区间,所以需要统计每个字符在每个位置出现的次数 #include <bits/stdc++.h> using namespace std; int n,k; string s; int brr[30]={}; int arr[30][100100]={}; int main(){ cin>>n>>k>>s; s='#'+s; //解题关键,数据的预处理 //统计每一个字母在每一个区间出现的次数,利用的是前缀和思想 int m=0; for(int i=1;i<s.size();i++){ arr[s[i]-'a'][i]++;//1.对当前字母进行统计 brr[s[i]-'a']++; if(brr[s[i]-'a']==1) m++; for(int j=0;j<26;j++){//对当前位置,所有字母的出现次数进行更新。 arr[j][i]+=arr[j][i-1]; } } //对所有字母的可能性进行统计,可能性就是出现了多少种字母,那么区间就得是多大 int sum=0; for(int i=1;i<=m;i++){ //根据字母的数量划分区间 for(int j=1;j<=n-i*k+1;j++){ //接下来需要检测区间的字母数量是否满足条件 int flag=1; for(int l=0;l<26;l++){//这里为什么对26个字母遍历而不是对区间每个字母遍历呢?你这样想,只要字母在这个区间出现了,那么他就必须成立 int a=arr[l][j+i*k-1]-arr[l][j-1]; if(a==0) continue; if(a!=k){ flag=0; break; } } if(flag) sum++; } } cout<<sum; return 0; }
- 1
信息
- ID
- 1446
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者