Đây là bộ tài liệu đề thi chính thức trong kỳ thi chọn học sinh giỏi (HSG) cấp tỉnh dành cho học sinh lớp 12 tại Quảng Nam, đợt 2 năm học 2023-2024. Với thời gian làm bài 150 phút và cấu trúc gồm 4 bài tập lập trình chuyên sâu, 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 HSG mà còn là tư liệu giảng dạy hữu ích cho các giáo viên bồi dưỡng chuyên Tin ở bậc THPT.
Cấu trúc & Nội dung trọng tâm
Đề thi được thiết kế theo ma trận phân hóa rõ rệt, bao quát nhiều mảng kiến thức quan trọng trong lập trình thi đấu. Cụ thể bao gồm 4 bài toán với các dạng chuyên đề sau:
- Bài 1: BOM CHÙM (Số học) - Tập trung vào kiến thức về ước số và tổng các ước nguyên dương. Bài toán yêu cầu tối ưu hóa thuật toán để xử lý số lượng truy vấn lớn (lên đến $10^6$) và giá trị số lớn (đến $10^{12}$), đòi hỏi học sinh phải nắm vững kỹ thuật sàng số nguyên tố hoặc phân tích thừa số nguyên tố.
- Bài 2: TỆP NHẬT KÝ (Xử lý chuỗi & Kỹ thuật đếm) - Kết hợp giữa xử lý xâu ký tự (loại bỏ nhiễu để trích xuất số) và bài toán đếm cặp có tổng bằng K. Đây là dạng bài điển hình để kiểm tra kỹ năng sử dụng Map hoặc kỹ thuật Two Pointers (hai con trỏ).
- Bài 3: BỜM VÀ PHÚ ÔNG (Quy hoạch động) - Một biến thể của bài toán Knapsack (Cái túi) kinh điển. Học sinh không chỉ tìm tổng trọng lượng lớn nhất mà còn phải đếm số cách đạt được tổng đó, yêu cầu sự chính xác trong việc quản lý trạng thái quy hoạch động và xử lý số dư (modulo $10^9+7$).
- Bài 4: KIẾN (Thuật toán đồ thị/Tìm kiếm trên lưới) - Yêu cầu vận dụng thuật toán BFS (Breadth-First Search) hoặc DFS để tìm số ô có thể đến được trong một lưới có vật cản với giới hạn bước đi $S$. Bài toán kiểm tra tư duy về tọa độ và khả năng tối ưu hóa bộ nhớ/thời gian khi $S$ lên đến $10^7$.
Điểm nổi bật của tài liệu
Bộ đề thi 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 loại Subtask chi tiết: Mỗi bài toán đều được chia thành nhiều Subtask với mức điểm khác nhau. Điều này giúp học sinh dễ dàng tiếp cận từ mức độ cơ bản (ăn điểm phần dễ) đến nâng cao (tối ưu cho test lớn).
- Độ khó thực tế và đa dạng: Đề thi không tập trung vào một dạng duy nhất mà trải dài từ Số học, Xử lý chuỗi, Quy hoạch động cho đến Đồ thị, buộc thí sinh phải có kiến thức tổng hợp.
- Yêu cầu tối ưu hóa cao: Với giới hạn thời gian 1s và bộ nhớ 1024MB, đề thi nhấn mạnh vào việc lựa chọn thuật toán có độ phức tạp thời gian thấp (ví dụ: $O(N \log N)$ hoặc $O(N)$), rất phù hợp để luyện tư duy tối ưu.
- Có hướng dẫn chấm rõ ràng: Tài liệu đi kèm hướng dẫn chấm chi tiết về số lượng test và phân bổ điểm, giúp người học tự đánh giá năng lực một cách khách quan.
Hướng dẫn ôn tập & Lời khuyên học tập
Để khai thác hiệu quả bộ đề 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:
- Tiếp cận theo từng Subtask: Đừng cố gắng giải quyết bài toán tối ưu ngay lập tức. Hãy viết code cho Subtask 1 để lấy điểm cơ bản, sau đó mới suy nghĩ cách tối ưu cho các Subtask tiếp theo.
- Luyện tập với Themis: Vì đề thi được chấm bằng phần mềm Themis, các bạn nên cài đặt công cụ này để kiểm tra thời gian chạy và bộ nhớ chính xác như khi thi thật.
- Chú trọng xử lý số lớn: Đặc biệt ở Bài 1 và Bài 3, hãy lưu ý sử dụng kiểu dữ liệu
long long (trong C++) để tránh tràn số.
- Đối với giáo viên:
- Sử dụng đề thi này làm bài kiểm tra đánh giá năng lực cuối giai đoạn bồi dưỡng.
- Hướng dẫn học sinh phân tích độ phức tạp thuật toán trước khi bắt tay vào lập trình để rèn luyện tư duy thiết kế giải thuật.
