Một vài tips và tricks C++ áp dụng cho Competitive Programming
C++ là một ngôn ngữ lập trình vô cùng phổ biến trong cộng đồng lập trình thi đấu hiện nay bởi là một trong những ngôn ngữ có tốc độ xử lí nhanh nhất. Ngoài ra, nó còn được sử dụng nhiều bởi có những thư viện hỗ trợ vô cùng tiện lợi, ví dụ như STL (Standard Template Library). Tuy nhiên, vẫn còn rất nhiều điều để khai thác từ ngôn ngữ này trong CP, hãy cùng Codedream khám phá những tips và tricks có thể bạn chưa biết để tiết kiệm được thời gian, cũng như code trở nên ngắn gọn hơn nhé.
Sử dụng ternary operator
Ternary opeator được sử dụng để tạo ra các biểu thức có điều kiện. Nó cho phép chúng ta đưa ra một quyết định dựa trên một điều kiện và trả về giá trị tùy thuộc vào kết quả của điều kiện đó. Cú pháp của ternary operator như sau:
condition ? value_if_true : value_if_false;
#include <vector> using namespace std; int a = 2, b = 1; bool larger; if (a > b) larger = true; else larger = false;
int a = 2, b = 1; bool larger; if (a > b) larger = true; else larger = false;
Ta có thể rút ngắn đoạn code trên sử dụng ternary operator:
int a = 2, b = 1; bool larger = (a > b) ? true : false;
Trong ví dụ trên, ta có 2 số nguyên [pmath size=12]a, b[/pmath] và biến [pmath size=12]larger[/pmath] để kiểm tra nếu [pmath size=12]a > b[/pmath]. Nếu [pmath size=12]a > b[/pmath] biểu thức trên sẽ trả về [pmath size=12]true[/pmath] và gán cho [pmath size=12]larger[/pmath], ngược lại nếu [pmath size=12]a \le b[/pmath] biểu thức trên sẽ trả về [pmath size=12]false[/pmath] và [pmath size=12]larger[/pmath] sẽ có giá trị là [pmath size=12]false[/pmath].
Ternary operator rất hữu ích khi chúng ta cần đưa ra quyết định ngắn gọn dựa trên một điều kiện duy nhất và trả về một giá trị tương ứng.
Sử dụng macro để biết được tên biến
Ta có thể sử dụng dấu [pmath size=12]’\#'[/pmath] để biến được chính xác tên của argument được truyền vào macro.
Ví dụ:
#define debug(x) cerr << #x << " is " << x << endl;
int K = -273;
debug(K)
// K is -273
debug(abs(K))
// abs(K) is 273
Việc sử dụng macro trên sẽ giúp chúng ta dễ dàng hơn nhiều trong việc debug.
Sử dụng {} để khởi tạo giá trị cho các container
Pair, Tuple
Thay vì
pair<int, int> a = make_pair(1, 2);
tuple<char, int, int> b = make_tuple('x', 1, 2);
```
ta có thể code như sau
```cpp
pair<int, int> a = {1, 2};
tuple<char, int, int> b = {'x', 1, 2};
STL containers
vector<int> a = {2, 7, 0, 6};
for (auto v : a){
cout << v << " ";
}
// 2 7 0 6
set<pair<int, int>> b = {{4, 3}, {2, 1}, {6, 7}, {3, 2}, {2, 1}};
for (auto v : b){
cout << v.first << " " << v.second << endl;
}
/* 2 1
* 3 2
* 4 3
* 6 7
*/
deque<vector<int>> c = {
{2, 1, 3, 4},
{6, 1, 4, 9, 2},
{7, 0, 1, 5, 0},
};
for (auto v : c){
for (auto x : v){
cout << x << " ";
}
cout << endl;
}
/*
* 2 1 3 4
* 6 1 4 9 2
* 7 0 1 5 0
*/
Lưu ý: cách gán trên không áp dụng được cho stack và queue.
Sử dụng bitset để chuyển số từ hệ thập phân sang nhị phân
Một cách phổ biến thường được dùng là:
vector<int> ToBinary(int val){
vector<int> ans;
while (val > 0){
ans.push_back(val % 2);
val /= 2;
}
reverse(ans.begin(), ans.end());
return ans;
}
Ta có thể sử dụng bitset để code nhìn gọn hơn:
int val = 27; cout << bitset<31>(val).to_string() << endl; // 0000000000000000000000000011011
Lưu ý: Với cách làm này ta cần phải xác định được trước số bit cần được in ra.
Một vài hàm hữu dụng trong C++
[pmath size=12]all(v)[/pmath]
Hàm này được mình tự viết lại và sử dụng thường xuyên bởi sự tiện lợi và ngắn gọn của nó.
#define all(v) v.begin(), v.end()
vector<int> a = {3, 2, 4, 1, 9, 2};
sort(all(a));
// Thay vì phải viết đầy đủ sort(a.begin(), a.end()) ta
// đã rút gọn lại thành sort(all(a)) ngắn gọn và dễ hiểu.
for (auto v : a) cout << v << " ";
// 1 2 2 3 4 9
[pmath size=12]unique(v)[/pmath]
Hàm [pmath size=12]unique[/pmath] được sử dụng để loại bỏ các phần tử trùng lặp liên tiếp trong một dãy. Có thể áp dụng hàm này để có thể thực hiện “nén số” với những bài tập chỉ cần quan tâm đến tính “lớn bé” của các phần tử.
#define all(v) v.begin(), v.end()
...
vector<int> v = {1, 1, 1, 2, 2, 3, 3, 3, 4, 4};
v.erase(unique(all(v)), v.end());
for (auto val : v){
cout << v << " ";
}
// 1 2 3 4
Ngoài ra có thể áp dụng hàm này để có thể thực hiện “nén số” với những bài tập chỉ cần quan tâm đến tính “lớn bé” của các phần tử. Phương pháp này bạn sẽ cần sử dụng nhiều trong các bài tập lập trình thi đấp.
#define all(v) v.begin(), v.end()
...
vector<int> a = {1009, 2012, 2016, 4096, 2706, 2012, 2005, 4096};
vector<int> b = a;
sort(all(b));
b.erase(unique(all(b)), b.end());
// 1009 2005 2012 2016 2706 4096
for (auto &v : a){
v = lower_bound(all(b), v) - b.begin() + 1;
cout << v << " ";
}
// 1 3 4 6 5 3 2 6
[pmath size=12]fill[/pmath]
Hàm [pmath size=12]fill[/pmath] trong C++ được sử dụng để gán giá trị nhất định cho tất cả các phần tử trong dãy
#define all(v) v.begin(), v.end() vector<int> a(10); fill(all(a), 5); for (auto v : a) cout << v << " "; // 5 5 5 5 5 5 5 5 5 5
[pmath size=12]iota[/pmath]
Hàm [pmath size=12]iota[/pmath] được sử dụng để gán giá trị tăng dần cho các phần tử trong dãy
#define all(v) v.begin(), v.end() vector<int> a(10); iota(all(a), 1); for (auto v : a) cout << v << " "; // 1 2 3 4 5 6 7 8 9 10 iota(all(a), 10); for (auto v : a) cout << v << " "; // 10 11 12 13 14 15 16 17 18 19
[pmath size=12]accumulate[/pmath]
Hàm [pmath size=12]accumulate[/pmath] được sử dụng để tính tổng các phần tử trong dãy số
#define all(v) v.begin(), v.end();
vector<int> a = {6, 1, 2, 3, 7, 0, 9, -6, 4, 5};
cout << accumulate(all(a), 0) << endl;
// 31
Lưu ý: tham số thứ 3 của hàm là giá trị khởi điểm của tổng và được cộng dần với các phần tử trong dãy. Nếu tổng của dãy lớn hơn giá trị thuộc [pmath size=12]int[/pmath] thì phải gán [pmath size=12]long \; long[/pmath] cho giá trị khởi điểm, nếu không sẽ xảy ra hiện tượng tràn số.
#define all(v) v.begin(), v.end();
vector<int> a = {1000000000, 1000000000, 1000000000};
cout << accumulate(all(a), 0) << endl; // -1294967296
cout << accumulate(all(a), 0ll) << endl; // 3000000000
[pmath size=12]generate[/pmath]
Hàm [pmath size=12]generate[/pmath] trong C++ được sử dụng để tạo ra các giá trị trong một dãy dựa trên một hàm sinh giá trị.
int gen() {
return rand() % 1000 + 1;
} // Sinh các giá trị ngẫu nhiên từ 1 -> 1000
#define all(v) v.begin(), v.end()
vector<int> a(10);
generate(all(a), gen);
for (auto v : a) cout << v << " ";
// 384 887 778 916 794 336 387 493 650 422
[pmath size=12]rotate[/pmath]
Hàm [pmath size=12]rotate[/pmath] trong C++ được sử dụng để xoay (quay) các phần tử trong một dãy.
#define all(v) v.begin(), v.end()
vector<int> a = {3, 2, 4, 1, 5};
rotate(a.begin(), a.begin() + 2, a.end());
for (auto v : a) cout << v << " ";
// 4 1 5 3 2
[pmath size=12]merge[/pmath]
Hàm [pmath size=12]merge[/pmath] trong C++ được sử dụng để trộn (hợp nhất) hai dãy đã được sắp xếp thành một dãy mới
#define all(v) v.begin(), v.end()
vector<int> a = {1, 3, 5};
vector<int> b = {2, 4, 6};
vector<int> c((int)a.size() + (int)b.size());
merge(all(a), all(b), c.begin());
for(auto v : c){
cout << v << " ";
}
// 1 2 3 4 5 6
Lời kết
Trong bài viết trên, chúng ta đã khám phá một số tips và tricks trong lập trình C++ áp dụng trong việc tham gia thi đấu, hi vọng bạn đọc thấy thú vị và có thể áp dụng vào các bài tập của mình. Ngoài ra vẫn còn nhiều tips và tricks nữa, nếu bạn thấy bài viết này hay hãy cho bọn mình biết để tiếp tục ra phần 2 của bài viết nhé.
Xem thêm các kiến thức thú vị tại: https://www.facebook.com/codedreamedu và https://codedream.edu.vn/hoc-thuat-toan/
