← 返回题目列表

Codeforces · 1820/B

B. JoJo 的奇妙冒险

中文机器翻译题面 查看原题

你以为这里会出现JoJo传奇吗?但不,那是我,迪奥!

给定一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$,由字符 0 和 1 组成。让我们构建一个大小为 $$$n \times n$$$ 的方桌,由 0 和 1 个字符组成,如下所示。

在表的第一行写入原始字符串$$$s$$$。在表的第二行中,将字符串 $$$s$$$ 向右循环移位一位。在表的第三行中,将 $$$s$$$ 行的循环移位向右写入 2。等等。因此,编号为 $$$k$$$ 的行将包含字符串 $$$s$$$ 向右循环移位 $$$k$$$。行从上到下从 $$$0$$$ 到 $$$n - 1$$$ 编号。

在结果表中,我们需要找到仅由面积最大的矩形组成的矩形。

我们将表中所有单元格 $$$(i, j)$$$ 的集合称为矩形,对于某些整数 $$$x_1 \le i \le x_2$$$ 和 $$$y_1 \le j \le y_2$$$ $$$0 \le x_1 \le x_2 < n$$$ 和 $$$0 \le y_1 \le y_2 < n$$$。

回想一下,字符串 $$$s$$$ 向右循环移位 $$$k$$$ 是字符串 $$$s_{n-k+1} \ldots s_n s_1 s_2 \ldots s_{n-k}$$$。例如,字符串“01011”向右循环移位$$$0$$$就是字符串本身“01011”,其向右循环移位$$$3$$$就是字符串“01101”。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行也是唯一一行包含一个二进制字符串 $$$s$$$ ($$$1 \le \lvert s \rvert \le 2 \cdot 10^5$$$),由字符 0 和 1 组成。

保证所有测试用例的字符串长度 $$$|s|$$$ 的总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数——仅由 1 组成的矩形的最大面积。如果不存在这样的矩形,则输出$$$0$$$。

示例

输入 #1

5
0
1
101
011110
101010

输出 #1

0
1
2
6
1

注意

在第一个测试用例中,有一个由单个字符 0 组成的表 $$$1 \times 1$$$,因此不存在由 1 组成的矩形,答案为 $$$0$$$。

在第二个测试用例中,有一个表$$$1 \times 1$$$,由单个字符1组成,所以答案是$$$1$$$。

在第三个测试用例中,有一个表:

101110011

在第四个测试用例中,有一个表:

011110001111100111110011111001111100

第五个测试用例中有一张表:

101010010101101010010101101010010101

面积最大的矩形以粗体显示。