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

AutumnMoon · 2026-07-24 14:30:45 · 题解

题意

给一个由小写字母组成的字符串，找连续一段子串，满足：这段里面出现过的每一种字母，数量恰好等于 k，没出现的字母不用管。求一共有多少种这样的连续区间方案。

推导

设 cnt_r[c] 表示前 r 个字符里，字符 c 的总数量。 区间 [l+1,r] 中字符 c 的数量为 val = cnt_r[c] - cnt_l[c]；\ 区间合法要求：val = 0 或 val=k；

• val=0$：$cnt_r[c] = cnt_l[c]
• val=k$：$cnt_r[c] - k = cnt_l[c]

两式同时对 k 取模：cnt_r[c] \bmod k = cnt_l[c] \bmod k。

结论：能组成合法区间的两个位置 l 和 r，26 个字符计数模 k 的结果必须完全相同喵。

思路

• 将 26 个字母的模 k 结果打包为状态 \text{Key}；
• map 保存每种 \text{Key} 对应的全部历史前缀计数；
• 算出当前 \text{Key}；
• 取出所有相同 \text{Key} 的历史状态，检验差值全部小等于 k，满足则答案加 1；
• 把当前前缀计数存入 map，继续向后遍历。

注意：n\le 10^5。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100005;
int n,k,cnt[26];
char s[N];
using Key=array<int,26>;

signed main(){
    cin>>n>>k>>s+1;
    map<Key,vector<array<int,26>>> mp;
    array<int,26> init{};
    mp[init].push_back(init);
    long long ans=0;
    for(int i=1;i<=n;i++){
        int c=s[i]-'a';
        cnt[c]++;
        Key now{};
        for(int j=0;j<26;j++) now[j]=cnt[j]%k;
        for(auto &pr:mp[now]){
            bool ok=1;
            for(int j=0;j<26;j++){
                if(cnt[j]-pr[j]>k){
                    ok=0;
                    break;
                }
            }
            if(ok) ans++;
        }
        array<int,26> cur;
        for(int j=0;j<26;j++) cur[j]=cnt[j];
        mp[now].push_back(cur);
    }
    cout<<ans;
}