CF1690D Black and White Stripe

Coros_Trusds · 2022-06-08 06:41:49 · 题解

题目分析

令 \verb!B! 为 1,\verb!W! 为 0。然后序列就变成了一个 01 序列。

求出这个序列的前缀和，然后枚举每个位置 i，假设这个位置 i 为连续 m 个 1 的起点，那么我们要的终点就是 i+m-1，看一下 [i,i+m-1] 这段区间里 0 的个数就好了，其实这也就是 m-(sum[i+m-1]-sum[i-1])。

代码

// Problem: D. Black and White Stripe
// Contest: Codeforces - Codeforces Round #797 (Div. 3)
// URL: https://codeforces.com/contest/1690/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Date:2022-06-07 23:12
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>
#include <climits>//need "INT_MAX","INT_MIN"
#include <cstring>//need "memset"
#include <numeric>
#include <algorithm>
#include <cmath>
#define enter putchar(10)
#define debug(c,que) std::cerr << #c << " = " << c << que
#define cek(c) puts(c)
#define blow(arr,st,ed,w) for(register int i = (st);i <= (ed); ++ i) std::cout << arr[i] << w;
#define speed_up() std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
#define mst(a,k) memset(a,k,sizeof(a))
#define stop return(0)
const int mod = 1e9 + 7;
inline int MOD(int x) {
    if(x < 0) x += mod;
    return x % mod;
}
namespace Newstd {
    inline int read() {
        int ret = 0,f = 0;char ch = getchar();
        while (!isdigit(ch)) {
            if(ch == '-') f = 1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            ret = (ret << 3) + (ret << 1) + ch - 48;
            ch = getchar();
        }
        return f ? -ret : ret;
    }
    inline double double_read() {
        long long ret = 0,w = 1,aft = 0,dot = 0,num = 0;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') w = -1;
            ch = getchar();
        }
        while (isdigit(ch) || ch == '.') {
            if (ch == '.') {
                dot = 1;
            } else if (dot == 0) {
                ret = (ret << 3) + (ret << 1) + ch - 48;
            } else {
                aft = (aft << 3) + (aft << 1) + ch - '0';
                num ++;
            }
            ch = getchar();
        }
        return (pow(0.1,num) * aft + ret) * w;
    }
    inline void write(int x) {
        if(x < 0) {
            putchar('-');
            x = -x;
        }
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace Newstd;

const int INF = 0x3f3f3f3f;
const int N = 2e5 + 5;
int sum[N];
char s[N];
int T,n,m;
inline void init() {
    mst(sum,0);
}
inline int Abs(int x) {
    return x > 0 ? x : -x;
}
inline void solve() {
    n = read(),m = read();
    scanf("%s",s + 1);
    int len = s[1] == 'B';
    for (register int i = 2;i <= n; ++ i) {
        if (s[i] != s[i - 1] && s[i] == 'B') {
            len = s[i] == 'B';
        } else if (s[i] == s[i - 1] && s[i] == 'B') {
            len ++;
        }
    }
    if (len >= m) {
        puts("0");
        return;
    }
    for (register int i = 1;i <= n; ++ i) {
        sum[i] = sum[i - 1] + (s[i] == 'B');
    }
    int ans = INF;
    for (register int i = 1;i <= n; ++ i) {
        int at = i + m - 1;
        if (at > n) continue;
        ans = std::min(ans,(at - i + 1) - (sum[at] - sum[i - 1]));
    }
    printf("%d\n",ans);
}
int main(void) {
    T = read();
    while (T --) {
        init();
        solve();
    }

    return 0;
}