Codeforces Round #668 C. Balanced Bitstring (Div. 2)题解(思维)

题目链接

题目大意

给你一个长为n的01串，要你使得每一个01串中0和1的个数都要相等，01串中有?字符，你可以使得这个字符变为0或1，要你求是否可以满足条件。输出YES或NO

题目思路

这个题目的难度其实不大，但是最主要的问题是你要发现s[i]=s[i%k],然后就变的简单了，具体实现看代码

代码

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<cstdio>

#include<vector>

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<unordered_map>

#define fi first

#define se second

#define debug printf(" I am here\n");

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int maxn=3e5+5,inf=0x3f3f3f3f,mod=1e9+7;

const double eps=1e-10;

int n,k;

char s[maxn];

signed main(){

    int _;

    scanf("%d", &_);

    while(_--){

        scanf("%d%d", &n,&k);

        scanf("%s",s+1);

        bool flag=1;

        int zer=0,one=0;

        for(int i=1;i<=k;i++){

            char ch='2';

            for(int j=i;j<=n;j+=k){

                if(s[j]=='?'){

                    continue;

                }else {

                    if(ch=='2'){

                        ch=s[j];

                    }else if(ch!=s[j]){

                        flag=0;

                        break;

                    }

                }

            }

            if(!flag) break;

            if(ch=='1'){

                one++;

            }else if(ch=='0'){

                zer++;

            }

        }

        if(2*max(zer,one)>k){//不能超过一半的元素

            flag=0;

        }

        printf(flag?"YES\n":"NO\n");

    }

    return 0;

}

巴特西

Codeforces Round #668 C. Balanced Bitstring (Div. 2)题解(思维)

题目链接

题目大意

题目思路

代码

最新文章

热门文章