Lưu ý thông thường
Lựa chọn ngôn ngữ và phiên bản đánh giá
- Đạt 100 điểm: Không có lỗi nào.
- Lỗi cú pháp: Điểm bằng 0 nếu không qua được trường hợp kiểm thử nào.
- Qua một số trường hợp kiểm thử: Điểm nhỏ hơn 100.
- Lỗi chạy chương trình, điểm bằng 0: Do tràn bộ nhớ hoặc giá trị biến vượt quá giới hạn.
- Thời gian chạy quá hạn định, điểm bằng 0: Thường do vòng lặp vô tận.
- Hiệu suất kém với dữ liệu lớn: Nhiều lần lặp dẫn đến thời gian xử lý lâu.
Yêu cầu về kiến thức
Bài toán đầu tiên: Thiết kế cơ bản trong C/C++ và xử lý dữ liệu đơn giản như mảng, sắp xếp, đếm số...
Bài toán thứ hai: Thực hiện các thuật toán liên quan đến cấu trúc dữ liệu cơ bản như đệ quy, sắp xếp, tìm kiếm và xử lý chuỗi.
Kiến thức nhỏ
Chuyển đổi giữa ký tự và số
Khái niệm chính: Mã ASCII
- Để chuyển đổi từ ký tự sang số nguyên, chỉ cần trừ đi ký tự '0'. Sự khác biệt giữa các mã ASCII sẽ là giá trị mong muốn.
char v1 = '3';
int num = v1 - '0'; // Chuyển đổi ký tự '3' thành số nguyên
- Để chuyển đổi từ số nguyên sang ký tự số, chỉ cần cộng thêm ký tự '0'.
int num = 1;
char v1 = num + '0';
Phân biệt i++ và ++i
- Khi đứng độc lập, cả i++ và ++i đều tăng giá trị của i lên 1.
- Trong biểu thức:
a = i++: Gán giá trị hiện tại của i vào a trước khi tăng i.a = ++i: Tăng i trước rồi mới gán giá trị vào a.
Ví dụ:
int i = 4;
int a = i++; // Kết quả: a = 4, i = 5
a = ++i; // Kết quả: i = 6, a = 6
Cấu trúc dữ liệu
Xác định cấu trúc dữ liệu và sắp xếp mảng cấu trúc.
struct Key {
int id, start, end_time; // Số hiệu khóa, thời gian bắt đầu, thời gian kết thúc
};
bool compare(const Key& a, const Key& b) {
return a.id < b.id;
}
int main() {
vector<Key> keys_to_return;
sort(keys_to_return.begin(), keys_to_return.end(), compare);
}
Toán tử ma trận
Nhân ma trận
vector<vector<int>> multiply_matrices(const vector<vector<int>>& A, const vector<vector<int>>& B) {
int d = A.size();
vector<vector<int>> result(d, vector<int>(d, 0));
for (int i = 0; i < d; ++i) {
for (int j = 0; j < d; ++j) {
for (int k = 0; k < d; ++k) {
result[i][j] += A[i][k] * B[k][j];
}
}
}
return result;
}
Tính chất:
- Không thỏa tính chất giao hoán: A × B ≠ B × A.
- Thỏa tính chất kết hợp: (A × B) × C = A × (B × C).
- Phân phối: A × (B + C) = A × B + A × C.
Sàng số nguyên tố
Phương pháp Eratosthenes để tìm số nguyên tố:
void sieve_of_eratosthenes(int N) {
vector<bool> is_prime(N + 1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i * i <= N; ++i) {
if (is_prime[i]) {
for (int j = i * i; j <= N; j += i) {
is_prime[j] = false;
}
}
}
for (int i = 2; i <= N; ++i) {
if (is_prime[i]) cout << i << " ";
}
}
Các lỗi phổ biến
Tràn ngăn xếp
Khi thực hiện các mảng động lớn trong hàm main có thể dẫn đến tràn ngăn xếp. Giải pháp là sử dụng mảng tĩnh hoặc cấp phát bộ nhớ trên heap.
// Sử dụng mảng toàn cục
int large_array[10000000];
// Hoặc sử dụng heap
int* large_array = new int[10000000];
delete[] large_array;
Định dạng nhập/xuất
Xử lý dòng nhập
Sử dụng getline để đọc toàn bộ dòng:
string line;
getline(cin, line);
Nếu có vấn đề với ký tự xuống dòng, sử dụng cin.ignore() để bỏ qua:
cin.ignore();
getline(cin, line);
Làm tròn số
Sử dụng round và printf để làm tròn và định dạng đầu ra:
double rounded = round(num * 1000.0) / 1000.0;
printf("%.3f\n", rounded);
Định dạng số với setprecision
Định dạng số với số chữ số thập phân cố định:
cout << fixed << setprecision(4) << pi << endl;
Tiền tố tổng
Tính tổng tiền tố giúp tối ưu hóa việc tính toán tổng của các đoạn con.
Chuỗi
Các thao tác phổ biến
Thêm ký tự hoặc chuỗi vào chuỗi đã tồn tại:
string str = "Hello";
str += " World"; // Kết nối chuỗi
str.push_back('!'); // Thêm ký tự vào cuối chuỗi
str.append(" Test"); // Thêm chuỗi khác vào cuối
Vector
Khởi tạo và thao tác
Khởi tạo vector rỗng hoặc với giá trị ban đầu:
vector<int> vec(5, 1); // Tạo vector có 5 phần tử, mỗi phần tử có giá trị 1
vec.push_back(2); // Thêm phần tử vào cuối vector
vec.insert(vec.begin() + 2, 8); // Chèn phần tử vào vị trí chỉ định
Map
Sử dụng map
Map lưu trữ cặp khóa-giá trị và tự động sắp xếp theo khóa.
map<string, int> my_map;
my_map["key"] = 10;
for (auto& pair : my_map) {
cout << pair.first << ": " << pair.second << endl;
}
Hàm erase
Xóa phần tử khỏi container:
vector<int> vec = {1, 2, 3, 4};
vec.erase(vec.begin() + 2); // Xóa phần tử tại vị trí 2
Hàm sort
Sắp xếp phần tử trong container:
vector<int> vec = {4, 2, 5, 1};
sort(vec.begin(), vec.end()); // Sắp xếp tăng dần