P76032 染黑连续一段 — 题解

专题： 滑动窗口
适用题目： 新生 OJ 本地题包中的 P76032，不要直接用于外站同名题。

解题思路

初始窗口统计 k 个位置中的 W 个数，滑动时加右边新字符、减左边旧字符的贡献。

复杂度

每组时间 $O(n)$，额外空间 $O(n)$。

易错点

窗口长度始终恰好是 k，不能选任意长度。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int main(void) {
    int t;scanf("%d",&t);static char s[100005];
    while(t--){int n,k;scanf("%d%d%100004s",&n,&k,s);
        int curr=0;
        for(int i=0;i<k;i++)curr+=s[i]=='W';
        int best=curr;
        for(int i=k;i<n;i++){
            curr+=(s[i]=='W')-(s[i-k]=='W');
            if(curr<best)best=curr;
        }
        printf("%d\n",best);
    }
    return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int n,k;
        string s;
        cin>>n>>k>>s;
        int curr=0;
        for(int i=0;i<k;i++)curr+=s[i]=='W';
        int best=curr;
        for(int i=k;i<n;i++){
            curr+=(s[i]=='W')-(s[i-k]=='W');
            best=min(best,curr);
        }
        cout<<best<<nl;
    }
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。