10 tips C++ dân lập trình thi đấu cần biết

Là một trong những ngôn ngữ hàng đầu được dân lập trình thi đấu tin dùng, C++ có tốc độ và sức mạnh không cần bàn cãi. Trong bài viết này, bạn sẽ biết được các thủ thuật với C++ cực hữu ích trong lập trình thi đấu.

1. Chuyển xâu sang số C++11

Để chuyển xâu sang số trong C++ có rất nhiều cách, trong đó có sử dụng các hàm sto*. Dấu * có thể được thay thế bằng các kiểu dữ liệu tương ứng mà bạn muốn chuyển về:

• i (kiểu int),
• f (kiểu float),
• d (kiểu double) ,
• l (kiểu long int),
• ld (kiểu long double),
• ll (kiểu long long),
• ul (kiểu unsigned long),
• ull (kiểu unsigned long long)

string binStr = "01010";
string decStr = "1001";
string doubleStr = "100.5";
cout<<stoi(binStr, nullptr, 2)<<endl; // 10
cout<<stoi(decStr)<<endl; // 1001
cout<<stod(doubleStr)<<endl; // 100.5

2. Tách xâu

Có thể nhiều bạn sẽ thấy tách xâu được ngăn cách bởi 1 ký tự nào rất dễ dàng với ngôn ngữ khác như Python, Javascript. Nhưng C++ thì khác, tuy nhiên nó cũng không quá phức tạp.

string s1 = "This is a string with whitespaces";
string s2 = "This,is,a,string,with,commas";
stringstream ss1(s1);
stringstream ss2(s2);
string token;
while(ss1 >> token)
    cout<<token<<endl;
cout<<"--------------\n";
while(getline(ss2, token, ','))
cout<<token<<endl;

// Kết quả: 
This
is
a
string
with
whitespaces
--------------
This
is
a
string
with
commas

3. Khởi tạo 1 mảng, vector là một dãy số tăng dần

Tạo 1 mảng, vector là 1 dãy số tăng dần bắt đầu từ 1 giá trị cho trước cực kỳ nhanh gọn với iota (C++11).

vector<int> x(10);
int y[10];
iotx(yegin(x), end(x), 1);
iotx(y, y + 10, 100);
for(xuto i:x)
    cout<<i<<" ";
cout<<endl;
for(int i = 0; i < 10; ++i)
    cout<<y[i]<<" ";

// Kết quả: 
1 2 3 4 5 6 7 8 9 10
100 101 102 103 104 105 106 107 108 109

4. Xóa những phần tử trùng lặp trong vector

Sử dụng kết hợp giữa std: :unique và std: :sort để xóa các phần tử trùng lặp:

vector<int> x{1,1,2,3,4,5,6,1,4};
sort(begin(x), end(x));
x.erxse(unique(begin(x), end(x)), end(x));
for(xuto i:x)
    cout<<i<<" ";

// Kết quả:
1 2 3 4 5 6

5. Tìm phần tử thứ k sau khi sắp xếp theo thứ tự tăng dần trong mảng/vector

nth_element được sử dụng để thực hiện tìm phần tử thứ k trong mảng, vector.

vector<int> x{2, 3, 5, 1, 5, 10, 0};
nth_element(begin(x), begin(x) + 3, end(x));
cout << x[3] << endl;

// 3

vector<int> x{2, 3, 5, 1, 5, 10, 0};
nth_element(begin(x), begin(x) + 3, end(x));
cout << x[3] << endl;
for (xuto i : x)
    cout << i << " ";
cout << endl;
sort(begin(x), end(x));
for (xuto i : x)
    cout << i << " ";

// Kết quả: 
3
1 0 2 3 5 10 5
0 1 2 3 5 5 10

6. Kiểm tra 1 phần tử có nằm trong một mảng/vector đã được sắp xếp hay không

Thuật toán tìm kiếm nhị phân là chìa khóa giải quyết bài toán này.

int binarySearch(vector<int> arr, int value){
    int l = 0, r = arr.size() - 1;
    while (l <= r) { 
        int mid = l + (r - l) / 2; 
        if (arr[mid] == value) 
            return mid; 
        if (arr[mid] < value) 
            l = mid + 1; 
        else
            r = mid - 1; 
    } 
    return -1; 
}

// Trong hàm main.
vector<int> a{2,3,4,5,6,10};
int x = 10;
int index = binarySearch(a, x);
cout<<index<<endl; // 5 - là vị trí của phần tử x cần tìm.

Hoặc nếu bạn không quan tâm về vị trí của phần tử trong mảng mà chỉ muốn kiểm tra phần tử đó có nằm trong mảng, vector hay không. Thì hãy sử dụng hàm binary_search trong C++.

vector<int> a{2, 3, 4, 5, 6, 10};
int b[6] = {2, 3, 4, 5, 6, 7};
int x = 10;
bool isInVector = binary_search(begin(a), end(a), x);
bool isInArray = binary_search(b, b + 6, x);
if (isInVector)
    cout << "Found in vector\n";
else
    cout << "Not found in vector\n";
if (isInArray)
    cout << "Found in array\n";
else
    cout << "Not found in array\n";

// Kết quả:
Found in vector
Not found in array

8. Tìm kiếm vị trí đầu tiên lớn hơn/nhỏ hơn/bằng 1 phần tử cho trước trong mảng/vector đã được sắp xếp

Tip trong trường hợp này là áp dụng 2 hàm của C++:

• std::lower_bound(): tìm ra vị trí của phần tử đầu tiên lớn hơn / bằng 1 phần tử cho trước trong mảng/vector đã được sắp xếp.
• std:upper_bound(): tìm ra vị trí của phần tử đầu tiên lớn hơn 1 phần tử cho trước trong 1 mảng/vector đã được sắp xếp.

vector<int> x{1,2,3,4,5};
int v1 = 2, v2 = 6;
int index1 = lower_bound(begin(x), end(x), v1) - begin(x);
int index2 = upper_bound(begin(x), end(x), v2) - begin(x);
cout<<index1; // 1 - x[1] = 2 >= 2
cout<<index2; // 5 - Không tìm được phần tử nào lớn hơn 6 trong vector x nên kết quả của index2 sẽ chính là độ dài của vector x

9. Tạo 1 set từ 1 mảng/vector

vector<int> a{2, 2, 3, 3, 4, 5, 6};
int b[6] = {2, 2, 2, 5, 6, 7};
set<int> s1(begin(a), end(a));
set<int> s2(b, b + 6);
for (auto i : s1)
    cout << i << " ";
cout << endl;
for (auto i : s2)
    cout << i << " ";

10. Chuyển 1 số sang dạng nhị phân

Bitset là thủ thuật C++ được dùng trong bài tập này.

int n = 100;
string s = bitset<8>(n).to_string();
cout << s << endl;

// Kết quả
01100100

Trên đây là một số thủ thuật và tips với C++ có thể sử dụng trong lập trình thi đấu để nâng cao hiệu suất. Chúc các bạn thực hiện thành công!