Đây là bộ tài liệu chính thức từ kỳ thi Học sinh giỏi cấp tỉnh THPT đợt 1 năm học 2022-2023 của Sở Giáo dục và Đào tạo tỉnh Quảng Nam. Với thời gian làm bài 180 phút và độ khó đặc trưng của kỳ thi HSG, tài liệu này không chỉ là nguồn tham khảo quý giá cho các bạn học sinh đang ôn luyện đội tuyển Tin học mà còn là tư liệu giảng dạy hữu ích cho các thầy cô giáo trong việc xây dựng ma trận đề thi và bồi dưỡng học sinh năng khiếu.
Cấu trúc & Nội dung trọng tâm
Đề thi được thiết kế gồm 4 bài toán lập trình với độ khó tăng dần, bao quát nhiều mảng kiến thức trọng tâm trong lập trình thi đấu (Competitive Programming). Cụ thể:
- Bài 1: Bộ số học (SOHOC) - Tập trung vào kiến thức Số học. Yêu cầu thí sinh vận dụng hiểu biết về Ước số chung lớn nhất (GCD), Bội số chung nhỏ nhất (LCM), tính chất chia hết và tổ hợp. Bài toán đòi hỏi kỹ năng xử lý số lớn và chia dư cho $10^9 + 9$.
- Bài 2: Đếm sỏi (DEMSOI) - Thuộc dạng bài Hình học tọa độ và Cấu trúc dữ liệu. Thí sinh cần xử lý các hình chữ nhật trên mặt phẳng 2 chiều, đếm số ô vuông thỏa mãn điều kiện. Đây là bài toán điển hình yêu cầu tối ưu hóa về bộ nhớ và thời gian (có thể sử dụng kỹ thuật Nén tọa độ hoặc Segment Tree 2D).
- Bài 3: Sóc ăn hạt dẻ (HATDE) - Một bài toán Tối ưu hóa/Quy hoạch động. Mục tiêu là tìm chi phí di chuyển nhỏ nhất để gộp các phần tử về $K$ khay. Với giới hạn $N \le 20$, bài toán hướng tới việc tìm kiếm tối ưu hoặc duyệt trạng thái.
- Bài 4: Hệ thống xe Bus (SBUS) - Chuyên đề Lý thuyết đồ thị (Cây - Tree). Bài toán yêu cầu xử lý đường đi ngắn nhất trên cây và xác định các cạnh không được sử dụng. Kỹ thuật then chốt thường dùng cho dạng này là Lowest Common Ancestor (LCA) và kỹ thuật mảng hiệu trên cây.
Điểm nổi bật của tài liệu
Tài liệu này sở hữu nhiều ưu điểm vượt trội, bám sát tiêu chuẩn của các kỳ thi HSG hiện nay:
- Phân hóa đối tượng rõ rệt: Mỗi bài toán đều có bảng Ràng buộc (Subtasks) chia theo tỷ lệ điểm (10%, 20%, 30%...), giúp học sinh ở mọi trình độ đều có thể ghi điểm từ những trường hợp cơ bản trước khi chinh phục các test case khó.
- Tính ứng dụng thực tế: Các bài toán được lồng ghép dưới dạng câu chuyện (cô giáo giảng bài, con sóc ăn hạt dẻ, hệ thống xe bus), giúp kích thích tư duy phân tích và chuyển đổi từ ngôn ngữ đời thực sang mô hình toán học.
- Yêu cầu khắt khe về hiệu năng: Với giới hạn thời gian 1s và bộ nhớ 1024M, tài liệu rèn luyện cho học sinh khả năng tối ưu hóa thuật toán, tránh các lỗi tràn bộ nhớ hoặc chạy quá thời gian (TLE).
- Chuẩn cấu trúc thi chuyên: Cách trình bày tệp dữ liệu vào (.INP) và ra (.OUT) đúng quy chuẩn thi lập trình quốc gia và quốc tế.
Hướng dẫn ôn tập & Lời khuyên học tập
Để khai thác tối đa giá trị của đề thi này, học sinh và giáo viên có thể áp dụng chiến thuật sau:
Đối với học sinh:
- Đi từ dễ đến khó: Đừng quá sa đà vào bài 4 nếu chưa giải quyết triệt để bài 1. Hãy cố gắng đạt điểm tối đa ở các subtask nhỏ để xây dựng sự tự tin.
- Phân tích độ phức tạp: Trước khi viết code, hãy tính toán độ phức tạp thời gian $O(n)$ của thuật toán để đảm bảo phù hợp với giới hạn của đề bài.
- Rèn luyện kỹ năng đọc đề: Tập trung vào các từ khóa quan trọng và điều kiện biên (ví dụ: $K \le 10^9$ trong bài 1) để chọn kiểu dữ liệu phù hợp (long long trong C++).
Đối với giáo viên:
- Xây dựng chuỗi bài tập tương tự: Từ 4 dạng bài trên, thầy cô có thể phát triển thêm các bài tập tương đương để học sinh rèn luyện sâu hơn về Số học, Hình học, DP và Đồ thị.
- Hướng dẫn tư duy giải quyết vấn đề: Thay vì đưa ra lời giải chi tiết ngay lập tức, hãy gợi ý cho học sinh về các cấu trúc dữ liệu/thuật toán then chốt (ví dụ: gợi ý về LCA cho bài 4).
