Codeforces Round #668 (Div. 2) C

Codeforces Round #668 (Div. 2) C

/ 0评 / 1913次 / 4

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;
}

发表回复

您的电子邮箱地址不会被公开。

你好 No.60998