309878: CF1750B. Maximum Substring
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Maximum Substring
题意翻译
给定一个01串 $s$ ，对于它的一个非空子串 $t$ ，若 $t$ 包含 $x$ 个 0 和 $y$ 个 1 ，则 $t$ 的价值为 $val_t=\left\{\begin{aligned} &x\cdot y\quad & x>0,y>0\\ &x^2\quad & x>0,y=0\\ &y^2\quad & x=0,y>0 \end{aligned}\right.$ 对于给定的01串 $s$ ，求出它的一个非空子串 $t$ （可以是自身），使得 $t$ 的价值最大，输出最大价值题目描述
A binary string is a string consisting only of the characters 0 and 1. You are given a binary string $ s $ . For some non-empty substring $ ^\dagger $ $ t $ of string $ s $ containing $ x $ characters 0 and $ y $ characters 1, define its cost as: - $ x \cdot y $ , if $ x > 0 $ and $ y > 0 $ ; - $ x^2 $ , if $ x > 0 $ and $ y = 0 $ ; - $ y^2 $ , if $ x = 0 $ and $ y > 0 $ . Given a binary string $ s $ of length $ n $ , find the maximum cost across all its non-empty substrings. $ ^\dagger $ A string $ a $ is a substring of a string $ b $ if $ a $ can be obtained from $ b $ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.输入输出格式
输入格式
Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^5 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of the string $ s $ . The second line of each test case contains a binary string $ s $ of length $ n $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .
输出格式
For each test case, print a single integer — the maximum cost across all substrings.
输入输出样例
输入样例 #1
6
5
11100
7
1100110
6
011110
7
1001010
4
1000
1
0输出样例 #1
9
12
16
12
9
1说明
In the first test case, we can take a substring $ 111 $ . It contains $ 3 $ characters 1 and $ 0 $ characters 0. So $ a = 3 $ , $ b = 0 $ and its cost is $ 3^2 = 9 $ . In the second test case, we can take the whole string. It contains $ 4 $ characters 1 and $ 3 $ characters 0. So $ a = 4 $ , $ b = 3 $ and its cost is $ 4 \cdot 3 = 12 $ . In the third test case, we can can take a substring $ 1111 $ and its cost is $ 4^2 = 16 $ . In the fourth test case, we can take the whole string and cost is $ 4 \cdot 3 = 12 $ . In the fifth test case, we can take a substring $ 000 $ and its cost is $ 3 \cdot 3 = 9 $ . In the sixth test case, we can only take the substring $ 0 $ and its cost is $ 1 \cdot 1 = 1 $ .Input
题意翻译
给定一个01串 $s$ ，对于它的一个非空子串 $t$ ，若 $t$ 包含 $x$ 个 0 和 $y$ 个 1 ，则 $t$ 的价值为 $val_t=\left\{\begin{aligned} &x\cdot y\quad & x>0,y>0\\ &x^2\quad & x>0,y=0\\ &y^2\quad & x=0,y>0 \end{aligned}\right.$ 对于给定的01串 $s$ ，求出它的一个非空子串 $t$ （可以是自身），使得 $t$ 的价值最大，输出最大价值Output
**最大子串价值**
**题意翻译**
给定一个01串 $ s $ ，对于它的一个非空子串 $ t $ ，若 $ t $ 包含 $ x $ 个 0 和 $ y $ 个 1 ，则 $ t $ 的价值为：
$$
val_t=\left\{
\begin{array}{ll}
x \cdot y & \text{if } x > 0, y > 0 \\
x^2 & \text{if } x > 0, y = 0 \\
y^2 & \text{if } x = 0, y > 0
\end{array}
\right.
$$
对于给定的01串 $ s $ ，求出它的一个非空子串 $ t $ （可以是自身），使得 $ t $ 的价值最大，输出最大价值。
**题目描述**
一个二进制字符串是只包含字符0和1的字符串。给你一个二进制字符串 $ s $ 。
对于字符串 $ s $ 的某个非空子串 $ t $ 包含 $ x $ 个字符0和 $ y $ 个字符1，定义其价值为：
- 如果 $ x > 0 $ 且 $ y > 0 $ ，价值为 $ x \cdot y $ ；
- 如果 $ x > 0 $ 且 $ y = 0 $ ，价值为 $ x^2 $ ；
- 如果 $ x = 0 $ 且 $ y > 0 $ ，价值为 $ y^2 $ 。
给定一个长度为 $ n $ 的二进制字符串 $ s $ ，找出所有非空子串中最大的价值。
**输入输出格式**
**输入格式**
每个测试包含多个测试用例。第一行包含一个整数 $ t $ （ $ 1 \leq t \leq 10^5 $ ）——测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数 $ n $ （ $ 1 \le n \le 2 \cdot 10^5 $ ）——字符串 $ s $ 的长度。
每个测试用例的第二行包含一个长度为 $ n $ 的二进制字符串 $ s $ 。
保证所有测试用例中 $ n $ 的总和不超过 $ 2 \cdot 10^5 $ 。
**输出格式**
对于每个测试用例，打印一个整数——所有子串中的最大价值。
**输入输出样例**
**输入样例 #1**
```
6
5
11100
7
1100110
6
011110
7
1001010
4
1000
1
0
```
**输出样例 #1**
```
9
12
16
12
9
1
```
**说明**
在第一个测试用例中，我们可以取子串 $ 111 $ 。它包含3个字符1和0个字符0。所以 $ a = 3 $ ， $ b = 0 $ ，其价值为 $ 3^2 = 9 $ 。
在第二个测试用例中，我们可以取整个字符串。它包含4个字符1和3个字符0。所以 $ a = 4 $ ， $ b = 3 $ ，其价值为 $ 4 \cdot 3 = 12 $ 。
在第三个测试用例中，我们可以取子串 $ 1111 $ ，其价值为 $ 4^2 = 16 $ 。
在第四个测试用例中，我们可以取整个字符串，价值为 $ 4 \cdot 3 = 12 $ 。
在第五个测试用例中，我们可以取子串 $ 000 $ ，其价值为 $ 3 \cdot 3 = 9 $ 。
在第六个测试用例中，我们只能取子串 $ 0 $ ，其价值为 $ 1 \cdot 1 = 1 $ 。**最大子串价值** **题意翻译** 给定一个01串 $ s $ ，对于它的一个非空子串 $ t $ ，若 $ t $ 包含 $ x $ 个 0 和 $ y $ 个 1 ，则 $ t $ 的价值为： $$ val_t=\left\{ \begin{array}{ll} x \cdot y & \text{if } x > 0, y > 0 \\ x^2 & \text{if } x > 0, y = 0 \\ y^2 & \text{if } x = 0, y > 0 \end{array} \right. $$ 对于给定的01串 $ s $ ，求出它的一个非空子串 $ t $ （可以是自身），使得 $ t $ 的价值最大，输出最大价值。 **题目描述** 一个二进制字符串是只包含字符0和1的字符串。给你一个二进制字符串 $ s $ 。 对于字符串 $ s $ 的某个非空子串 $ t $ 包含 $ x $ 个字符0和 $ y $ 个字符1，定义其价值为： - 如果 $ x > 0 $ 且 $ y > 0 $ ，价值为 $ x \cdot y $ ； - 如果 $ x > 0 $ 且 $ y = 0 $ ，价值为 $ x^2 $ ； - 如果 $ x = 0 $ 且 $ y > 0 $ ，价值为 $ y^2 $ 。 给定一个长度为 $ n $ 的二进制字符串 $ s $ ，找出所有非空子串中最大的价值。 **输入输出格式** **输入格式** 每个测试包含多个测试用例。第一行包含一个整数 $ t $ （ $ 1 \leq t \leq 10^5 $ ）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $ （ $ 1 \le n \le 2 \cdot 10^5 $ ）——字符串 $ s $ 的长度。 每个测试用例的第二行包含一个长度为 $ n $ 的二进制字符串 $ s $ 。 保证所有测试用例中 $ n $ 的总和不超过 $ 2 \cdot 10^5 $ 。 **输出格式** 对于每个测试用例，打印一个整数——所有子串中的最大价值。 **输入输出样例** **输入样例 #1** ``` 6 5 11100 7 1100110 6 011110 7 1001010 4 1000 1 0 ``` **输出样例 #1** ``` 9 12 16 12 9 1 ``` **说明** 在第一个测试用例中，我们可以取子串 $ 111 $ 。它包含3个字符1和0个字符0。所以 $ a = 3 $ ， $ b = 0 $ ，其价值为 $ 3^2 = 9 $ 。 在第二个测试用例中，我们可以取整个字符串。它包含4个字符1和3个字符0。所以 $ a = 4 $ ， $ b = 3 $ ，其价值为 $ 4 \cdot 3 = 12 $ 。 在第三个测试用例中，我们可以取子串 $ 1111 $ ，其价值为 $ 4^2 = 16 $ 。 在第四个测试用例中，我们可以取整个字符串，价值为 $ 4 \cdot 3 = 12 $ 。 在第五个测试用例中，我们可以取子串 $ 000 $ ，其价值为 $ 3 \cdot 3 = 9 $ 。 在第六个测试用例中，我们只能取子串 $ 0 $ ，其价值为 $ 1 \cdot 1 = 1 $ 。
**题意翻译**
给定一个01串 $ s $ ，对于它的一个非空子串 $ t $ ，若 $ t $ 包含 $ x $ 个 0 和 $ y $ 个 1 ，则 $ t $ 的价值为：
$$
val_t=\left\{
\begin{array}{ll}
x \cdot y & \text{if } x > 0, y > 0 \\
x^2 & \text{if } x > 0, y = 0 \\
y^2 & \text{if } x = 0, y > 0
\end{array}
\right.
$$
对于给定的01串 $ s $ ，求出它的一个非空子串 $ t $ （可以是自身），使得 $ t $ 的价值最大，输出最大价值。
**题目描述**
一个二进制字符串是只包含字符0和1的字符串。给你一个二进制字符串 $ s $ 。
对于字符串 $ s $ 的某个非空子串 $ t $ 包含 $ x $ 个字符0和 $ y $ 个字符1，定义其价值为：
- 如果 $ x > 0 $ 且 $ y > 0 $ ，价值为 $ x \cdot y $ ；
- 如果 $ x > 0 $ 且 $ y = 0 $ ，价值为 $ x^2 $ ；
- 如果 $ x = 0 $ 且 $ y > 0 $ ，价值为 $ y^2 $ 。
给定一个长度为 $ n $ 的二进制字符串 $ s $ ，找出所有非空子串中最大的价值。
**输入输出格式**
**输入格式**
每个测试包含多个测试用例。第一行包含一个整数 $ t $ （ $ 1 \leq t \leq 10^5 $ ）——测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数 $ n $ （ $ 1 \le n \le 2 \cdot 10^5 $ ）——字符串 $ s $ 的长度。
每个测试用例的第二行包含一个长度为 $ n $ 的二进制字符串 $ s $ 。
保证所有测试用例中 $ n $ 的总和不超过 $ 2 \cdot 10^5 $ 。
**输出格式**
对于每个测试用例，打印一个整数——所有子串中的最大价值。
**输入输出样例**
**输入样例 #1**
```
6
5
11100
7
1100110
6
011110
7
1001010
4
1000
1
0
```
**输出样例 #1**
```
9
12
16
12
9
1
```
**说明**
在第一个测试用例中，我们可以取子串 $ 111 $ 。它包含3个字符1和0个字符0。所以 $ a = 3 $ ， $ b = 0 $ ，其价值为 $ 3^2 = 9 $ 。
在第二个测试用例中，我们可以取整个字符串。它包含4个字符1和3个字符0。所以 $ a = 4 $ ， $ b = 3 $ ，其价值为 $ 4 \cdot 3 = 12 $ 。
在第三个测试用例中，我们可以取子串 $ 1111 $ ，其价值为 $ 4^2 = 16 $ 。
在第四个测试用例中，我们可以取整个字符串，价值为 $ 4 \cdot 3 = 12 $ 。
在第五个测试用例中，我们可以取子串 $ 000 $ ，其价值为 $ 3 \cdot 3 = 9 $ 。
在第六个测试用例中，我们只能取子串 $ 0 $ ，其价值为 $ 1 \cdot 1 = 1 $ 。**最大子串价值** **题意翻译** 给定一个01串 $ s $ ，对于它的一个非空子串 $ t $ ，若 $ t $ 包含 $ x $ 个 0 和 $ y $ 个 1 ，则 $ t $ 的价值为： $$ val_t=\left\{ \begin{array}{ll} x \cdot y & \text{if } x > 0, y > 0 \\ x^2 & \text{if } x > 0, y = 0 \\ y^2 & \text{if } x = 0, y > 0 \end{array} \right. $$ 对于给定的01串 $ s $ ，求出它的一个非空子串 $ t $ （可以是自身），使得 $ t $ 的价值最大，输出最大价值。 **题目描述** 一个二进制字符串是只包含字符0和1的字符串。给你一个二进制字符串 $ s $ 。 对于字符串 $ s $ 的某个非空子串 $ t $ 包含 $ x $ 个字符0和 $ y $ 个字符1，定义其价值为： - 如果 $ x > 0 $ 且 $ y > 0 $ ，价值为 $ x \cdot y $ ； - 如果 $ x > 0 $ 且 $ y = 0 $ ，价值为 $ x^2 $ ； - 如果 $ x = 0 $ 且 $ y > 0 $ ，价值为 $ y^2 $ 。 给定一个长度为 $ n $ 的二进制字符串 $ s $ ，找出所有非空子串中最大的价值。 **输入输出格式** **输入格式** 每个测试包含多个测试用例。第一行包含一个整数 $ t $ （ $ 1 \leq t \leq 10^5 $ ）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $ （ $ 1 \le n \le 2 \cdot 10^5 $ ）——字符串 $ s $ 的长度。 每个测试用例的第二行包含一个长度为 $ n $ 的二进制字符串 $ s $ 。 保证所有测试用例中 $ n $ 的总和不超过 $ 2 \cdot 10^5 $ 。 **输出格式** 对于每个测试用例，打印一个整数——所有子串中的最大价值。 **输入输出样例** **输入样例 #1** ``` 6 5 11100 7 1100110 6 011110 7 1001010 4 1000 1 0 ``` **输出样例 #1** ``` 9 12 16 12 9 1 ``` **说明** 在第一个测试用例中，我们可以取子串 $ 111 $ 。它包含3个字符1和0个字符0。所以 $ a = 3 $ ， $ b = 0 $ ，其价值为 $ 3^2 = 9 $ 。 在第二个测试用例中，我们可以取整个字符串。它包含4个字符1和3个字符0。所以 $ a = 4 $ ， $ b = 3 $ ，其价值为 $ 4 \cdot 3 = 12 $ 。 在第三个测试用例中，我们可以取子串 $ 1111 $ ，其价值为 $ 4^2 = 16 $ 。 在第四个测试用例中，我们可以取整个字符串，价值为 $ 4 \cdot 3 = 12 $ 。 在第五个测试用例中，我们可以取子串 $ 000 $ ，其价值为 $ 3 \cdot 3 = 9 $ 。 在第六个测试用例中，我们只能取子串 $ 0 $ ，其价值为 $ 1 \cdot 1 = 1 $ 。