C. Balanced Bitstring
Description
定义一个字符串为\(k-balanced\)字符串，当且仅当字符串中包含有\(k/2\)个\(0\)和\(1\)
先给定一个\(n\)长度的\(0\),\(1\)字符串，其中存在未知位数的未知值，用\(?\)表示。
试问能否存在这样的一种情况使得该\(n\)长度的字符串能够满足任一\(k\)长度子串均为\(k-balanced\)字符串
Input
第一行输入测试用例组数\(t\)
之后每一组输入包含两行，第一行一个整数\(n\)和\(k\)
第二行为\(n\)长度的字符串，保证仅包含\(0\),\(1\),\(?\)三种元素
Output
一行输出\(YES\)或\(NO\)
Analysis
无技术含量，直接利用对应关系确定每一个\(i+p*k\) (\(p\)从0起始)，是否存在冲突关系即可
Accepted Code
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class T>
void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(long long &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
template <class T>
void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const long long &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
char in[300005];
int sen[300005];
int main()
{
int t;
_R(t);
while (t--)
{
int n, k;
_R(n);
_R(k);
_R(in);
for (int i = 0; i < n; i++)
{
sen[i] = in[i] - '0';
if (sen[i] > 1)
{
sen[i] = -1;
}
}
int cnt = 0;
int que = 0;
int flag = 1;
for (int i = 0; i < k; i++)
{
if (sen[i] == 1)
{
cnt++;
}
else if (sen[i] == -1)
{
que++;
}
}
if (cnt + que >= k / 2 && cnt <= k / 2)
{
flag = 1;
}
else
{
flag = 0;
}
if (flag == 1)
{
for (int i = 0; i < k && flag; i++)
{
if (flag == 0)
break;
int f = sen[i];
if (f == -1)
{
for (int j = i; j < n; j += k)
{
if (sen[j] != f)
{
f = sen[j];
break;
}
}
}
if (f != -1)
{
for (int j = i; j < n; j += k)
{
if (sen[j] == -1)
{
sen[j] = f;
}
else if (sen[j] != f)
{
flag = 0;
break;
}
}
}
}
}
if (flag) //再次判断头部能否合法
{
cnt = 0;
que = 0;
for (int i = 0; i < k; i++)
{
if (sen[i] == 1)
{
cnt++;
}
else if (sen[i] == -1)
{
que++;
}
}
if (!(cnt + que >= k / 2 && cnt <= k / 2))
{
flag = 0;
}
}
if (flag)
{
_W("YES\n");
}
else
{
_W("NO\n");
}
}
return 0;
}