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

· · 题解

题目传送门

思路

这题 N 最大 10^5，暴力 O(n^3) 绝对会超时，如果用前缀和优化是 O(n^2)，还是很有可能 TLE。所以我们一定要观察规律来进行优化。题目说区间一定要字符出现次数等于 k，设区间一共有 j 种字符，那么区间长度一定等于 j \times k。那么如果当前左端点为 l，由于长度固定，所以计算可得 r=l+j \times k-1，这样就省下了一层循环。然后前缀和统计区间满足条件的字符个数，再判断就能稳稳 AC。

代码

:::success[AC Code]

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define rep(x, y, z) for (int x = (y); x <= (z); ++x)
#define per(x, y, z) for (int x = (y); x >= (z); --x)
inline void fast_io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
const int N = 1e5 + 5;
string s;
int n, k;
int pre[26][N]; //前缀和数组
int main() {
    fast_io(); //快读，如果不加容易TLE。建议加上
    cin >> n >> k >> s;
    rep(i, 1, n) {
        rep(c, 0, 25)
            pre[c][i] = pre[c][i - 1]; //前缀和预处理
        pre[s[i - 1] - 'a'][i]++;
    }
    int ans = 0;
    rep(l, 1, n) {
        for (int j = 1; l + j * k - 1 <= n; j++) { //内层字符种类循环
            int r = l + j * k - 1; //计算右端点
            int cnt = 0;
            rep(c, 0, 25) {
                if (pre[c][r] - pre[c][l - 1] == k) cnt++;
            }
            if (cnt == j) ans++; //满足条件答案就加一
        }
    }
    cout << ans;
    return 0;
}

::: 写题解属实不易，点个赞再走吧！