Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

解決過 Conference* 的人自然會想到這個問題。

給你一個長度為 $N$ 的字串 $S$。$S$ 中的每個字元都是 A、B、C 或 ? 之一。特別地,$S$ 的第一個和最後一個字元都是 A。

對於一個僅由 A、B 和 C 組成的長度為 $N$ 的字串,定義其得分為滿足第 $i$ 個字元與第 $(i + 1)$ 個字元不同的整數 $i$($1 \le i \le N - 1$)的個數。

給你 $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
:
X_Q Y_Q Z_Q

輸出格式

輸出 $Q$ 行。第 $i$ 行輸出第 $i$ 個查詢的答案。

資料範圍

  • $N, Q, X_i, Y_i, Z_i$ 是整數。
  • $2 \le N \le 3 \times 10^5$
  • $S$ 是一個長度為 $N$ 的字串,由 A、B、C 和 ? 組成。
  • $S$ 的第一個和最後一個字元都是 A。
  • $1 \le Q \le 2 \times 10^5$
  • $0 \le X_i$
  • $0 \le Y_i$
  • $0 \le Z_i$
  • $X_i + Y_i + Z_i$ 等於 $S$ 中 ? 字元的數量。

範例

輸入範例 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

4
8
4
10

輸入範例 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

24
21
23
21
19
20
19
21
19
17
19
22
19
17
22
19
23
22
20
13
15
19
20
17
21
17

說明

在第一個範例中:

  • 對於第一個查詢,將字元替換為 ABCBABCBA 得到的得分為 $8$,這是可能的最大得分。
  • 對於第二個查詢,將字元替換為 ABABAACAA 得到的得分為 $6$。
  • 對於第三個查詢,將字元替換為 ACCBCCCCA 得到的得分為 $4$。

* https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference-en.pdf

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1417EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.