Các thủ thuật C++ cho lập trình thi đấu (C++11)

Các thủ thuật C++ hữu ích cho Competitive Programming (CP), tương thích C++11 trở lên.

1. Kiểm tra chẵn/lẻ không dùng %

if (n & 1) { /* lẻ */ } else { /* chẵn */ }

Bitwise AND với 1: số lẻ có LSB = 1.

2. Nhân/chia nhanh 2^k bằng shift

x = 40;
y = x << 2;  // x * 4 = 160
y = x >> 2;  // x / 4 = 10

3. Hoán đổi không biến tạm (XOR swap)

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

Lưu ý: Không dùng cho cùng một biến (x ^= x = 0). Hiện đại: dùng std::swap (tối ưu hơn, an toàn).

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

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

s[i] khác 0 (khác '\0') → tiếp tục.

5. emplace_back() thay push_back()

vector<pair<int,int>> v;
v.emplace_back(1, 2); // Tạo trực tiếp tại chỗ, nhanh hơn

6. GCD builtin

__gcd(x, y) // GCC extension
// C++17: std::gcd(x, y) trong <numeric>

7. Kích thước mảng toàn cục vs cục bộ

• Trong main/function: max ~10⁶ phần tử (stack limit).
• Toàn cục (global/static): max ~10⁷-10⁸ (data segment).

8. Chữ số hàng đầu (Most Significant Digit)

int n = 4578;
double k = log10(n);
k = k - floor(k);
int msd = pow(10, k); // 4

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

int digits = floor(log10(n)) + 1;

10. Kiểm tra lũy thừa của 2

bool isPowerOfTwo = x && !(x & (x - 1));

11. Algorithms kiểm tra điều kiện (C++11)

all_of(begin, end, pred);  // Tất cả thỏa mãn
any_of(begin, end, pred);  // Ít nhất 1 thỏa mãn
none_of(begin, end, pred); // Không có nào thỏa mãn

12. Copy container

copy_n(src, n, dest); // <algorithm>

13. iota - sinh dãy tăng dần

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

14. Hằng nhị phân (C++14)

int x = 0b1101; // = 13

15. Toán tử logic dạng từ khóa

if (x < 10 and x > 5) // thay &&
if (x < 5 or x > 10)  // thay ||
if (not flag)         // thay !

16. Structured Binding (C++17)

auto [x, y] = pair(1, 2);
auto [a, b, c] = tuple(1, 2, 3);
for (auto [key, val] : map) { ... }

17. if/while với initializer (C++17)

if (auto it = m.find(key); it != m.end()) { ... }
while (auto line = readLine(); line) { ... }

Lưu ý quan trọng

• Đọc kỹ quy tắc cuộc thi: một số thủ thuật (như XOR swap) không được khuyến khích do readability.
• Ưu tiên code rõ ràng, đúng trước; tối ưu sau.
• __gcd là GCC extension, dùng std::gcd (C++17) để portable.