Skip to content

Lộ trình học Lập trình thi đấu

Lộ trình từ zero đến hero — từ người mới bắt đầu đến giải cao ICPC/VOI. Mỗi bài học đều có link trực tiếp, mô tả ngắn và yêu cầu tiên quyết.

Cách sử dụng lộ trình

  • Học theo thứ tự nhóm từ ⭐ đến ⭐⭐⭐⭐
  • Trong mỗi nhóm, học từ trên xuống dưới
  • Các nhóm có ký hiệu "nhánh rẽ" có thể học song song sau khi xong Nhóm 3
  • Nhóm 9 (Kỹ năng thi đấu) nên xen kẽ từ sớm, không cần chờ

Sơ đồ tổng quan

Chi tiết lộ trình theo nhóm

⭐ Nhóm 1 — Nhập môn (6 bài)

Dành cho người hoàn toàn mới. Học xong nhóm này, bạn có thể giải các bài cơ bản.

Bài học Nội dung chính Tiên quyết
Setup môi trường Cài đặt IDE, compiler, template C++/Python Không
Độ phức tạp thời gian Big-O, Big-Omega, ước lượng thời gian chạy Không
Thuật toán sắp xếp Merge Sort, Quick Sort, Counting Sort Độ phức tạp
Tìm kiếm nhị phân Binary Search, lower/upper bound Sắp xếp
Phép toán bit AND, OR, XOR, bitmask, subset enumeration Không
Đệ quy và quay lui Recursion, backtracking, N-Queens, Sudoku Không

⭐⭐ Nhóm 2 — Kỹ thuật cơ bản (3 bài)

Các kỹ thuật dùng rất thường xuyên trong thi đấu. Học xong có thể giải 60-70% bài cơ bản.

Bài học Nội dung chính Tiên quyết
Hai con trỏ Two pointers, sliding window, Two Sum Sắp xếp, Tìm kiếm nhị phân
Mảng, Stack, Prefix Sum Prefix Sum, Difference Array, Monotone Stack Không
Lũy thừa nhị phân & Sàng nguyên tố Fast modular exponentiation, Sieve of Eratosthenes Không

⭐⭐ Nhóm 3 — Cấu trúc dữ liệu cơ bản (9 bài)

Các cấu trúc dữ liệu bắt buộc phải biết. Không có chúng, bạn không thể giải nhiều bài.

Bài học Nội dung chính Tiên quyết
Linked List Danh sách liên kết đơn/đôi, cài đặt Stack/Queue Không
Queue Hàng đợi FIFO, mảng vòng, BFS cơ bản Không
Hash Table Bảng băm, hash function, chaining, open addressing Không
Deque & Sliding Window Deque, hàng đợi đơn điệu, min/max trên đoạn Queue
Trie Cây tiền tố, bitwise trie, autocomplete Hash Table
Heap Priority Queue, Binary Heap, Heap Sort Sắp xếp
DSU Disjoint Set Union, Path Compression, Union by Rank Hash Table
Segment Tree Cây phân đoạn, Lazy Propagation, Range Query Mảng, Prefix Sum
Fenwick Tree Cây chỉ số nhị phân, Prefix Sum Query Mảng, Prefix Sum

⭐⭐⭐ Nhóm 4 — Đồ thị (4 bài)

Đồ thị là lĩnh vực lớn nhất trong competitive programming. Học xong nhóm này, bạn có thể giải phần lớn bài đồ thị.

Bài học Nội dung chính Tiên quyết
BFS/DFS trên đồ thị Duyệt đồ thị, thành phần liên thông, topo sort Queue
MST, Dijkstra, Topo Sort Cây khung nhỏ nhất, đường đi ngắn nhất BFS/DFS, Heap
Floyd-Warshall & Bellman-Ford Đường đi ngắn nhất tất cả cặp, cạnh âm BFS/DFS
LCA & Binary Lifting Tổ tiên chung gần nhất, nhảy bậc \(2^k\) BFS/DFS

⭐⭐⭐ Nhóm 5 — Quy hoạch động & Tham lam (3 bài)

Quy hoạch động là kỹ năng quan trọng nhất trong competitive programming. Cần nhiều thời gian luyện tập.

Bài học Nội dung chính Tiên quyết
Greedy Thuật toán tham lam, chứng minh tính đúng Sắp xếp
Quy hoạch động 4 bước xây dựng DP, Knapsack, LIS, LCS Không
Binary Search on Answer Tìm kiếm nhị phân trên đáp án, parametric search Tìm kiếm nhị phân

⭐⭐⭐ Nhóm 6 — Xử lý xâu (4 bài)

Xử lý xâu là mảng riêng biệt, cần học các thuật toán chuyên biệt.

Bài học Nội dung chính Tiên quyết
KMP Thuật toán Knuth-Morris-Pratt, prefix function Không
Hash xâu & Z-algorithm Rolling hash, Z-function, Rabin-Karp Không
Manacher Tìm palindrome dài nhất trong \(O(N)\) Không
Suffix Array Mảng hậu tố, LCP array, Doubling algorithm Không

⭐⭐⭐ Nhóm 7 — Toán & Số học (12 bài)

Toán học xuất hiện ở rất nhiều bài. Học các kỹ thuật số học giúp giải nhiều bài "khó hiểu".

Bài học Nội dung chính Tiên quyết
Euclid & Modular Inverse GCD, Extended Euclid, nghịch đảo modulo Lũy thừa nhị phân
Tổ hợp & Xác suất \(C(n,k)\), giai thừa modulo, xác suất cơ bản Modular Inverse
Số học nâng cao Euler's totient, Lucas Theorem, CRT, Möbius Modular Inverse
Lý thuyết trò chơi Sprague-Grundy, Nim, Grundy number Không
Sàng nâng cao & Hàm ước Linear sieve, SPF, đếm ước, phân tích thừa số Sàng nguyên tố
Nguyên lý bao hàm - loại trừ Inclusion-Exclusion, derangement Tổ hợp
Đếm đường đi trên lưới \(\binom{n+m}{n}\), Catalan, đếm trên lưới có vật cản Tổ hợp
Nhân ma trận Ma trận, lũy thừa ma trận, đếm đường đi Lũy thừa nhị phân
Logarithm rời rạc BSGS (Baby-Step Giant-Step), discrete log Modular Inverse
Căn nguyên thủy Primitive root, Tonelli-Shanks, dấu hiệu bình phương Euler's totient
NTT & Nhân đa thức Number Theoretic Transform, FFT modulo Căn nguyên thủy
Khử Gauss Elimination, hạng ma trận, hệ phương trình tuyến tính Không

⭐⭐⭐ Nhóm 8 — Hình học (10 bài)

Hình học tính toán — từ cơ bản đến nâng cao. Cần nắm vững tích vô hướng/có hướng.

Bài học Nội dung chính Tiên quyết
Hình học cơ bản Tích vô hướng, tích có hướng, diện tích, vị trí tương đối Không
Phương trình đường thẳng Giao điểm, khoảng cách, diện tích đa giác Hình học cơ bản
Hình học đường tròn Tiếp tuyến, giao đường tròn, diện tích giao Hình học cơ bản
Định lý Pick Đếm điểm nguyên trong đa giác, Pick's theorem Hình học cơ bản
Góc & Phép quay atan2, quay điểm, quay không gian Hình học cơ bản
Sắp xếp cực & Quét góc Sắp xếp theo góc, sweep line, rotating calipers Hình học cơ bản
Bao lồi Convex Hull, Graham Scan, Andrew's Monotone Chain Hình học cơ bản
Stack nâng cao Monotone stack, biểu thức, hình chữ nhật lớn nhất Stack
BST Cây tìm kiếm nhị phân, chèn/xóa/tìm, duyệt cây Sắp xếp
Sparse Table Truy vấn min/max \(O(1)\) trên mảng tĩnh Mảng

🏆 Nhóm 9 — Kỹ năng thi đấu (4 bài)

Không phải thuật toán, nhưng cực kỳ quan trọng để đạt điểm cao. Nên học xen kẽ từ sớm.

Bài học Nội dung chính Tiên quyết
Kỹ năng thi đấu Chiến thuật đọc đề, quản lý thời gian, phân bổ thời gian Không
Sinh testcase & Stress test Tạo testcase ngẫu nhiên, stress test tìm bug Không
Debug & Mẹo thi đấu Debug hiệu quả, fix WA/TLE/RE, mẹo code nhanh Không
Tổ chức code & Nộp bài Quản lý thư mục, script test tự động, template Không

⭐⭐⭐⭐ Nhóm 10 — Đồ thị nâng cao (4 bài)

Các thuật toán đồ thị nâng cao, cần thiết cho ICPC/VOI.

Bài học Nội dung chính Tiên quyết
SCC & Cầu & Khớp Tarjan, Kosaraju, bridges, articulation points BFS/DFS
Network Flow Edmonds-Karp, Dinic, Min-Cost Max-Flow BFS/DFS
Bipartite Matching Kuhn's, Hopcroft-Karp, Hungarian BFS/DFS
2-SAT Bài toán thỏa mãn logic, implication graph, SCC SCC

⭐⭐⭐⭐ Nhóm 11 — Cây nâng cao (3 bài)

Các kỹ thuật xử lý cây nâng cao, xuất hiện rất thường xuyên trong bài khó.

Bài học Nội dung chính Tiên quyết
Euler Tour Flatten cây thành mảng, subtree query, LCA BFS/DFS
Centroid Decomposition Phân tách trọng tâm, đếm đường đi trên cây BFS/DFS
HLD Phân rã cây, truy vấn đường đi \(O(\log^2 N)\) LCA, Segment Tree

⭐⭐⭐⭐ Nhóm 12 — Quy hoạch động nâng cao (4 bài)

Các dạng DP nâng cao, thường xuất hiện trong bài khó.

Bài học Nội dung chính Tiên quyết
DP trên cây Subtree DP, rerooting, tree knapsack Quy hoạch động, BFS/DFS
Digit DP Đếm số theo chữ số, memoization trên digit Quy hoạch động
Interval DP Matrix chain, merge stones, boolean parenthesization Quy hoạch động
Tối ưu DP Knuth's, Divide & Conquer DP, CHT, Alien's trick Quy hoạch động

⭐⭐⭐⭐ Nhóm 13 — Xâu nâng cao (2 bài)

Các thuật toán xử lý xâu nâng cao.

Bài học Nội dung chính Tiên quyết
Aho-Corasick Tìm nhiều mẫu trong xâu, failure links KMP, Trie
Suffix Automaton Máy trạng thái hậu tố, \(O(N)\) construction Suffix Array

⭐⭐⭐⭐ Nhóm 14 — Kỹ thuật nâng cao (3 bài)

Các kỹ thuật và cấu trúc dữ liệu nâng cao.

Bài học Nội dung chính Tiên quyết
Chia căn & Mo's Algorithm Sqrt decomposition, offline queries, Hilbert curve Mảng
Convex Hull Trick Tối ưu DP với đường thẳng, Li Chao Tree Quy hoạch động
Ternary Search Tìm kiếm tam phân, hàm unimodal Tìm kiếm nhị phân

Gợi ý lộ trình theo thời gian

Giai đoạn Thời gian Nội dung Số bài
Nền tảng Tuần 1–4 Lập trình cơ bản → Nhóm 1 6
Kỹ thuật Tuần 5–10 Nhóm 2 → Nhóm 3 12
Mở nhánh Tuần 11–16 Nhóm 4 (chính) + Nhóm 5 hoặc 6 hoặc 7 7–12
Nâng cao Tuần 17–22 Nhóm 10/11 (tiếp 4) + Nhóm 8 hoặc 9 7–14
Chuyên sâu Tuần 23–34 Nhóm 12, 13, 14 9

Tổng: 71 bài giảng — từ cơ bản đến chuyên sâu.

Chú thích

Ký hiệu Độ khó Đối tượng
⭐ Cơ bản Người mới bắt đầu
⭐⭐ Trung bình Nền tảng thi đấu
⭐⭐⭐ Nâng cao Thi HSG, ICPC
⭐⭐⭐⭐ Rất khó Thi cao cấp

Tài liệu tham khảo

💬 Bình luận