📚 FPTOJ Problem Set¶
Chào mừng các bạn đến với FPTOJ Problem Set! Dưới đây là danh sách các bài tập thực hành được thiết kế đồng bộ với các bài học lý thuyết trên Wiki, giúp các bạn rèn luyện từ cơ bản đến nâng cao. Hãy click vào liên kết để bắt đầu làm bài và nộp bài trực tiếp trên hệ thống FPTOJ.
🟢 1. Nhóm Nhập môn & Cài đặt (Setup & Basic I/O)¶
Tập trung vào hướng dẫn làm quen hệ thống, đọc/ghi dữ liệu, câu lệnh rẽ nhánh và các bài toán cơ bản đầu tiên.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
setup-hello |
Lời chào từ An | ⭐ | Nhập xuất cơ bản | Setup môi trường thi đấu |
setup-sum |
An và chiếc hộp quà | ⭐ | Phép toán cơ bản | Setup môi trường thi đấu |
setup-fibo |
Gia tộc thỏ Bình | ⭐⭐ | Vòng lặp & Dãy số | Setup môi trường thi đấu |
setup-game |
Trò chơi chia kẹo | ⭐⭐ | Phép toán cơ bản | Setup môi trường thi đấu |
setup-triangle |
Mảnh đất hình tam giác | ⭐⭐⭐ | Hình học cơ bản | Setup môi trường thi đấu |
🟢 1b. Nhóm Phân tích Độ phức tạp (Time Complexity)¶
Luyện tập cách ước lượng thời gian chạy, so sánh và tối ưu hóa độ phức tạp của các thuật toán.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
comp-sum |
An và chiếc máy tính | ⭐ | Phép toán cơ bản | Độ phức tạp thời gian |
comp-pairs |
Đếm cặp số của An | ⭐⭐ | Phép toán cơ bản | Độ phức tạp thời gian |
comp-pow |
Trò chơi lũy thừa | ⭐⭐⭐ | Lý thuyết số | Độ phức tạp thời gian |
comp-subseg |
Dãy con của Việt | ⭐⭐⭐ | Quy hoạch động | Độ phức tạp thời gian |
comp-digits |
Số lượng ước số | ⭐⭐⭐⭐ | Lý thuyết số | Độ phức tạp thời gian |
🟢 1c. Nhóm Thuật toán Sắp xếp (Sorting Algorithms)¶
Học cách tổ chức lại dữ liệu, từ việc sắp xếp cơ bản, so sánh tùy biến, đến áp dụng sắp xếp trong giải thuật Tham lam và đếm nghịch thế.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
sort-basic |
Sắp xếp dãy số | ⭐ | Sắp xếp | Thuật toán sắp xếp |
sort-desc |
Sắp xếp giảm dần | ⭐ | Sắp xếp | Thuật toán sắp xếp |
sort-distinct |
Số lượng giá trị khác nhau | ⭐⭐ | Sắp xếp | Thuật toán sắp xếp |
sort-points |
Xếp hạng học sinh | ⭐⭐ | Sắp xếp | Thuật toán sắp xếp |
sort-parity |
Sắp xếp chẵn lẻ | ⭐⭐ | Sắp xếp | Thuật toán sắp xếp |
sort-median |
Tìm số trung vị | ⭐⭐ | Sắp xếp | Thuật toán sắp xếp |
sort-closest |
Cặp số gần nhau nhất | ⭐⭐⭐ | Sắp xếp | Thuật toán sắp xếp |
sort-meetings |
Lịch họp tối đa | ⭐⭐⭐ | Sắp xếp & Tham lam | Thuật toán sắp xếp |
sort-pairs |
Ghép cặp mũ bảo hiểm | ⭐⭐⭐⭐ | Sắp xếp & Hai con trỏ | Thuật toán sắp xếp |
sort-inversions |
Đếm số cặp nghịch thế | ⭐⭐⭐⭐⭐ | Sắp xếp & Chia để trị | Thuật toán sắp xếp |
🟢 1d. Nhóm Tìm kiếm nhị phân (Binary Search)¶
Luyện tập các kỹ thuật chia để trị cơ bản trên mảng đã sắp xếp, tìm kiếm nhị phân trên không gian kết quả, chia mảng tối ưu và bảng nhân.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
bs-basic |
Tìm kiếm cơ bản | ⭐ | Tìm kiếm nhị phân | Tìm kiếm nhị phân |
bs-first-last |
Đoạn giá trị trùng nhau | ⭐⭐ | Tìm kiếm nhị phân | Tìm kiếm nhị phân |
bs-sqrt |
Căn bậc hai số nguyên | ⭐⭐ | Tìm kiếm nhị phân | Tìm kiếm nhị phân |
bs-wood |
Máy cưa gỗ tối ưu | ⭐⭐⭐ | BS on Answer | Tìm kiếm nhị phân |
bs-cows |
Bố trí đàn bò | ⭐⭐⭐ | BS on Answer | Tìm kiếm nhị phân |
bs-split |
Chia mảng tối ưu | ⭐⭐⭐ | BS on Answer | Tìm kiếm nhị phân |
bs-factory |
Nhà máy sản xuất | ⭐⭐⭐⭐ | BS on Answer | Tìm kiếm nhị phân |
bs-multiplication |
Bảng nhân kì diệu | ⭐⭐⭐⭐⭐ | BS on Answer | Tìm kiếm nhị phân |
bs-upper |
Đếm số ≤ X | ⭐ | Tìm kiếm nhị phân | Tìm kiếm nhị phân |
bs-miss |
Số bị thiếu | ⭐ | Tìm kiếm nhị phân | Tìm kiếm nhị phân |
🟢 1i. Nhóm Mảng cộng dồn & Stack (Prefix Sum & Stack)¶
Kiến thức nền tảng: mảng cộng dồn 1D/2D, Kadane, mảng hiệu (difference array), stack và stack đơn điệu.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
ps-sum |
Truy vấn tổng | ⭐ | Prefix Sum | Mảng, Stack, Prefix Sum |
st-bracket |
Ngoặc đơn vui nhộn | ⭐ | Stack | Mảng, Stack, Prefix Sum |
ps-kadane |
Sòng bạc may rủi | ⭐⭐ | Kadane | Mảng, Stack, Prefix Sum |
ps-diff |
Cơn mưa đầu mùa | ⭐⭐ | Difference Array | Mảng, Stack, Prefix Sum |
ps-equal |
Kho báu dưới lòng đất | ⭐⭐ | Prefix Sum + HashMap | Mảng, Stack, Prefix Sum |
st-next |
Đội hình thể thao | ⭐⭐ | Stack đơn điệu | Mảng, Stack, Prefix Sum |
ps-grid |
Vườn trái cây | ⭐⭐ | Prefix Sum 2D | Mảng, Stack, Prefix Sum |
ps-paint |
Tô hàng rào | ⭐⭐⭐ | Difference + Max | Mảng, Stack, Prefix Sum |
🟡 2. Nhóm Toán học & Số học (Mathematics)¶
Nền tảng số học thiết yếu cho lập trình thi đấu: kiểm tra nguyên tố, sàng, phân tích thừa số, đếm ước, nghịch đảo modulo, tổ hợp, hàm phi Euler và định lý thặng dư Trung Hoa.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
math-prime |
Kiểm tra số nguyên tố | ⭐ | Lý thuyết số | Số học nâng cao |
math-sieve |
Sàng nguyên tố | ⭐⭐ | Lý thuyết số | Số học nâng cao |
math-factor |
Phân tích thừa số nguyên tố | ⭐⭐ | Lý thuyết số | Số học nâng cao |
math-divcnt |
Đếm số lượng ước số | ⭐⭐ | Lý thuyết số | Số học nâng cao |
math-modinv |
Nghịch đảo modulo | ⭐⭐⭐ | Lý thuyết số | Số học nâng cao |
math-binom |
Tổ hợp chập | ⭐⭐⭐ | Lý thuyết số | Số học nâng cao |
phi-euler |
Hàm Phi Euler | ⭐⭐ | Lý thuyết số | Hàm Phi Euler & Hàm Nhân Tính |
crt |
Định Lý Thặng Dư Trung Hoa | ⭐⭐⭐ | Lý thuyết số | Định lý Thặng dư Trung Hoa (CRT) |
🟡 2b. Nhóm Lũy thừa nhị phân & Sàng nguyên tố (Binary Exponentiation & Prime Sieve)¶
Thực hành lũy thừa nhị phân, Fermat nhỏ, sàng Eratosthenes, sàng SPF, sàng phân đoạn, ma trận lũy thừa, hàm Euler và nguyên lý bao hàm.
🟢 1e. Nhóm Phép toán Bit (Bitwise Operations)¶
Làm quen với thao tác trên bit: AND, OR, XOR, dịch bit, bitmask và ứng dụng.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
bit-single |
Số duy nhất | ⭐ | XOR | Phép toán bit |
bit-power |
Lũy thừa của 2 | ⭐ | Bit trick | Phép toán bit |
bit-count |
Đếm bit 1 | ⭐ | Đếm bit | Phép toán bit |
bit-subset |
Tập con may mắn | ⭐⭐⭐ | Bitmask duyệt tập con | Phép toán bit |
bit-assign |
Phân công công việc | ⭐⭐⭐⭐ | Bitmask DP | Phép toán bit |
🟢 1f. Nhóm Fun với Bits (Fun with Bits)¶
Các thủ thuật bit nâng cao: LSB, xóa bit, duyệt tập con, XOR/AND lớn nhất.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
fun-lsb |
Bit thấp nhất | ⭐ | n & -n (LSB) |
Fun with Bits |
fun-clear |
Xóa bit 1 | ⭐ | n & (n-1) |
Fun with Bits |
fun-subsets |
Đếm tập con | ⭐⭐ | Duyệt bitmask | Fun with Bits |
fun-pairxor |
Cặp XOR lớn nhất | ⭐⭐⭐ | XOR | Fun with Bits |
fun-maxand |
Cặp AND lớn nhất | ⭐⭐⭐⭐ | AND | Fun with Bits |
🟢 1g. Nhóm Đệ quy & Quay lui (Recursion & Backtracking)¶
Từ đệ quy cơ bản (giai thừa, Fibonacci, GCD) đến quay lui liệt kê hoán vị, tổ hợp, và các bài toán ứng dụng (N-Queens, Tháp Hà Nội, Knapsack).
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
rec-fact |
Tính giai thừa | ⭐ | Đệ quy | Đệ quy & Quay lui |
rec-fibo |
Số Fibonacci | ⭐ | Đệ quy có nhớ | Đệ quy & Quay lui |
rec-power |
Lũy thừa bằng đệ quy | ⭐ | Đệ quy | Đệ quy & Quay lui |
rec-digit |
Đếm chữ số | ⭐ | Đệ quy | Đệ quy & Quay lui |
rec-gcd |
GCD bằng đệ quy | ⭐ | Đệ quy Euclid | Đệ quy & Quay lui |
rec-binary |
Xâu nhị phân | ⭐⭐ | Quay lui | Đệ quy & Quay lui |
rec-perm |
Hoán vị | ⭐⭐ | Quay lui | Đệ quy & Quay lui |
rec-comb |
Tổ hợp | ⭐⭐ | Quay lui | Đệ quy & Quay lui |
rec-subsetsum |
Tổng tập con | ⭐⭐ | Quay lui | Đệ quy & Quay lui |
rec-maze |
Đếm đường đi | ⭐⭐ | Đệ quy | Đệ quy & Quay lui |
rec-nqueen |
N-Queens | ⭐⭐⭐ | Quay lui | Đệ quy & Quay lui |
rec-knap |
Knapsack vét cạn | ⭐⭐⭐ | Quay lui + nhánh cận | Đệ quy & Quay lui |
rec-coin |
Đổi tổng | ⭐⭐⭐ | Quay lui | Đệ quy & Quay lui |
rec-partition |
Phân hoạch số | ⭐⭐⭐ | Quay lui | Đệ quy & Quay lui |
rec-tower |
Tháp Hà Nội | ⭐⭐⭐ | Đệ quy | Đệ quy & Quay lui |
rec-sudoku |
Sudoku | ⭐⭐⭐⭐⭐ | Quay lui | Đệ quy & Quay lui |
rec-mcolor |
Tô màu đồ thị | ⭐⭐⭐⭐⭐ | Quay lui | Đệ quy & Quay lui |
🟢 1h. Nhóm Kỹ thuật Hai con trỏ (Two Pointers)¶
Từ tìm cặp tổng, trộn mảng, sliding window đến 3Sum, 4Sum, hứng nước và các biến thể nâng cao.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
tp-pairx |
Cặp tổng X | ⭐ | Two pointers | Kỹ thuật hai con trỏ |
tp-merge |
Trộn hai mảng | ⭐ | Merge | Kỹ thuật hai con trỏ |
tp-maxlen |
Đoạn con dài nhất | ⭐ | Sliding window | Kỹ thuật hai con trỏ |
tp-same |
Phần tử trùng | ⭐ | Two pointers | Kỹ thuật hai con trỏ |
tp-diff |
Cặp hiệu X | ⭐⭐ | Two pointers | Kỹ thuật hai con trỏ |
tp-subsum |
Đoạn tổng S | ⭐⭐ | Sliding window | Kỹ thuật hai con trỏ |
tp-three |
3Sum | ⭐⭐ | Two pointers + sort | Kỹ thuật hai con trỏ |
tp-cntpair |
Đếm cặp tổng ≤ X | ⭐⭐ | Two pointers | Kỹ thuật hai con trỏ |
tp-trap |
Hứng nước | ⭐⭐⭐ | Two pointers | Kỹ thuật hai con trỏ |
tp-subk |
Đoạn con K phần tử khác | ⭐⭐⭐ | Sliding window | Kỹ thuật hai con trỏ |
tp-closest |
3 tổng gần nhất | ⭐⭐⭐ | Two pointers + sort | Kỹ thuật hai con trỏ |
tp-ksum |
4Sum | ⭐⭐⭐ | Two pointers + sort | Kỹ thuật hai con trỏ |
🟢 1j. Nhóm Chia đôi tập (Meet in the Middle)¶
Xử lý bài toán tập con với N ≤ 40 bằng cách chia đôi, sinh tổ hợp từng nửa và ghép kết quả.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
mitm-subset-x |
Đếm tập con tổng X | ⭐⭐ | Chia đôi tập | Meet in the Middle |
mitm-closest |
Tập con gần X nhất | ⭐⭐ | Chia đôi tập | Meet in the Middle |
mitm-range |
Tập con tổng trong [L, R] | ⭐⭐ | Chia đôi tập | Meet in the Middle |
mitm-knap |
Cái túi - Meet in the Middle | ⭐⭐⭐ | Knapsack | Meet in the Middle |
mitm-balanced |
Chia kẹo | ⭐⭐⭐ | Chia tập | Meet in the Middle |
🟢 1k. Nhóm Rời rạc hoá (Discretization)¶
Thu nhỏ miền giá trị, nén tọa độ, ứng dụng cho bài toán đếm và sweep line.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
disc-basic |
Rời rạc hoá mảng | ⭐ | Nén cơ bản | Rời rạc hoá |
disc-freq |
Tần số giá trị | ⭐ | Nén + đếm | Rời rạc hoá |
disc-distinct |
Số lượng giá trị khác nhau | ⭐ | Nén + đếm | Rời rạc hoá |
disc-closest |
Số lớn hơn X gần nhất | ⭐ | Nén + TKNP | Rời rạc hoá |
disc-pair |
Cặp số bằng nhau | ⭐ | Nén + tổ hợp | Rời rạc hoá |
disc-range-freq |
Truy vấn tần số trong đoạn | ⭐⭐ | Nén + prefix | Rời rạc hoá |
disc-sweep |
Đoạn phủ dày nhất | ⭐⭐ | Nén + diff array | Rời rạc hoá |
🟢 1l. Nhóm Linked List (Danh sách liên kết)¶
Thao tác cơ bản, đảo ngược, phát hiện chu trình, gộp danh sách, Two pointers.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
ll-basic |
Danh sách liên kết cơ bản | ⭐ | Thao tác cơ bản | Linked List |
ll-search |
Tìm kiếm trong danh sách | ⭐ | Duyệt tuyến tính | Linked List |
ll-reverse |
Đảo ngược danh sách | ⭐⭐ | Đảo ngược con trỏ | Linked List |
ll-merge |
Gộp hai danh sách | ⭐⭐ | Merge có thứ tự | Linked List |
ll-middle |
Phần tử ở giữa | ⭐⭐ | Two pointers slow/fast | Linked List |
ll-remove-nth |
Xóa phần tử thứ N từ cuối | ⭐⭐ | Two pointers | Linked List |
ll-cycle |
Phát hiện chu trình | ⭐⭐⭐ | Floyd's cycle detection | Linked List |
ll-josephus |
Josephus Problem | ⭐⭐⭐ | Linked list vòng tròn | Linked List |
🟢 1m. Nhóm Queue — Hàng đợi (Queue)¶
Queue cơ bản, mô phỏng, sliding window, deque đơn điệu, BFS ứng dụng.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
q-basic |
Queue cơ bản | ⭐ | Enqueue, dequeue, front, back | Queue |
q-generate |
Sinh số nhị phân | ⭐ | BFS với queue | Queue |
q-sim |
Mô phỏng hàng chờ | ⭐⭐ | Mô phỏng | Queue |
q-interleave |
Xen kẽ queue | ⭐⭐ | Thao tác queue | Queue |
q-rotate |
Xoay hàng đợi | ⭐⭐ | Xoay vòng | Queue |
q-reversal |
Đảo K phần tử đầu | ⭐⭐ | Stack + Queue | Queue |
q-josephus |
Josephus với Queue | ⭐⭐ | Mô phỏng vòng tròn | Queue |
q-card |
Trò chơi đánh bài | ⭐⭐ | Mô phỏng | Queue |
q-sliding-sum |
Tổng cửa sổ trượt | ⭐⭐ | Sliding window | Queue |
q-first-neg |
Số âm đầu tiên trong cửa sổ | ⭐⭐⭐ | Sliding window | Queue |
q-queue-stack |
Queue bằng hai Stack | ⭐⭐⭐ | Amortized O(1) | Queue |
q-topo |
Thứ tự topo | ⭐⭐⭐ | BFS + in-degree | Queue |
q-sliding-max |
Cửa sổ trượt lớn nhất | ⭐⭐⭐⭐ | Deque đơn điệu | Queue |
q-first-unique |
Ký tự đầu tiên không lặp | ⭐⭐⭐⭐ | Queue + đếm tần số | Queue |
q-circular-deque |
Hàng đợi hai đầu vòng | ⭐⭐⭐⭐ | Circular deque | Queue |
🟢 1n. Nhóm Deque & Sliding Window (Hàng đợi hai đầu & Cửa sổ trượt)¶
Deque cơ bản, Deque đơn điệu, cửa sổ trượt max/min/sum, chênh lệch giới hạn, đoạn con không lặp.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
dq-basic |
Mô phỏng Deque Cơ Bản | ⭐ | Thao tác push/pop đầu cuối | Deque & Sliding Window |
dq-sliding-max |
Cửa Sổ Trượt Lớn Nhất | ⭐⭐ | Deque đơn điệu giảm dần | Deque & Sliding Window |
dq-sliding-min |
Cửa Sổ Trượt Nhỏ Nhất | ⭐⭐ | Deque đơn điệu tăng dần | Deque & Sliding Window |
dq-sliding-sum |
Tổng Cửa Sổ Trượt | ⭐⭐ | Cửa sổ trượt cơ bản | Deque & Sliding Window |
dq-first-neg |
Số Âm Đầu Tiên Trong Cửa Sổ | ⭐⭐ | Cửa sổ trượt & Deque | Deque & Sliding Window |
dq-longest-distinct |
Đoạn Con Không Trùng Lặp Dài Nhất | ⭐⭐⭐ | Sliding Window & Map/Set | Deque & Sliding Window |
dq-max-min-sum |
Tổng Max Min Của Cửa Sổ | ⭐⭐⭐ | Song song hai Deque | Deque & Sliding Window |
dq-diff-limit |
Chênh Lệch Giới Hạn | ⭐⭐⭐ | Sliding Window & hai Deque | Deque & Sliding Window |
🟢 1o. Nhóm Heap — Hàng đợi ưu tiên (Priority Queue)¶
Heap cơ bản, K phần tử lớn nhất/nhỏ nhất, Median, Dijkstra, Ugly number, Sliding window median, Task scheduler.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
heap-basic |
Heap cơ bản | ⭐ | Heap cơ bản | Heap |
heap-kth-min |
Phần tử nhỏ thứ K | ⭐⭐ | Min-heap | Heap |
heap-top-k |
K phần tử lớn nhất | ⭐⭐ | Max-heap | Heap |
heap-median |
Median trong luồng | ⭐⭐⭐ | 2 heaps | Heap |
heap-merge-sorted |
Gộp K dãy đã sắp xếp | ⭐⭐⭐ | Min-heap | Heap |
heap-k-closest |
K điểm gần gốc nhất | ⭐⭐⭐ | Max-heap | Heap |
heap-k-sum |
Tổng lớn nhất K cặp | ⭐⭐⭐ | Min-heap + sort | Heap |
heap-nearly-sorted |
Sắp xếp mảng gần đúng | ⭐⭐⭐ | Min-heap | Heap |
heap-reorganize |
Sắp xếp lại xâu | ⭐⭐⭐ | Max-heap | Heap |
heap-task-scheduler |
Lập lịch tác vụ | ⭐⭐⭐ | Max-heap | Heap |
heap-ugly-number |
Số ugly thứ N | ⭐⭐⭐ | Min-heap | Heap |
heap-dijkstra |
Đường đi ngắn nhất | ⭐⭐⭐ | Dijkstra | Heap |
heap-sliding-median |
Median cửa sổ trượt | ⭐⭐⭐ | 2 multisets | Heap |
heap-min-rooms |
Tối thiểu phòng họp | ⭐⭐⭐ | Min-heap + sort | Heap |
heap-kth-stream |
Phần tử lớn thứ K trong luồng | ⭐⭐⭐ | Min-heap | Heap |
🟢 1p. Nhóm DSU (Disjoint Set Union)¶
Gộp tập hợp, kiểm tra cùng tập, Kruskal, DSU mở rộng, offline.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
dsu-basic |
Gộp tập hợp cơ bản | ⭐ | DSU cơ bản | DSU |
dsu-size |
Kích thước tập hợp | ⭐ | DSU + size | DSU |
dsu-cycle |
Phát hiện chu trình | ⭐ | DSU + cycle | DSU |
dsu-components |
Số thành phần liên thông | ⭐ | DSU + components | DSU |
dsu-same |
Quan hệ tương đương | ⭐ | DSU + query | DSU |
dsu-query-size |
Truy vấn kích thước | ⭐⭐ | DSU + size + query | DSU |
dsu-kruskal |
Cây khung nhỏ nhất | ⭐⭐ | Kruskal MST | DSU |
dsu-max-size |
Nhóm bạn lớn nhất | ⭐⭐ | DSU + max size | DSU |
dsu-enemies |
Bạn và thù | ⭐⭐⭐ | DSU mở rộng | DSU |
dsu-offline |
Xoá cạnh (offline) | ⭐⭐⭐ | DSU offline | DSU |
🟢 1q. Nhóm DSU Rollback (Gộp tập hợp có hoàn tác)¶
DSU Rollback, D&C trên thời gian, đồ thị động, persistent DSU.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
dsur-basic |
Rollback cơ bản | ⭐⭐ | DSU Rollback | DSU Rollback |
dsur-sum |
Tổng nhóm có rollback | ⭐⭐ | DSU + sum | DSU Rollback |
dsur-timeline |
Dòng thời gian | ⭐⭐⭐ | D&C + DSU Rollback | DSU Rollback |
dsur-online |
Đồ thị động | ⭐⭐⭐ | Segment Tree + DSU | DSU Rollback |
dsur-persistence |
Lưu trữ trạng thái | ⭐⭐⭐ | Persistent DSU | DSU Rollback |
dsur-connect |
Số vùng kết nối | ⭐⭐⭐ | DSU + components | DSU Rollback |
dsur-bipartite |
Đồ thị hai phía động | ⭐⭐⭐⭐ | DSU parity | DSU Rollback |
dsur-mst |
Cây khung động | ⭐⭐⭐⭐⭐ | Dynamic MST | DSU Rollback |
🟢 1r. Nhóm Trie (Cây tiền tố)¶
Thêm/tìm kiếm xâu, đếm tiền tố, Bitwise Trie XOR, Autocomplete, Trie kết hợp quy hoạch động.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
trie-insert-search |
Tập Từ Vựng Cây Tiền Tố | ⭐ | Thao tác Trie cơ bản | Trie |
trie-prefix-count |
Đếm Tần Suất Tiền Tố | ⭐⭐ | Đếm tiền tố xâu | Trie |
trie-longest-prefix |
Tiền Tố Chung Dài Nhất | ⭐⭐ | So khớp tiền tố dài nhất | Trie |
trie-xor-max |
Cặp XOR Lớn Nhất | ⭐⭐⭐ | Bitwise Trie XOR lớn nhất | Trie |
trie-xor-min |
Cặp XOR Nhỏ Nhất | ⭐⭐⭐ | Bitwise Trie XOR nhỏ nhất | Trie |
trie-autocomplete |
Gợi Ý Từ Khóa Autocomplete | ⭐⭐⭐ | Trie lưu giá trị tối ưu | Trie |
trie-xor-limit |
Cặp XOR Giới Hạn | ⭐⭐⭐⭐ | Bitwise Trie đếm số cặp | Trie |
trie-word-break |
Phân Tách Từ | ⭐⭐⭐⭐ | Trie + Quy hoạch động | Trie |
🟢 1s. Nhóm Segment Tree (Cây phân đoạn)¶
Truy vấn tổng/min/max/gcd, Lazy Propagation, đoạn con lớn nhất, Persistent Segment Tree.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
st-sum-query |
Truy Vấn Tổng Đoạn | ⭐ | Segment Tree tính tổng cơ bản | Segment Tree |
st-min-query |
Truy Vấn Nhỏ Nhất Đoạn | ⭐⭐ | Segment Tree tìm cực tiểu | Segment Tree |
st-max-query |
Truy Vấn Lớn Nhất Đoạn | ⭐⭐ | Segment Tree tìm cực đại | Segment Tree |
st-gcd-query |
Truy Vấn Ước Chung Lớn Nhất | ⭐⭐ | Segment Tree tìm GCD | Segment Tree |
st-count-min |
Tìm Min Và Đếm Tần Suất | ⭐⭐ | Lưu thông tin phức hợp tại mỗi node | Segment Tree |
st-kth-zero |
Tìm Số Không Thứ K | ⭐⭐⭐ | Đi trên cây Segment Tree (Binary Search) | Segment Tree |
st-inverse-count |
Đếm Số Cặp Nghịch Thế | ⭐⭐⭐ | Ứng dụng Segment Tree đếm xuôi | Segment Tree |
st-range-add |
Cập Nhật Đoạn Cộng Giá Trị | ⭐⭐⭐ | Lazy Propagation cộng đoạn, truy vấn điểm | Segment Tree |
st-range-sum |
Cộng Đoạn Và Tính Tổng | ⭐⭐⭐ | Lazy Propagation đầy đủ (cộng & tính tổng) | Segment Tree |
st-range-min |
Cộng Đoạn Và Tìm Nhỏ Nhất | ⭐⭐⭐ | Lazy Propagation cộng & tìm cực tiểu | Segment Tree |
st-range-set |
Gán Đoạn Và Tính Tổng | ⭐⭐⭐ | Lazy Propagation gán trị & tính tổng | Segment Tree |
st-range-set-min |
Gán Đoạn Và Tìm Nhỏ Nhất | ⭐⭐⭐ | Lazy Propagation gán trị & tìm cực tiểu | Segment Tree |
st-distinct-cnt |
Đếm Giá Trị Phân Biệt Đoạn | ⭐⭐⭐ | Kết hợp Offline Queries & Segment Tree | Segment Tree |
st-max-subarray |
Đoạn Con Tổng Lớn Nhất | ⭐⭐⭐⭐ | Quản lý tiền tố, hậu tố cực đại tại mỗi node | Segment Tree |
st-persistent-kth |
Tìm Phần Tử Nhỏ Thứ K | ⭐⭐⭐⭐ | Cây phân đoạn bền vững (Persistent Segment Tree) | Segment Tree |
🟢 1t. Nhóm Segment Tree nâng cao (Cải tiến)¶
Nhân cộng đoạn lồng nhau, Dynamic Segment Tree, gộp cây phân đoạn, Heavy-Light Decomposition (HLD) trên cây, Segment Tree Beats.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
st-range-mul-add |
Cộng Nhân Đoạn Tính Tổng | ⭐⭐⭐ | Quản lý đồng thời 2 nhãn lười | Cải tiến Segment Tree |
st-dynamic |
Cây Phân Đoạn Động | ⭐⭐⭐ | Cấp phát động node | Cải tiến Segment Tree |
st-tree-path |
Cập Nhật Đường Đi Trên Cây | ⭐⭐⭐⭐ | HLD + Segment Tree | Cải tiến Segment Tree |
st-sweepline-area |
Hợp Diện Tích Hình Chữ Nhật | ⭐⭐⭐⭐ | Sweep Line quét dọc | Cải tiến Segment Tree |
st-2d-basic |
Cập Nhật Điểm Tổng Ma Trận Con | ⭐⭐⭐⭐ | Segment Tree 2 chiều | Cải tiến Segment Tree |
st-persistent-sum |
Tổng Đoạn Trên Lịch Sử | ⭐⭐⭐⭐ | Persistent Segment Tree | Cải tiến Segment Tree |
st-merge |
Tần Suất Màu Sắc Cây Con | ⭐⭐⭐⭐ | Segment Tree Merging | Cải tiến Segment Tree |
st-range-chmin |
Chmin Đoạn Và Tính Tổng | ⭐⭐⭐⭐⭐ | Segment Tree Beats | Cải tiến Segment Tree |
🟢 1u. Nhóm Fenwick Tree (BIT)¶
Cập nhật điểm tính tổng, cập nhật đoạn truy vấn điểm, cập nhật đoạn tính tổng đoạn, đếm cặp nghịch thế, BIT 2D, Binary Lifting trên BIT.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
bit-point-add |
Cộng Điểm Tính Tổng | ⭐⭐ | Point Update, Range Query cơ bản | Fenwick Tree (BIT) |
bit-range-add |
Cộng Đoạn Truy Vấn Điểm | ⭐⭐ | Range Update, Point Query (Mảng hiệu) | Fenwick Tree (BIT) |
bit-range-sum |
Cộng Đoạn Tính Tổng Đoạn | ⭐⭐⭐ | Cập nhật đoạn, tính tổng đoạn (2 BIT) | Fenwick Tree (BIT) |
bit-inv-cnt |
Đếm Cặp Nghịch Thế | ⭐⭐⭐ | Ứng dụng đếm số cặp nghịch thế | Fenwick Tree (BIT) |
bit-salary |
Quản Lý Mức Lương | ⭐⭐⭐ | BIT + Nén tọa độ | Fenwick Tree (BIT) |
bit-distinct |
Số Màu Sắc Phân Biệt | ⭐⭐⭐ | Offline Queries + BIT (Quét phải) | Fenwick Tree (BIT) |
bit-prefix-max |
Giá Cổ Phiếu Lớn Nhất | ⭐⭐⭐ | Point Update, Prefix Max Query | Fenwick Tree (BIT) |
bit-kth-small |
Tìm Điểm Nhỏ Thứ K | ⭐⭐⭐⭐ | Binary Lifting trên BIT | Fenwick Tree (BIT) |
bit-2d-point |
Đếm Cây Nông Trại 2D | ⭐⭐⭐⭐ | 2D Fenwick Tree cơ bản | Fenwick Tree (BIT) |
bit-2d-range |
Điều Khiển LED 2D | ⭐⭐⭐⭐ | 2D Fenwick Tree range update | Fenwick Tree (BIT) |
bit-lex-min |
Hoán Vị Nhỏ Nhất Từ Điển | ⭐⭐⭐⭐ | Tham lam + BIT đếm dịch chuyển | Fenwick Tree (BIT) |
bit-nested |
Đếm Đoạn Thẳng Bao Nhau | ⭐⭐⭐⭐ | Sorting + BIT đếm đoạn bao | Fenwick Tree (BIT) |
🟢 1v. Nhóm BIT 2D¶
Cập nhật điểm tính tổng, cập nhật đoạn truy vấn điểm, cập nhật đoạn tính tổng đoạn 2D, BIT 2D trên XOR, rời rạc hóa tọa độ + BIT 2D, sweep-line + BIT 2D.
| Mã bài | Tên bài tập | Độ khó | Kiểu bài tập (Bản chất) | Bài học lý thuyết |
|---|---|---|---|---|
b2d-point-add |
Cập Nhật Điểm Tổng Lưới | ⭐⭐ | Point Update, Range Query cơ bản | BIT 2D |
b2d-range-add |
Cộng Đoạn Lưới Truy Vấn Điểm | ⭐⭐ | Range Update, Point Query (Mảng hiệu 2D) | BIT 2D |
b2d-rect-xor |
Tổng XOR Vùng Hình Chữ Nhật | ⭐⭐⭐ | 2D BIT trên phép toán XOR tự nghịch đảo | BIT 2D |
b2d-invert |
Lật Bóng Đèn Ma Trận | ⭐⭐⭐ | Đảo trạng thái + Đếm tổng vùng | BIT 2D |
b2d-range-sum |
Cộng Đoạn Lưới Tính Tổng | ⭐⭐⭐⭐ | Range Update 2D, Range Query 2D (4 BIT 2D) | BIT 2D |
b2d-max-subgrid |
Tổng Lưới Con Lớn Nhất | ⭐⭐⭐⭐ | BIT 2D + Duyệt max lưới con cố định | BIT 2D |
b2d-coord-comp |
Ngôi Sao Trên Bầu Trời | ⭐⭐⭐⭐ | Rời rạc hóa tọa độ + BIT 2D | BIT 2D |
b2d-nested-rect |
Khung Tranh Bao Nhau | ⭐⭐⭐⭐ | Sorting (Sweep-line) + BIT 2D | BIT 2D |