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

 

本文地址：https://blog.csdn.net/C_13579/article/details/109610700