Nhận biết dạng bài giúp bạn chọn đúng thuật toán ngay từ đầu. Dưới đây là các dạng phổ biến nhất.
1. Bài toán trên mảng/dãy số
Truy vấn đoạn
- Tổng đoạn tĩnh → Prefix sum /query
- Tổng đoạn + cập nhật điểm → Fenwick Tree
- Tổng / max / min đoạn + cập nhật → Segment Tree
Dãy con
- Dãy con tăng dài nhất → LIS
- Tổng dãy con lớn nhất → Kadane's algorithm
- Dãy con chung dài nhất → LCS
Hai con trỏ (Two Pointers)
Dùng khi tìm cặp/đoạn thỏa điều kiện trên mảng đã sắp xếp:
int l = 0, r = n-1;
while (l < r) {
if (a[l]+a[r] == target) { /* tìm thấy */ break; }
if (a[l]+a[r] < target) l++;
else r--;
}
Sliding Window
Dùng khi tìm đoạn con độ dài thỏa điều kiện:
// Tổng lớn nhất đoạn độ dài k
long long sum = 0, best = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
if (i >= k) sum -= a[i-k];
if (i >= k-1) best = max(best, sum);
}
2. Bài toán đồ thị
| Yêu cầu | Thuật toán |
|---|---|
| Liên thông / đếm thành phần | DFS / BFS / DSU |
| Đường đi ngắn nhất (không trọng số) | BFS |
| Đường đi ngắn nhất (trọng số dương) | Dijkstra |
| Đường đi ngắn nhất (trọng số âm) | Bellman-Ford |
| Đường đi ngắn nhất mọi cặp | Floyd-Warshall |
| Cây khung nhỏ nhất | Kruskal / Prim |
| Thứ tự thực hiện (DAG) | Topo sort |
| Chu trình | DFS + màu sắc |
3. Bài toán tối ưu (Optimization)
- Tối ưu có cấu trúc con → DP
- Lựa chọn tham lam rõ ràng → Greedy
- Tìm min/max thỏa điều kiện → Binary search trên đáp án
Ví dụ binary search trên đáp án: "In xong cuốn sách trong ngày với tốc độ tối thiểu bao nhiêu?" → Binary search trên tốc độ, kiểm tra tính khả thi.
4. Bài toán đếm / tổ hợp
- Đếm số cách chọn / sắp xếp → Tổ hợp
- Đếm số cách chia / phân hoạch → DP
- Đếm cặp thỏa điều kiện → Two pointers hoặc Hash map
- Đếm nghịch thế → Merge sort hoặc BIT
5. Bài toán xâu chuỗi
| Yêu cầu | Thuật toán |
|---|---|
| Tìm pattern trong text | KMP / Z-function |
| So sánh chuỗi con | String hashing |
| Tìm kiếm theo prefix | Trie |
| Palindrome dài nhất | Manacher's algorithm |
6. Bài toán số học / toán học
- Chia hết, GCD, LCM → Euclid
- Số nguyên tố → Sàng / kiểm tra
- Lũy thừa lớn → Fast power + modulo
- Đếm tổ hợp → Precompute factorial
- Số học đồng dư → Fermat's little theorem
Checklist khi gặp bài mới
[ ] Đọc ràng buộc → xác định O(?) cần thiết
[ ] Brute force được không?
[ ] Bài có dạng quen không? (xem bảng trên)
[ ] Cần sắp xếp trước không?
[ ] Có thể binary search trên đáp án không?
[ ] Bài có cấu trúc con → DP?
[ ] Bài có lựa chọn tham lam → Greedy?
Bình luận