A
考虑枚举每一个区间,考虑如何 \(\mathcal O(1)\) 判断。
如果区间符合条件当且仅当区间内没有 \(0\),区间外没有 \(1\)。
维护一个前缀和即可。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int T,n,k,sum0[N],sum1[N];
string s;
signed main()
{
cin>>T;
while(T--)
{
cin>>n>>k>>s;s=' '+s;
for(int i=0;i<=n;++i)sum0[i]=sum1[i]=0;
for(int i=1;i<=n;++i)
{
sum0[i]=sum0[i-1]+(s[i]=='0');
sum1[i]=sum1[i-1]+(s[i]=='1');
}
int cnt=0;
for(int i=1;i+k-1<=n;++i)
{
if((sum0[i+k-1]-sum0[i-1]==0)&&
(sum1[i+k-1]-sum1[i-1]==sum1[n]))cnt++;
}
if(cnt==1)cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}