1 条题解

  • 0
    @ 2026-1-14 19:51:10
    //这道题最容易想到的思路肯定是暴力枚举,对每个区间中每个字母出现的次数,进行统计,目前的第一个目前就如果统计区间内字母出现的次数
    //如果每一次循环重新统计肯定超时,所以肯定得要用前缀和,如果只是单纯的统计出现的次数,那么还是没法用到具体的区间,所以需要统计每个字符在每个位置出现的次数 
    
    #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
    上传者