题解：B4560 [合肥市小学组 2024 T2] 买花

CJJ_niuniu · 2026-07-21 14:28:16 · 题解

思路

从题目可以知道，能满足条件的字符串长度一定是 K 的倍数。

又因为，小写英文字母只有 26 个，所以 K 的倍数最多到 26 倍。

因此，现在的问题转换成了：如何判断是否每种花都恰好有 K 枝。

可以令 S_{i,j} 是原字符串的，各种小写字母的前缀和数组。

（S_{i,j} 表示从开头到第 i 个所包含第 j 种小写字母的个数）。

所以在区间 l\sim r 中，第 j 种小写字母的个数是：S_{r,j}-S_{l-1,j}。

因此，可以先枚举 K 的倍数（用于计算区间长度），然后枚举出 r，再用 r 算出 l，接着进行判断是否合法，统计后输出结果。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAX 100000
int N,K;
string a;
int S[MAX+5][28];
signed main(){
    cin>>N>>K>>a;
    for(int i=0;i<N;i++){
        int a1=a[i]-'a'+1;
        for(int j=1;j<=26;j++){
            S[i+1][j]=S[i][j];
        }S[i+1][a1]+=1;
    }
    int ans=0;
    for(int i=1;i<=26;i++){
        for(int r=i*K;r<=N;r++){
            int l=r-i*K+1;
            int sum=0;
            for(int j=1;j<=26;j++){
                if(S[r][j]-S[l-1][j]==K){
                    sum++;
                }
            }
            if(sum==i) ans++;
        }
    }cout<<ans;
    return 0;
}