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.