Lộ trình ôn thi Tin học trẻ toàn quốc cho bảng A, B, C: kiến thức theo từng chặng và lịch ôn 12 tuần

Hội thi Tin học trẻ toàn quốc do Trung ương Đoàn TNCS Hồ Chí Minh chủ trì phối hợp với các bộ, ngành tổ chức hằng năm từ những năm 1990. Phần thi lập trình là phần được nhiều học sinh và phụ huynh quan tâm nhất, vì nó kiểm tra khả năng tư duy thuật toán, gần với các kỳ thi học sinh giỏi Tin học và mở ra cơ hội tuyển thẳng vào các trường THPT chuyên trên cả nước.

Bài viết này dành cho học sinh đang chuẩn bị thi bảng A, B hoặc C và cho giáo viên, phụ huynh muốn có một kế hoạch ôn tập rõ ràng, khoa học. Nội dung gồm năm phần: cấu trúc các bảng thi và thể thức chấm trực tiếp (Live Score), lộ trình bốn chặng cho bảng B và bảng C, bài toán mẫu về đếm cặp số đồng dư, chiến thuật làm bài thi trên hệ thống chấm trực tuyến, và lịch ôn 12 tuần kèm các lỗi thường gặp.

Lưu ý: thể lệ cụ thể (số vòng, thời gian làm bài, ngôn ngữ được dùng, phần thi sản phẩm sáng tạo) có thể thay đổi theo từng năm. Hãy luôn đọc thể lệ chính thức do Ban Tổ chức công bố ở năm bạn dự thi; bài này tập trung vào phần kiến thức và phương pháp ôn luyện, vốn ổn định qua các năm.

1. Các bảng thi và kiến thức cần chuẩn bị

Phần thi lập trình chia theo cấp học, nên mỗi bảng có mức độ kiến thức khác nhau. Bảng dưới đây tóm tắt những gì học sinh mỗi bảng nên chuẩn bị:

Với bảng A, mục tiêu chính là làm quen với tư duy chia bài toán thành các bước nhỏ tuần tự. Các em học sinh lớp 4, lớp 5 có nền Toán tốt có thể học thêm Python cơ bản (biến, vòng lặp for, danh sách) để thấy cùng một ý tưởng có thể viết gọn trong vài dòng lệnh thay vì kéo thả hàng chục khối lệnh phức tạp. Không nên vội dạy các thuật toán nâng cao ở cấp này; quan trọng hơn là tập thói quen đọc kỹ đề, vẽ hình nháp và thử tay với các số nhỏ.

Với bảng B và bảng C, đề thi có cấu trúc rất gần với đề học sinh giỏi cấp tỉnh và đề thi vào lớp 10 chuyên Tin. Phần lớn kiến thức của hai kỳ thi này giao thoa nhau tới hơn 80%, nên học sinh lớp 8, lớp 9 ôn Tin học trẻ cũng đồng thời trang bị kiến thức vững vàng để bước vào kỳ thi tuyển sinh trường chuyên.

2. Lộ trình bốn chặng cho bảng B và bảng C

Một đề thi lập trình Tin học trẻ thường có từ 3 đến 4 bài, xếp từ dễ tới khó. Bốn chặng dưới đây tương ứng với bốn nhóm bài hay gặp, từ bài mở màn lấy điểm tới bài phân loại huy chương. Học xong chặng nào, hãy giải đủ bài luyện của chặng đó rồi mới chuyển sang chặng sau.

Chặng 1: Số học và đồng dư

Bài đầu tiên trong đề thi Tin học trẻ luôn là một tình huống đời thường (xếp hàng đồng diễn, chia kẹo, đếm các số có tính chất đối xứng) nhưng giới hạn ở mức cuối thường lên tới \(N \le 10^{12}\) hoặc \(10^{18}\) để loại các lời giải chỉ dùng một vòng lặp đơn giản. Những kiến thức bắt buộc phải nắm vững:

• Công thức thay cho vòng lặp: Tổng dãy số cách đều \(1 + 2 + \dots + N = N(N+1)/2\); đếm số bội của \(K\) trong đoạn \([L, R]\) bằng công thức một dòng \(\lfloor R/K \rfloor - \lfloor (L-1)/K \rfloor\) trong \(\mathcal{O}(1)\).
• Tính chất đồng dư: \((a + b) \bmod K = ((a \bmod K) + (b \bmod K)) \bmod K\), tương tự với phép nhân. Tính chất này cho phép làm việc với các số dư nhỏ thay vì số gốc rất lớn, tránh hoàn toàn nguy cơ tràn số.
• Ước và số nguyên tố: Kiểm tra một số có phải số nguyên tố bằng cách thử chia tới \(\sqrt{N}\), đếm số lượng ước của một số, Sàng nguyên tố Eratosthenes để đánh dấu mọi số nguyên tố tới \(10^6\) hoặc \(10^7\) trong thời gian gần như tuyến tính.
• Ước chung lớn nhất: Thuật toán Euclid và mối quan hệ \(\text{BCNN}(a, b) = (a / \text{UCLN}(a, b)) \times b\) (chia trước rồi nhân để giảm nguy cơ tràn số nguyên 64-bit).

Chặng 2: Xâu, sắp xếp và tham lam

• Xâu ký tự: Đếm tần suất từng chữ cái bằng mảng đánh dấu kích thước 26, kiểm tra tính đối xứng của một xâu, nén các đoạn ký tự giống nhau liên tiếp (ví dụ aaabcc thành a3b1c2), tách từ và chuẩn hóa các dấu cách thừa trong câu.
• Sắp xếp với tiêu chí riêng: Sắp xếp theo nhiều khóa bằng cách tự viết hàm so sánh (sắp xếp điểm thi giảm dần, nếu bằng điểm thì sắp xếp theo họ tên tăng dần), sắp xếp các khoảng thời gian theo mốc kết thúc.
• Chiến thuật tham lam: Bài toán chọn nhiều hoạt động nhất không chồng chéo nhau (sắp xếp theo thời điểm kết thúc rồi chọn lần lượt), bài toán nối dây nơ với chi phí nhỏ nhất (mỗi bước lấy hai đoạn ngắn nhất từ hàng đợi ưu tiên priority_queue, nối lại và đẩy tổng mới vào lại hàng đợi).

Với bài tham lam, hãy luôn tự hỏi "có phản ví dụ làm sai thuật toán không?". Cách đơn giản và hiệu quả nhất là viết thêm một lời giải vét cạn thử mọi khả năng và so sánh kết quả trên dữ liệu nhỏ, như hướng dẫn trong bài Kỹ thuật sinh test và đối chiếu code.

Chặng 3: Mảng cộng dồn, hai con trỏ và tìm kiếm nhị phân

Khi đề bài hỏi về các cặp chỉ số \((i, j)\) hoặc các đoạn con liên tiếp trên mảng có kích thước lên tới \(2 \cdot 10^5\) phần tử, việc sử dụng hai vòng lặp lồng nhau sẽ tốn khoảng \(4 \cdot 10^{10}\) phép tính và chắc chắn quá thời gian. Có ba kỹ thuật quen thuộc để loại bỏ vòng lặp bên trong:

1. Đếm những gì đã đi qua bằng mảng tần suất: Khi duyệt chỉ số \(j\) từ trái sang phải, ta duy trì một mảng đếm các giá trị đã xuất hiện ở bên trái \(j\). Bài mẫu ở phần 3 dùng đúng kỹ thuật này để giảm thời gian từ \(\mathcal{O}(N^2)\) xuống \(\mathcal{O}(N)\).
2. Sắp xếp rồi dùng hai con trỏ hoặc tìm kiếm nhị phân: Áp dụng khi thứ tự ban đầu của các phần tử không ảnh hưởng tới kết quả của bài toán.
3. Mảng cộng dồn: Biến điều kiện tổng trên đoạn con \([l, r]\) thành mối liên hệ giữa hai giá trị độc lập \(P[r]\) và \(P[l-1]\), sau đó kết hợp với mảng đếm để giải quyết trong một lượt duyệt duy nhất.

Chặng 4: Quy hoạch động và đồ thị cơ bản

Bài cuối của đề bảng B và bảng C thường là bài toán phân loại giải Nhất, Nhì:

• Quy hoạch động: Các bài toán cổ điển như ếch nhảy qua các phiến đá với bước nhảy tối đa \(K\), chọn các đoạn con rời nhau có tổng lớn nhất, bài toán đường đi trên bảng lưới chữ nhật có vật cản, bài toán cái túi Knapsack.
• Đồ thị cơ bản (Bảng C và Bảng B nâng cao): Thuật toán loang trên lưới BFS/DFS đếm số vùng liên thông, tìm đường đi ngắn nhất với trọng số không âm bằng thuật toán Dijkstra, và kiểm tra tính liên thông khi thêm cạnh bằng cấu trúc Tập hợp rời rạc (DSU).

Kể cả khi chưa nghĩ ra cách tối ưu toàn bộ trạng thái của bài toán, một công thức quy hoạch động đúng với độ phức tạp \(\mathcal{O}(N^2)\) thường đã lấy được từ 50% đến 70% số điểm của bài cuối. Hãy cài đặt bản vét cạn trước để chắc chắn có điểm, sau đó mới suy nghĩ cách giảm chiều trạng thái.

3. Bài mẫu: đếm cặp số có tổng chia hết cho K

Bài toán dưới đây là dạng bài rất hay xuất hiện trong các đề thi Tin học trẻ cấp tỉnh và toàn quốc, minh họa rõ nét cách chuyển đổi từ thuật toán duyệt toàn bộ sang thuật toán tuyến tính nhờ tính chất đồng dư.

Đề bài: Cho dãy \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(N \le 2 \cdot 10^5\), \(A_i \le 10^9\)) và số nguyên dương \(K \le 10^6\). Hãy đếm số lượng cặp chỉ số \((i, j)\) với \(1 \le i \lt j \le N\) sao cho tổng \(A_i + A_j\) chia hết cho \(K\).

Phân tích từ vét cạn lên tối ưu:

• Lời giải chậm cho giới hạn nhỏ (\(N \le 5000\)): Duyệt mọi cặp chỉ số \((i, j)\) bằng hai vòng lặp lồng nhau và kiểm tra điều kiện (A[i] + A[j]) % K == 0. Khi \(N = 2 \cdot 10^5\), số cặp lên tới \(\frac{N(N-1)}{2} \approx 2 \cdot 10^{10}\), chắc chắn nhận kết quả quá thời gian. Lời giải này chỉ lấy được 40% số điểm ở Subtask 1.
• Lời giải nhanh tuyến tính trong \(\mathcal{O}(N + K)\): Ta nhận thấy giá trị tuyệt đối của từng số không quyết định tính chia hết, mà chỉ có số dư khi chia cho \(K\) mới quyết định. Gọi \(r = A_j \bmod K\) (với \(0 \le r \lt K\)). Để tổng \(A_i + A_j\) chia hết cho \(K\), số đứng trước \(A_i\) phải có số dư khi chia cho \(K\) là:

\[\text{can} = (K - r) \bmod K\]

Viết công thức (K - r) % K giúp xử lý gọn gàng cả hai trường hợp: khi \(r = 0\) thì số dư cần tìm là 0; khi \(r \gt 0\) thì số dư cần tìm là \(K - r\). Do đó, ta chỉ cần duy trì một mảng đếm tần suất freq kích thước \(K\). Khi duyệt từng phần tử \(A_j\) từ trái sang phải, ta cộng ngay freq[can] vào đáp án, rồi tăng freq[r] lên một đơn vị. Mỗi bước chỉ tốn \(\mathcal{O}(1)\), toàn bộ bài toán chạy trong \(\mathcal{O}(N + K)\).

Bảng chạy tay trên dãy \(A = [2, 5, 1, 7, 4, 8]\) với \(K = 3\) (mảng đếm ban đầu freq = [0, 0, 0] cho ba số dư 0, 1, 2):

Kết quả thu được là 9 cặp hợp lệ. Kiểm tra lại bằng tổ hợp: dãy có 3 số dư 1 (gồm 1, 7, 4) và 3 số dư 2 (gồm 2, 5, 8). Để có tổng chia hết cho 3, ta ghép một số dư 1 với một số dư 2, tạo ra \(3 \times 3 = 9\) cặp. Kết quả tính toán hoàn toàn trùng khớp.

#include <bits/stdc++.h>
using namespace std;

// Đếm số cặp chỉ số (i < j) sao cho (a[i] + a[j]) chia hết cho K trong O(N + K)
long long count_divisible_pairs(const vector<long long>& a, int k) {
    vector<long long> freq(k, 0);
    long long ans = 0;
    for (long long x : a) {
        int r = (int)((x % k + k) % k);
        int need = (k - r) % k;
        ans += freq[need];
        freq[r]++;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) {
        cout << count_divisible_pairs({2, 5, 1, 7, 4, 8}, 3) << "\n";
        return 0;
    }
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    cout << count_divisible_pairs(a, k) << "\n";
    return 0;
}

import sys

def count_divisible_pairs(a: list[int], k: int) -> int:
    freq = [0] * k
    ans = 0
    for x in a:
        r = x % k
        need = (k - r) % k
        ans += freq[need]
        freq[r] += 1
    return ans

def main() -> None:
    data = sys.stdin.read().split()
    if not data:
        print(count_divisible_pairs([2, 5, 1, 7, 4, 8], 3))
        return
    n = int(data[0])
    k = int(data[1])
    a = [int(x) for x in data[2:2 + n]]
    print(count_divisible_pairs(a, k))

if __name__ == "__main__":
    main()

Lưu ý quan trọng trong C++: biến tổng kết quả ans bắt buộc phải khai báo bằng kiểu long long. Trong trường hợp xấu nhất khi tất cả các phần tử đều có số dư 0, số cặp có thể lên tới \(2 \cdot 10^{10}\), vượt xa giới hạn khoảng \(2.14 \cdot 10^9\) của kiểu số nguyên 32-bit int.

4. Chiến thuật làm bài trên hệ thống chấm trực tuyến

Hội thi Tin học trẻ từ Vòng Khu vực trở đi áp dụng hệ thống chấm bài trực tuyến hiển thị điểm tức thì (Live Scoreboard tương tự CMS của Olympic quốc tế). Nắm vững đặc thù này mang lại lợi thế chiến thuật cực lớn:

1. Nộp ngay lời giải vét cạn để lấy điểm nền: Vì hệ thống chấm ngay và thường tính điểm lần nộp cao nhất, bạn nên viết và nộp ngay một bản code vét cạn đơn giản cho bài 1 và bài 2 trong 30 phút đầu. Khi bảng điểm đã hiện 40–50 điểm an toàn, tâm lý làm bài của bạn sẽ thoải mái hơn rất nhiều để suy nghĩ thuật toán tối ưu.
2. Đọc kỹ phản hồi của máy chấm khi bị lỗi: Nếu bài nộp nhận kết quả WA (Wrong Answer) ở các test nhỏ, lỗi nằm ở logic thuật toán hoặc ca biên (\(N = 1\), số âm). Nếu nhận TLE (Time Limit Exceeded) ở các test cuối, thuật toán của bạn chưa đạt độ phức tạp yêu cầu hoặc chưa dùng kỹ thuật nhập xuất nhanh. Nếu nhận RTE (Runtime Error), hãy kiểm tra ngay kích thước mảng khai báo có đủ chứa chỉ số lớn nhất hay không.
3. Phân bổ thời gian theo đồng hồ phòng thi: Dành 15 phút đầu đọc đề; 45 phút tiếp theo hoàn thành trọn vẹn bài 1; 45 phút giữa giờ xử lý bài 2; thời gian còn lại vét điểm các Subtask của bài 3 và bài 4. Dành 15 phút cuối cùng kiểm tra lại toàn bộ mã nguồn trước khi rời phòng thi.

5. Lịch ôn 12 tuần và những lỗi thường gặp

Lịch dưới đây dành cho học sinh bảng B hoặc C đã biết cú pháp cơ bản của C++ hoặc Python, mỗi tuần dành khoảng 6–8 giờ cho việc học và luyện tập:

Ở hai tuần cuối, hãy làm đề trong điều kiện giống thi thật: bấm giờ nghiêm túc, không tra tài liệu trên mạng, sau đó tự chấm theo từng mức giới hạn. Việc chia thời gian trong phòng thi được trình bày chi tiết trong bài Cách đọc đề và ăn điểm subtask.

Những lỗi khiến học sinh mất điểm oan nhất:

• Tràn số nguyên 32-bit: Tổng, tích hoặc số cặp vượt giới hạn của int. Khi kết quả có thể lớn hơn \(2 \cdot 10^9\), luôn dùng kiểu long long.
• Đọc dữ liệu chậm: Với vài trăm nghìn số nguyên, cách đọc mặc định có thể chiếm phần lớn thời gian chạy của chương trình. Xem kỹ bài Tăng tốc nhập xuất trong C++ và Python.
• Bỏ trống bài khó: Kể cả khi không nghĩ ra cách tối ưu, lời giải vét cạn bằng quay lui vẫn giúp bạn lấy được phần điểm của các mức giới hạn nhỏ.
• Không thử ca biên: Trường hợp \(N = 1\), mọi phần tử bằng nhau, \(K = 1\), hoặc giá trị lớn nhất theo quy định của đề bài.
• Sai tên tệp hoặc cách đọc ghi: Đọc kỹ quy định của đề (đọc từ bàn phím luồng chuẩn hay đọc từ tệp văn bản) và kiểm tra lại trước khi hết giờ làm bài.

Khi đã vững bốn chặng trên, học sinh có thể tiếp tục nâng cao trình độ theo Lộ trình lập trình thi đấu và HSG Tin học để hướng tới các sân chơi lớn hơn ở bậc THPT.

Luyện ngay trên Big-O Coding

Ba bài dưới đây trong lộ trình Tin học trẻ 200 tương ứng ba chặng của bài: đếm theo số dư, tham lam nối dây và quy hoạch động bước nhảy:

Nguồn tham khảo

• USACO Guide — Introduction to Competitive Programming
• USACO Guide — Prefix Sums
• CP-Algorithms — Number of divisors and sum of divisors