Các dạng bài thường gặp

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 $[l,r]$ tĩnh → Prefix sum $O(1)$/query
• Tổng đoạn $[l,r]$ + cập nhật điểm → Fenwick Tree $O(\log N)$
• Tổng / max / min đoạn + cập nhật → Segment Tree $O(\log N)$

Dãy con

• Dãy con tăng dài nhất → LIS $O(N\log N)$
• Tổng dãy con lớn nhất → Kadane's algorithm $O(N)$
• Dãy con chung dài nhất → LCS $O(NM)$

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 $K$ 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ị

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 $N$ cuốn sách trong $D$ 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 $C(n,k)$
• Đế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

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 $O(\sqrt{N})$
• 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?