Giới thiệu
Tài liệu này ghi lại quá trình học tập các thuật toán cơ bản từ khóa học của AcWing, bao gồm các chủ đề chính như sắp xếp nhanh, tìm kiếm nhị phân, tổng tiền tố, phép toán bit và thuật toán hai con trỏ.
Sắp xếp nhanh (Quick Sort)
Bài toán 1: Sắp xếp cơ bản
#include <iostream>
using namespace std;
const int MAX_SIZE = 100010;
int arr[MAX_SIZE];
void quickSort(int data[], int start, int end) {
if (start >= end) return;
int pivot = data[(start + end) / 2];
int left = start - 1, right = end + 1;
while (left < right) {
do left++; while (data[left] < pivot);
do right--; while (data[right] > pivot);
if (left < right) {
swap(data[left], data[right]);
}
}
quickSort(data, start, right);
quickSort(data, right + 1, end);
}
int main() {
int count;
cin >> count;
for (int i = 0; i < count; i++) {
cin >> arr[i];
}
quickSort(arr, 0, count - 1);
for (int i = 0; i < count; i++) {
cout << arr[i] << " ";
}
return 0;
}
Các điểm cần lưu ý:
- Chọn phần tử giữa làm mốc để tránh trường hợp biên
- Sử dụng vòng lặp do-while nên cần điều chỉnh vị trí ban đầu của con trỏ
- Phân chia đệ quy cần chú ý các chỉ số sau khi chia
Bài toán 2: Tìm phần tử thứ K
#include <iostream>
using namespace std;
const int MAX_SIZE = 100010;
int numbers[MAX_SIZE];
void partitionSort(int nums[], int begin, int finish) {
if (begin >= finish) return;
int i = begin - 1, j = finish + 1;
int pivotValue = nums[(i + j) / 2];
while (i < j) {
do i++; while (nums[i] < pivotValue);
do j--; while (nums[j] > pivotValue);
if (i < j) swap(nums[i], nums[j]);
}
partitionSort(nums, begin, j);
partitionSort(nums, j + 1, finish);
}
int main() {
int size, target;
cin >> size >> target;
for (int i = 0; i < size; i++) {
cin >> numbers[i];
}
partitionSort(numbers, 0, size - 1);
cout << numbers[target - 1];
return 0;
}
Tìm kiếm nhị phân (Binary Search)
Bài toán 1: Ranh giới nguyên
#include <iostream>
using namespace std;
const int MAX_SIZE = 100010;
int sequence[MAX_SIZE];
int main() {
int length, queries;
cin >> length >> queries;
for (int i = 0; i < length; i++) {
cin >> sequence[i];
}
while (queries--) {
int target;
cin >> target;
// Ranh giới trái
int left = 0, right = length - 1;
while (left < right) {
int middle = (left + right) >> 1;
if (sequence[middle] >= target) {
right = middle;
} else {
left = middle + 1;
}
}
if (sequence[left] != target) {
cout << "-1 -1" << endl;
continue;
}
cout << left << " ";
// Ranh giới phải
left = 0, right = length - 1;
while (left < right) {
int middle = (left + right + 1) >> 1;
if (sequence[middle] <= target) {
left = middle;
} else {
right = middle - 1;
}
}
cout << left << endl;
}
return 0;
}
Bài toán 2: Số thực nhị phân
#include <iostream>
using namespace std;
int main() {
double value;
cin >> value;
double low = -10.0, high = 10.0;
while (high - low > 1e-8) {
double mid = (low + high) / 2.0;
if (mid * mid * mid >= value) {
high = mid;
} else {
low = mid;
}
}
printf("%.6f", low);
return 0;
}
Tổng tiền tố và Phép hiệu
Bài toán 1: Tổng đoạn
#include <iostream>
using namespace std;
const int MAX_SIZE = 100010;
int prefix[MAX_SIZE];
int main() {
int elements, operations;
cin >> elements >> operations;
for (int i = 1; i <= elements; i++) {
cin >> prefix[i];
prefix[i] += prefix[i - 1];
}
while (operations--) {
int start, end;
cin >> start >> end;
cout << prefix[end] - prefix[start - 1] << endl;
}
return 0;
}
Bài toán 2: Tổng ma trận con
#include <iostream>
using namespace std;
const int MAX_DIM = 1010;
int matrix[MAX_DIM][MAX_DIM];
int main() {
int rows, cols, queries;
cin >> rows >> cols >> queries;
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
cin >> matrix[i][j];
matrix[i][j] += matrix[i][j - 1];
}
}
while (queries--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int result = 0;
for (int i = x1; i <= x2; i++) {
result += matrix[i][y2] - matrix[i][y1 - 1];
}
cout << result << endl;
}
return 0;
}
Bài toán 3: Phép hiệu
#include <iostream>
using namespace std;
const int MAX_SIZE = 100010;
int original[MAX_SIZE];
int difference[MAX_SIZE];
int main() {
int size, updates;
cin >> size >> updates;
for (int i = 1; i <= size; i++) {
cin >> original[i];
difference[i] = original[i] - original[i - 1];
}
while (updates--) {
int left, right, increment;
cin >> left >> right >> increment;
difference[left] += increment;
difference[right + 1] -= increment;
}
for (int i = 1; i <= size; i++) {
original[i] = original[i - 1] + difference[i];
cout << original[i] << " ";
}
return 0;
}
Thuật toán hai con trỏ
Bài toán 1: Dãy con dài nhất không lặp
#include <iostream>
using namespace std;
const int MAX_SIZE = 100010;
int data[MAX_SIZE];
int counter[MAX_SIZE];
int main() {
int n;
cin >> n;
int maxLength = 0;
for (int i = 0, j = 0; i < n; i++) {
cin >> data[i];
counter[data[i]]++;
while (j <= i && counter[data[i]] > 1) {
counter[data[j]]--;
j++;
}
maxLength = max(maxLength, i - j + 1);
}
cout << maxLength;
return 0;
}
Bài toán 2: Tổng mục tiêu
Cách tiếp cận hai con trỏ:
#include <iostream>
using namespace std;
const int MAX_SIZE = 100010;
int arrayA[MAX_SIZE];
int arrayB[MAX_SIZE];
int main() {
int sizeA, sizeB, target;
cin >> sizeA >> sizeB >> target;
for (int i = 0; i < sizeA; i++) {
cin >> arrayA[i];
}
for (int i = 0; i < sizeB; i++) {
cin >> arrayB[i];
}
for (int i = 0, j = sizeB - 1; i < sizeA; i++) {
while (j >= 0 && arrayA[i] + arrayB[j] > target) {
j--;
}
if (arrayA[i] + arrayB[j] == target) {
cout << i << " " << j;
break;
}
}
return 0;
}
Bài toán 3: Kiểm tra dãy con
#include <iostream>
using namespace std;
const int MAX_SIZE = 100010;
int seqA[MAX_SIZE];
int seqB[MAX_SIZE];
int main() {
int lenA, lenB;
cin >> lenA >> lenB;
for (int i = 0; i < lenA; i++) {
cin >> seqA[i];
}
for (int i = 0; i < lenB; i++) {
cin >> seqB[i];
}
int ptrA = 0, ptrB = 0;
while (ptrA < lenA && ptrB < lenB) {
if (seqA[ptrA] == seqB[ptrB]) {
ptrA++;
}
ptrB++;
}
if (ptrA == lenA) {
cout << "Yes";
} else {
cout << "No";
}
return 0;
}
Toán tử bit
Bài toán 1: Đếm bit 1
#include <iostream>
using namespace std;
int extractLowestBit(int num) {
return num & (-num);
}
int main() {
int testCases;
cin >> testCases;
while (testCases--) {
int number;
cin >> number;
int count = 0;
while (number) {
number -= extractLowestBit(number);
count++;
}
cout << count << " ";
}
return 0;
}
Hàm extractLowestBit trả về giá trị của bit 1 thấp nhất trong biểu diễn nhị phân của số đó.