Kỳ thi: Chọn HSG tỉnh THPT Gia Lai 2025-2026
Tóm tắt: Đề thi gồm 4 bài toán kiểm tra các kỹ năng trọng tâm của học sinh giỏi, trải dài từ đếm số học bằng bao hàm - loại trừ, quy hoạch động đoạn trên xâu, đến tham lam kết hợp chặt nhị phân và cấu trúc dữ liệu gộp tập hợp.

Trong Bài 1: Đếm dãy (Chọn HSG cấp tỉnh THPT Gia Lai 2025-2026), yêu cầu đếm số dãy số nguyên dương có tổng bằng \(S\) và ước chung lớn nhất bằng \(1\) dễ khiến người làm nghĩ đến việc duyệt phân hoạch. Tuy nhiên khi \(S\) lên tới \(10^9\), quan sát thấy tổng số dãy có tổng \(S\) luôn là \(2^{S-1}\) giúp chuyển bài toán về việc trừ đi các dãy có ước chung lớn hơn \(1\) thông qua phân tích thừa số nguyên tố của \(S\) và áp dụng nguyên lý bao hàm - loại trừ.

Cấu trúc đề tiếp tục thử thách khả năng xử lý truy vấn nhanh qua Bài 2: Xâu đối xứng (Chọn HSG cấp tỉnh THPT Gia Lai 2025-2026). Với độ dài xâu \(N \le 5000\), ta có thể xác định tính đối xứng của mọi đoạn con trước, sau đó xây dựng bảng quy hoạch động hai chiều theo công thức tiền tố \(dp[l][r] = dp[l+1][r] + dp[l][r-1] - dp[l+1][r-1] + pal[l][r]\) để trả lời mỗi truy vấn trong thời gian \(O(1)\).

Nửa sau của đề tập trung vào tư duy tối ưu hóa và tổ chức dữ liệu. Bài 3: Chọn quà (Chọn HSG cấp tỉnh THPT Gia Lai 2025-2026) yêu cầu nhận xét chỉ có tối đa một loại quà được chọn nhiều lần để duyệt từng mốc \(b_i\) kết hợp mảng tiền tố và chặt nhị phân, trong khi Bài 4: Tải ứng dụng (Chọn HSG tỉnh THPT Gia Lai 2025-2026) là ví dụ chuẩn mực cho việc dùng Disjoint Set Union kết hợp kỹ thuật gộp bảng băm từ tập nhỏ sang tập lớn (small-to-large).

Bạn nên bắt đầu giải từ Bài 2: Xâu đối xứng (Chọn HSG cấp tỉnh THPT Gia Lai 2025-2026) để khởi động kỹ năng quy hoạch động mảng hai chiều, trước khi chuyển sang phân tích số học ở Bài 1: Đếm dãy (Chọn HSG cấp tỉnh THPT Gia Lai 2025-2026) và thử sức với hai bài còn lại.