CTT 2026 - Ngày 3

Ngày trước, bạn M và người bạn N cùng chuẩn bị một kỳ thi lập trình. Họ nghĩ ra \(n\) bài, đánh số từ \(1\) đến \(n\); chất lượng của bài thứ \(i\) là số nguyên không âm \(a_i\).

Thời gian trôi qua. M không còn là thí sinh Olympic Tin học, nhưng hai người từng hẹn sẽ cùng tổ chức một chuỗi kỳ thi. M chưa quên lời hẹn đó.

M muốn chia \(n\) bài thành một số buổi luyện tập, tức chia dãy bài thành các đoạn liên tiếp. Một cách chia được biểu diễn bởi

Có \(k\) buổi; buổi thứ \(i\) gồm các bài từ \(r_{i-1}+1\) đến \(r_i\).

M nhận thấy chất lượng của một kỳ thi được quyết định bởi bài hay nhất và bài cuối cùng. Vì vậy, chất lượng của một buổi luyện tập được định nghĩa là tích của:

• giá trị \(a_i\) lớn nhất trong buổi;
• giá trị \(a_i\) của bài có chỉ số lớn nhất trong buổi.

M chưa quyết định số buổi và có \(q\) giá trị ứng viên \(k_1,k_2,\ldots,k_q\). Với mỗi \(k_j\), hãy tìm tổng chất lượng lớn nhất của các buổi trong mọi cách chia thành đúng \(k_j\) buổi.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test.

• Dòng đầu chứa số nguyên dương \(t\), số bộ test.
• Với mỗi bộ test:
• Dòng đầu chứa hai số nguyên dương \(n,q\).
• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_1,a_2,\ldots,a_n\).
• Dòng thứ ba chứa \(q\) số nguyên dương \(k_1,k_2,\ldots,k_q\).

Dữ liệu ra

Với mỗi bộ test, in một dòng gồm \(q\) số nguyên không âm. Số thứ \(j\) là tổng chất lượng lớn nhất khi chia thành đúng \(k_j\) buổi.

Ràng buộc

Tính trên toàn bộ các bộ test:

Chấm điểm

Các cột \(\sum n\) và \(\sum q\) được tính trên toàn bộ các bộ test trong một tệp.

Ví dụ

2
4 3
3 2 4 1
3 1 4
5 5
10 3 16 8 7
1 2 3 4 5

26 4 30
112 312 412 469 478

Nguồn

Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.

Xét trò chơi niềm tin giữa hai người chơi sau đây. Lưu ý rằng trò chơi này có thể khác với một trò chơi mà bạn từng biết.

• Khi một người chơi bỏ một đồng xu vào máy, người chơi kia nhận được ba đồng xu.
• Trò chơi kéo dài \(2m\) lượt. Hai người luân phiên hành động; ở mỗi lượt, người đang hành động chọn một trong hai cách:
• Hợp tác: bỏ vào một đồng xu.
• Lừa dối: không bỏ đồng xu.
• Nếu hợp tác, người hành động mất một đồng xu và người kia nhận ba đồng xu. Nếu lừa dối, không có gì xảy ra.
• Sau mỗi lượt, người chơi kia biết lựa chọn vừa được thực hiện.

Bạn chơi với một máy lặp lại và đi trước. Chiến lược của máy được mô tả bởi một đa tập \(S\) gồm các xâu nhị phân có độ dài không quá \(m\). Máy chọn ngẫu nhiên đều một xâu \(s\in S\). Gọi \(k=|s|\). Ở lượt \(2i\) (\(1\le i\le m\)), tức hành động thứ \(i\) của máy:

• Nếu \(1\le i\le k\), máy hợp tác khi \(s_i=0\) và lừa dối khi \(s_i=1\).
• Nếu \(k<i\le m\), máy lặp lại lựa chọn gần nhất của bạn, tức lựa chọn ở lượt \(2i-1\).

Ban đầu tập chiến lược chưa được xác định. Có \(n\) thao tác; thao tác thứ \(i\) cho xâu nhị phân \(s_i\) và số nguyên \(a_i\):

• Nếu \(a_i>0\), thêm \(a_i\) bản sao của \(s_i\) vào \(S\).
• Nếu \(a_i<0\), xóa \(-a_i\) bản sao của \(s_i\) khỏi \(S\). Đề bảo đảm trước khi xóa có đủ số bản sao và sau khi xóa, \(S\) vẫn chứa ít nhất một xâu.

Sau mỗi thao tác, hãy tính kỳ vọng lớn nhất của số xu bạn thu được khi chơi tối ưu. Các truy vấn sau từng thao tác độc lập với nhau. Bạn biết toàn bộ đa tập \(S\) nhưng không biết máy đã chọn xâu cụ thể nào; mỗi hành động của bạn có thể phụ thuộc vào tất cả lựa chọn trước đó của cả hai bên.

Bạn chỉ cần in kỳ vọng nhân với \(|S|\). Có thể chứng minh kết quả này là một số nguyên.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương \(n,m\).
• Dòng thứ \(i+1\) chứa một xâu nhị phân \(s_i\) có độ dài không quá \(m\) và một số nguyên \(a_i\).

Dữ liệu ra

In \(n\) dòng. Dòng thứ \(i\) là đáp án sau thao tác thứ \(i\).

Ràng buộc

Nếu \(a_i<0\), trước thao tác có ít nhất \(-a_i\) bản sao của \(s_i\) trong \(S\) và sau thao tác \(S\) vẫn chứa ít nhất một xâu.

Chấm điểm

• Tính chất A: \(a_i=1\) với mọi \(i\) và \(\sum_{i=1}^{n}|s_i|\le5000\).
• Tính chất B: \(|s_i|\ge|s_{i+1}|\) với mọi \(1\le i<n\).

Trong từng phần:

• Chỉ trả lời đúng đáp án sau thao tác thứ \(n\) trên mọi tệp nhận được \(40\%\) số điểm của phần.
• Trả lời đúng đáp án sau mọi thao tác nhận được \(100\%\) số điểm của phần.

Ngay cả khi chỉ trả lời thao tác cuối, bạn vẫn phải in đủ \(n\) số nguyên, tương ứng với đáp án sau từng thao tác.

Ví dụ

8 3
111 1
1 1
0 1
011 4
1 -1
01 3
011 -3
0 3

0
3
10
18
15
28
22
41

Nguồn

Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.

Cho cơ số \(p\in\{2,3\}\). Ta định nghĩa các phép toán theo từng chữ số trong cơ số \(p\) như sau.

Với \(0\le x<p^d\), viết biểu diễn cơ số \(p\) đủ \(d\) chữ số của \(x\) là

Định nghĩa \(\operatorname{popcount}_p(x)\) là số chữ số khác \(0\):

Với \(0\le x,y<p^d\), gọi các chữ số của \(x,y\) lần lượt là \(x_i,y_i\). Ba phép toán sau tạo số \(z=(z_{d-1}\ldots z_1z_0)_p\):

1. AND cơ số \(p\): \(x\operatorname{and}_p y\), với \(z_i=\min(x_i,y_i)\).
2. OR cơ số \(p\): \(x\operatorname{or}_p y\), với \(z_i=\max(x_i,y_i)\).
3. XOR cơ số \(p\) (cộng từng chữ số không nhớ): \(x\operatorname{xor}_p y\), với \(z_i=(x_i+y_i)\bmod p\).

Cho hai dãy \(a,w\) có độ dài \(n\) và dãy \(z\) có độ dài \(p^d\), trong đó \(0\le a_i<p^d\).

Với mỗi \(0\le u<p^d\) và ba hệ số không âm \(A,B,C\), định nghĩa dãy sinh \(F(u)\) như sau. Với \(1\le i\le n\), đặt

\(F(u)\) là dãy nhận được khi sắp xếp \(b_1,b_2,\ldots,b_n\) theo thứ tự không giảm.

Có \(q\) truy vấn. Mỗi truy vấn cho \(A,B,C,l_1,r_1,l_2,r_2\) và yêu cầu tính

Lưu ý rằng dãy \(F(i)\) trong mỗi truy vấn được xác định bởi chính bộ hệ số \(A,B,C\) của truy vấn đó.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên không âm \(n,d,p\).
• Dòng thứ hai chứa \(n\) số \(a_1,a_2,\ldots,a_n\).
• Dòng thứ ba chứa \(n\) số \(w_1,w_2,\ldots,w_n\).
• Dòng thứ tư chứa \(p^d\) số \(z_0,z_1,\ldots,z_{p^d-1}\).
• Dòng thứ năm chứa số nguyên dương \(q\).
• Mỗi dòng trong \(q\) dòng tiếp theo chứa bảy số \(A,B,C,l_1,r_1,l_2,r_2\).

Dữ liệu ra

Với mỗi truy vấn, in một số nguyên không âm trên một dòng: kết quả theo modulo \(2^{32}\).

Ràng buộc

Chấm điểm

• Tính chất A: bộ ba \((A,B,C)\) giống nhau trong mọi truy vấn.
• Tính chất B: \(l_1=r_1\) trong mọi truy vấn.
• Tính chất C: \(l_1=0\) và \(r_1=p^d-1\) trong mọi truy vấn.

Ví dụ

3 2 2
0 0 2
1 1 2
3 4 4 4
5
1 7 2 0 1 1 1
3 3 5 0 2 2 3
5 2 10 0 1 2 3
3 9 7 0 3 3 3
5 6 1 0 1 2 3

36
304
312
736
182

Khối lượng vào/ra có thể lớn; nên sử dụng phương thức vào/ra nhanh.

Nguồn

Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.