309709: CF1722D. Line
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：67
Solved：0
Description
Line
题意翻译
$t$ 组数据，每组给出 $n$ 与长度为 $n$ 的，仅由 `L` ，`R` 构成的字符串。 其中 `L` 的得分为其左边的字母数量， `R` 的得分为其右边的字母数量，字符串得分为所有字母得分之和。 你可以修改其中的某几个字符来获得更大得分。求出修改 $1$个、$2$个 ...... $n$个字符可以获得的最大字符串得分。 By Binary_1110011_题目描述
There are $ n $ people in a horizontal line, each looking either to the left or the right. Each person counts the number of people in the direction they are looking. The value of the line is the sum of each person's count. For example, in the arrangement LRRLL, where L stands for a person looking left and R stands for a person looking right, the counts for each person are $ [0, 3, 2, 3, 4] $ , and the value is $ 0+3+2+3+4=12 $ . You are given the initial arrangement of people in the line. For each $ k $ from $ 1 $ to $ n $ , determine the maximum value of the line if you can change the direction of at most $ k $ people.输入输出格式
输入格式
The input consists of multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 2\cdot10^5 $ ) — the length of the line. The following line contains a string consisting of $ n $ characters, each of which is either L or R, representing a person facing left or right, respectively — the description of the line. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ . Please note that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).
输出格式
For each test case, output $ n $ space-separated non-negative integers — the maximum value of the line if you can change the direction of at most $ k $ people for each $ k $ from $ 1 $ to $ n $ , inclusive.
输入输出样例
输入样例 #1
6
3
LLR
5
LRRLL
1
L
12
LRRRLLLRLLRL
10
LLLLLRRRRR
9
LRLRLRLRL输出样例 #1
3 5 5
16 16 16 16 16
0
86 95 98 101 102 102 102 102 102 102 102 102
29 38 45 52 57 62 65 68 69 70
44 50 54 56 56 56 56 56 56说明
In the first test case: - $ k=1 $ : change the direction of $ 1 $ person to make the line RLR. The total value is $ 2+1+0=3 $ . - $ k=2 $ : change the direction of $ 2 $ people to make the line RLL. The total value is $ 2+1+2=5 $ . - $ k=3 $ : change the direction of $ 2 $ people to make the line RLL. The total value is $ 2+1+2=5 $ . Note that you have to change the direction of at most $ k $ people. In the second test case, it is optimal to only change the direction of the first person for all $ k $ from $ 1 $ to $ 5 $ (that is, make the line RRRLL).Input
题意翻译
$t$ 组数据，每组给出 $n$ 与长度为 $n$ 的，仅由 `L` ，`R` 构成的字符串。 其中 `L` 的得分为其左边的字母数量， `R` 的得分为其右边的字母数量，字符串得分为所有字母得分之和。 你可以修改其中的某几个字符来获得更大得分。求出修改至多 $1$个、$2$个 ...... $n$个字符可以获得的最大字符串得分。 By Binary_1110011_Output
**题意翻译**
有 $ t $ 组数据，每组数据给出一个长度为 $ n $ 的字符串，字符串由字符 `L` 和 `R` 组成。`L` 的得分是它左边字母的数量，`R` 的得分是它右边字母的数量。字符串的得分是所有字母得分之和。你可以改变字符串中的几个字符来获得更大的得分。求出改变 $ 1 $ 个、$ 2 $ 个...... $ n $ 个字符能获得的最大字符串得分。
**题目描述**
有 $ n $ 个人站成一行，每个人要么向左看要么向右看。每个人计算他们看方向的人数。这行人的价值是每个人计算结果的和。
例如，在排列 LRRLL 中，L 表示一个人向左看，R 表示一个人向右看，每个人的计算结果是 $ [0, 3, 2, 3, 4] $，这行人的价值是 $ 0+3+2+3+4=12 $。
给你这行人的初始排列。对于每个 $ k $ 从 $ 1 $ 到 $ n $，确定如果你可以改变最多 $ k $ 个人的方向，这行人的最大价值是多少。
**输入输出格式**
**输入格式**
输入由多个测试案例组成。第一行包含一个整数 $ t $（$ 1 \leq t \leq 100 $）——测试案例的数量。接下来是测试案例的描述。
每个测试案例的第一行包含一个整数 $ n $（$ 1 \leq n \leq 2 \times 10^5 $）——这行人的长度。
下一行包含一个由 $ n $ 个字符组成的字符串，每个字符要么是 L 要么是 R，代表一个人向左或向右看——这行人的描述。
请注意到，对于某些测试案例，答案可能不适合 32 位整数类型，所以你应该在编程语言中使用至少 64 位整数类型（例如 C++ 中的 long long）。
**输出格式**
对于每个测试案例，输出 $ n $ 个空格分隔的非负整数——如果你可以改变最多 $ k $ 个人的方向，对于每个 $ k $ 从 $ 1 $ 到 $ n $（包括 $ n $），这行人的最大价值是多少。
**输入输出样例**
**输入样例 #1**
```
6
3
LLR
5
LRRLL
1
L
12
LRRRLLLRLLRL
10
LLLLLRRRRR
9
LRLRLRLRL
```
**输出样例 #1**
```
3 5 5
16 16 16 16 16
0
86 95 98 101 102 102 102 102 102 102 102 102
29 38 45 52 57 62 65 68 69 70
44 50 54 56 56 56 56 56 56
```
**说明**
在第一个测试案例中：
- 当 $ k=1 $ 时：改变 1 个人的方向使这行成为 RLR。总价值是 $ 2+1+0=3 $。
- 当 $ k=2 $ 时：改变 2 个人的方向使这行成为 RLL。总价值是 $ 2+1+2=5 $。
- 当 $ k=3 $ 时：改变 2 个人的方向使这行成为 RLL。总价值是 $ 2+1+2=5 $。注意，你只能改变最多 $ k $ 个人的方向。
在第二个测试案例中，对于所有 $ k $ 从 $ 1 $ 到 $ 5 $，最优的策略是只改变第一个人的方向（即让这行成为 RRRLL）。**题意翻译** 有 $ t $ 组数据，每组数据给出一个长度为 $ n $ 的字符串，字符串由字符 `L` 和 `R` 组成。`L` 的得分是它左边字母的数量，`R` 的得分是它右边字母的数量。字符串的得分是所有字母得分之和。你可以改变字符串中的几个字符来获得更大的得分。求出改变 $ 1 $ 个、$ 2 $ 个...... $ n $ 个字符能获得的最大字符串得分。 **题目描述** 有 $ n $ 个人站成一行，每个人要么向左看要么向右看。每个人计算他们看方向的人数。这行人的价值是每个人计算结果的和。 例如，在排列 LRRLL 中，L 表示一个人向左看，R 表示一个人向右看，每个人的计算结果是 $ [0, 3, 2, 3, 4] $，这行人的价值是 $ 0+3+2+3+4=12 $。 给你这行人的初始排列。对于每个 $ k $ 从 $ 1 $ 到 $ n $，确定如果你可以改变最多 $ k $ 个人的方向，这行人的最大价值是多少。 **输入输出格式** **输入格式** 输入由多个测试案例组成。第一行包含一个整数 $ t $（$ 1 \leq t \leq 100 $）——测试案例的数量。接下来是测试案例的描述。 每个测试案例的第一行包含一个整数 $ n $（$ 1 \leq n \leq 2 \times 10^5 $）——这行人的长度。 下一行包含一个由 $ n $ 个字符组成的字符串，每个字符要么是 L 要么是 R，代表一个人向左或向右看——这行人的描述。 请注意到，对于某些测试案例，答案可能不适合 32 位整数类型，所以你应该在编程语言中使用至少 64 位整数类型（例如 C++ 中的 long long）。 **输出格式** 对于每个测试案例，输出 $ n $ 个空格分隔的非负整数——如果你可以改变最多 $ k $ 个人的方向，对于每个 $ k $ 从 $ 1 $ 到 $ n $（包括 $ n $），这行人的最大价值是多少。 **输入输出样例** **输入样例 #1** ``` 6 3 LLR 5 LRRLL 1 L 12 LRRRLLLRLLRL 10 LLLLLRRRRR 9 LRLRLRLRL ``` **输出样例 #1** ``` 3 5 5 16 16 16 16 16 0 86 95 98 101 102 102 102 102 102 102 102 102 29 38 45 52 57 62 65 68 69 70 44 50 54 56 56 56 56 56 56 ``` **说明** 在第一个测试案例中： - 当 $ k=1 $ 时：改变 1 个人的方向使这行成为 RLR。总价值是 $ 2+1+0=3 $。 - 当 $ k=2 $ 时：改变 2 个人的方向使这行成为 RLL。总价值是 $ 2+1+2=5 $。 - 当 $ k=3 $ 时：改变 2 个人的方向使这行成为 RLL。总价值是 $ 2+1+2=5 $。注意，你只能改变最多 $ k $ 个人的方向。 在第二个测试案例中，对于所有 $ k $ 从 $ 1 $ 到 $ 5 $，最优的策略是只改变第一个人的方向（即让这行成为 RRRLL）。
有 $ t $ 组数据，每组数据给出一个长度为 $ n $ 的字符串，字符串由字符 `L` 和 `R` 组成。`L` 的得分是它左边字母的数量，`R` 的得分是它右边字母的数量。字符串的得分是所有字母得分之和。你可以改变字符串中的几个字符来获得更大的得分。求出改变 $ 1 $ 个、$ 2 $ 个...... $ n $ 个字符能获得的最大字符串得分。
**题目描述**
有 $ n $ 个人站成一行，每个人要么向左看要么向右看。每个人计算他们看方向的人数。这行人的价值是每个人计算结果的和。
例如，在排列 LRRLL 中，L 表示一个人向左看，R 表示一个人向右看，每个人的计算结果是 $ [0, 3, 2, 3, 4] $，这行人的价值是 $ 0+3+2+3+4=12 $。
给你这行人的初始排列。对于每个 $ k $ 从 $ 1 $ 到 $ n $，确定如果你可以改变最多 $ k $ 个人的方向，这行人的最大价值是多少。
**输入输出格式**
**输入格式**
输入由多个测试案例组成。第一行包含一个整数 $ t $（$ 1 \leq t \leq 100 $）——测试案例的数量。接下来是测试案例的描述。
每个测试案例的第一行包含一个整数 $ n $（$ 1 \leq n \leq 2 \times 10^5 $）——这行人的长度。
下一行包含一个由 $ n $ 个字符组成的字符串，每个字符要么是 L 要么是 R，代表一个人向左或向右看——这行人的描述。
请注意到，对于某些测试案例，答案可能不适合 32 位整数类型，所以你应该在编程语言中使用至少 64 位整数类型（例如 C++ 中的 long long）。
**输出格式**
对于每个测试案例，输出 $ n $ 个空格分隔的非负整数——如果你可以改变最多 $ k $ 个人的方向，对于每个 $ k $ 从 $ 1 $ 到 $ n $（包括 $ n $），这行人的最大价值是多少。
**输入输出样例**
**输入样例 #1**
```
6
3
LLR
5
LRRLL
1
L
12
LRRRLLLRLLRL
10
LLLLLRRRRR
9
LRLRLRLRL
```
**输出样例 #1**
```
3 5 5
16 16 16 16 16
0
86 95 98 101 102 102 102 102 102 102 102 102
29 38 45 52 57 62 65 68 69 70
44 50 54 56 56 56 56 56 56
```
**说明**
在第一个测试案例中：
- 当 $ k=1 $ 时：改变 1 个人的方向使这行成为 RLR。总价值是 $ 2+1+0=3 $。
- 当 $ k=2 $ 时：改变 2 个人的方向使这行成为 RLL。总价值是 $ 2+1+2=5 $。
- 当 $ k=3 $ 时：改变 2 个人的方向使这行成为 RLL。总价值是 $ 2+1+2=5 $。注意，你只能改变最多 $ k $ 个人的方向。
在第二个测试案例中，对于所有 $ k $ 从 $ 1 $ 到 $ 5 $，最优的策略是只改变第一个人的方向（即让这行成为 RRRLL）。**题意翻译** 有 $ t $ 组数据，每组数据给出一个长度为 $ n $ 的字符串，字符串由字符 `L` 和 `R` 组成。`L` 的得分是它左边字母的数量，`R` 的得分是它右边字母的数量。字符串的得分是所有字母得分之和。你可以改变字符串中的几个字符来获得更大的得分。求出改变 $ 1 $ 个、$ 2 $ 个...... $ n $ 个字符能获得的最大字符串得分。 **题目描述** 有 $ n $ 个人站成一行，每个人要么向左看要么向右看。每个人计算他们看方向的人数。这行人的价值是每个人计算结果的和。 例如，在排列 LRRLL 中，L 表示一个人向左看，R 表示一个人向右看，每个人的计算结果是 $ [0, 3, 2, 3, 4] $，这行人的价值是 $ 0+3+2+3+4=12 $。 给你这行人的初始排列。对于每个 $ k $ 从 $ 1 $ 到 $ n $，确定如果你可以改变最多 $ k $ 个人的方向，这行人的最大价值是多少。 **输入输出格式** **输入格式** 输入由多个测试案例组成。第一行包含一个整数 $ t $（$ 1 \leq t \leq 100 $）——测试案例的数量。接下来是测试案例的描述。 每个测试案例的第一行包含一个整数 $ n $（$ 1 \leq n \leq 2 \times 10^5 $）——这行人的长度。 下一行包含一个由 $ n $ 个字符组成的字符串，每个字符要么是 L 要么是 R，代表一个人向左或向右看——这行人的描述。 请注意到，对于某些测试案例，答案可能不适合 32 位整数类型，所以你应该在编程语言中使用至少 64 位整数类型（例如 C++ 中的 long long）。 **输出格式** 对于每个测试案例，输出 $ n $ 个空格分隔的非负整数——如果你可以改变最多 $ k $ 个人的方向，对于每个 $ k $ 从 $ 1 $ 到 $ n $（包括 $ n $），这行人的最大价值是多少。 **输入输出样例** **输入样例 #1** ``` 6 3 LLR 5 LRRLL 1 L 12 LRRRLLLRLLRL 10 LLLLLRRRRR 9 LRLRLRLRL ``` **输出样例 #1** ``` 3 5 5 16 16 16 16 16 0 86 95 98 101 102 102 102 102 102 102 102 102 29 38 45 52 57 62 65 68 69 70 44 50 54 56 56 56 56 56 56 ``` **说明** 在第一个测试案例中： - 当 $ k=1 $ 时：改变 1 个人的方向使这行成为 RLR。总价值是 $ 2+1+0=3 $。 - 当 $ k=2 $ 时：改变 2 个人的方向使这行成为 RLL。总价值是 $ 2+1+2=5 $。 - 当 $ k=3 $ 时：改变 2 个人的方向使这行成为 RLL。总价值是 $ 2+1+2=5 $。注意，你只能改变最多 $ k $ 个人的方向。 在第二个测试案例中，对于所有 $ k $ 从 $ 1 $ 到 $ 5 $，最优的策略是只改变第一个人的方向（即让这行成为 RRRLL）。