首页 > 其他分享 >AtCoder Regular Contest 150

AtCoder Regular Contest 150

时间:2022-10-17 22:12:27浏览次数:77  
标签:150 Contest int AtCoder Regular 区间

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

标签:150,Contest,int,AtCoder,Regular,区间
From: https://www.cnblogs.com/lnwhl/p/16800905.html

相关文章