Lộ trình ôn thi chuyên Tin lớp 10: dạng đề thường gặp, năm nhóm kiến thức và kế hoạch ôn từ hè lớp 8

Kỳ thi tuyển sinh vào lớp 10 chuyên Tin là bước đầu tiên của nhiều học sinh trên con đường lập trình thi đấu. Khác với bài kiểm tra Tin học ở trường, đề thi chuyên Tin yêu cầu viết chương trình giải bài toán và được chấm bằng bộ test bí mật. Chương trình đúng nhưng chậm sẽ chỉ lấy được một phần điểm; chương trình nhanh nhưng sai một ca biên cũng mất điểm.

Mỗi trường chuyên và mỗi sở giáo dục có cách ra đề riêng. Có nơi thi trên máy tính, có nơi viết chương trình trên giấy; số bài, thời gian làm bài và ngôn ngữ cho phép cũng khác nhau. Vì vậy, việc đầu tiên khi ôn là đọc kỹ thông báo tuyển sinh và đề các năm gần nhất của đúng trường bạn thi. Phần còn lại của bài này tập trung vào thứ ổn định qua các năm và các trường: kiến thức cần có, đặc trưng đề thi của các trường trọng điểm, kỹ thuật ăn điểm từng phần và kế hoạch ôn tập theo tháng.

Bài viết gồm năm phần: cấu trúc đề thi và đặc trưng các trường chuyên lớn, năm nhóm kiến thức cốt lõi, bài toán mẫu về sàng ước và mảng cộng dồn, chiến thuật phân bổ 150 phút trong phòng thi, và kế hoạch ôn theo từng giai đoạn từ hè lớp 8.

1. Các dạng bài thường gặp trong đề chuyên Tin

Nhìn lại đề của nhiều trường trong những năm gần đây, các bài thường được xếp theo độ khó tăng dần với vai trò khá rõ ràng:

Mỗi bài thường có nhiều mức giới hạn. Ví dụ, bài số học có thể cho \(N \le 10^6\) ở mức đầu (duyệt được) và \(N \le 10^{12}\) ở mức cuối (phải dùng công thức hoặc duyệt tới \(\sqrt{N}\)). Bài mảng có thể cho \(N \le 2000\) ở mức đầu (hai vòng lặp chạy kịp) và \(N \le 2 \cdot 10^5\) ở mức cuối.

Cấu trúc này có nghĩa là: không có bài nào nên bỏ trắng. Kể cả bài cuối, một lời giải quay lui thử mọi khả năng cũng thường lấy được mức giới hạn nhỏ nhất. Cách đọc ràng buộc để biết lời giải nào kịp thời gian được trình bày chi tiết ở bài Cách đọc đề và ăn điểm subtask.

Đặc trưng đề thi của các trường chuyên trọng điểm

Mỗi trường có phong cách ra đề mang bản sắc riêng mà thí sinh cần nắm rõ trước kỳ thi:

• Trường Phổ thông Năng khiếu (ĐHQG TP.HCM): Đề thi lập trình trên máy trong 150 phút, thường gồm 4 bài toán. Bài 1 và 2 tập trung vào số học và cấu trúc dữ liệu mảng, xâu ký tự. Bài 3 đòi hỏi kỹ năng tối ưu đoạn (hai con trỏ, mảng cộng dồn hai chiều). Bài 4 là quy hoạch động hoặc quay lui có nhánh cận thông minh. Đề thi chấm tự động trên hệ thống, phân loại thí sinh rất công bằng và rõ ràng.
• Trường THPT Chuyên Khoa học Tự nhiên & Chuyên Sư phạm (Hà Nội): Đề thi có hàm lượng toán học rời rạc rất cao. Các bài toán số học thường có giới hạn rất lớn, đòi hỏi biến đổi đại số, phân tích đồng dư hoặc dùng các tính chất tổ hợp trước khi cài đặt code. Lời giải thường ngắn gọn nhưng khâu suy luận trên giấy nháp chiếm phần lớn thời gian.
• Sở Giáo dục và Đào tạo Hà Nội (Chuyên Hà Nội - Amsterdam, Chuyên Nguyễn Huệ, Chu Văn An): Đề thi bám sát chương trình học sinh giỏi THCS, các bài toán có tính ứng dụng thực tế cao, đòi hỏi thí sinh cẩn thận trong việc đọc hiểu đề, xử lý xâu văn bản và không bỏ sót các trường hợp đặc biệt ở dữ liệu biên.
• Sở Giáo dục và Đào tạo TP.HCM (Chuyên Lê Hồng Phong, Chuyên Trần Đại Nghĩa): Đề thi chú trọng kỹ năng thuật toán hiện đại, xuất hiện nhiều bài toán về tìm kiếm nhị phân trên kết quả, mảng hiệu và các dạng quy hoạch động cổ điển có biến thể.

2. Năm nhóm kiến thức cốt lõi

Để xây dựng một nền tảng vững chắc, bạn cần tập trung vào năm nhóm chủ đề sau đây theo thứ tự từ dễ đến nâng cao:

Nhóm 1: Số học và toán rời rạc

Số học là mỏ điểm lớn nhất trong đề thi chuyên Tin lớp 10, thường chiếm từ 2.5 đến 3.5 điểm trong tổng số 10 điểm của toàn bài:

• Kiểm tra và sàng số nguyên tố: Thuật toán kiểm tra một số nguyên dương \(N\) có nguyên tố hay không bằng cách thử chia tới \(\sqrt{N}\) trong \(\mathcal{O}(\sqrt{N})\). Kỹ thuật Sàng nguyên tố Eratosthenes để đánh dấu mọi số nguyên tố nhỏ hơn hoặc bằng \(10^7\) trong \(\mathcal{O}(M \log \log M)\).
• Ước số và phân tích thừa số nguyên tố: Thuật toán đếm số ước và tính tổng các ước của một số nguyên dương trong \(\mathcal{O}(\sqrt{N})\), công thức phân tích thừa số nguyên tố \(N = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}\) để suy ra số lượng ước bằng \((a_1 + 1)(a_2 + 1) \dots (a_k + 1)\).
• Ước chung lớn nhất và Bội chung nhỏ nhất: Thuật toán Euclid tìm ước chung lớn nhất \(\gcd(a, b)\) trong thời gian logarit. Công thức tính bội chung nhỏ nhất \(\text{BCNN}(a, b) = (a / \gcd(a, b)) \times b\), chú ý chia trước rồi mới nhân để tránh nguy cơ tràn số nguyên 64-bit.
• Đếm số lượng bội số trong đoạn: Đếm số lượng các số là bội của \(K\) nằm 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)\), thay thế hoàn toàn cho vòng lặp duyệt từng số.
• Tính chất đồng dư: Các quy tắc cộng và nhân theo mô-đulo: \((a + b) \bmod M = ((a \bmod M) + (b \bmod M)) \bmod M\), áp dụng triệt để khi đề yêu cầu in đáp án theo một số dư cho trước.

Nhóm 2: Xâu ký tự và mảng đánh dấu tần suất

Các bài toán xâu ký tự kiểm tra sự cẩn thận và kỹ năng thao tác mảng của thí sinh:

• Duyệt xâu từng ký tự, sử dụng bảng đánh dấu kích thước 26 phần tử để đếm tần suất xuất hiện của các chữ cái thường tiếng Anh trong \(\mathcal{O}(|S|)\).
• Kiểm tra tính đối xứng của một xâu (Palindrome), tìm xâu con đối xứng dài nhất bằng cách loang từ tâm trong \(\mathcal{O}(N^2)\).
• Kỹ thuật nén đoạn ký tự liên tiếp giống nhau (Run-Length Encoding) và bài toán chuẩn hóa khoảng trắng trong văn bản.
• Tách các số nguyên nằm xen kẽ giữa các ký tự chữ trong xâu văn bản để đưa vào mảng số xử lý độc lập.

Nhóm 3: Mảng cộng dồn, mảng hiệu và hai con trỏ

Nhóm kỹ thuật giúp giảm bậc độ phức tạp từ \(\mathcal{O}(N^2)\) xuống \(\mathcal{O}(N)\):

• Mảng cộng dồn một chiều: Tiền xử lý \(\text{pref}[i] = \text{pref}[i-1] + A[i]\) để tính tổng đoạn con bất kỳ \(A[L \dots R]\) trong \(\mathcal{O}(1)\) bằng \(\text{pref}[R] - \text{pref}[L-1]\).
• Mảng cộng dồn hai chiều: Tính tổng của một hình chữ nhật con bất kỳ trên bảng số kích thước \(N \times M\) trong \(\mathcal{O}(1)\) sau khi tiền xử lý bảng cộng dồn hai chiều trong \(\mathcal{O}(N \times M)\).
• Mảng hiệu (Difference Array): Cho phép thực hiện thao tác cộng thêm một giá trị \(V\) vào tất cả các phần tử trong đoạn \([L, R]\) chỉ bằng hai phép gán \(D[L] += V\) và \(D[R+1] -= V\) trong \(\mathcal{O}(1)\).
• Kỹ thuật Hai con trỏ: Sử dụng hai con trỏ cùng chiều hoặc ngược chiều để tìm đoạn con thỏa mãn điều kiện tổng hoặc hiệu trên mảng đã sắp xếp hoặc mảng số không âm.

Nhóm 4: Sắp xếp và tìm kiếm nhị phân

• Thành thạo hàm sắp xếp std::sort trong C++ với việc tự định nghĩa hàm so sánh (Comparator) theo nhiều tiêu chí (ví dụ sắp xếp điểm giảm dần, nếu điểm bằng nhau thì sắp xếp theo tên tăng dần).
• Sử dụng các hàm tìm kiếm nhị phân có sẵn trong thư viện chuẩn: std::lower_bound (tìm vị trí đầu tiên có giá trị lớn hơn hoặc bằng khóa) và std::upper_bound (tìm vị trí đầu tiên có giá trị lớn hơn hẳn khóa).
• Kỹ thuật tìm kiếm nhị phân trên đáp án: Áp dụng khi hàm kiểm tra tính khả thi có tính đơn điệu, giúp chuyển đổi bài toán tối ưu thành bài toán kiểm tra điều kiện.

Nhóm 5: Quy hoạch động và quay lui cơ bản

• Kỹ thuật đệ quy quay lui sinh toàn bộ các tập con, chỉnh hợp và hoán vị với kích thước dữ liệu nhỏ (\(N \le 20\)), kết hợp nhánh cận để lấy điểm ở các Subtask đầu của bài phân loại.
• Quy hoạch động một chiều: Các bài toán kinh điển như leo cầu thang, ếch nhảy qua các phiến đá, tìm đoạn con có tổng lớn nhất (thuật toán Kadane).
• Quy hoạch động hai chiều: Bài toán tìm đường đi có tổng lớn nhất trên bảng lưới chữ nhật, bài toán cái túi Knapsack chọn đồ vật sao cho tổng giá trị lớn nhất trong giới hạn khối lượng cho trước.

3. Bài mẫu: tổng số ước trên nhiều đoạn

Bài dưới đây kết hợp nhóm 1 (số học) và nhóm 3 (mảng cộng dồn), là kiểu bài rất hay xuất hiện ở vị trí thứ hai hoặc thứ ba trong đề thi tuyển sinh chuyên Tin.

Đề bài: Gọi \(d(x)\) là số lượng ước nguyên dương của số \(x\). Cho \(Q\) truy vấn độc lập, mỗi truy vấn gồm hai số nguyên dương \(L, R\). Với mỗi truy vấn, hãy tính tổng \(d(L) + d(L+1) + \dots + d(R)\). Giới hạn dữ liệu: số lượng truy vấn \(Q \le 10^5\), các biên \(1 \le L \le R \le 10^6\).

Phân tích thuật toán: Nếu với mỗi truy vấn, ta duyệt từng số \(x\) từ \(L\) tới \(R\) và đếm số ước của \(x\) bằng cách thử chia tới \(\sqrt{x}\), mỗi truy vấn có thể tốn tới \((R - L + 1) \times \sqrt{R} \approx 10^6 \times 10^3 = 10^9\) phép toán. Với \(Q = 10^5\) truy vấn, tổng thời gian chạy sẽ lên tới hàng trăm giây và chắc chắn nhận kết quả quá thời gian (Time Limit Exceeded). Lời giải vét cạn này chỉ giúp bạn lấy được khoảng 30% số điểm ở Subtask 1 khi \(Q \le 100\) và \(R \le 1000\).

Để giải trọn vẹn bài toán với \(100\%\) số điểm, ta áp dụng kỹ thuật tiền xử lý ngoại tuyến (Offline Precomputation) qua hai bước:

Bước 1: Sàng ước số trong \(\mathcal{O}(M \ln M)\). Thay vì đếm ước cho từng số độc lập, ta đảo ngược góc nhìn: mỗi số nguyên \(i\) từ 1 tới \(M\) (\(M = \max R \le 10^6\)) sẽ là ước của các bội số của nó: \(i, 2i, 3i, 4i, \dots\). Do đó, ta chỉ cần khởi tạo mảng \(d\) ban đầu toàn số 0. Với mỗi bước lặp \(i\) từ 1 tới \(M\), ta duyệt qua tất cả các bội số \(j = i, 2i, 3i, \dots \le M\) và tăng \(d[j] += 1\). Tổng số thao tác cộng được tính bằng chuỗi điều hòa:

\[\sum_{i=1}^{M} \frac{M}{i} = M \left( 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{M} \right) \approx M \ln M\]

Với \(M = 10^6\), tổng số phép tính chỉ khoảng \(1.4 \times 10^7\), thực thi trong chưa đầy 0.05 giây trong ngôn ngữ C++.

Bước 2: Xây dựng mảng cộng dồn trong \(\mathcal{O}(M)\). Sau khi có mảng \(d\), ta dựng mảng tiền tố tổng: \(\text{pref}[0] = 0\) và \(\text{pref}[x] = \text{pref}[x-1] + d[x]\) với mọi \(x\) từ 1 tới \(M\). Khi đó, với mỗi truy vấn \((L, R)\), đáp án được tính ngay lập tức bằng một phép trừ duy nhất: \(\text{pref}[R] - \text{pref}[L-1]\) trong thời gian \(\mathcal{O}(1)\). Toàn bộ \(Q\) truy vấn được trả lời trong \(\mathcal{O}(Q)\), đưa tổng độ phức tạp của toàn bộ bài toán về \(\mathcal{O}(M \ln M + Q)\).

Bảng chạy tay với giá trị \(x\) từ 1 tới 12 minh họa rõ các bước tính toán:

Khi kiểm tra với 3 truy vấn mẫu:

• Truy vấn 1 (\(L = 1, R = 6\)): \(\text{pref}[6] - \text{pref}[0] = 14 - 0 = \mathbf{14}\).
• Truy vấn 2 (\(L = 4, R = 10\)): \(\text{pref}[10] - \text{pref}[3] = 27 - 5 = \mathbf{22}\). Tính tay đối chiếu: \(d(4) + d(5) + d(6) + d(7) + d(8) + d(9) + d(10) = 3 + 2 + 4 + 2 + 4 + 3 + 4 = 22\) (hoàn toàn chính xác).
• Truy vấn 3 (\(L = 1, R = 12\)): \(\text{pref}[12] - \text{pref}[0] = 35 - 0 = \mathbf{35}\).

Dưới đây là mã nguồn cài đặt hoàn chỉnh bằng C++17 và Python 3:

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

// Sàng đếm số ước d(x) kết hợp mảng cộng dồn trả lời Q truy vấn tổng số ước trên [L, R]
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    vector<pair<int, int>> queries;
    int max_r = 0;
    if (!(cin >> q)) {
        queries = {{1, 6}, {4, 10}, {1, 12}};
        max_r = 12;
    } else {
        queries.resize(q);
        for (int i = 0; i < q; ++i) {
            cin >> queries[i].first >> queries[i].second;
            max_r = max(max_r, queries[i].second);
        }
    }
    vector<int> d(max_r + 1, 0);
    for (int i = 1; i <= max_r; ++i) {
        for (int j = i; j <= max_r; j += i) {
            d[j]++;
        }
    }
    vector<long long> pref(max_r + 1, 0);
    for (int i = 1; i <= max_r; ++i) {
        pref[i] = pref[i - 1] + d[i];
    }
    for (size_t i = 0; i < queries.size(); ++i) {
        int l = queries[i].first, r = queries[i].second;
        cout << (pref[r] - pref[l - 1]) << (i + 1 == queries.size() ? "" : " ");
    }
    cout << "\n";
    return 0;
}

import sys

def solve() -> None:
    data = sys.stdin.read().split()
    if not data:
        queries = [(1, 6), (4, 10), (1, 12)]
    else:
        q = int(data[0])
        queries = []
        idx = 1
        for _ in range(q):
            queries.append((int(data[idx]), int(data[idx + 1])))
            idx += 2
    max_r = max(r for _, r in queries)
    d = [0] * (max_r + 1)
    for i in range(1, max_r + 1):
        for j in range(i, max_r + 1, i):
            d[j] += 1
    pref = [0] * (max_r + 1)
    for i in range(1, max_r + 1):
        pref[i] = pref[i - 1] + d[i]
    ans = [str(pref[r] - pref[l - 1]) for l, r in queries]
    print(" ".join(ans))

if __name__ == "__main__":
    solve()

Với ba truy vấn mẫu trên, chương trình xuất ra kết quả:

14 22 35

4. Chiến thuật 150 phút và tâm lý phòng thi chuyên Tin

Một kỳ thi tuyển sinh lớp 10 thường kéo dài 150 phút với 3 đến 4 bài. Để đạt được điểm số từ 8.0 trở lên, thí sinh cần có kỷ luật phòng thi rõ ràng:

Phân bổ 150 phút theo 4 chặng hợp lý

1. Chặng 1 (15 phút đầu): Đọc kỹ toàn bộ đề bài. Không chạm vào bàn phím gõ code. Đọc kỹ từng câu chữ, gạch chân các giới hạn của từng Subtask ra giấy nháp. Xác định ngay bài nào là bài số học dễ, bài nào là xâu ký tự và bài nào là bài khó phân loại.
2. Chặng 2 (45 phút tiếp theo): Giải quyết trọn vẹn Bài 1 và Bài 2. Đây là hai bài bắt buộc phải đạt điểm tối đa. Viết code cẩn thận, chạy thử với ví dụ trong đề và tự kiểm tra thêm các ca biên nhỏ (\(N = 1\), số nguyên tố, mảng toàn số 0).
3. Chặng 3 (60 phút giữa giờ): Tấn công Bài 3 và lấy điểm Subtask của Bài 4. Dành trọn thời gian suy nghĩ thuật toán tối ưu cho Bài 3. Với Bài 4, nếu chưa thấy hướng giải toàn vẹn, hãy lập tức viết một hàm quay lui hoặc quy hoạch động đơn giản để bỏ túi từ 1 đến 2 điểm của Subtask đầu tiên.
4. Chặng 4 (30 phút cuối giờ): Kiểm tra lại toàn diện mã nguồn. Kiểm tra lại tên tệp nhập xuất (freopen("TENBAI.INP", "r", stdin); và freopen("TENBAI.OUT", "w", stdout); nếu thi ngoại tuyến), kiểm tra biến kết quả đã khai báo long long chưa, và chắc chắn rằng tệp nộp bài đã được lưu đúng thư mục quy định của hội đồng coi thi.

Những lỗi sơ đẳng làm mất điểm oan

• Lỗi tràn số nguyên 32-bit: Trong C++, kiểu int chỉ chứa được giá trị tối đa khoảng \(2.14 \times 10^9\). Khi tính tổng các phần tử của một mảng lớn hoặc nhân hai số nguyên \(10^6\), kết quả sẽ bị tràn sang số âm nếu không khai báo biến bằng kiểu long long (hoặc ép kiểu 1LL * a * b).
• Sai quy định đọc ghi tệp: Nhiều hội đồng thi sử dụng phần mềm Themis chấm tự động qua tệp .INP và .OUT. Nếu đề bài yêu cầu tên tệp là TIMSO.INP mà bạn gõ nhầm thành timso.inp hoặc quên mở tệp, chương trình sẽ nhận 0 điểm tuyệt đối dù thuật toán hoàn toàn đúng.
• Bỏ quên ca biên: Quên xử lý trường hợp mảng chỉ có đúng một phần tử \(N = 1\), các số trong mảng đều bằng nhau, hoặc giá trị \(L = R\) trong các truy vấn đoạn.

5. Kế hoạch ôn từ hè lớp 8 tới kỳ thi

Kế hoạch dưới đây dành cho học sinh bắt đầu từ hè lớp 8 lên lớp 9, mỗi tuần dành khoảng 6–8 giờ cho lập trình. Nếu bắt đầu muộn hơn vào giữa năm lớp 9, hãy tập trung tối đa thời gian cho nhóm 1 đến nhóm 3, vì đây là những chủ đề chiếm phần lớn số điểm trong mọi đề thi:

Đừng quên rằng điểm xét tuyển vào lớp chuyên Tin thường tính tổng điểm môn chuyên nhân hệ số kết hợp với các môn thi chung (Toán chung, Ngữ văn chung, Tiếng Anh chung). Do đó, học sinh cần giữ nhịp học tập cân bằng ở tất cả các môn trong năm lớp 9 để đảm bảo tổng điểm xét tuyển đạt mức an toàn nhất.

Luyện ngay trên Big-O Coding

Ba bài dưới đây trong lộ trình PTNK 2026 tương ứng các nhóm kiến thức của bài: số học về ước, mảng cộng dồn hai chiều và quy hoạch động tổng tập con:

Nguồn tham khảo

• CP-Algorithms — Sieve of Eratosthenes
• USACO Guide — Introduction to Complete Search
• USACO Guide — Prefix Sums