Template chuẩn
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// code here
return 0;
}
ios_base::sync_with_stdio(false) và cin.tie(NULL) giúp I/O nhanh hơn ~5 lần. Luôn thêm khi dùng cin/cout.
Kiểu dữ liệu
int // ~2.1 × 10^9
long long // ~9.2 × 10^18
double // số thực
bool // true / false
char // ký tự
string // chuỗi
// Hằng số hữu ích
INT_MAX // 2147483647
LLONG_MAX // 9223372036854775807
1e9+7 // 10^9+7 (số nguyên tố dùng làm MOD)
Vector
vector<int> v;
vector<int> v(n, 0); // n phần tử, giá trị 0
vector<int> v = {1, 2, 3};
v.push_back(x); // thêm cuối O(1)
v.pop_back(); // xóa cuối O(1)
v.size(); // kích thước
v.empty(); // kiểm tra rỗng
v.front(); v.back(); // phần tử đầu/cuối
v.resize(n); // đổi kích thước
v.clear(); // xóa tất cả
// Duyệt
for (int x : v) { ... }
for (int i = 0; i < v.size(); i++) { ... }
// 2D vector
vector<vector<int>> g(n, vector<int>(m, 0));
Sort & Tìm kiếm
sort(v.begin(), v.end()); // tăng dần
sort(v.begin(), v.end(), greater<int>()); // giảm dần
sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
// Binary search (mảng đã sort)
lower_bound(v.begin(), v.end(), x); // iterator đến phần tử >= x
upper_bound(v.begin(), v.end(), x); // iterator đến phần tử > x
// Đổi iterator ra index
int idx = lower_bound(v.begin(), v.end(), x) - v.begin();
// Min/max
*min_element(v.begin(), v.end());
*max_element(v.begin(), v.end());
min(a, b); max(a, b);
Set / Map
// set — BST, không trùng, có thứ tự
set<int> s;
s.insert(x); s.erase(x);
s.count(x); // 1 nếu tồn tại
s.find(x); // iterator
*s.begin(); // nhỏ nhất
*s.rbegin(); // lớn nhất
s.lower_bound(x); // >= x
// map — BST key-value
map<string,int> mp;
mp["key"] = 10;
mp.count("key");
for (auto& [k,v] : mp) { ... }
// Phiên bản O(1): unordered
unordered_set<int> us;
unordered_map<string,int> um;
Stack / Queue / Priority Queue
// Stack (LIFO)
stack<int> st;
st.push(x); st.pop(); st.top(); st.empty();
// Queue (FIFO)
queue<int> q;
q.push(x); q.pop(); q.front(); q.empty();
// Priority Queue
priority_queue<int> pq; // max-heap
priority_queue<int,vector<int>,greater<int>> pq; // min-heap
pq.push(x); pq.pop(); pq.top();
// Deque
deque<int> dq;
dq.push_front(x); dq.push_back(x);
dq.pop_front(); dq.pop_back();
String
string s = "hello";
s.length(); s.size();
s[i];
s.substr(l, len); // chuỗi con từ l, độ dài len
s.find("ell"); // vị trí hoặc string::npos
s += "world";
to_string(42); // int → string
stoi("42"); stoll("42"); // string → int/long long
// Duyệt
for (char c : s) { ... }
Toán học
abs(x); // giá trị tuyệt đối
sqrt(x); // căn bậc hai (double)
pow(a, b); // a^b (double)
__gcd(a, b); // GCD (C++14)
#include <numeric>
gcd(a, b); lcm(a, b); // C++17
// Bit operations
x & 1; // kiểm tra số lẻ
x >> 1; // chia 2
x << 1; // nhân 2
x & (x-1); // xóa bit thấp nhất
__builtin_popcount(x); // đếm số bit 1
__builtin_ctz(x); // đếm số bit 0 cuối
Thuật toán thường dùng
// Đảo mảng
reverse(v.begin(), v.end());
// Xóa trùng sau sort
v.erase(unique(v.begin(), v.end()), v.end());
// Accumulate (tổng)
long long sum = accumulate(v.begin(), v.end(), 0LL);
// Fill
fill(a, a+n, 0);
// Hoán vị
swap(a, b);
// next_permutation
do { /* xử lý hoán vị */ } while (next_permutation(v.begin(), v.end()));
I/O nhanh
// Đọc/ghi file
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
// In số thực với độ chính xác
cout << fixed << setprecision(6) << x;
Bình luận