地址: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
黄山市民网:https://www.huangshanshimin.com/