Cheatsheet C++
đã đăng vào 31 tháng 3 năm 2025, 11:38 p.m. 0Hướ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:
- Sắp xếp theo key
- Ổn định
❌ Nhược điểm:
- Chậm hơn
unordered_maphoặcgp_hash_tablevớ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ấtO(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_mapvớ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
- Bedao Grand Contest 10 - PERFECT
- Atcoder ABC250E - Prefix Equality
- Hackerrank - Number Game on a Tree
- Codeforces 1175F - The Number of Subpermutations
- Codeforces 1418G - Three Occurrences
📌 Ghi chú
- Với test ngẫu nhiên lớn,
gp_hash_tablethườ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ếnunordered_mapbằ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) |