AT_joisp2025_h 会議 (Conference)

K 理事长计划运营 $N$ 天的会议。每天（第 $1$ 天至第 $N$ 天）将举办一场会议，每场会议会使用主会场 A 或辅会场 B、C 中的一个。 每场会议使用的会场信息以只包含 `A`、`B`、`C`、`?` 的字符串 $S$ 给出。对于第 $i$ 天（$1 \leq i \leq N$），若 $S$ 的第 $i$ 个字符为 `A`，则第 $i$ 天的会议在会场 A 举行，若为 `B` 则在会场 B，若为 `C` 则在会场 C，若为 `?` 则尚未确定。不过，第 $1$ 天和第 $N$ 天的会议因有更多人参加，已确定在会场 A 举办。 接下来，K 理事长需要为尚未确定会场的会议分配会场，每个未定会议都要分配到会场 A、B、C 的其中一个。为了减少与会人员的移动负担，希望使得满足 $j$ 天和 $j+1$ 天会议的会场不同的 $j$ 的个数（$1\leq j\leq N-1$）最小。 关于如何分配未定会议的会场，将给出 $Q$ 个不同的分配场景，需要分别计算上面所述的 $j$ 的最小个数。第 $k$ 个（$1\leq k\leq Q$）场景定义如下： - 对于尚未确定会场的会议，分配 $X_k$ 个到会场 A，$Y_k$ 个到会场 B，$Z_k$ 个到会场 C。在这种分配下，求出 $j$ 天和 $j+1$ 天会议的会场不同的 $j$ 的个数的最小值。 给定会场信息和 $Q$ 个分配场景，请编写程序回答每个场景下的最小值。 ---

输入以如下格式从标准输入给出： > $N$ $S$ $Q$ > $X_1$ $Y_1$ $Z_1$ > $X_2$ $Y_2$ $Z_2$ > $\vdots$ > $X_Q$ $Y_Q$ $Z_Q$

输出 $Q$ 行。第 $k$ 行（$1\leq k \leq Q$）输出：对于第 $k$ 个场景，即分配 $X_k$ 个未定会议到会场 A、$Y_k$ 个到会场 B、$Z_k$ 个到会场 C 时，$j$ 天和 $j+1$ 天会议的会场不同的 $j$ 的最小个数。

## 小子任务 1.（4分）$N \leq 50$，$S$ 中出现的 `?` 不超过 $13$ 个。 2.（7分）$N \leq 500$。 3.（13分）$N \leq 5\,000$，$Q \leq 10$。 4.（18分）$N \leq 5\,000$。 5.（12分）$Q \leq 10$。 6.（8分）$S$ 中不包含 `C`，且所有 $Z_k = 0$（$1\leq k \leq Q$）。 7.（13分）所有 $Z_k = 0$（$1\leq k \leq Q$）。 8.（25分）无附加限制。 --- ## 样例说明 1 第 $1$ 个场景：5 个未定会议中，分配 1 个到 A，3 个到 B，1 个到 C。例如，最终会场分配为 `ABBBBCCAA`，此时满足 $j$ 和 $j+1$ 天会场不同的 $j$ 有 $1,5,7$，共 $3$ 个。无法做到不超过 $2$ 个，因此第 1 行输出 3。 第 $2$ 个场景：5 个未定会议中，分配 4 个到 A，1 个到 B。例如，最终会场分配为 `AAABBACAA`，此时满足 $j$ 和 $j+1$ 天会场不同的 $j$ 有 $3,5,6,7$，共 $4$ 个。无法做到不超过 $3$ 个，因此第 2 行输出 4。 第 $3$ 个场景：5 个未定会议全部分配到 C，满足 $j$ 和 $j+1$ 天会场不同的 $j$ 有 $1,3,4,8$，共 $4$ 个，因此第 3 行输出 4。 本输入示例满足小子任务 1,2,3,4,5,8 的限制。 --- ## 样例说明 2 本输入示例满足所有小子任务的限制要求。 --- ## 样例说明 3 本输入示例满足小子任务 1,2,4,8 的限制。 # 数据范围与约定 - $2 \leq N \leq 300\,000$。 - $S$ 是由 `A`、`B`、`C`、`?` 组成的长为 $N$ 的字符串。 - $S$ 的第 $1$ 个和第 $N$ 个字符为 `A`。 - $1 \leq Q \leq 200\,000$。 - $0 \leq X_k$（$1\leq k \leq Q$）。 - $0 \leq Y_k$（$1\leq k \leq Q$）。 - $0 \leq Z_k$（$1\leq k \leq Q$）。 - $X_k + Y_k + Z_k$ 等于 $S$ 中 `?` 的数量（$1\leq k \leq Q$）。 - $N, Q, X_k, Y_k, Z_k$ 均为整数（$1\leq k \leq Q$）。 由 ChatGPT 5 翻译