cpp-312Bước 1Cơ bản
Tìm vị trí xuất hiện đầu tiên của một giá trị
Dãy điểm kiểm tra được lưu theo đúng thứ tự chỗ ngồi trong lớp, nên dãy không được sắp
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.
22
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.
7
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 (22 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.
Cơ bản 7 bài
Khởi động
Nhập xuất, biến, rẽ nhánh và các bước suy luận đơn giản.
cpp-314Bước 2Cơ bản
Đếm số lần xuất hiện của một giá trị
Một giá trị có thể lặp lại nhiều lần trong dãy dữ liệu thô. Câu hỏi "giá trị này xuất hiện
cpp-318Bước 3Cơ bản
Sắp xếp dãy và in ra theo dấu phẩy
Dữ liệu thô thường được in lại theo thứ tự tăng dần để so sánh bằng mắt. Yêu cầu ở đây gồm
cpp-313Bước 4Cơ bản
Tìm kiếm nhị phân trên dãy đã sắp xếp
Dãy đã được sắp xếp tăng dần, nên ta không cần quét từng phần tử. Mỗi lần so sánh với phần
Làm quen
Vòng lặp, mảng một chiều, chuỗi và hàm ở mức cơ bản.
cpp-315Bước 5Cơ bản
Phần tử đầu tiên lớn hơn x trong dãy đã sắp xếp
Khi tra cứu ngưỡng trong một bảng đã sắp xếp, ta thường cần giá trị nhỏ nhất còn lớn hơn
cpp-316Bước 6Cơ bản
Đếm số cặp phần tử có tổng bằng s
Trong một dãy ngắn, câu hỏi "có bao nhiêu cặp số cộng lại đúng bằng một mốc cho trước"
cpp-317Bước 7Cơ bản
Số nguyên dương nhỏ nhất còn thiếu trong dãy
Khi cấp phát số thứ tự cho một tập dữ liệu nhỏ, ta muốn tìm số thứ tự còn trống đầu tiên để
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-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.
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ộ…
