Chọn ĐTQG Thanh Hóa 2025

Chọn ĐTQG Thanh Hóa 2025

Nguồn: ClueOJ statement pages printed to PDF and merged in exam order; not an original scan

Chuyển nhập/xuất tệp sang stdin/stdout khi chạy trên website.

Câu 1. WONDERFUL

Cho một hoán vị p của các số nguyên từ 1 đến n. Bạn được thực hiện thao tác sau một số lần: Chọn một số nguyên i thỏa mãn 1 ≤ i ≤ n - 1, và đổi giá trị của hai phần tử p_i và p_i+1 cho nhau.

Một hoán vị q được gọi là tuyệt vời nếu q_i ≠ i với mọi số nguyên i thỏa mãn 1 ≤ i ≤ n. Gọi f(p) là số thao tác tối thiểu cần phải thực hiện để chuyển đổi hoán vị p thành một hoán vị tuyệt vời.

Yêu cầu : Hãy tính tổng của f(p)² với mọi hoán vị p có thể. Vì tổng này có thể rất lớn, nên hãy in ra phần dư của đáp án khi chia cho 998244353.

Input

Một số nguyên n là độ dài của hoán vị p (2 ≤ n ≤ 2 · 10⁵).

Output

Phần dư của đáp án khi chia cho 998244353.

Scoring

Sample Input 1

3

Sample Output 1

7

Sample Input 2

4

Sample Output 2

27

Sample Input 3

101206

Sample Output 3

160323547

Notes

Ở test ví dụ thứ nhất, với n = 3 thì ta có 6 hoán vị là (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).

Số thao tác tối thiểu để chuyển các hoán vị tương ứng trên thành hoán vị tuyệt vời là 2, 1, 1, 0, 0, 1. Tổng các f(p)² là 2² + 1² + 1² + 0² + 0² + 1² = 7.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 2. ZEN

Công viên Thiền nằm trên một lưới ô vuông, các ô vuông là cát hoặc là đá. Kiến trúc sư nhận thấy công viên còn rất bừa bộn. Khu vườn Thiền đẹp phải có dạng hình chữ nhật, mọi ô bên trong hình chữ nhật đều là cát và nếu có các ô giáp biên với hình chữ nhật này thì các ô đó phải là đá.

Bây giờ bạn đã được yêu cầu, với tư cách là một chuyên gia xây dựng, cần loại bỏ càng ít các ô đá càng tốt để có được những khu vườn Thiền đẹp (khi một ô đá nào đó được loại bỏ thì ô đó sẽ trở thành ô cát). Trong ví dụ dưới, các ô vuông có dấu chấm (.) là cát và các ô vuông có dấu thăng (\#) là đá.

Sau khi loại bỏ 6 ô đá ở Hình A thì ta được 2 khu vườn Thiền đẹp như Hình B. Ở Hình C thì ta không cần xóa ô đá nào.

Yêu cầu : Cho một lưới ô vuông kích thước N × M hãy loại bỏ ít ô đá nhất để làm cho khu vườn Thiền trở nên đẹp và in ra nó trông như thế nào.

Input

• Dòng đầu tiên ghi số nguyên N và M lần lượt là số hàng và số cột của công viên Thiền (1 ≤ N, M ≤ 10³).

• Mỗi dòng trong N dòng tiếp theo sẽ là một chuỗi M ký tự.nếu ô vuông là cát và\#nếu ô vuông tương ứng là đá.

Output

Một ma trận kích thước N × M mô tả khu vườn Thiền sẽ trông như thế nào sau khi loại bỏ số lượng đá nhỏ nhất. Giải pháp của bạn bị sai nếu vẫn còn khu vườn Thiền chứa các ô là cát mà không phải là khu vườn Thiền đẹp.

Scoring

Sample Input 1

6 6
###...
#.#...
..#...
..#.##
..##.#
###..#

Sample Output 1

###...
..#...
..#...
..#...
..#...
###...

Sample Input 2

3 3
###
###
###

Sample Output 2

###
###
###

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 3. RALLY

Linh là một cô giáo dạy hát cho các bạn trẻ. Để rèn luyện đôi tai cho học trò, Linh thực hiện bài tập sau:

Đầu tiên Linh đưa cho học sinh của mình một chuỗi nốt, gọi chuỗi nốt này là A. Sau đó, Linh hát một chuỗi nốt khác mà học sinh phải nghe, gọi chuỗi nốt này là B. Cuối cùng, học sinh phải trả lời liệu tất cả các nốt trong A có xuất hiện trong B theo cùng một thứ tự, bất kể giữa chúng có các nốt trung gian hay không.

Ví dụ: Giả sử các chữ cái được sử dụng để thể hiện các nốt. Nếu A = abcad và B = baaacbcaad, câu trả lời sẽ là có vì các nốt trong A xuất hiện trong B theo cùng một thứ tự. Tuy nhiên, nếu A = abc và B = acbbbb, câu trả lời sẽ là không vì các nốt trong A không xuất hiện trong B theo cùng một thứ tự.

Không chỉ hát hay, Linh còn là CPer đỉnh cao. Với bài tập trên, Linh sử dụng biểu diễn cây. Nghĩa là, một cấu trúc gồm N đỉnh được kết nối bởi N-1 cạnh sao cho với mỗi cặp đỉnh u và v có một đường đi duy nhất từ u đến v đi qua một dãy các cạnh.

Trong bài tập, Linh cho học sinh của mình chuỗi A và chọn ngẫu nhiên hai đỉnh u và v từ cây của mình và một chuỗi nốt gồm các ký tự dọc theo chuỗi từ u đến v ứng với chuỗi B.

Trong bài này, bạn sẽ nhận được cây đầu vào mà Linh đã sử dụng trong bài tập của mình. Mỗi đỉnh được gán một chữ cái viết thường tượng trưng cho một nốt nhạc. Chương trình của bạn phải trả lời Q truy vấn. Mỗi truy vấn bao gồm hai đỉnh u, v và chuỗi A mà học sinh phải xác định.

Yêu cầu : Đối với mỗi truy vấn, chương trình của bạn phải viếtYESnếu chuỗi A xuất hiện, theo cùng thứ tự trên đường dẫn giữa u và v hoặcNOnếu không.

Input

• Dòng đầu tiên ghi 2 số nguyên N và Q.

• Dòng thứ hai ghi một chuỗi N ký tự. Ký tự thứ i của chuỗi đã cho được gán cho đỉnh i. Các đỉnh được đánh số từ 1 đến N.

• Mỗi dòng trong N-1 dòng sau ghi 2 số nguyên dương u và v và chỉ ra rằng có một cạnh giữa 2 đỉnh trên.

• Mỗi dòng trong Q dòng cuối ghi 2 số nguyên dương u, v và một chuỗi A đại diện cho một truy vấn.

Output

Với mỗi truy vấn, in ra trên một dòngYEShoặcNO.

Scoring

Gọi a là số ký tự trong chuỗi A. Gọi S_A là tổng của tất cả a. 2 ≤ N, Q ≤ 3 · 10⁵, Q ≤ S_A ≤ 3 · 10⁵.

Sample Input 1

10 3
zynserbero
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10 zysero
2 9 ser
9 3 ymyr

Sample Output 1

YES
YES
NO

Notes

Trong truy vấn đầu tiên, chuỗi được hình thành bởi đường đi giữa các đỉnh 1 và 10 làzynserbero. Chuỗizyseroxuất hiện dưới dạng một chuỗi con nếu bạn loại trừ các ký tự đỉnh 3, 5, 6, 7.

Trong truy vấn 2, chuỗi được hình thành bởi đường đi giữa các đỉnh 2 và 9 làynserber. Chuỗiserxuất hiện dưới dạng một chuỗi con nếu bạn loại trừ các ký tự đỉnh 2, 3, 5, 6, 7.

Trong truy vấn cuối cùng, chuỗi được hình thành bởi đường đi giữa các đỉnh 9 và 3 làrebresn. Chuỗiymyrkhông xuất hiện trong bất kỳ chuỗi con nào vì chữmkhông bao giờ xuất hiện trong chuỗirebresn.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 4. RING

Cho một đồ thị vô hướng gồm N đỉnh, ban đầu không có cạnh nào.

Có M truy vấn, mỗi truy vấn có dạng như sau: "u v" - Thêm cạnh (u, v) vào đồ thị.

Một thành phần liên thông có dạng vòng là thành phần liên thông thỏa mãn mọi đỉnh đều kề với đúng 2 đỉnh khác.

Yêu cầu : Sau mỗi truy vấn, hãy đếm số thành phần liên thông có dạng vòng.

Input

• Dòng đầu tiên gồm 2 số nguyên N và M (1 ≤ N, M ≤ 3 × 10⁵).

• Mỗi dòng thứ i trong M dòng tiếp theo ghi 2 số nguyên u, v là cạnh được thêm vào trong truy vấn thứ i (1 ≤ u, v ≤ N).

Dữ liệu vào luôn đảm bảo không có cạnh trùng và cạnh nối một đỉnh với chính nó.

Output

Gồm M dòng, dòng thứ i là số thành phần liên thông có dạng vòng sau truy vấn thứ i.

Scoring

Sample Input 1

4 4
1 2
2 3
3 1
3 4

Sample Output 1

0
0
1
0

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 5. SUPERIOR

Đội dự tuyển có N học sinh vừa làm xong một contest gồm K bài, điểm tối đa của bài thứ j là M_j. Bạn nhận được điểm của toàn bộ học sinh, điểm của học sinh i ở bài j là A_{i, j}.

Học sinh i được coi là vượt trội hoàn toàn học sinh j nếu điểm của học sinh i trong mọi bài đều bằng hoặc cao hơn học sinh j. Nói cách khác, học sinh i vượt trội hoàn toàn học sinh j nếu A_{i, x} ≥ A_{j, x} với mọi 1 ≤ x ≤ K.

Yêu cầu : Với mỗi học sinh i, hãy đếm xem học sinh i vượt trội hoàn toàn so với bao nhiêu học sinh khác trong đội dự tuyển.

Dữ liệu đảm bảo 2 học sinh không có kết quả giống hệt nhau. Nghĩa là với mọi cặp số (i, j) thỏa mãn 1 ≤ i < j ≤ N luôn tồn tại số x sao cho A_{i, x} ≠ A_{j, x}.

Input

• Dòng đầu tiên ghi 2 số nguyên N và K (1 ≤ N ≤ 3 × 10⁵, 1 ≤ K ≤ 20).

• Dòng tiếp theo ghi K số nguyên M₁, M₂, ⋯, M_K (1 ≤ M_i ≤ 10⁹).

• Mỗi dòng thứ i trong N dòng tiếp theo ghi K số nguyên A_{i, 1}, A_{i, 2}, ⋯, A_{i, K} (0 ≤ A_{i, j} ≤ M_j).

Output

Gồm N dòng, dòng thứ i là số lượng học sinh khác trong đội dự tuyển mà học sinh i vượt trội hoàn toàn.

Scoring

Gọi P = (M₁ + 1)(M₂ + 1) ⋯ (M_K + 1)

Sample Input 1

3 2
2 2
1 1
2 1
1 2

Sample Output 1

0
1
1

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 6. ARRAY

Lớp học có n học sinh. Ban đầu, cô Nga có một danh sách đo độ thông minh của đội dự tuyển đã được sắp xếp tăng dần và cô cho các học sinh ngồi trên một đường thẳng theo thứ tự đó.

Sau khi cô Nga rời khỏi phòng, đôi khi sẽ có một nhóm học sinh có chỗ ngồi liên tiếp rủ nhau chơi Caro hoặc chơi xếp hình ngay tại chỗ. Do vậy, thi thoảng sẽ có nhóm học sinh ngồi từ vị trí L đến vị trí R cùng tăng hoặc cùng giảm một lượng độ thông minh.

Tuy nhiên, thỉnh thoảng cô Nga sẽ quay lại phòng để kiểm tra. Nếu cô thấy độ thông minh của học sinh trong phòng không còn tăng dần, cô sẽ phát hiện ra đó là điều không đúng. Do vậy, ngay khi cô vào phòng, lớp sẽ bắt đầu ngồi học. Kết quả là độ thông minh của các bạn đều giữ nguyên hoặc tăng lên. Do thời gian có hạn nên từng bạn trong lớp sẽ học ít nhất để sao cho độ thông minh của các học sinh vẫn phải là tăng dần theo chỗ ngồi đã được xếp (các học sinh vẫn giữ nguyên vị trí chỗ ngồi của mình).

Yêu cầu : Xuyên suốt trong quá trình này, Linh ngồi quan sát và đặt ra các câu hỏi về tổng độ thông minh của một nhóm học sinh ở vị trí liên tiếp là bao nhiêu. Bạn hãy giúp Linh nhé.

Input

• Dòng đầu ghi hai số nguyên n và t tương ứng là số học sinh trong lớp và số subtask của test này (1 ≤ n ≤ 5 × 10⁵, 1 ≤ t ≤ 5).

• Dòng thứ hai chứa n số nguyên a₁, a₂, ⋯, a_n là độ thông minh của các học sinh ban đầu luôn đảm bảo là dãy không giảm, nghĩa là a_i-1 ≤ a_i với mọi 2 ≤ i ≤ n (-10⁶ ≤ a_i ≤ 10⁶).

• Dòng thứ ba ghi số nguyên q là số sự kiện xảy ra (1 ≤ q ≤ 5 × 10⁵).

• Dòng thứ j trong số q dòng tiếp theo chứa miêu tả một sự kiện theo một trong các dạng sau:1 L R x: độ thông minh của nhóm học sinh có chỗ ngồi từ vị trí L đến vị trí R tăng thêm x (1 ≤ L ≤ R ≤ n; L, R, x là số nguyên và |x| ≤ 10⁶).2: cô Nga quay lại phòng để kiểm tra. Lúc này, độ thông minh của lớp sẽ thay đổi như đã miêu tả trên.3 L R: Linh đặt ra câu hỏi tổng độ thông minh của các học sinh từ vị trí L đến vị trí R (L, R là số nguyên và 1 ≤ L ≤ R ≤ n).

Output

Với mỗi sự kiện loại 3, in ra một số là tổng độ thông minh mà Linh đặt ra.

Scoring

Sample Input 1

7 1
-5 -3 -3 0 1 4 5
6
1 3 4 3
2
3 2 6
1 2 5 -6
2
3 1 6

Sample Output 1

7
-17

Notes

Sau mỗi sự kiện, độ thông minh của các học sinh thay đổi như sau:

• Sau sự kiện đầu tiên (1 3 4 3), độ thông minh các học sinh lần lượt là: {-5, -3, 0, 3, 1, 4, 5}.

• Sau sự kiện thứ hai (2): Học sinh thứ 5 có độ thông minh tăng lên ít nhất sau khi học là 2 để thành dãy không giảm là {-5, -3, 0, 3, 3, 4, 5}.

• Ở sự kiện thứ ba (3 2 6), tổng độ thông minh của các học sinh từ vị trí 2 đến vị trí 6 là 7.

• Sau sự kiện thứ tư (1 2 5 -6): {-5, -9, -6, -3, -3, 4, 5}.

• Sau sự kiện thứ năm (2): Độ thông minh tăng lên ít nhất sau khi học của học sinh thứ 2 và học sinh thứ 3 lần lượt là 4 và 1 để thành dãy không giảm là {-5, -5, -5, -3, -3, 4, 5}.

• Ở sự kiện thứ sáu (3 1 6), tổng độ thông minh của các học sinh từ vị trí 1 đến vị trí 6 là -17.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.