CF 1405C Balanced Bitstring

题目描述

https://codeforces.com/contest/1405/problem/C

Solution

不妨假设在第一个窗口合法的情况下，每次窗口右移都必须保证出去的那个和进来的那个必须是同一个数字

那么我们只需要在满足这个的条件下，使得第一个窗口合法即可

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#define maxn 300010
#define maxm 100010
#define ll long long
#define cn const node
using namespace std;

int n, m, a[maxn];

char s[maxn];

void work() {
    cin >> n >> m >> s + 1;
    if (m & 1) return (void) (cout << "NO\n");
    for (int k = 0; k < m; ++k) {
        int f = -1;
        for (int i = k; i <= n; i += m) {
            if (!i || s[i] == '?') continue;
            if (~f && s[i] - '0' != f) return (void) (cout << "NO\n");
            f = s[i] - '0';
        }
        if (~f) for (int i = k; i <= n; i += m) s[i] = f + 48;
    } int sum = 0, v = 0;
    for (int i = 1; i <= m; ++i) {
        if (s[i] == '?') ++v;
        else sum += s[i] == '1' ? -1 : 1;
    }
    abs(sum) <= v ? cout << "YES\n" : cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}