Hướng dẫn sử dụng mt19937 và mt19937_64 trong C++
📌 Mục tiêu
- Giải thích cách sử dụng bộ sinh số ngẫu nhiên chất lượng cao trong C++
- Phân biệt
mt19937 (32-bit) và mt19937_64 (64-bit)
- Hướng dẫn sinh số ngẫu nhiên, số trong khoảng, số thực, mảng ngẫu nhiên
🧠 Tổng quan
mt19937 và mt19937_64 là gì?
- Là bộ sinh số ngẫu nhiên dựa trên thuật toán Mersenne Twister.
mt19937: sinh số nguyên 32-bit (unsigned int).mt19937_64: sinh số nguyên 64-bit (unsigned long long).- Chu kỳ rất dài, phân phối đồng đều, dùng nhiều trong lập trình thi đấu và mô phỏng.
🔧 Code mẫu cơ bản
#include <bits/stdc++.h>
using namespace std;
mt19937 rng32(time(0)); // Sinh số ngẫu nhiên 32-bit
mt19937_64 rng64(time(0)); // Sinh số ngẫu nhiên 64-bit
int main() {
cout << "random 32 (bit): " << rng32() << endl;
cout << "random 64 (bit): " << rng64() << endl;
}
📘 C++ Hash Map Cheatsheet: map, unordered_map, gp_hash_table
1. std::map
- Dạng: Cây đỏ-đen (Red-Black Tree)
- Tự động sắp xếp theo key
- Độ phức tạp:
O(log n) cho các thao tác chèn, tìm kiếm, xóa
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> um;
int main() {
map<int, int> mp;
mp[1] = 100;
if (mp.count(1)) {
cout << mp[1]; // Output: 100
}
}
✅ Ưu điểm:
❌ Nhược điểm:
- Chậm hơn
unordered_map hoặc gp_hash_table với dữ liệu ngẫu nhiên
2. std::unordered_map
- Dạng: Hash Table chuẩn
- Không sắp xếp theo key
- Độ phức tạp trung bình:
O(1) (xấu nhất O(n))
🛠 Tip: Tăng hiệu năng bằng reserve() khi biết trước số phần tử:
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> um;
int main() {
um.reserve(1000000);
um[3] = 3;
cout << um[3];
}
3. __gnu_pbds::gp_hash_table
- Cấu trúc dữ liệu thay thế
unordered_map với hiệu suất cao hơn
- Cần include đặc biệt:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
int main() {
gp_hash_table<int, int> m;
m[3] = 1;
cout << m[3];
}
✅ Ưu điểm:
- Rất nhanh cho dữ liệu ngẫu nhiên
- Ít bị đụng độ hash
❌ Nhược điểm:
- Không tương thích với Clang
- Không có trong chuẩn STL, chỉ dùng trên GCC (như Codeforces)
4. So sánh hiệu suất
| Dữ liệu |
std::map |
unordered_map |
gp_hash_table |
| Tìm kiếm |
log(n) |
Trung bình O(1) |
Nhanh hơn O(1) |
| Bộ nhớ |
Cao |
Thấp - TB |
Tối ưu tốt |
| Dữ liệu ngẫu nhiên |
Chậm |
TB - có thể bị tệ |
Rất tốt |
| Hỗ trợ Clang |
✔️ |
✔️ |
❌ |
5. Một số tối ưu khi dùng unordered_map
unordered_map<int, int> um;
um.reserve(1 << 20); // Dự phòng bộ nhớ
um.max_load_factor(0.25); // Giảm load factor để tránh đụng độ hash
6. Khi nào dùng cái nào?
| Trường hợp |
Cấu trúc phù hợp |
| Cần sắp xếp key |
std::map |
| Tìm kiếm nhanh, không cần sắp xếp |
unordered_map |
| Dữ liệu ngẫu nhiên lớn, cần tốc độ |
gp_hash_table (nếu dùng GCC) |
7. Bài tập áp dụng
📌 Ghi chú
- Với test ngẫu nhiên lớn,
gp_hash_table thường vượt trội về thời gian và bộ nhớ.
- Nếu không dùng được
gp_hash_table, bạn có thể thử tùy biến unordered_map bằng cách tự viết hàm hash.
struct custom_hash {
size_t operator()(uint64_t x) const {
return x ^ (x >> 16);
}
};
unordered_map<uint64_t, int, custom_hash> safe_map;
📘 C++ Cheatsheet: vector 1 chiều & 2 chiều
1. vector 1 chiều
🔹 Khai báo
vector<int> a; // Vector rỗng
vector<int> b(5); // Vector 5 phần tử, giá trị mặc định = 0
vector<int> c(5, -1); // Vector 5 phần tử, mỗi phần tử = -1
🔹 Truy cập phần tử
a[0], a.at(0); // Truy cập phần tử đầu tiên
a.front(); // Phần tử đầu
a.back(); // Phần tử cuối
🔹 Thêm / Xóa phần tử
a.push_back(10); // Thêm vào cuối
a.pop_back(); // Xóa phần tử cuối
a.insert(a.begin() + 2, 100);// Chèn 100 tại vị trí thứ 2
a.erase(a.begin() + 1); // Xóa phần tử tại vị trí thứ 1
🔹 Duyệt
for (int x : a) cout << x;
for (int i = 0; i < a.size(); ++i) cout << a[i];
🔹 Resize & Clear
a.resize(10); // Thay đổi kích thước thành 10 phần tử
a.clear(); // Xóa toàn bộ phần tử
🔹 Gán
a = vector<int>(5, 7); // Gán lại vector a thành 5 phần tử = 7
a.assign(3, 100); // Gán 3 phần tử bằng 100
2. vector 2 chiều
🔹 Khai báo
int n = 3, m = 4;
vector<vector<int>> mat(n, vector<int>(m)); // ma trận n x m, mặc định 0
vector<vector<int>> mat2(n, vector<int>(m, -1)); // ma trận n x m, mỗi phần tử = -1
🔹 Truy cập & Duyệt
mat[i][j]; // Truy cập phần tử hàng i, cột j
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cout << mat[i][j];
🔹 Resize sau khai báo
vector<vector<int>> mat;
mat.resize(n, vector<int>(m, 0)); // Resize thành n x m, tất cả = 0
🔹 Gán lại toàn bộ
mat.assign(n, vector<int>(m, 1)); // Gán lại ma trận n x m toàn bộ = 1
3. Một số mẹo
Duyệt nhanh:
for (auto &row : mat)
for (auto x : row)
cout << x << " ";
Xoay chiều ma trận:
vector<vector<int>> rotate90(const vector<vector<int>>& mat) {
int n = mat.size(), m = mat[0].size();
vector<vector<int>> res(m, vector<int>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
res[j][n - 1 - i] = mat[i][j];
return res;
}
🔚 Tổng kết
| Tác vụ |
Cú pháp |
| Khởi tạo |
vector<int> v(n, val); |
| Resize |
v.resize(new_size); |
| Gán toàn bộ |
v.assign(n, val); |
| Vector 2D |
vector<vector<int>> mat(n, vector<int>(m)); |
| Xóa |
v.clear(); |
| Truy cập |
v[i], mat[i][j] |
| Duyệt |
for (int x : v) hoặc for (auto x : row) |
