A15942. JoJo's Incredible Adventures
编程题
普及/提高-
知识点
题目描述
Did you think there was going to be a JoJo legend here? But no, that was me, Dio!
Given a binary string $s$ of length $n$ , consisting of characters 0 and 1. Let's build a square table of size $n \times n$ , consisting of 0 and 1 characters as follows.
In the first row of the table write the original string $s$ . In the second row of the table write cyclic shift of the string $s$ by one to the right. In the third row of the table, write the cyclic shift of line $s$ by two to the right. And so on. Thus, the row with number $k$ will contain a cyclic shift of string $s$ by $k$ to the right. The rows are numbered from $0$ to $n - 1$ top-to-bottom.
In the resulting table we need to find the rectangle consisting only of ones that has the largest area.
We call a rectangle the set of all cells $(i, j)$ in the table, such that $x_1 \le i \le x_2$ and $y_1 \le j \le y_2$ for some integers $0 \le x_1 \le x_2 < n$ and $0 \le y_1 \le y_2 < n$ .
Recall that the cyclic shift of string $s$ by $k$ to the right is the string $s_{n-k+1} \ldots s_n s_1 s_2 \ldots s_{n-k}$ . For example, the cyclic shift of the string "01011" by $0$ to the right is the string itself "01011", its cyclic shift by $3$ to the right is the string "01101".
Given a binary string $s$ of length $n$ , consisting of characters 0 and 1. Let's build a square table of size $n \times n$ , consisting of 0 and 1 characters as follows.
In the first row of the table write the original string $s$ . In the second row of the table write cyclic shift of the string $s$ by one to the right. In the third row of the table, write the cyclic shift of line $s$ by two to the right. And so on. Thus, the row with number $k$ will contain a cyclic shift of string $s$ by $k$ to the right. The rows are numbered from $0$ to $n - 1$ top-to-bottom.
In the resulting table we need to find the rectangle consisting only of ones that has the largest area.
We call a rectangle the set of all cells $(i, j)$ in the table, such that $x_1 \le i \le x_2$ and $y_1 \le j \le y_2$ for some integers $0 \le x_1 \le x_2 < n$ and $0 \le y_1 \le y_2 < n$ .
Recall that the cyclic shift of string $s$ by $k$ to the right is the string $s_{n-k+1} \ldots s_n s_1 s_2 \ldots s_{n-k}$ . For example, the cyclic shift of the string "01011" by $0$ to the right is the string itself "01011", its cyclic shift by $3$ to the right is the string "01101".
输入格式
Each test consists of multiple test cases. The first line contains a single integer $t$ ( $1 \le t \le 2 \cdot 10^4$ ) — the number of test cases. The description of test cases follows.
The first and the only line of each test case contains a single binary string $s$ ( $1 \le \lvert s \rvert \le 2 \cdot 10^5$ ), consisting of characters 0 and 1.
It is guaranteed that the sum of string lengths $|s|$ over all test cases does not exceed $2 \cdot 10^5$ .
The first and the only line of each test case contains a single binary string $s$ ( $1 \le \lvert s \rvert \le 2 \cdot 10^5$ ), consisting of characters 0 and 1.
It is guaranteed that the sum of string lengths $|s|$ over all test cases does not exceed $2 \cdot 10^5$ .
输出格式
For each test case, output a single integer — the maximum area of a rectangle consisting only of ones. If there is no such rectangle, output $0$ .
输入输出样例
输入 #1
5 0 1 101 011110 101010
输出 #1
0 1 2 6 1
说明/提示
In the first test case, there is a table $1 \times 1$ consisting of a single character 0, so there are no rectangles consisting of ones, and the answer is $0$ .
In the second test case, there is a table $1 \times 1$ , consisting of a single character 1, so the answer is $1$ .
In the third test case, there is a table:
101110011In the fourth test case, there is a table:
011110001111100111110011111001111100In the fifth test case, there is a table:
101010010101101010010101101010010101Rectangles with maximum area are shown in bold.
In the second test case, there is a table $1 \times 1$ , consisting of a single character 1, so the answer is $1$ .
In the third test case, there is a table:
101110011In the fourth test case, there is a table:
011110001111100111110011111001111100In the fifth test case, there is a table:
101010010101101010010101101010010101Rectangles with maximum area are shown in bold.