Thủ Thuật C++ Hay Trong Lập Trình Thi Đấu Cho Người Mới Bắt Đầu

Posted on by mtoplistChuyên mục:Top List

Khi bắt đầu bước chân vào con đường lập trình thi đấu (competitive programming), ngoài việc phải làm rất nhiều bài tập ra thì việc đọc code của những cao thủ đi trước cũng là một cách để học hỏi phong cách code và các phương pháp tối ưu.

Trong bài viết này mình sẽ tổng hợp một số trick hữu ích khi mới bắt đầu đi theo con đường này, giúp các bạn viết code nhanh hơn và có thể đọc được code của các cao thủ. Từ giờ lập trình thi đấu trong bài viết sẽ được viết tắt là CP.

1. Fast I/O.

Trong CP một trong những việc quan trọng là đọc đầu vào càng nhanh càng tốt để tiết kiệm được thời gian. Thông thường thì nên sử dụng scanf/printf thay cho cin/cout để có tốc độ đọc dữ liệu đầu vào nhanh hơn. Tuy nhiên thì các bạn cũng có thể thêm các dòng sau vào trong hàm main để tăng tốc độ đọc đầu vào cin/cout thành gần ngang bằng scanf/printf.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0); // insert
    cin.tie(0); // insert
    return 0;
}

Sau khi chèn thêm 2 dòng trên vào trong hàm main, nếu bạn muốn in ra ký tự xuống dòng thì nên sử dụng ‘\n’ thay cho endl vì theo mình thấy nếu sử dụng endl thì chương trình của bạn vẫn chạy chậm như thường.

2. Define/typedef

Sử dụng define và typedef khiến bạn tiết kiệm phần lớn thời gian trong việc viết code.

Nếu bạn đang chạy debug và cần in tên biến và giá trị của nó, thay vì sử dụng cout như bình thường thì bạn có thể define như code dưới đây

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << (#x) << " is " << (x) << endl

int main() {
	int x = 1;    
	debug(x);
    return 0;
}

Hoặc để viết một vòng lặp chỉ có tác dụng lặp lại đúng n lần, bạn có thể define như dưới đây để có thể dễ dàng gọi nó mà không tốn quá nhiều thời gian gõ code.

#include <bits/stdc++.h>
using namespace std;

#define FTB(i,a,b) for(ll i=a,_b=b;i<=_b;i++)
#define FT(i,a,b) for(ll i=a,_b=b;i<_b;i++)
#define FGB(i,a,b) for(ll i=a,_b=b;i>=_b;i--)
#define FG(i,a,b) for(ll i=a,_b=b;i>_b;i--)

int main() {
	int n = 5;
	    
	FTB(i,0,n) cout << i << " ";
	cout << endl;

	FT(i,0,n) cout << i << " ";
	cout << endl;

	FGB(i,n,0) cout << i << " ";
	cout << endl;

	FG(i,n,0) cout << i << " ";

    return 0;
}

Sau khi đã biết cách sử dụng define rồi, một cách đơn giản cho phần Fast I/O là nếu bạn sợ chẳng may trong quá trình viết code sẽ viết nhầm endl thì có thể định nghĩa lại như sau.

#define endl "\n"

Đối với các tên kiểu dữ liệu thì mình sẽ sử dụng typedef như thế này.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;

int main() {
	ll n = 1e12;
	cout << n << endl;

	vii vec_pair;

	for (int i = 0; i < n; i++) {
		vec_pair.push_back(ii(i, i+1));
	}

	for (int i = 0; i < n; i++) {
		cout << vec_pair[i].first << vec_pair[i].second << endl;
	}

    return 0;
}

3. Sử dụng từ khóa auto

Từ khóa auto có thể sử dụng ở nhiều nơi, từ đặt tên biến 

auto a = 1; // a will become 'int'
auto b = 1LL; // b will become 'long long'
auto c = 1.0; // c will become 'double'
auto d = "variable"; // d will become 'string'

Cho đến duyệt các phần tử trong các STL containers của C++ mà không cần dùng đến các iterator

#include <bits/stdc++.h>
using namespace std;

vector<int> my_vec;
set<int> my_set;
map<int,int> my_map;

int main() {
  my_vec.push_back(1);
  my_vec.push_back(3);
  my_vec.push_back(2);
  for (auto it: my_vec) cout << it << " ";
  cout << endl;

  my_set.insert(6);
  my_set.insert(4);
  my_set.insert(5);
  for (auto it: my_set) cout << it << " ";
  cout << endl;

  my_map[8] = 7;
  my_map[4] = 9;
  my_map[7] = 6;
  for (auto it: my_map) cout << it.first << " " << it.second << endl;
  cout << endl;

  return 0;
}

4. Các phép toán sử dụng bit

Như các bạn đã biết thì các con số trong máy tinh được biểu diễn dưới dạng bit nhị phân. Do đó nếu muốn kiểm tra một số có chia hết cho 2 không thì chỉ cần kiểm tra bit đầu tiên có bằng không hay không. Thay vì viết như này:

if (n % 2 == 1) {
 	cout << n << " le"; 
}
else cout << n << " chan";

Chúng ta có thể viết như thế này:

if (n & 1) {
 	cout << n << " le"; 
}
else cout << n << " chan";

Muốn hoán đổi giá trị 2 biến a và b, chúng ta có thể viết như sau:

a ^= b; 
b ^= a; 
a ^= b;

Muốn nhân một số với lũy thừa của 2 (giả sử ở đây là 2^x) thì chúng ta đơn giản là đẩy toàn bộ các bit của số đó sang bên trái x bit, và nếu chia lấy phần nguyên thì là đẩy các bit của số đó sang bên phải x bit, do đó có thể viết như sau

n << x; // nhân n với 2 ^ x
n >> x; // chia n cho 2 ^ x

Trong trường hợp muốn sinh nhị phân để kiểm tra toàn bộ cấu hình, bài toán đặt ra là cho n người, cần duyệt tất cả các trạng thái để người thứ i trong n người đó có  được chọn hay không. Thay vì viết hẳn hàm sinh từng cấu hình liên tiếp như thông thường thì chúng ta có thể sử dụng phép dịch bit và duyệt như sau.

for (int i = 0; i < (1<<n); i++) {
	for(int j = 0; j < n; j++) {
		cout << ((i >> j) & 1) << " "; 
	}
	cout << endl;
}

5. Các phương pháp xử lý khi tính toán lấy mod

Phần này thì không chỉ C++ mà bất kỳ một ngôn ngữ nào cũng đều có thể áp dụng. Tùy theo kiểu dữ liệu input của đề bài mà mình lựa chọn được phương pháp phù hợp nhất.

1: (A / B) % MOD = (A % (MOD * B)) / B

2: (A / B) % MOD = ((A % MOD) * (Bphi(MOD) – 1 % MOD)) % MOD

Trong đó phi(MOD) là phi hàm eurler của MOD. 

3: (A / B) % MOD = ((A % MOD) * (BMOD – 2 % MOD)) % MOD

4: AN % MOD = AN % phi(MOD) % MOD

5: (A * B) % MOD khi mod không biểu diễn được trong kiểu int

long long mulMod(long long a,long long b,long long mod) {
    long long res = 0;
    while (b > 0) {
        if (b & 1) {
            res = (res + a) % mod;
        }
        a = (a * 2) % mod;
        b = b / 2;
    }
    return res;
}

Tạm kết

Trong bài viết trên mình đã giới thiệu một số kỹ thuật mà mình nghĩ là hữu ích cho các bạn mới bắt đầu đi vào con đường competitive programming . Nếu các bạn có góp ý gì thì hãy để lại bình luận bên dưới, nếu cảm thấy bài viết hữu ích thì đừng quên đánh giá 5 sao nhé.

Tham khảo: geeksforgeeks, hackerearth

mtoplist