cpp-276Bước 1Cơ bản
Trung bình cộng của mảng
Trung bình cộng là chỉ số thống kê cơ bản nhất, nhưng cũng là nơi hay sai định dạng đầu ra và sai kiểu phép chia. Trong C++, fixed và setprecision kiểm soát số chữ số thập phân.
CHUYÊN ĐỀ C++ THỰC CHIẾN
Bài tập Mảng & Các kỹ thuật xử lý mảng tối ưu trong C++
Mảng là cấu trúc dữ liệu nền tảng nhất. Luyện tập các kỹ thuật tinh tế giúp giải quyết bài toán mảng lớn trong thời gian giới hạn 1 giây của hệ thống chấm bài.
26
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.
10
cơ bản
Củng cố nền tảng và làm quen với kỹ thuật cốt lõi.
15
trung bình
Kết hợp nhiều bước suy luận để vận dụng kiến thức.
1
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
Thao tác mảng căn bản
Nhập xuất mảng, tìm min/max, đếm phần tử thỏa mãn và chèn/xóa phần tử.
Bước 2
Mảng cộng dồn 1D & 2D
Xây dựng prefix sum giải bài toán tính tổng đoạn [L, R] và tổng hình chữ nhật con trong O(1).
Bước 3
Kỹ thuật Hai con trỏ
Xử lý cặp số, hợp hai mảng đã sắp xếp và loại bỏ phần tử trùng lặp trong O(N).
Bước 4
Cửa sổ trượt (Sliding Window)
Tìm đoạn con dài nhất hoặc ngắn nhất thỏa mãn điều kiện tổng/phần tử phân biệt.
Lỗi thường gặp & Cách phòng tránh
•
Lỗi tràn bộ nhớ mảng tĩnh cục bộ trên stack (cần khai báo mảng kích thước lớn ở vùng toàn cục global).
•
Lỗi truy xuất ngoài biên mảng (Out of bounds) khi tính prefix[i] với chỉ số 0.
Danh sách bài tập thực hành (26 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 10 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-262Bước 2Cơ bản
Tổng các phần tử
In kết quả phép toán trong tên bài.
cpp-263Bước 3Cơ bản
Phần tử lớn nhất
In kết quả của điều kiện.
cpp-264Bước 4Cơ bản
Phần tử nhỏ nhất
In kết quả của điều kiện.
cpp-265Bước 5Cơ bản
Đếm phần tử chẵn
In kết quả duyệt mảng.
Làm quen
Vòng lặp, mảng một chiều, chuỗi và hàm ở mức cơ bản.
cpp-266Bước 6Cơ bản
Đếm phần tử dương
In kết quả duyệt mảng.
cpp-267Bước 7Cơ bản
Đảo ngược mảng
In kết quả duyệt mảng.
cpp-268Bước 8Cơ bản
Tìm vị trí đầu tiên
In kết quả duyệt mảng.
cpp-271Bước 9Cơ bản
Đếm số 0
In kết quả duyệt mảng.
cpp-274Bước 10Cơ bản
Đếm số âm
In kết quả duyệt mảng.
Trung bình 15 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-006Bước 1Trung bình
Phần tử xuất hiện nhiều nhất và lọc số dương
Hệ thống cảm biến phân tích hiệu năng của AI Empire thu thập một chuỗi gồm N số nguyên đo lường A1, A2, …, AN (1 ≤ N ≤ 105, -109 ≤ Ai ≤ 109).
cpp-129Bước 2Trung bình
Tìm Phần Tử Đa Số (Boyer-Moore Majority Vote Algorithm)
Cho một mảng gồm N số nguyên A1, A2, …, AN.
cpp-132Bước 3Trung bình
Thiết Lập Số Không Trên Ma Trận (Set Matrix Zeroes In-place)
Cho một ma trận A kích thước M × N.
cpp-272Bước 4Trung bình
Tổng đường chéo chính của ma trận
Đường chéo chính là tập ô (i, i) của ma trận vuông — dữ liệu của vết ma trận, dùng trong đại số tuyến tính và phân tích ma trận hiệp phương sai.
cpp-273Bước 5Trung bình
Chuyển vị ma trận
Chuyển vị đổi hàng thành cột. Thao tác này xuất hiện trong nhân ma trận, đổi hệ trục toạ độ và trong học máy khi đổi tensor từ (H, W, C) sang (C, H, W).
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-128Bước 6Trung bình
Xoay Mảng 1D Sang Phải K Vị Trí Tại Chỗ (Rotate Array In-place)
Cho một mảng gồm N số nguyên A1, A2, …, AN và số nguyên K.
cpp-131Bước 7Trung bình
Xoay Ma Trận Vuông 90 Độ Theo Chiều Kim Đồng Hồ Tại Chỗ
Cho một ma trận vuông A kích thước N × N.
cpp-134Bước 8Trung bình
Nhân Hai Ma Trận Vuông Modulo (Matrix Multiplication)
Cho hai ma trận vuông A và B kích thước N × N.
cpp-154Bước 9Trung bình
Tìm Điểm Yên Ngựa Trong Ma Trận (Matrix Saddle Point)
Cho một ma trận A kích thước M × N.
cpp-081Bước 10Trung bình
Mảng hiệu số: Cập nhật đoạn O(1) trên mảng 1D và 2D
Ban đầu có một dãy gồm N số 0 được đánh số từ 1 đến N. Bạn cần thực hiện Q thao tác cập nhật: mỗi thao tác cộng thêm V vào tất cả các phần tử từ chỉ số L đến R (1 ≤ L ≤ R ≤ N…
Thành thạo
Bài dài hơn, cần chọn đúng cấu trúc dữ liệu.
cpp-085Bước 11Trung bình
Cửa sổ trượt: Xâu con dài nhất không chứa ký tự lặp lại
Cho một xâu ký tự S gồm các ký tự ASCII in được (từ mã 32 đến 126). Hãy tìm độ dài của xâu con liên tiếp dài nhất trong S mà không chứa bất kỳ ký tự nào bị lặp lại.
cpp-089Bước 12Trung bình
Ma trận 2D: Xoay ma trận 90 độ tại chỗ và Duyệt xoắn ốc
1. Chuyển vị ma trận (Transpose): Hoán đổi M[i][j] với M[j][i] (i < j).
cpp-083Bước 13Trung bình
Kỹ thuật hai con trỏ: Đếm bộ ba và bộ bốn có tổng bằng K
Cho một dãy gồm N số nguyên A1, A2, …, AN và một số nguyên S. Hãy đếm số lượng bộ ba chỉ số (i, j, k) (1 ≤ i < j < k ≤ N) phân biệt sao cho:
cpp-084Bước 14Trung bình
Bài toán Hứng nước mưa: Kỹ thuật Hai con trỏ và Ngăn xếp đơn điệu
Cho N cột thẳng đứng có độ rộng bằng 1, chiều cao của các cột lần lượt là các số nguyên không âm H1, H2, …, HN. Sau một cơn mưa lớn, nước bị giữ lại giữa các cột.
cpp-007Bước 15Trung bình
Mảng cộng dồn và truy vấn đoạn con
Một máy chủ xử lý dữ liệu AI của AI Empire ghi nhận lượng gói tin xử lý trong N giây liên tiếp thành một dãy số nguyên không âm A1, A2, …, AN (0 ≤ Ai ≤ 109).
Nâng cao 1 bài
cpp-032Bước 1Nâng cao
Cửa sổ trượt Max bằng hàng đợi hai đầu đơn điệu Monotonic Deque
Hệ thống tiền xử lý chuỗi thời gian (time-series stream) cho mô hình Deep Learning tại AI Empire Academy cần trích xuất đặc trưng cực đại địa phương. Cho một mảng gồm N số nguyên A…