Các tính năng "ẩn" hữu ích của C++ cho lập trình thi đấu

Dưới đây là một số thủ thuật và tính năng ít bekannt của C++ giúp tối ưu hóa mã nguồn, đặc biệt hữu ích trong lập trình thi đấu (competitive programming) để giảm thời gian viết code. Chúng ta sẽ đi qua từng ví dụ một.

1. Kiểm tra số chẵn/lẻ không dùng toán tử %

Thực hiện phép AND bitwise giữa số cần kiểm tra và 1. Nếu kết quả khác 0 là số lẻ, ngược lại là số chẵn. Nguyên lý: mọi số lẻ đều có bit cuối (LSB) bằng 1.

if ((n & 1) != 0) {
    // số lẻ
} else {
    // số chẵn
}

2. Nhân/chia nhanh bằng toán tử dịch bit

Nhân với 2ⁿ: dịch trái n lần. Chia cho 2ⁿ: dịch phải n lần.

x = 40;
y = x << 2; // nhân 4 → y = 160
x = 40;
y = x >> 2; // chia 4 → y = 10

3. Hoán đổi hai biến không dùng biến trung gian (XOR swap)

x ^= y;
y ^= x;
x ^= y;

4. Duyệt chuỗi không cần strlen()

Kiểm tra ký tự tại vị trí i có khác '\0' (non-zero) để quyết định tiếp tục lặp.

for (int i = 0; s[i]; i++) {
    cout << s[i];
}

5. emplace_back() thay vì push_back()

emplace_back() nhanh hơn vì xây dựng đối tượng trực tiếp trong bộ nhớ của container, tránh cấp phát/ sao chép thêm.

6. Hàm GCD tích hợp sẵn

__gcd(x, y) // trả về ước chung lớn nhất

7. Kích thước mảng tối đa

Trong hàm main: ~10⁶ phần tử. Khai báo global: lên đến 10⁷.

8. Tìm chữ số hàng đầu (most significant digit) bằng log

n = 4578;
double k = log10(n);
k = k - floor(k);
int x = pow(10, k); // x là chữ số hàng đầu

9. Đếm số chữ số không dùng vòng lặp

n = 4578;
int digit_count = floor(log10(n)) + 1;

10. Kiểm tra số nguyên tố 2 (power of 2)

x = 1024;
bool check = x && (!(x & (x - 1))); // true nếu là 2^k

11. Thuật toán all_of, any_of, none_of

all_of(begin, end, isPositive);  // tất cả dương?
any_of(begin, end, isPositive);   // ít nhất một dương?
none_of(begin, end, isPositive);  // không có dương?

12. copy_n() sao chép mảng/container

int src[5] = {10,20,30,40,50};
int dest[5];
copy_n(src, 5, dest);

13. iota() sinh dãy giá trị tăng dần

int arr[5] = {0};
char str[5] = {0};
iota(arr, arr+5, 15);   // {15,16,17,18,19}
iota(str, str+5, 'A');  // {'A','B','C','D','E'}

14. Hằng số nhị phân với tiền tố 0b (C++14)

int x = 0b1101; // x = 13

15. Từ khóa thay thế cho toán tử logic (and, or, not)

if (x < 10 and x > 5) cout << "True";