309746: CF1729C. Jumping on Tiles
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：8
Solved：0
Description
Jumping on Tiles
题意翻译
### 题目大意 给定一个字符串 $s$，polycarp 欲从字符串首跳到字符串末 ($s_1$ → $s_n$，其中 $n$ 表示该字符串长度)。 假设 polycarp 现从 $a_i$ 跳到了 $a_j$ 我们定义这一次跳跃的权值为 $|\operatorname{index}(a_i) - \operatorname{index}(a_j)|$，其中 $\operatorname{index}$ 表示该字符在字母表中的序号 ( 如 $\operatorname{index}('a') = 1, \; \operatorname{index}('z') = 26$ )。 请构造出一种在保证**权值和最小**的情况下**经过的字符最多**的跳跃方案 ( 当然，同一个字符只能经过一次，其中同一个仅指在字符串中的位置相同 )。 ### 输入格式 第一行包含一个整数 $t \; (1 \leqslant t \leqslant 10^4)$ ，表示测试样例组数。 对于每组测试样例，包含一行一个字符串 $s \; (2 \leqslant |s| \leqslant 2 \cdot 10^5)$，意义见题面。 ### 输出格式 对于每组测试样例，第一行包含两个用空格隔开的整数 $cost$ 和 $m$ 分别表示 最小权值和 和 最大经过的字符数。 第二行包含 $m$ 个整数，分别表示沿途经过的所有字符位置。( 例如输出 $1 \; 4 \; 3 \; 5$ 表示跳跃路径为 $s_1$ → $s_4$ → $s_3$ → $s_5$ ) 数与数之间用空格隔开。 $Translated \; by \; Zigh$题目描述
Polycarp was given a row of tiles. Each tile contains one lowercase letter of the Latin alphabet. The entire sequence of tiles forms the string $ s $ . In other words, you are given a string $ s $ consisting of lowercase Latin letters. Initially, Polycarp is on the first tile of the row and wants to get to the last tile by jumping on the tiles. Jumping from $ i $ -th tile to $ j $ -th tile has a cost equal to $ |index(s_i) - index(s_j)| $ , where $ index(c) $ is the index of the letter $ c $ in the alphabet (for example, $ index( $ 'a' $ )=1 $ , $ index( $ 'b' $ )=2 $ , ..., $ index( $ 'z' $ )=26 $ ) . Polycarp wants to get to the $ n $ -th tile for the minimum total cost, but at the same time make maximum number of jumps. In other words, among all possible ways to get to the last tile for the minimum total cost, he will choose the one with the maximum number of jumps. Polycarp can visit each tile at most once. Polycarp asks you to help — print the sequence of indices of string $ s $ on which he should jump.输入输出格式
输入格式
The first line of the input contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases in the test. Each test case is given by the string $ s $ ( $ 2 \le |s| \le 2 \cdot 10^5 $ ), where $ |s| $ — is the length of string $ s $ . The string $ s $ consists of lowercase Latin letters. It is guaranteed that the sum of string lengths $ s $ over all test cases does not exceed $ 2 \cdot 10^5 $ .
输出格式
The answer to each test case consists of two lines. In the first line print two integers $ cost $ , $ m $ , where $ cost $ is the minimum total cost of the path, and $ m $ is the maximum number of visited tiles Polycarp can make to get to $ n $ -th tiles for the minimum total cost $ cost $ (i.e. the number of jumps is $ m-1 $ ). In the next line print $ m $ different numbers $ j_1, j_2, \dots, j_m $ ( $ 1 \le j_i \le |s| $ ) — the sequence of indices of the tiles Polycarp will jump on. The first number in the sequence must be $ 1 $ (that is, $ j_1=1 $ ) and the last number must be the value of $ |s| $ (that is, $ j_m=|s| $ ). If there are multiple answers, print any of them.
输入输出样例
输入样例 #1
6
logic
codeforces
bca
aaaaaaaaaaa
adbaadabad
to输出样例 #1
9 4
1 4 3 5
16 10
1 8 3 4 9 5 2 6 7 10
1 2
1 3
0 11
1 8 10 4 3 5 7 2 9 6 11
3 10
1 9 5 4 7 3 8 6 2 10
5 2
1 2说明
In the first test case, the required path corresponds to the picture: In this case, the minimum possible total cost of the path is achieved. Since $ index( $ 'l' $ )=12 $ , $ index( $ 'o' $ )=15 $ , $ index( $ 'g' $ )=7 $ , $ index( $ 'i' $ )=9 $ , $ index( $ 'c' $ )=3 $ , then the total cost of the path is $ |12-9|+|9-7|+|7-3|=3+2+4=9 $ .Input
题意翻译
### 题目大意 给定一个字符串 $s$，polycarp 欲从字符串首跳到字符串末 ($s_1$ → $s_n$，其中 $n$ 表示该字符串长度)。 假设 polycarp 现从 $a_i$ 跳到了 $a_j$ 我们定义这一次跳跃的权值为 $|\operatorname{index}(a_i) - \operatorname{index}(a_j)|$，其中 $\operatorname{index}$ 表示该字符在字母表中的序号 ( 如 $\operatorname{index}('a') = 1, \; \operatorname{index}('z') = 26$ )。 请构造出一种在保证**权值和最小**的情况下**经过的字符最多**的跳跃方案 ( 当然，同一个字符只能经过一次，其中同一个仅指在字符串中的位置相同 )。 ### 输入格式 第一行包含一个整数 $t \; (1 \leqslant t \leqslant 10^4)$ ，表示测试样例组数。 对于每组测试样例，包含一行一个字符串 $s \; (2 \leqslant |s| \leqslant 2 \cdot 10^5)$，意义见题面。 ### 输出格式 对于每组测试样例，第一行包含两个用空格隔开的整数 $cost$ 和 $m$ 分别表示 最小权值和 和 最大经过的字符数。 第二行包含 $m$ 个整数，分别表示沿途经过的所有字符位置。( 例如输出 $1 \; 4 \; 3 \; 5$ 表示跳跃路径为 $s_1$ → $s_4$ → $s_3$ → $s_5$ ) 数与数之间用空格隔开。 $Translated \; by \; Zigh$Output
**题目大意**
给定一个字符串 $ s $，Polycarp 想要从字符串的第一个字符跳到最后一个字符（从 $ s_1 $ 到 $ s_n $，其中 $ n $ 是字符串的长度）。
如果 Polycarp 从 $ a_i $ 跳到 $ a_j $，我们定义这次跳跃的权值为 $ |\text{index}(a_i) - \text{index}(a_j)| $，其中 $ \text{index} $ 表示该字符在字母表中的位置（例如 $ \text{index}('a') = 1, \; \text{index}('z') = 26 $）。
请构造出一种在保证权值和最小的情况下经过的字符最多的跳跃方案（当然，同一个字符只能经过一次，这里指的是在字符串中的位置相同）。
**输入格式**
第一行包含一个整数 $ t \; (1 \leqslant t \leqslant 10^4) $，表示测试样例的数量。
对于每组测试样例，包含一行一个字符串 $ s \; (2 \leqslant |s| \leqslant 2 \cdot 10^5) $，意义见题面。
**输出格式**
对于每组测试样例，第一行包含两个用空格隔开的整数 $ cost $ 和 $ m $，分别表示最小权值和和最大经过的字符数。
第二行包含 $ m $ 个整数，分别表示沿途经过的所有字符位置。（例如输出 $ 1 \; 4 \; 3 \; 5 $ 表示跳跃路径为 $ s_1 $ → $ s_4 $ → $ s_3 $ → $ s_5 $）数字之间用空格隔开。
**题目描述**
Polycarp was given a row of tiles. Each tile contains one lowercase letter of the Latin alphabet. The entire sequence of tiles forms the string $ s $.
In other words, you are given a string $ s $ consisting of lowercase Latin letters.
Initially, Polycarp is on the first tile of the row and wants to get to the last tile by jumping on the tiles. Jumping from $ i $ -th tile to $ j $ -th tile has a cost equal to $ |index(s_i) - index(s_j)| $, where $ index(c) $ is the index of the letter $ c $ in the alphabet (for example, $ index('a')=1 $, $ index('b')=2 $, ..., $ index('z')=26 $).
Polycarp wants to get to the $ n $ -th tile for the minimum total cost, but at the same time make maximum number of jumps.
In other words, among all possible ways to get to the last tile for the minimum total cost, he will choose the one with the maximum number of jumps.
Polycarp can visit each tile at most once.
Polycarp asks you to help — print the sequence of indices of string $ s $ on which he should jump.
**输入输出格式**
**输入格式**
The first line of the input contains an integer $ t \; (1 \le t \le 10^4) $ — the number of test cases in the test.
Each test case is given by the string $ s \; (2 \le |s| \le 2 \cdot 10^5) $, where $ |s| $ — is the length of string $ s $. The string $ s $ consists of lowercase Latin letters.
It is guaranteed that the sum of string lengths $ s $ over all test cases does not exceed $ 2 \cdot 10^5 $.
**输出格式**
The answer to each test case consists of two lines.
In the first line print two integers $ cost $, $ m $, where $ cost $ is the minimum total cost of the path, and $ m $ is the maximum number of visited tiles Polycarp can make to get to $ n $ -th tiles for the minimum total cost $ cost $ (i.e. the number of jumps is $ m-1 $).
In the next line print $ m $ different numbers $ j_1, j_2, \dots, j_m \; (1 \le j_i \le |s|) $ — the sequence of indices of the tiles Polycarp will jump on. The first number in the sequence must be $ 1 $ (that is, $ j_1=1 $) and the last number must be the value of $ |s| $ (that is, $ j_m=|s| $).
If there are multiple answers, print any of them.**题目大意** 给定一个字符串 $ s $，Polycarp 想要从字符串的第一个字符跳到最后一个字符（从 $ s_1 $ 到 $ s_n $，其中 $ n $ 是字符串的长度）。 如果 Polycarp 从 $ a_i $ 跳到 $ a_j $，我们定义这次跳跃的权值为 $ |\text{index}(a_i) - \text{index}(a_j)| $，其中 $ \text{index} $ 表示该字符在字母表中的位置（例如 $ \text{index}('a') = 1, \; \text{index}('z') = 26 $）。 请构造出一种在保证权值和最小的情况下经过的字符最多的跳跃方案（当然，同一个字符只能经过一次，这里指的是在字符串中的位置相同）。 **输入格式** 第一行包含一个整数 $ t \; (1 \leqslant t \leqslant 10^4) $，表示测试样例的数量。 对于每组测试样例，包含一行一个字符串 $ s \; (2 \leqslant |s| \leqslant 2 \cdot 10^5) $，意义见题面。 **输出格式** 对于每组测试样例，第一行包含两个用空格隔开的整数 $ cost $ 和 $ m $，分别表示最小权值和和最大经过的字符数。 第二行包含 $ m $ 个整数，分别表示沿途经过的所有字符位置。（例如输出 $ 1 \; 4 \; 3 \; 5 $ 表示跳跃路径为 $ s_1 $ → $ s_4 $ → $ s_3 $ → $ s_5 $）数字之间用空格隔开。 **题目描述** Polycarp was given a row of tiles. Each tile contains one lowercase letter of the Latin alphabet. The entire sequence of tiles forms the string $ s $. In other words, you are given a string $ s $ consisting of lowercase Latin letters. Initially, Polycarp is on the first tile of the row and wants to get to the last tile by jumping on the tiles. Jumping from $ i $ -th tile to $ j $ -th tile has a cost equal to $ |index(s_i) - index(s_j)| $, where $ index(c) $ is the index of the letter $ c $ in the alphabet (for example, $ index('a')=1 $, $ index('b')=2 $, ..., $ index('z')=26 $). Polycarp wants to get to the $ n $ -th tile for the minimum total cost, but at the same time make maximum number of jumps. In other words, among all possible ways to get to the last tile for the minimum total cost, he will choose the one with the maximum number of jumps. Polycarp can visit each tile at most once. Polycarp asks you to help — print the sequence of indices of string $ s $ on which he should jump. **输入输出格式** **输入格式** The first line of the input contains an integer $ t \; (1 \le t \le 10^4) $ — the number of test cases in the test. Each test case is given by the string $ s \; (2 \le |s| \le 2 \cdot 10^5) $, where $ |s| $ — is the length of string $ s $. The string $ s $ consists of lowercase Latin letters. It is guaranteed that the sum of string lengths $ s $ over all test cases does not exceed $ 2 \cdot 10^5 $. **输出格式** The answer to each test case consists of two lines. In the first line print two integers $ cost $, $ m $, where $ cost $ is the minimum total cost of the path, and $ m $ is the maximum number of visited tiles Polycarp can make to get to $ n $ -th tiles for the minimum total cost $ cost $ (i.e. the number of jumps is $ m-1 $). In the next line print $ m $ different numbers $ j_1, j_2, \dots, j_m \; (1 \le j_i \le |s|) $ — the sequence of indices of the tiles Polycarp will jump on. The first number in the sequence must be $ 1 $ (that is, $ j_1=1 $) and the last number must be the value of $ |s| $ (that is, $ j_m=|s| $). If there are multiple answers, print any of them.
给定一个字符串 $ s $，Polycarp 想要从字符串的第一个字符跳到最后一个字符（从 $ s_1 $ 到 $ s_n $，其中 $ n $ 是字符串的长度）。
如果 Polycarp 从 $ a_i $ 跳到 $ a_j $，我们定义这次跳跃的权值为 $ |\text{index}(a_i) - \text{index}(a_j)| $，其中 $ \text{index} $ 表示该字符在字母表中的位置（例如 $ \text{index}('a') = 1, \; \text{index}('z') = 26 $）。
请构造出一种在保证权值和最小的情况下经过的字符最多的跳跃方案（当然，同一个字符只能经过一次，这里指的是在字符串中的位置相同）。
**输入格式**
第一行包含一个整数 $ t \; (1 \leqslant t \leqslant 10^4) $，表示测试样例的数量。
对于每组测试样例，包含一行一个字符串 $ s \; (2 \leqslant |s| \leqslant 2 \cdot 10^5) $，意义见题面。
**输出格式**
对于每组测试样例，第一行包含两个用空格隔开的整数 $ cost $ 和 $ m $，分别表示最小权值和和最大经过的字符数。
第二行包含 $ m $ 个整数，分别表示沿途经过的所有字符位置。（例如输出 $ 1 \; 4 \; 3 \; 5 $ 表示跳跃路径为 $ s_1 $ → $ s_4 $ → $ s_3 $ → $ s_5 $）数字之间用空格隔开。
**题目描述**
Polycarp was given a row of tiles. Each tile contains one lowercase letter of the Latin alphabet. The entire sequence of tiles forms the string $ s $.
In other words, you are given a string $ s $ consisting of lowercase Latin letters.
Initially, Polycarp is on the first tile of the row and wants to get to the last tile by jumping on the tiles. Jumping from $ i $ -th tile to $ j $ -th tile has a cost equal to $ |index(s_i) - index(s_j)| $, where $ index(c) $ is the index of the letter $ c $ in the alphabet (for example, $ index('a')=1 $, $ index('b')=2 $, ..., $ index('z')=26 $).
Polycarp wants to get to the $ n $ -th tile for the minimum total cost, but at the same time make maximum number of jumps.
In other words, among all possible ways to get to the last tile for the minimum total cost, he will choose the one with the maximum number of jumps.
Polycarp can visit each tile at most once.
Polycarp asks you to help — print the sequence of indices of string $ s $ on which he should jump.
**输入输出格式**
**输入格式**
The first line of the input contains an integer $ t \; (1 \le t \le 10^4) $ — the number of test cases in the test.
Each test case is given by the string $ s \; (2 \le |s| \le 2 \cdot 10^5) $, where $ |s| $ — is the length of string $ s $. The string $ s $ consists of lowercase Latin letters.
It is guaranteed that the sum of string lengths $ s $ over all test cases does not exceed $ 2 \cdot 10^5 $.
**输出格式**
The answer to each test case consists of two lines.
In the first line print two integers $ cost $, $ m $, where $ cost $ is the minimum total cost of the path, and $ m $ is the maximum number of visited tiles Polycarp can make to get to $ n $ -th tiles for the minimum total cost $ cost $ (i.e. the number of jumps is $ m-1 $).
In the next line print $ m $ different numbers $ j_1, j_2, \dots, j_m \; (1 \le j_i \le |s|) $ — the sequence of indices of the tiles Polycarp will jump on. The first number in the sequence must be $ 1 $ (that is, $ j_1=1 $) and the last number must be the value of $ |s| $ (that is, $ j_m=|s| $).
If there are multiple answers, print any of them.**题目大意** 给定一个字符串 $ s $，Polycarp 想要从字符串的第一个字符跳到最后一个字符（从 $ s_1 $ 到 $ s_n $，其中 $ n $ 是字符串的长度）。 如果 Polycarp 从 $ a_i $ 跳到 $ a_j $，我们定义这次跳跃的权值为 $ |\text{index}(a_i) - \text{index}(a_j)| $，其中 $ \text{index} $ 表示该字符在字母表中的位置（例如 $ \text{index}('a') = 1, \; \text{index}('z') = 26 $）。 请构造出一种在保证权值和最小的情况下经过的字符最多的跳跃方案（当然，同一个字符只能经过一次，这里指的是在字符串中的位置相同）。 **输入格式** 第一行包含一个整数 $ t \; (1 \leqslant t \leqslant 10^4) $，表示测试样例的数量。 对于每组测试样例，包含一行一个字符串 $ s \; (2 \leqslant |s| \leqslant 2 \cdot 10^5) $，意义见题面。 **输出格式** 对于每组测试样例，第一行包含两个用空格隔开的整数 $ cost $ 和 $ m $，分别表示最小权值和和最大经过的字符数。 第二行包含 $ m $ 个整数，分别表示沿途经过的所有字符位置。（例如输出 $ 1 \; 4 \; 3 \; 5 $ 表示跳跃路径为 $ s_1 $ → $ s_4 $ → $ s_3 $ → $ s_5 $）数字之间用空格隔开。 **题目描述** Polycarp was given a row of tiles. Each tile contains one lowercase letter of the Latin alphabet. The entire sequence of tiles forms the string $ s $. In other words, you are given a string $ s $ consisting of lowercase Latin letters. Initially, Polycarp is on the first tile of the row and wants to get to the last tile by jumping on the tiles. Jumping from $ i $ -th tile to $ j $ -th tile has a cost equal to $ |index(s_i) - index(s_j)| $, where $ index(c) $ is the index of the letter $ c $ in the alphabet (for example, $ index('a')=1 $, $ index('b')=2 $, ..., $ index('z')=26 $). Polycarp wants to get to the $ n $ -th tile for the minimum total cost, but at the same time make maximum number of jumps. In other words, among all possible ways to get to the last tile for the minimum total cost, he will choose the one with the maximum number of jumps. Polycarp can visit each tile at most once. Polycarp asks you to help — print the sequence of indices of string $ s $ on which he should jump. **输入输出格式** **输入格式** The first line of the input contains an integer $ t \; (1 \le t \le 10^4) $ — the number of test cases in the test. Each test case is given by the string $ s \; (2 \le |s| \le 2 \cdot 10^5) $, where $ |s| $ — is the length of string $ s $. The string $ s $ consists of lowercase Latin letters. It is guaranteed that the sum of string lengths $ s $ over all test cases does not exceed $ 2 \cdot 10^5 $. **输出格式** The answer to each test case consists of two lines. In the first line print two integers $ cost $, $ m $, where $ cost $ is the minimum total cost of the path, and $ m $ is the maximum number of visited tiles Polycarp can make to get to $ n $ -th tiles for the minimum total cost $ cost $ (i.e. the number of jumps is $ m-1 $). In the next line print $ m $ different numbers $ j_1, j_2, \dots, j_m \; (1 \le j_i \le |s|) $ — the sequence of indices of the tiles Polycarp will jump on. The first number in the sequence must be $ 1 $ (that is, $ j_1=1 $) and the last number must be the value of $ |s| $ (that is, $ j_m=|s| $). If there are multiple answers, print any of them.