1405. C. Balanced Bitstring(思维)

link

考虑到 [ 1 , k ] [1,k] [1,k]和 [ 2 , k + 1 ] [2,k+1] [2,k+1]只有一个位置不同,所以必定有 a 1 = a k + 1 a_1=a_{k+1} a1​=ak+1​

推广一下得到 a i = a i + k a_i=a_{i+k} ai​=ai+k​,用这个可以特判掉一些无解的情况

也就是可以分为 k k k组

a 1 = a 1 + k = a 2 + k . . . a_1=a_{1+k}=a_{2+k}... a1​=a1+k​=a2+k​...

这样如果只存在一个 0 / 1 0/1 0/1,我们就可以把其他问号都赋值为 0 / 1 0/1 0/1,若都有就无解

否则,我们确保 [ 1 , k ] [1,k] [1,k]有解,那么可以推断 [ 2 , k + 1 ] [2,k+1] [2,k+1]必然有解,因为我们可以令 a k + 1 = a 1 a_{k+1}=a_1 ak+1​=a1​

由 [ 2 , k ] [2,k] [2,k]有解又可以推到之后的每一个大小为 k k k的子串有解,所以只需要检查 [ 1 , k ] [1,k] [1,k]是否有解即可

#include 
using namespace std;
const int maxn = 3e5+10;
int t,n,k,ok[maxn];
char a[maxn];
int main()
{
	cin >> t;
	while( t-- )
	{
		cin >> n >> k >> ( a+1 );
		int res = 1;
		for(int i=1;i<=k;i++)
		{
			int flag = 0;
			for(int j=i;j<=n;j+=k)
			{
				if( a[j]=='0' )	flag |= 1;
				else if( a[j]=='1' )	flag |= 2;
			}
			if( flag==3 )	res = 0;
			if( flag==0 )	continue;
			for(int j=i;j<=n;j+=k)
			{
				if( flag==1 )	a[j] = '0';
				else	a[j] = '1';	
			}	
		}
		int sum = 0, z = 0;
		for(int i=1;i<=k;i++)
		{
			if( a[i]=='0' )	sum++;
			else if( a[i]=='1' )	sum--;
			else	z++;
		}
		if( res && abs( sum )<=z )	cout << "YESn";
		else	cout << "NOn";	
	}
}