AT_utpc2025_m.Max Conference

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

解过 Conference 的人，也许很自然地就能想到这个问题。

给定一个长度为 $N$ 的字符串 $S$ ，其中 $S$ 的每个字符都是 A、B、C、? 之一，且特别地， $S$ 的第 $1$ 个和第 $N$ 个字符都是 A。

我们将使每个字符都是 A、B 或 C 的字符串的分数定义为： $i$ 满足 $1 \leq i \leq N-1$ ，且第 $i$ 个字符与第 $i+1$ 个字符不同的 $i$ 的个数。

请你回答 $Q$ 个询问。第 $i$ 个询问如下：

给定非负整数 $X_i, Y_i, Z_i$ 。其中 $X_i + Y_i + Z_i$ 等于 $S$ 中 ? 的总个数。将 $S$ 中的 ? 全部替换为恰好 $X_i$ 个 A、 $Y_i$ 个 B、 $Z_i$ 个 C 后，所能获得的最大分数是多少？请输出这个最大值。

输入格式

输入按以下格式从标准输入给出。

$N$ $S$ $Q$ $X_1$ $Y_1$ $Z_1$ $X_2$ $Y_2$ $Z_2$ $\vdots$ $X_Q$ $Y_Q$ $Z_Q$

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个询问的答案。

输入输出样例

输入#1
```
9
A??B??C?A
3
1 3 1
4 1 0
0 0 5
```
输出#1
```
8
6
4
```

输入#2

12
A???A?B????A
4
0 8 0
2 6 0
7 1 0
3 5 0

输出#2

输入#3

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

输出#3

说明/提示

样例解释 1

第 $1$ 个询问中，将 ? 替换为 ABCBABCBA 后，可获得分数 $8$ 。
第 $2$ 个询问中，将 ? 替换为 ABABAACAA 后，可获得分数 $6$ 。
第 $3$ 个询问中，将 ? 替换为 ACCBCCCCA 后，可获得分数 $4$ 。

数据范围

$N, Q, X_i, Y_i, Z_i$ 均为整数。
$2 \leq N \leq 3 \times 10^5$ 。
$S$ 仅包含 A、B、C、?。
$S$ 的第 $1$ 个和第 $N$ 个字符都是 A。
$1 \leq Q \leq 2 \times 10^5$ 。
$0 \leq X_i$ 。
$0 \leq Y_i$ 。
$0 \leq Z_i$ 。
$X_i + Y_i + Z_i$ 等于 $S$ 中 ? 的个数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页