Chọn đội tuyển HSG quốc gia Thanh Hóa 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HÓA ĐỀ CHÍNH THỨC
(Mỗi ngày thi có 03 câu, gồm 04 trang)

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH – CHỌN ĐỘI TUYỂN THAM DỰ KỲ THI CHỌN HỌC SINH GIỎI QUỐC GIA TRUNG HỌC PHỔ THÔNG Năm học 2025 - 2026
Môn thi: Tin học
Thời gian làm bài: 180 phút mỗi ngày (không kể thời gian phát đề)
Ngày thi: 23/9/2025 và 24/9/2025

---

Ghi chú

Bản chụp đề ngày thứ nhất bị mất phần tiêu đề phía trên trang 1, nên tên kỳ thi ở trên được ghi theo đề ngày thứ hai.

Ngày thi thứ nhất (23/9/2025)

Hạn chế kĩ thuật:

Tên bài	Tên chương trình	Dữ liệu vào	Kết quả ra	Thời gian	Bộ nhớ
WONDERFUL	WONDERFUL.*	WONDERFUL.INP	WONDERFUL.OUT	1s/Test	1024Mb
ZEN	ZEN.*	ZEN.INP	ZEN.OUT	1s/Test	1024Mb
RALLY	RALLY.*	RALLY.INP	RALLY.OUT	1s/Test	1024Mb

(Dấu * trong chương trình được thay bởi PY hoặc CPP tùy vào ngôn ngữ sử dụng)

Hãy lập trình giải các bài toán sau:

Câu 1 (7.0 điểm): 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ᵢ và pᵢ₊₁ cho nhau.

Một hoán vị q được gọi là tuyệt vời nếu qᵢ ≠ 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.

Dữ liệu: Vào từ tệp văn bản WONDERFUL.INP một số nguyên n là độ dài của hoán vị p (2 ≤ n ≤ 2.10⁵).

Kết quả: Ghi ra tệp văn bản WONDERFUL.OUT là phần dư của đáp án khi chia cho 998244353.

Ví dụ:

WONDERFUL.INP	WONDERFUL.OUT
3	7
4	27
101206	160323547

Giải thích: Ở 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.

Giới hạn:

• Subtask 1: 10% số điểm có n ≤ 10;
• Subtask 2: 10% số điểm có n ≤ 16;
• Subtask 3: 20% số điểm có n ≤ 300;
• Subtask 4: 30% số điểm có n ≤ 5000;
• Subtask 5: 30% số điểm không có ràng buộc gì thêm.

Câu 2 (7.0 điểm): 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.

Dữ liệu: Vào từ tệp văn bản ZEN.INP gồm:

• 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à đá.

Kết quả: Ghi ra tệp văn bản ZEN.OUT gồm 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.

Ví dụ:

ZEN.INP	ZEN.OUT
6 6 ###... #.#... ..#... ..#.## ..##.# ###..#	###... ..#... ..#... ..#... ..#... ###...
3 3 ### ### ###	### ### ###

Giới hạn:

• Subtask 1: 25% số điểm có M = 2;
• Subtask 2: 25% số điểm có số lượng khu vực ô cát liên thông trong input và output như nhau;
• Subtask 3: 25% số điểm có 1 ≤ N, M ≤ 100;
• Subtask 4: 25% số điểm không có giới hạn gì thêm.

Câu 3 (6.0 điểm): 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ết YES nếu chuỗi A xuất hiện, theo cùng thứ tự trên đường dẫn giữa u và v hoặc NO nếu không.

Dữ liệu: Vào từ tệp văn bản RALLY.INP gồm:

• 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.

Kết quả: Ghi kết quả vào tệp văn bản RALLY.OUT với mỗi truy vấn, in ra trên một dòng YES hoặc NO.

Ví dụ:

RALLY.INP	RALLY.OUT
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	YES YES NO

Giải thích: 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ỗi “zysero” xuấ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ỗi “ser” xuấ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ỗi “ymyr” không xuất hiện trong bất kỳ chuỗi con nào vì chữ “m” không bao giờ xuất hiện trong chuỗi “rebresn”.

Giới hạn: Gọi aᵢ là số ký tự trong chuỗi i. Gọi A là tổng của tất cả aᵢ. 2 ≤ N, Q ≤ 3 × 10⁵, Q ≤ A ≤ 3 × 10⁵;

• Subtask 1: 20% số điểm có N, Q ≤ 10⁵. Cây là một đường thẳng, đặc biệt các cạnh có dạng (i, i + 1). Hơn nữa u = 1 và tất cả các chuỗi câu hỏi đều có độ dài bằng 1;
• Subtask 2: 20% số điểm có N, Q ≤ 1000, A ≤ 2000;
• Subtask 3: 20% số điểm có N, Q ≤ 10⁵, A ≤ 2 × 10⁵. Các đỉnh u và v đều giống nhau trong mọi câu hỏi;
• Subtask 4: 20% số điểm có N, Q ≤ 10⁵, A ≤ 2 × 10⁵. Cây là một đường. Đặc biệt, các cạnh có dạng (i, i + 1);
• Subtask 5: 20% số điểm không có ràng buộc gì thêm.

Ngày thi thứ hai (24/9/2025)

Hạn chế kĩ thuật:

	Tên bài	Tên chương trình	Dữ liệu vào	Kết quả ra	Thời gian	Bộ nhớ
Câu 4	RING	RING.*	RING.INP	RING.OUT	1.0s/Test	256 Mb
Câu 5	SUPERIOR	SUPERIOR.*	SUPERIOR.INP	SUPERIOR.OUT	1.5s/Test	256 Mb
Câu 6	ARRAY	ARRAY.*	ARRAY.INP	ARRAY.OUT	2.0s/Test	1024 Mb

(Dấu * trong chương trình được thay bởi PY hoặc CPP tùy vào ngôn ngữ sử dụng)

Câu 4 (7.0 điểm): 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.

Dữ liệu: Vào từ tệp văn bản RING.INP gồm:

• 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ó.

Kết quả: Ghi ra tệp văn bản RING.OUT 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.

Ví dụ:

RING.INP	RING.OUT
4 4 1 2 2 3 3 1 3 4	0 0 1 0

Giới hạn:

• Subtask 1: 30% số điểm có N, M ≤ 10³;
• Subtask 2: 70% số điểm không có giới hạn gì thêm.

Câu 5 (7.0 điểm): 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ứ i là Mᵢ. 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ᵢⱼ.

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ᵢₓ ≥ Aⱼₓ 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 tồn tại số x sao cho Aᵢₓ khác Aⱼₓ.

Dữ liệu: Vào từ tệp văn bản SUPERIOR.INP gồm:

• 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ᵢ ≤ 10⁹);
• Mỗi dòng thứ i trong N dòng tiếp theo ghi K số nguyên Aᵢ₁, Aᵢ₂, …, Aᵢ_K (0 ≤ Aᵢⱼ ≤ Mⱼ).

Kết quả: Ghi ra tệp văn bản SUPERIOR.OUT 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.

Ví dụ:

SUPERIOR.INP	SUPERIOR.OUT
3 2 2 2 1 1 2 1 1 2	0 1 1

Giới hạn: Gọi P = (M₁ + 1)(M₂ + 1)…(M_K + 1)

• Subtask 1: 10% số điểm có N ≤ 10³;
• Subtask 2: 10% số điểm có K = 1;
• Subtask 3: 20% số điểm có K = 2;
• Subtask 4: 20% số điểm có P ≤ 3 ×10⁵, Mᵢ = 1;
• Subtask 5: 20% số điểm có P ≤ 3 ×10⁵, 10 ≤ Mᵢ ≤ 20;
• Subtask 6: 20% số điểm có P ≤ 3 ×10⁵.

Câu 6 (6.0 điểm): 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 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é.

Dữ liệu: Vào từ tệp văn bản ARRAY.INP gồm:

• 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ᵢ là độ thông minh của các học sinh ban đầu luôn đảm bảo là dãy tăng dần, nghĩa là aᵢ₋₁ ≤ aᵢ với mọi 2 ≤ i ≤ n; (−10⁶ ≤ aᵢ ≤ 10⁶);
• Dòng 3 ghi số nguyên q là số sự kiện xảy ra (1 ≤ q ≤ 5×10⁵);
• Dòng thứ i 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 là độ 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 là 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 là 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).

Kết quả: Ghi vào tệp văn bản ARRAY.OUT 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.

Ví dụ:

ARRAY.INP	ARRAY.OUT
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	7 -17

Giải thích: 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, độ 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: 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, 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ư: {-5, -9, -6, -3, -3, 4, 5};
• Sau sự kiện thứ năm: Độ 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, tổng độ thông minh của các học sinh từ vị trí 1 đến vị trí 6 là -17.

Giới hạn:

• Subtask 1: 10% số điểm có n, q ≤ 2000;
• Subtask 2: 20% số điểm có x > 0 và R = n với mọi sự kiện loại 1;
• Subtask 3: 20% số điểm thỏa mãn độ thông minh của các học sinh luôn không âm và bé hơn hoặc bằng 5 tại mọi thời điểm;
• Subtask 4: 20% số điểm thỏa mãn giữa hai sự kiện loại 2 liên tiếp có đúng một thao tác loại 1;
• Subtask 5: 30% số điểm không có điều kiện gì thêm.

---

Hết