Codeforces Round #668 (Div. 2)-C. Balanced Bitstring
程序员文章站
2022-04-05 23:41:29
地址: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:#.....
地址: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
推荐阅读
-
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
-
Codeforces Round #668 (Div. 2)-C. Balanced Bitstring
-
Educational Codeforces Round 99 (Rated for Div. 2) C. Ping-pong
-
Codeforces Round #256 (Div. 2) C. Painting Fence(分治贪心)_html/css_WEB-ITnose
-
Codeforces Round #277 (Div. 2)-C. Palindrome Transformation (贪心)_html/css_WEB-ITnose
-
Codeforces Round #277 (Div. 2)-C. Palindrome Transformation (贪心)_html/css_WEB-ITnose
-
C. Mortal Kombat Tower(动态规划)Educational Codeforces Round 95 (Rated for Div. 2)