CF1658F Juju and Binary String

一个二进制字符串的可爱度定义为 $1$ 的个数除以字符串的长度。例如，$\texttt{01101}$ 的可爱度为 $\frac{3}{5}$。 Juju 有一个长度为 $n$ 的二进制字符串 $s$。她想选择若干个不相交的 $s$ 的子段，使得这些子段拼接后的总长度为 $m$，且拼接后的字符串的可爱度与 $s$ 的可爱度相同。 更具体地说，她想找到两个等长数组 $l$ 和 $r$，长度为 $k$，满足 $1 \leq l_1 \leq r_1 < l_2 \leq r_2 < \ldots < l_k \leq r_k \leq n$，并且： - $\sum\limits_{i=1}^k (r_i - l_i + 1) = m$； - $s[l_1, r_1] + s[l_2, r_2] + \ldots + s[l_k, r_k]$ 的可爱度等于 $s$ 的可爱度，其中 $s[x, y]$ 表示子段 $s_x s_{x+1} \ldots s_y$，$+$ 表示字符串拼接。 Juju 不喜欢把字符串分成太多段，所以她还希望 $k$ 的值尽量小。请你求出满足上述条件的最小 $k$，或者判断是否不存在这样的 $l$ 和 $r$。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq m \leq n \leq 2 \times 10^5$）。 每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，如果不存在满足条件的 $l$ 和 $r$，输出 $-1$。 否则，输出 $k+1$ 行。 第一行输出一个整数 $k$（$1 \leq k \leq m$），表示所需的最小子段数。 接下来的 $k$ 行，每行输出两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$），表示第 $i$ 个子段的区间。注意，输出的子段需满足 $l_1 \leq r_1 < l_2 \leq r_2 < \ldots < l_k \leq r_k$。

在第一个样例中，$\texttt{0011}$ 的可爱度与 $\texttt{01}$ 的可爱度相同。 在第二个样例中，$\texttt{11000011}$ 的可爱度为 $\frac{1}{2}$，不存在长度为 $6$ 的子段可爱度相同，所以必须用两个不相交的子段 $\texttt{10}$ 和 $\texttt{0011}$。 在第三个样例中，有 $8$ 种方式将字符串分成长度和为 $3$ 的若干段，但没有一种可爱度与 $\texttt{0101}$ 相同。 在最后一个样例中，不需要分割字符串。 由 ChatGPT 4.1 翻译