← 返回题目列表

AtCoder · joig2023_f

F. 打字比赛

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

配点: 100 点

問題文

在JOIG国使用JOIG语,在JOIG语中,文字 A, B, C, D, E, F, G, H, I, J, K, L, M, N, O 可以得到第 15 种类的字符被使用.

下个月在JOIG国举办的打字比赛中,将竞争输入由JOIG语使用的 15 种类的字符组成的长度 N 的字符串所需的时间.在这次比赛中,参赛者按照以下条件进行打字. S 参赛者

  • 使用1 根手指进行打字.
  • 使用15 种类的字符键 1 个一组地 1 列排布,使用左右细长的键盘。此外,哪个位置放哪个字符的键,由参与者自由决定。
  • 参与者将通过打出字符串 S 可以得到第 1, 2, \dots, N 第几个字符的键按这个顺序来输入字符串 S 。

预计有 Q 人参加本次比赛。参与者的打字能力各不相同。i 番目 (1 \leqq i \leqq Q)的参与者在打字时需要以下时间。

  • 按位于手指正下方的键 1 次需要 A_i 毫秒。
  • 将手指 1 移动到左边第几个键上需要 L_i 毫秒。
  • 将手指 1 移动到右边第几个键上需要 R_i 毫秒。

文字列 S ,并且给出每位参与者的信息,因此对于每位参与者,可以对字符串 S 从开始输入第一个字符到输入最后一个字符所需的最短毫秒数的程序。

制約

  • 1 \leqq N \leqq 1\,000\,000.
  • S 是长度 N 的字符串.
  • S 的每个字符是 A, B, C, D, E, F, G, H, I, J, K, L, M, N, O 的其中之一.
  • 1 \leqq Q \leqq 150\,000.
  • 1 \leqq A_i \leqq 10^{11} (1 \leqq i \leqq Q).
  • 1 \leqq L_i \leqq 10^{11} (1 \leqq i \leqq Q).
  • 1 \leqq R_i \leqq 10^{11} (1 \leqq i \leqq Q).
  • N, Q, A_i, L_i, R_i 是整数.

小課題

  1. (2 点) S 的每个字符是 A 是,Q = 1.
  2. (3 点) S 的每个字符是 A, B 之一Q = 1.
  3. (4 点) S 的每个字符是 A, B, C 之一Q = 1.
  4. (9 点) S 的每个字符是 A, B, C, D, E, F, G, H 之一Q = 1,N \leqq 100.
  5. (14 点) S 的每个字符是 A, B, C, D, E, F, G, H 之一Q = 1.
  6. (26 点) S 的每个字符是 A, B, C, D, E, F, G, H 的其中之一.
  7. (23 点) Q = 1.
  8. (7 点) L_i = R_i (1 \leqq i \leqq Q).
  9. (12 点)没有额外的限制。

入力

输入按以下格式给出。

N
S
Q
A_1 L_1 R_1
A_2 L_2 R_2
\vdots
A_Q L_Q R_Q

出力

Q 行输出。i 行目 (1 \leqq i \leqq Q)有参与者 i 从开始输入第一个字符到输入最后一个字符所需的最短毫秒数 S 输出字符串


入力例 1

6
ABAABB
1
100 150 210

出力例 1

1110

例如,考虑键盘的排列顺序从左到右为 ONMLKJIHGFEDCBA 。在这种情况下,通过执行下表中的动作, 1\,110 毫秒可以输入字符串 ABAABB 。

手順 動作 手指正下方的键 时间(毫秒)
1 按 A 键 A 100
2 将手指 1 向左移动一个键 A → B 150
3 按 B 键 B 100
4 将手指 1 向右移动一键 B → A 210
5 按 A 键 A 100
6 按 A 键 A 100
7 将手指 1 向左移动一个键 A → B 150
8 按 B 键 B 100
9 按 B 键 B 100

除了上面列出的键盘布局之外,您还可以 有多种方法可以在相同的时间内输入 ABAABB ,但无法在更短的时间内输入。因此 1\,110 。 你只需要砍掉

此输入示例是一个小作业。 2, 3, 4, 5, 6, 7, 9 满足约束。


入力例 2

6
CBACAB
1
150 240 220

出力例 2

2260

例如,考虑键盘的排列顺序从左到右为 CABDEFGHIJKLMNO 。在这种情况下,通过执行下表中的动作,2\,260 毫秒可以输入字符串 CBACAB 。

手順 動作 手指正下方的键 时间(毫秒)
1 按 C 键 C 150
2 将手指 1 向右移动一键 C → A 220
3 将手指 1 向右移动一键 A → B 220
4 按 B 键 B 150
5 将手指 1 向左移动一个键 B → A 240
6 按 A 键 A 150
7 将手指 1 向左移动一个键 A → C 240
8 按 C 键 C 150
9 将手指 1 向右移动一键 C → A 220
10 按 A 键 A 150
11 将手指 1 向右移动一键 A → B 220
12 按 B 键 B 150

除了上面列出的键盘布局之外,字符串 CBACAB ,但无法在更短的时间内输入。因此 2\,260 。 你只需要砍掉

此输入示例是一个小作业。 3, 4, 5, 6, 7, 9 满足约束。


入力例 3

20
AAAAAAAAAAAAAAAAAAAA
1
230000000 80000000 80000000

出力例 3

4600000000

A 该值应乘以 20 次,因此无论键盘布局如何,完成打字所需的时间都是最短的。 230\,000\,000 \times 20 = 4\,600\,000\,000 需要几毫秒。因此 4\,600\,000\,000 。 你只需要砍掉

此输入示例满足所有子任务约束。


入力例 4

7
EACHBAG
5
130 104 162
107 219 45
144 168 157
213 79 257
100000000000 100000000000 100000000000

出力例 4

2078
1766
2465
2894
1600000000000

此输入示例是一个小作业。 6, 9 满足约束。


入力例 5

19
JOIGCODINGCHALLENGE
5
1 1 1
100 200 200
225 111 111
123456789 987654321 987654321
31415926535 27182818284 27182818284

出力例 5

48
7700
7494
30987654300
1385204334401

此输入示例是一个小作业。 8, 9 满足约束。