欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #668 (Div. 2)-C. Balanced Bitstring

程序员文章站 2024-03-19 19:09:52
...

Codeforces Round #668 (Div. 2)-C. Balanced Bitstring

地址:http://codeforces.com/contest/1405/problem/C

思路:参考博客:https://blog.csdn.net/hzf0701/article/details/108439484
对于子串a[0,k-1],a[1,k],两者满足条件,则必须满足a[0]=a[k],而对于相邻子串a[x,x+k-1],a[x+1,x+k]则必须满足 a[x]==a[x+k],因此对于所有子串有满足a[x%k]=a[x],且第一个子串a[0,k-1]合法即可

Code:

#include<iostream>
using namespace std;

int n,m,T;
string s;

int main()
{
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--){
		cin>>n>>m>>s;
		bool boo=true;
		for(int i=m;i<n;++i)
			if(s[i%m]!=s[i]){
				if(s[i%m]=='?'){
					s[i%m]=s[i];
				}else if(s[i]!='?'){
					boo=false;	break;
				}
			}
		int s0=0,s1=0;
		for(int i=0;i<m;++i)
			if(s[i]=='0')	++s0;
			else if(s[i]=='1')	++s1;
		if(s0>m/2||s1>m/2)	boo=false;
		if(boo)	cout<<"YES"<<endl;
		else	cout<<"NO"<<endl;
	}
	
	return 0;
}