CF1658F Juju and Binary String 做题记录

对于一个 01 序列 $b$，定义 $f(b)=\frac{\sum\limits [b_i=1]}{|b|}$，即 $b$ 中 $1$ 的个数除以它的长度。

现给定一个长度为 $n$ 的序列 $a$ 和一个正整数 $m$，请你找到 $a$ 的若干不相交子串使得这些它们拼起来后得到的 01 串 $p$ 满足 $|p|=m$ 且 $f(p)=f(a)$。输出方案。

$1\le m\le n\le 2\times 10^5$。

设 $c1=\sum[a_i=1],x=\frac{c1\cdot m}{n}$ 即 $p$ 中需要的 $1$ 的个数。

首先显然若 $\frac{c1\cdot m}{n}$ 不是整数即 $m$ 不是 $\frac{n}{\gcd(n,c1)}$ 的倍数则无解，否则一定有解。

对于这种题，一般猜想答案 $\le 2$。那么猜想最多只需要两段，考虑证明。

考虑最多两段不交的区间可能是什么，不难想到它有可能是一个环上的一段区间。那么考虑把 $a$ 放到环上，即令 $a_{i+n}=a_i$。设 $c_i=\sum\limits_{j=i}^{i+m-1}[a_j=1]$，考察 $c$ 的性质：

1. $|c_{i}-c_{i+1}|\le 1$：显然，因为滑动窗口不可能同时加入/删除两个 $1$；

2. $\forall y\in \mathbb{N},\min\{c_i\}\le y\le \max\{c_i\},\exist c_k=y$：通过第一条性质不难得出，因为无法“跳过”某个 $y$；

3. $\min\{c_i\}\le x\le \max\{c_i\}$：

   考虑反证，假设 $\min\{c_i\}>x$，则 $\sum\limits_{i=1}^n c_i>c1\cdot m$。注意到 $\sum\limits_{i=1}^n c_i=c1\cdot m$ 因为每个 $1$ 都被计算了 $m$ 次。所以有 $c1\cdot m>c1\cdot m$，矛盾。

   $\max\{c_i\}\ge x$ 的证明同理。

根据第二条和第三条性质可以得出 $\exist c_k=x$，那么找到这个 $k$ 即可找到环上符合条件的区间，即序列上最多两个不交的区间。

所以最多只需要两段。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=200005;

int n,m;
char a[S];
int c1,c[S];

inline int gcd(int x,int y)
{
	int t=x%y;
	while(t!=0) x=y,y=t,t=x%y;
	return y;
}

inline void slove()
{
	scanf("%d%d",&n,&m);
	scanf("%s",a+1);
	for(int i=1;i<=n;i++) c[i]=c1=0;
	for(int i=1;i<=n;i++) c1+=a[i]=='1';
	if(m%(n/gcd(n,c1))!=0) return puts("-1"),void();
	int x=1ll*c1*m/n;
	for(int i=1;i<=m;i++) c[1]+=a[i]=='1';
	for(int i=2;i<=n;i++)
	{
		c[i]=c[i-1];
		c[i]-=a[i-1]=='1';
		c[i]+=a[(i+m-1-1)%n+1]=='1';
	}
	for(int i=1;i<=n;i++)
	{
		if(c[i]==x)
		{
			if(i+m-1<=n) printf("1\n%d %d\n",i,i+m-1);
			else printf("2\n%d %d\n%d %d\n",i,n,1,i+m-1-n);
			return;
		}
	}
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T-->0) slove();
	return 0;
}