Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

Những ai đã giải bài Conference* có thể tự nhiên nghĩ ra bài toán này.

Bạn được cho một xâu $S$ có độ dài $N$. Mỗi ký tự của $S$ là một trong A, B, C, hoặc ?. Đặc biệt, ký tự đầu tiên và ký tự cuối cùng của $S$ đều là A.

Đối với một xâu có độ dài $N$ chỉ bao gồm A, B, và C, định nghĩa điểm của nó là số lượng số nguyên $i$ ($1 \le i \le N - 1$) sao cho ký tự thứ $i$ và ký tự thứ $(i + 1)$ là khác nhau.

Bạn được cho $Q$ truy vấn. Truy vấn thứ $i$ như sau:

Các số nguyên không âm $X_i, Y_i, Z_i$ được cho, trong đó $X_i + Y_i + Z_i$ bằng số lượng ký tự ? trong $S$. Trong tất cả các xâu thu được bằng cách thay thế $X_i$ ký tự ? trong $S$ bằng A, $Y_i$ ký tự trong số đó bằng B, và $Z_i$ ký tự trong số đó bằng C, hãy in ra số điểm lớn nhất có thể.

Dữ liệu vào

Dữ liệu vào được cung cấp theo định dạng sau:

N
S
Q
X_1 Y_1 Z_1
X_2 Y_2 Z_2
:
X_Q Y_Q Z_Q

Dữ liệu ra

In ra $Q$ dòng. Trên dòng thứ $i$, in ra câu trả lời cho truy vấn thứ $i$.

Ràng buộc

  • $N, Q, X_i, Y_i, Z_i$ là các số nguyên.
  • $2 \le N \le 3 \times 10^5$
  • $S$ là một xâu có độ dài $N$ bao gồm A, B, C, và ?.
  • Ký tự đầu tiên và ký tự cuối cùng của $S$ là 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$ bằng số lượng ký tự ? trong $S$.

Ví dụ

Đầu vào 1

9
A??B??C?A
3
1 3 1
4 1 0
0 0 5

Đầu ra 1

8
6
4

Đầu vào 2

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

Đầu ra 2

4
8
4
10

Đầu vào 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

Đầu ra 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

Ghi chú

Trong ví dụ đầu tiên:

  • Đối với truy vấn đầu tiên, thay thế các ký tự thành ABCBABCBA mang lại số điểm là $8$, đây là mức tối đa có thể.
  • Đối với truy vấn thứ hai, thay thế các ký tự thành ABABAACAA mang lại số điểm là $6$.
  • Đối với truy vấn thứ ba, thay thế các ký tự thành ACCBCCCCA mang lại số điểm là $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.