cpp-143Bước 1Trung bình
Sinh Toàn Bộ Hoán Vị Theo Thứ Tự Từ Điển
Cho số nguyên dương N. Hãy liệt kê tất cả các hoán vị của tập hợp {1, 2, …, N} theo thứ tự từ điển tăng dần.
CHUYÊN ĐỀ C++ THỰC CHIẾN
Bài tập Tìm kiếm nhị phân & Chặt nhị phân kết quả trong C++
Giảm thời gian tìm kiếm từ O(N) xuống O(log N). Kỹ thuật chặt nhị phân kết quả là công cụ cực mạnh để giải quyết các bài toán tối ưu hóa phức tạp.
15
bài tập có chấm code
Bài tập theo chuyên đề, có đề bài, ví dụ và starter code riêng.
0
cơ bản
Củng cố nền tảng và làm quen với kỹ thuật cốt lõi.
12
trung bình
Kết hợp nhiều bước suy luận để vận dụng kiến thức.
3
nâng cao
Thử thách tối ưu, cấu trúc dữ liệu và thuật toán chuyên sâu.
Lộ trình thực hành đề xuất
Bước 1
Cài đặt Binary Search
Cài đặt chính xác không bị lặp vô tận, kiểm tra mảng sắp xếp.
Bước 2
Hàm STL lower/upper_bound
Tìm vị trí đầu tiên hoặc cuối cùng của phần tử thỏa mãn điều kiện.
Bước 3
Chặt nhị phân kết quả
Kiểm tra tính đơn điệu của hàm điều kiện f(x) để tìm nghiệm tối ưu.
Lỗi thường gặp & Cách phòng tránh
•
Tính (low + high) / 2 có thể gây tràn số nguyên (cần viết low + (high - low) / 2).
•
Điều kiện dừng low <= high bị lặp vô hạn do cập nhật mid thay vì mid + 1 / mid - 1.
Danh sách bài tập thực hành (15 bài)
Trong mỗi mức độ, bài tập được xếp từ dễ nhất đến khó nhất — hãy đi theo số bước.
Trung bình 12 bài
Vận dụng
Dùng một kỹ thuật quen thuộc: sắp xếp, tìm kiếm, đếm, ngăn xếp.
cpp-249Bước 2Trung bình
Tìm kiếm nhị phân trên mảng đã sắp xếp
Tìm kiếm tuyến tính quét cả mảng nên tốn O(N). Với dữ liệu đã sắp xếp, mỗi bước loại được một nửa không gian tìm kiếm và đưa chi phí xuống O(log N).
cpp-146Bước 3Trung bình
Chặt Nhị Phân Kết Quả - Đốn Gỗ Tối Ưu (EKO Woodcutters)
Một người đốn gỗ cần thu hoạch ít nhất M mét gỗ từ một hàng gồm N cây gỗ có chiều cao lần lượt là H1, H2, …, HN.
cpp-147Bước 4Trung bình
Chặt Nhị Phân Kết Quả - Xếp Bò Vào Chuồng (Aggressive Cows)
Người nông dân có N chuồng bò nằm trên một trục thẳng tại các tọa độ X1, X2, …, XN. Anh ta cần đưa C con bò vào C chuồng khác nhau sao cho khoảng cách giữa hai con bò gần nh…
cpp-148Bước 5Trung bình
Phân Hoạch Thợ Sơn Tường (Painter's Partition / Book Allocation)
Có N tấm bảng được xếp thành một hàng, tấm thứ i có độ dài Li. Có K người thợ sơn cần sơn toàn bộ N tấm bảng này.
cpp-149Bước 6Trung bình
Tìm Phần Tử Nhỏ Thứ K Trong Bảng Cửu Chương (K-th Smallest)
Cho một bảng cửu chương kích thước M × N, trong đó giá trị tại hàng i và cột j (1 ≤ i ≤ M, 1 ≤ j ≤ N) là i · j.
Kết hợp kỹ thuật
Phối hợp hai kỹ thuật trong cùng một lời giải.
cpp-086Bước 7Trung bình
Thuật toán Quickselect: Tìm phần tử thứ K trong thời gian O(N)
Cho một mảng gồm N số nguyên A1, A2, …, AN và một số nguyên K (1 ≤ K ≤ N). Hãy tìm giá trị của phần tử sẽ đứng ở vị trí thứ K nếu mảng được sắp xếp theo thứ tự không giả…
cpp-144Bước 8Trung bình
Đếm Số Cặp Nghịch Thế Bằng Merge Sort (Inversion Count)
Cho một dãy gồm N số nguyên A1, A2, …, AN.
cpp-142Bước 9Trung bình
Giải Ô Số Sudoku Bằng Quay Lui (Sudoku Solver)
Cho một bảng Sudoku kích thước 9 × 9, trong đó các ô trống được biểu diễn bằng số 0.
cpp-203Bước 10Trung bình
Tìm Kiếm Nhị Phân Trên Mảng Đã Sắp Xếp
Tìm kiếm nhị phân (Binary Search) là một trong những thuật toán cơ bản và hiệu quả nhất trong lập trình thuật toán. Thuật toán hoạt động theo nguyên lý chia để trị (Divide and Conq…
cpp-013Bước 11Trung bình
Chặt nhị phân kết quả phân bổ gói tài nguyên
Trung tâm siêu máy tính AI Empire Academy có N gói tác vụ huấn luyện mô hình ngôn ngữ xếp thành một hàng dài, gói thứ i có khối lượng tính toán là Ai (1 ≤ N ≤ 105, 1 ≤ Ai…
cpp-015Bước 12Trung bình
Quay lui sinh hoán vị không có hai số chẵn liền kề
Hệ thống lên lịch thực thi song song của AI Empire Academy cần lập lịch chạy N tác vụ được đánh số từ 1 đến N (1 ≤ N ≤ 9).
Nâng cao 3 bài
cpp-090Bước 1Nâng cao
Tìm trung vị của hai mảng đã sắp xếp trong O(log(min(M, N)))
Cho hai mảng đã sắp xếp tăng dần A (gồm N phần tử) và B (gồm M phần tử). Hãy tìm giá trị trung vị của mảng hợp nhất A ∪ B.
cpp-145Bước 2Nâng cao
Tìm Trung Vị Của Hai Mảng Đã Sắp Xếp (Median of Two Sorted Arrays)
Cho hai mảng số nguyên A và B đã được sắp xếp theo thứ tự tăng dần, kích thước lần lượt là N và M.
cpp-141Bước 3Nâng cao
Bài Toán N Quân Hậu Tối Ưu Bằng Bitmask (N-Queens)
Cho một bàn cờ vua kích thước N × N. Bạn cần đặt N quân hậu lên bàn cờ sao cho không có hai quân hậu nào tấn công lẫn nhau (tức là không có hai quân hậu nào cùng hàng, cùng cộ…