cpp-135Bước 1Trung bình
Mô Phỏng Hàng Đợi Hai Đầu (Double-Ended Queue - Deque)
Hãy cài đặt một hàng đợi hai đầu (Deque) hỗ trợ các thao tác sau:
CHUYÊN ĐỀ C++ THỰC CHIẾN
Bài tập Cấu trúc dữ liệu & Thư viện chuẩn STL C++
Khai thác tối đa sức mạnh của C++ Standard Template Library để code ngắn gọn, chuẩn xác và đạt hiệu năng tối ưu nhất trong mọi kỳ thi.
14
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.
2
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
Vector & Pair
Mảng động tự co giãn, sắp xếp với std::sort và comparator tùy biến.
Bước 2
Ngăn xếp (Stack)
Ứng dụng stack giải bài toán dấu ngoặc hợp lệ, tính biểu thức hậu tố và phần tử lớn hơn tiếp theo.
Bước 3
Hàng đợi & Priority Queue
Queue cho duyệt BFS và hàng đợi ưu tiên cho bài toán chọn phần tử cực trị liên tục.
Bước 4
Set & Map
Cây đỏ đen std::set/std::map O(log N) và bảng băm std::unordered_map O(1).
Lỗi thường gặp & Cách phòng tránh
•
Gọi top() hoặc pop() trên stack/queue rỗng gây lỗi Segment Fault (SIGSEGV).
•
Sử dụng unordered_map không an toàn trong thi đấu dễ bị hack hash gây TLE O(N^2).
Danh sách bài tập thực hành (14 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-012Bước 2Trung bình
Đếm số cặp có tổng bằng S bằng Bảng băm
Hệ thống cân bằng tải truyền thông của AI Empire Academy tiếp nhận N gói tín hiệu với cường độ A1, A2, …, AN (1 ≤ N ≤ 105, -109 ≤ Ai ≤ 109).
cpp-137Bước 3Trung bình
Kiểm Tra Dấu Ngoặc Hợp Lệ Nhiều Loại (Valid Parentheses)
Cho một chuỗi ký tự S chỉ gồm các dấu ngoặc: '(', ')', '[', ']', '{', '}'.
cpp-138Bước 4Trung bình
Hợp Nhất Hai Danh Sách Đã Sắp Xếp (Merge Two Sorted Lists)
Cho hai danh sách số nguyên đã được sắp xếp theo thứ tự không giảm:
cpp-136Bước 5Trung bình
Đánh Giá Biểu Thức Hậu Tố Ba Lan (Reverse Polish Notation)
Cho một biểu thức toán học dưới dạng ký pháp Ba Lan ngược (Reverse Polish Notation - RPN) gồm N thẻ (tokens). Mỗi token là một số nguyên hoặc một trong 4 toán tử cơ bản: +, -, *, /…
cpp-139Bước 6Trung bình
Tìm Điểm Giao Của Hai Danh Sách Liên Kết (Intersection of Two Lists)
Hai danh sách liên kết A và B có thể hợp nhất tại một nút chung X, sau đó tiếp tục đi chung một đoạn đuôi đến hết danh sách (hình dạng chữ Y).
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-140Bước 7Trung bình
Phát Hiện Chu Trình Trong Danh Sách (Thuật Toán Rùa và Thỏ Floyd)
Cho một danh sách liên kết gồm N nút (được đánh số thứ tự từ 0 đến N - 1). Mỗi nút i trỏ đến nút kế tiếp next[i].
cpp-087Bước 8Trung bình
Cài đặt bộ nhớ đệm LRU Cache: Danh sách liên kết kép kết hợp Bảng băm
Cài đặt bộ nhớ đệm LRU có sức chứa C. Bạn cần xử lý Q truy vấn thuộc 2 loại:
cpp-099Bước 9Trung bình
Gộp K danh sách đã sắp xếp: Hàng đợi ưu tiên Min-Heap O(N log K)
Cho K dãy số nguyên đã được sắp xếp tăng dần. Hãy gộp tất cả K dãy này thành một dãy số duy nhất được sắp xếp tăng dần.
cpp-009Bước 10Trung bình
Kiểm tra biểu thức dấu ngoặc hợp lệ
Bộ tiền xử lý cú pháp của trình biên dịch ngôn ngữ truy vấn AI tại AI Empire Academy cần kiểm tra xem một chuỗi biểu thức S chỉ gồm các ký tự mở ngoặc (, [, { và đóng ngoặc ), ], }…
cpp-010Bước 11Trung bình
Hàng đợi ưu tiên duy trì Top K phần tử lớn nhất
Hệ thống chấm thi trực tuyến của AI Empire Academy cần theo dõi ngưỡng điểm để lọt vào Top K thí sinh dẫn đầu trong suốt quá trình diễn ra kỳ thi (1 ≤ K ≤ 104).
cpp-014Bước 12Trung bình
Ngăn xếp đơn điệu tìm phần tử lớn hơn đầu tiên bên phải
Hệ thống cảm biến đo đạc địa hình thực tế ảo của AI Empire Academy thu thập độ cao của N trạm radar đặt thẳng hàng từ trái sang phải: H1, H2, …, HN (1 ≤ N ≤ 2 · 105…
Nâng cao 2 bài
cpp-095Bước 1Nâng cao
Hình chữ nhật lớn nhất trong biểu đồ cột: Ngăn xếp đơn điệu O(N)
Cho một biểu đồ cột gồm N cột liền kề có độ rộng mỗi cột bằng 1. Chiều cao của cột thứ i là số nguyên không âm Hi. Hãy tìm diện tích của hình chữ nhật lớn nhất có thể vẽ được bên…
cpp-011Bước 2Nâng cao
Quản lý đa tập hợp số nguyên động
Hệ thống sàn giao dịch thẻ bài huấn luyện AI của AI Empire Academy quản lý một kho dữ liệu chứa các giá trị sức mạnh của các thẻ bài. Kho dữ liệu bắt đầu với trạng thái rỗng.