題目地址：點擊打開鏈接

思路：

普通的方法從左到右枚舉翻轉n^2復雜度會超時。

用白書上的維護記錄區(qū)間的翻轉次數(shù)，可以達到nlogn復雜度。

代碼：

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn = 1e5+5;char str[maxn];int k, m, a[maxn], f[maxn];bool solve(){    memset(f, 0, sizeof(f));    int res = 0, sum = 0, len = strlen(str);    for(int i = 0; i < len; i++)        a[i] = str[i]-'0';    for(int i = 0; i+k-1 < len; i++)    {        if((a[i]+sum)%2)        {            res++;            f[i] = 1;            sum++;        }        if(i-k+1 >= 0)            sum -= f[i-k+1];    }    for(int i = len-k+1; i < len; i++)    {        if((a[i]+sum)%2) return 0;        if(i-k+1 >= 0)            sum -= f[i-k+1];    }    return res <= m;}int main(void){    int t;    cin >> t;    while(t--)    {        scanf("%d%d", &k, &m);        scanf(" %s", str);        puts(solve() ? "YES" : "NO");    }    return 0;}