Codeforces Round #668 (Div. 2)-C. Balanced Bitstring
程序员文章站
2024-03-19 19:09:52
...
地址: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;
}
推荐阅读
-
C. Balanced Bitstring(字符串+思维) Codeforces Round #668 (Div. 2)
-
Codeforces Round #668 (Div. 2)-C. Balanced Bitstring
-
Codeforces Round #561 (Div. 2) C. A Tale of Two Lands
-
Codeforces Round #459 (Div. 2) C. The Monster(枚举+思维)
-
Codeforces Round #449 (Div. 2) C. Nephren gives a riddle
-
Codeforces Round #256 (Div. 2) C. Painting Fence(分治贪心)_html/css_WEB-ITnose
-
Codeforces Round #320 (Div. 2) C. A Problem about Polyline ( 数学 )
-
Codeforces Round #654 (Div. 2)-C. A Cookie for You
-
Educational Codeforces Round 85 (Rated for Div. 2) C. Circle of Monsters(前缀和 预处理 贪心)
-
Codeforces Round #651 (Div. 2) C. Number Game