1. Interval DP (DP trên đoạn / Range DP) Dạng này dùng khi bạn cần giải quyết bài toán trên một mảng bằng cách gộp (merge) đáp án từ các đoạn con ngắn hơn lại thành đoạn dài hơn. Dấu hiệu nhận bi...

1. Tư duy cốt lõi 🔗 Bài toán: Dãy nghịch thế Giả sử ta cần đếm số cặp $(i, j)$ sao cho $i < j$ và $A_i > A_j$. Cách làm ngây thơ là 2 vòng lặp $O(N^2)$. Để tối ưu xuống $O(N \...

Dạng 1: Hai con trỏ trên hai mảng Dạng này dùng để trộn, so sánh hoặc ghép cặp các phần tử giữa hai mảng khác nhau (thường cả 2 mảng đã được sắp xếp). Con trỏ $i$ chạy trên mảng $A$, con trỏ $...

Đây là phần 2 của Các thuật toán về xâu kí tự, xem phần 1 ở đây: Các thuật toán về xâu kí tự🔐 (Phần 1) A. Trie + Trie XOR I, Trie 1. Khái niệm Trie là một cấu trúc dữ liệu dạng cây, được thiết...

A. Kỹ thuật bắc cầu trên DAG bằng Bitset Kỹ thuật bắc cầu kết hợp với Bitset DP trên DAG là kỹ thuật giải quyết triệt để bài toán: “Cho đồ thị có hướng, hãy xác định xem từ đỉnh $u$ có thể đi đến ...

Đây là phần 1 của Các thuật toán về xâu kí tự, xem phần 2 ở đây: Các thuật toán về xâu kí tự🔐 (Phần 2) A. Thuật toán Z & KMP I. Thuật toán Z 1. Khái niệm Z-function Cho một chuỗi $S$ có ...

1. Khái niệm về cây Trong lý thuyết đồ thị, cây có các thuộc tính sau: Là một đồ thị vô hướng gồm $V$ đỉnh và $V-1$ cạnh Liên thông Không có chu trình Giữa hai ...

Thuật toán Kruskal Dựa trên tư tưởng tham lam (Greedy) và Cấu trúc dữ liệu các tập hợp rời rạc (DSU - Disjoint Set Union). Thuật toán sắp xếp các cạnh tăng dần theo trọng số và thêm vào cây nế...

Minh họa thuật toán Tarjan Dạng 1: Thành phần liên thông mạnh Thuật toán Tarjan dựa trên việc duyệt theo chiều sâu (DFS) để tìm các Thành phần liên thông mạnh (TPLTM - Strongly Connected Componen...

🔗 Bài toán kinh điển: ONEZERO - Ones and zeros I. Tóm tắt đề bài Cho một số nguyên dương $n$. Hãy tìm số nguyên dương $X$ nhỏ nhất thỏa mãn đồng thời hai điều kiện: $X$ là bội số c...