题目描述
K 主席计划在接下来 N 天内举办一系列会议,每天都会举办恰好一场会议,且会议将在三个场馆之一举行:主场馆 A 或两个副场馆 B 和 C 中的一个。
每场会议的场馆信息由字符串 S 给出,该字符串由 A、B、C 和 ? 组成。对于第 i 天(1≤i≤N),如果 S 的第 i 个字符是 A,则会议在场馆 A 举行;如果是 B,则在场馆 B 举行;如果是 C,则在场馆 C 举行;如果是 ?,则表示第 i 天的场馆尚未决定。
由于第一天和第 N 天的会议预计会有大量参与者,因此已确定这两天必须使用场馆 A。
现在,K 主席需要为每个未决定的会议分配场馆(每个 ? 处可以选择 A、B 或 C)。此外,为了最小化场馆间移动的负担,他希望最小化满足以下条件的索引 j(1≤j≤N−1)的数量:第 j 天的场馆与第 (j+1) 天的场馆不同。
现在需要考虑 Q 个分配场景。对于第 k 个场景(1≤k≤Q)及其对应的问题描述如下:
- K 主席必须将 Xk 个未决定的会议分配到场馆 A,Yk 个分配到场馆 B,Zk 个分配到场馆 C。
- 请确定在此条件下,满足「第 j 天的场馆与第 (j+1) 天的场馆不同」的最小可能索引 j 的数量。
给定场馆信息和需要考量的场景,请编写程序回答这些问题。
输入格式
N
S
Q
X1 Y1 Z1
X2 Y2 Z2
⋮
XQ YQ ZQ
输出格式
输出 Q 行。
在第 k 行(1≤k≤Q)中,输出在 K 主席将 Xk 个未决定会议分配到 A,Yk 个分配到 B,Zk 个分配到 C 的条件下,满足「第 j 天的场馆与第 (j+1) 天的场馆不同」的最小可能索引 j 的数量。
9
A??B??C?A
3
1 3 1
4 1 0
0 0 5
3
4
4
12
A???A?B????A
4
0 8 0
2 6 0
7 1 0
3 5 0
4
4
2
2
28
ACB??B???BCB??B????B?AAA?BBA
26
6 1 6
4 5 4
2 3 8
9 2 2
11 0 2
8 4 1
11 0 2
2 0 11
0 1 12
12 1 0
10 3 0
1 4 8
3 7 3
2 8 3
1 3 9
11 1 1
7 0 6
6 4 3
8 4 1
0 10 3
13 0 0
11 1 1
0 6 7
2 8 3
9 0 4
0 0 13
15
11
13
13
15
12
15
15
16
15
13
12
10
9
13
15
15
11
12
9
15
15
11
9
15
17
提示
样例解释
样例解释 1
在第一个场景中,K 主席需要将 5 个未决定会议中的 1 个分配到场馆 A,3 个分配到 B,1 个分配到 C。例如,一种可能的分配结果会生成场馆信息字符串 ABBBBCCAA。此时,满足"第 j 天的场馆与第 (j+1) 天的场馆不同"的索引 j 是 1、5、7,共 3 个。由于无法将这个数量减少到 2 或更少,因此第一行的正确输出是 3。
在第二个场景中,K 主席需要将 5 个未决定会议中的 4 个分配到 A,1 个分配到 B。例如,一种可能的分配结果会生成字符串 AAABBACAA。此时,满足条件的索引 j 是 3、5、6、7,共 4 个。因此第二行的正确输出是 4。
在第三个场景中,K 主席需要将所有 5 个未决定会议分配到 C。满足条件的索引 j 是 1、3、4、8,共 4 个。因此第三行的正确输出是 4。
该样例满足子任务 1∼5,8 的限制。
样例解释 2
该样例满足所有子任务的限制。
样例解释 3
该样例满足子任务 1,2,4,8 的限制。
数据范围
- 2≤N≤300000;
- S 是长度为 N 且由 A、B、C 和 ? 组成的字符串;
- S 的首字符和末字符均为 A;
- 1≤Q≤200000;
- 0≤Xk(1≤k≤Q);
- 0≤Yk(1≤k≤Q);
- 0≤Zk(1≤k≤Q);
- Xk+Yk+Zk 等于 S 中 ? 的数量(1≤k≤Q);
- N、Q、Xk、Yk、Zk 均为整数。
子任务
- Subtask 1 (4 pts):N≤50 且 S 中 ? 的数量不超过 13;
- Subtask 2 (7 pts):N≤500;
- Subtask 3 (13 pts):N≤5000,Q≤10;
- Subtask 4 (18 pts):N≤5000;
- Subtask 5 (12 pts):Q≤10;
- Subtask 6 (8 pts):S 不含 C 且所有 Zk=0(1≤k≤Q);
- Subtask 7 (13 pts):所有 Zk=0(1≤k≤Q);
- Subtask 8 (25 pts):无额外限制。