Nền Tảng Competitive Programming & Kỹ Thuật Tối Ưu C++20
Trong các kỳ thi Học sinh giỏi Tin học THPT (từ cấp Trường, Tỉnh/Thành phố đến Quốc gia VOI), ngôn ngữ C++ luôn là sự lựa chọn số 1 nhờ tốc độ thực thi vượt trội và thư viện chuẩn STL (Standard Template Library) phong phú. Tuy nhiên, để giành trọn vẹn điểm số trong 180 phút, thí sinh phải làm chủ tốc độ vào/ra (Fast I/O), tư duy chặn tràn số và phân tích độ phức tạp thuật toán cực kỳ khắt khe.
Fast I/O & Xử Lý Tràn Số
Lệnh cin/cout mặc định đồng bộ với thư viện C nên rất chậm. Bắt buộc thêm cin.tie(NULL); ios_base::sync_with_stdio(false); và dùng \n thay cho endl. Với giá trị lên đến $10^{18}$, dùng long long; với phép nhân có kết quả vượt phạm vi long long nhưng nằm trong khoảng $\pm 1{,}7\times10^{38}$, có thể dùng __int128 (mở rộng GCC/Clang, không thuộc ISO C++20).
Quy Tắc Ước Lượng 1.0 Giây
Hệ thống chấm thi hiện đại (Themis, CMS, VNOJ, Codeforces) thực hiện được khoảng $10^7$–$10^8$ thao tác đơn giản / giây tùy máy chấm, ngôn ngữ và thao tác. Nhìn vào giới hạn $N$ để đoán độ phức tạp:
• $N \le 20 \rightarrow O(2^N)$ (còn $O(N!)$ chỉ khả thi với $N$ nhỏ hơn nhiều)$
• $N \le 500 \rightarrow O(N^3)$ | $N \le 5000 \rightarrow O(N^2)$
• $N \le 2\cdot 10^5 \rightarrow O(N \log N)$ | $N \le 10^7 \rightarrow O(N)$
• $N \le 10^{18} \rightarrow O(\log N)$ hoặc $O(1)$
#include <bits/stdc++.h>
using namespace std;
#define int long long // Phổ biến trong thi CP để tránh tràn số âm thầm
#define all(x) (x).begin(), (x).end()
const int MOD = 1e9 + 7;
const int INF = 1e18;
void solve() {
int n;
if (!(cin >> n)) return;
vector<int> a(n);
for (int &x : a) cin >> x;
if (a.empty()) return;
sort(all(a));
cout << a.back() << "\n";
}
int32_t main() {
// Tối ưu hóa I/O: bắt buộc trong mọi bài thi HSG
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Chuyển hướng file nếu đề thi yêu cầu tên file (VD: BAI1.INP / BAI1.OUT)
#ifndef ONLINE_JUDGE
if (fopen("BAI1.INP", "r")) {
freopen("BAI1.INP", "r", stdin);
freopen("BAI1.OUT", "w", stdout);
}
#endif
int t = 1;
// cin >> t; // Bỏ comment nếu bài có nhiều bộ test
while (t--) solve();
return 0;
}endl vì nó gọi kèm hàm flush() làm chậm hàng trăm lần. Trong trường hợp cần dùng unordered_map hoặc unordered_set, phải cấu hình custom hash với thời gian thực (time seed) để chống lại các test hack cố tình tạo xung đột hàm băm (Hash collision attack $O(N^2)$).
Bài Tập Trắc Nghiệm Thuật Toán (Bài 1)
Câu 1.1: Cho bài toán với giới hạn $N \le 2 \times 10^5$, thời gian thực thi tối đa $1.0$ giây. Thuật toán có độ phức tạp nào sau đây là phù hợp nhất để đạt điểm tối đa (Full subtask)?
Câu 1.2: Trong C++, vì sao trong các bài toán yêu cầu đọc/ghi dữ liệu lớn ($N \ge 10^5$), thí sinh nên dùng '\n' thay vì std::endl?
Câu 1.3: Giới hạn giá trị của kiểu số nguyên long long trong C++ tiêu chuẩn là khoảng bao nhiêu?
Câu 1.4: Kỹ thuật nào sau đây giúp kiểm thử tính đúng đắn của thuật toán chuẩn bằng cách so sánh kết quả tự động với thuật toán "vét cạn" (Brute-force) trên hàng nghìn bộ dữ liệu ngẫu nhiên?
Mảng Cộng Dồn (Prefix Sum) & Kỹ Thuật Hai Con Trỏ (Two Pointers)
Mảng cộng dồn (Prefix Sum), Mảng hiệu (Difference Array) và Hai con trỏ (Two Pointers / Sliding Window) là những những kỹ thuật nền tảng thường gặp trong các bài thi lập trình. Chúng biến đổi các thao tác tính toán từ độ phức tạp $O(N)$ hoặc $O(N^2)$ xuống chỉ còn $O(1)$ hoặc $O(N)$.
| Kỹ thuật | Công thức cốt lõi | Thời gian tiền xử lý | Độ phức tạp truy vấn |
|---|---|---|---|
| Prefix Sum 1D | pref[i] = pref[i-1] + a[i] sum(l, r) = pref[r] - pref[l-1] |
O(N) | O(1) |
| Prefix Sum 2D | pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + a[i][j] sum(x1,y1,x2,y2) = pref[x2][y2] - pref[x1-1][y2] - pref[x2][y1-1] + pref[x1-1][y1-1] |
O(N * M) | O(1) |
| Difference Array (Mảng hiệu) | Cộng đoạn [L, R] thêm V: diff[L] += V; diff[R + 1] -= V; |
O(1) mỗi cập nhật | O(N) khôi phục mảng sau Q truy vấn |
| Two Pointers (Hai con trỏ) | Con trỏ L và R chỉ dịch chuyển một chiều (Monotonicity) | O(N log N) nếu cần sort | O(N) duyệt tổng thể |
#include <bits/stdc++.h>
using namespace std;
// Tìm độ dài đoạn con liên tiếp dài nhất có tổng <= S
int longestSubarraySumAtMostS(const vector<long long>& a, long long S) {
int n = a.size();
int l = 0, max_len = 0;
long long cur_sum = 0;
for (int r = 0; r < n; ++r) {
cur_sum += a[r];
// Thu hẹp cửa sổ khi tổng vượt quá S (tính đơn điệu vì a[i] > 0)
while (l <= r && cur_sum > S) {
cur_sum -= a[l];
l++;
}
max_len = max(max_len, r - l + 1);
}
return max_len;
}Bài Tập Trắc Nghiệm Thuật Toán (Bài 2)
Câu 2.1: Cho mảng $a$ gồm $N$ số nguyên. Có $Q$ truy vấn, mỗi truy vấn yêu cầu cộng thêm giá trị $V$ vào tất cả phần tử từ vị trí $L$ đến $R$ ($1 \le L \le R \le N$). Sau $Q$ truy vấn cần in ra mảng kết quả. Cấu trúc nào tối ưu nhất với $N, Q \le 10^6$?
Câu 2.2: Công thức tính tổng các phần tử trong hình chữ nhật từ ô $(x_1, y_1)$ đến ô $(x_2, y_2)$ bằng mảng tiền tố 2D pref[i][j] là gì?
Câu 2.3: Điều kiện tiên quyết để kỹ thuật Hai Con Trỏ (Sliding Window / Two Pointers) đạt độ phức tạp $O(N)$ khi tìm đoạn con thỏa mãn tính chất tổng hoặc số lượng là gì?
Câu 2.4: Cho mảng $A$ chứa cả số âm và số dương. Bài toán yêu cầu đếm số đoạn con liên tiếp có tổng bằng đúng số nguyên $K$. Kỹ thuật nào sau đây giải quyết trong thời gian kỳ vọng $O(N)$?
Tìm Kiếm Nhị Phân & Kỹ Thuật "Chặt Nhị Phân Kết Quả" (Binary Search the Answer)
Tìm kiếm nhị phân (Binary Search) không chỉ dùng để tìm phần tử trên mảng đã sắp xếp trong $O(log N)$. Trong các đề thi HSG Quốc gia và Olympic, kỹ thuật quyền năng nhất chính là "Chặt nhị phân kết quả" (Binary Search on Answer): chuyển đổi bài toán tối ưu (tìm giá trị nhỏ nhất hoặc lớn nhất) thành bài toán kiểm tra tính khả thi (Hàm kiểm tra check(val) trả về true/false).
Dấu hiệu nhận biết bài toán Chặt nhị phân kết quả:
- Đề bài có cụm từ: "Tìm giá trị lớn nhất sao cho...", "Tìm chi phí nhỏ nhất để...", "Độ chênh lệch lớn nhất là nhỏ nhất (Minimax)".
- Khoảng giá trị kết quả có thể xác định được chặn dưới $L$ và chặn trên $R$ (ví dụ: $1 \le ans \le 10^{18}$).
- Tồn tại tính đơn điệu: Nếu giá trị $mid$ thỏa mãn điều kiện thì mọi giá trị $\le mid$ (hoặc $\ge mid$) cũng thỏa mãn.
- Hàm
check(mid)có thể tính toán nhanh bằng thuật toán tham lam (Greedy) trong $O(N)$. Tổng độ phức tạp sẽ là $O(N log(R - L))$.
#include <bits/stdc++.h>
using namespace std;
// Với a[i] >= 0, 1 <= K <= N; có thể tách thêm để được đúng K đoạn.
// Hàm kiểm tra: có thể chia mảng thành <= K đoạn mà mỗi đoạn có tổng <= max_sum?
bool check(long long max_sum, const vector<long long>& a, int k) {
int segments = 1;
long long cur = 0;
for (long long x : a) {
if (x > max_sum) return false; // Một phần tử đã vượt giới hạn
if (cur + x > max_sum) {
segments++;
cur = x;
} else {
cur += x;
}
}
return segments <= k;
}
long long solve(int n, int k, const vector<long long>& a) {
long long low = *max_element(a.begin(), a.end());
long long high = accumulate(a.begin(), a.end(), 0LL);
long long ans = high;
while (low <= high) {
long long mid = low + (high - low) / 2;
if (check(mid, a, k)) {
ans = mid; // Ghi nhận đáp án hợp lệ
high = mid - 1; // Thử tìm giá trị nhỏ hơn nữa
} else {
low = mid + 1; // Bắt buộc tăng giới hạn tổng
}
}
return ans;
}Bài Tập Trắc Nghiệm Thuật Toán (Bài 3)
Câu 3.1: Khi tính giá trị phần tử giữa mid giữa low và high trong C++, vì sao nên viết mid = low + (high - low) / 2 thay vì mid = (low + high) / 2?
Câu 3.2: Hàm std::lower_bound trong C++ STL trả về con trỏ (iterator) trỏ tới phần tử nào trong một mảng đã sắp xếp tăng dần?
Câu 3.3: Trong bài toán "Chặt nhị phân trên tập số thực" (Binary Search on Reals) tìm nghiệm phương trình hoặc khoảng cách với sai số $\le 10^{-6}$, cách kiểm soát vòng lặp nào sau đây an toàn nhất để tránh vòng lặp vô hạn do sai số dấu phẩy động?
Câu 3.4: Khi một hàm mục tiêu $f(x)$ có tính chất đơn đỉnh (Unimodal - tăng dần đến cực đại rồi giảm dần hoặc ngược lại), thuật toán tìm kiếm nào được áp dụng để tìm điểm cực trị trong $O(log N)$?
Số Học & Lý Thuyết Số Trong Thi HSG (Number Theory & Math)
Số học là "mỏ điểm" trong hầu hết các đề thi HSG Tỉnh và Quốc gia. Các bài toán thường yêu cầu kết quả lấy dư theo modulo $10^9 + 7$ hoặc $998244353$. Thí sinh bắt buộc phải nhuần nhuyễn các thuật toán số học có độ phức tạp $O(log N)$ hoặc tiền xử lý $O(N)$ để trả lời truy vấn trong $O(1)$.
Lũy Thừa Nhị Phân & Nghịch Đảo Modulo
Tính $A^B \pmod M$ trong $O(\log B)$. Khi $M$ là số nguyên tố (như $10^9+7$) và $A$ không chia hết cho $M$, theo định lý Fermat nhỏ: $A^{M-1} \equiv 1 \pmod M$, do đó nghịch đảo modulo của $A$ là $A^{-1} \equiv A^{M-2} \pmod M$. Với $B$ không chia hết cho $M$, phép chia $(A / B) \pmod M$ được chuyển thành $(A \times B^{M-2}) \pmod M$.
Tổ Hợp $C_N^K$ & Sàng Số Nguyên Tố SPF
Tiền xử lý mảng giai thừa fact[i] và nghịch đảo giai thừa invFact[i] trong $O(N)$, với $N < M$ khi modulo nguyên tố $M$, cho phép tính $C_N^K = \frac{N!}{K!(N-K)!}$ trong $O(1)$ mỗi truy vấn. Sàng Smallest Prime Factor (SPF) giúp phân tích thừa số nguyên tố của bất kỳ số nào $\le 10^7$ trong $O(\log N)$.
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 5;
long long fact[MAXN], invFact[MAXN];
long long power(long long base, long long exp) {
long long res = 1;
base %= MOD;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp /= 2;
}
return res;
}
long long modInverse(long long n) {
return power(n, MOD - 2); // Chỉ đúng nếu n % MOD != 0
}
void precompute() {
fact[0] = 1;
invFact[0] = 1;
for (int i = 1; i < MAXN; i++) {
fact[i] = (fact[i - 1] * i) % MOD;
}
invFact[MAXN - 1] = modInverse(fact[MAXN - 1]);
for (int i = MAXN - 2; i >= 1; i--) {
invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
}
}
long long nCr(int n, int r) {
if (r < 0 || r > n) return 0;
if (n >= MAXN) throw out_of_range("n exceeds precomputed range");
return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}Bài Tập Trắc Nghiệm Thuật Toán (Bài 4)
Câu 4.1: Để tính số Fibonacci thứ $N$ ($N \le 10^{18}$) chia lấy dư cho $10^9 + 7$, phương pháp nào sau đây đạt độ phức tạp thời gian tối ưu $O(log N)$?
Câu 4.2: Theo Định lý Fermat nhỏ, nếu $P$ là một số nguyên tố và số nguyên $A$ không chia hết cho $P$, nghịch đảo modulo của $A$ theo modulo $P$ bằng:
Câu 4.3: Thuật toán Euclid mở rộng (Extended Euclidean Algorithm) tìm nghiệm nguyên $(x, y)$ của phương trình vô định nào?
Câu 4.4: Sàng phân đoạn (Segmented Sieve) thường được sử dụng trong tình huống nào trong đề thi HSG?
Quy Hoạch Động Cơ Bản Đến Trung Cấp (Dynamic Programming - DP)
Quy hoạch động (DP) là nội dung chiếm tỷ trọng điểm số cao nhất trong các kỳ thi chọn học sinh giỏi. Bản chất của DP là phân rã bài toán lớn thành các bài toán con gối nhau (Overlapping Subproblems) và có cấu trúc con tối ưu (Optimal Substructure), lưu kết quả vào bảng để không bao giờ phải tính toán lại.
1. Dãy Con Tăng Dài Nhất (LIS)
Thuật toán $O(N^2)$ cơ bản nâng cấp lên $O(N log N)$ bằng mảng tail[] kết hợp lower_bound.
2. Bài Toán Ba Lô (0/1 Knapsack)
Duyệt trọng lượng từ $W$ ngược về $w_i$: dp[j] = max(dp[j], dp[j - w_i] + v_i) trong không gian $O(W)$.
3. Dãy Con Chung Dài Nhất (LCS)
So khớp chuỗi $S_1, S_2$ trong $O(N \times M)$. Tối ưu bộ nhớ về 2 dòng luân phiên hoặc chuyển về LIS nếu ký tự đôi một khác nhau.
#include <bits/stdc++.h>
using namespace std;
// Trả về độ dài dãy con tăng dài nhất với N <= 2*10^5
int lis(const vector<int>& a) {
vector<int> tail; // tail[i] lưu phần tử kết thúc nhỏ nhất của dãy con tăng độ dài i + 1
for (int x : a) {
auto it = lower_bound(tail.begin(), tail.end(), x);
if (it == tail.end()) {
tail.push_back(x); // Tạo dãy con tăng có độ dài mới lớn hơn
} else {
*it = x; // Cập nhật giá trị kết thúc nhỏ hơn tối ưu cho tương lai
}
}
return tail.size();
}Bài Tập Trắc Nghiệm Thuật Toán (Bài 5)
Câu 5.1: Trong bài toán Ba lô 0/1 (mỗi đồ vật chỉ được chọn tối đa 1 lần) tối ưu không gian trạng thái về mảng 1D dp[j], vì sao vòng lặp trọng lượng $j$ phải chạy ngược từ $W$ giảm về $w_i$?
Câu 5.2: Thuật toán tìm Dãy con tăng dài nhất (LIS) cải tiến bằng mảng tail[] và hàm std::lower_bound có độ phức tạp thời gian là bao nhiêu?
Câu 5.3: Trong bài toán Balo 0/1 có $N \le 100$, nhưng trọng lượng $W \le 10^9$ và tổng giá trị $\sum V_i \le 10^5$. Cách đổi chiều trạng thái DP nào giúp giải bài toán này?
Câu 5.4: Để truy vết nghiệm tối ưu (tìm danh sách cụ thể các phần tử được chọn) sau khi hoàn tất bảng quy hoạch động, ta thường thực hiện thao tác gì?
Quy Hoạch Động Nâng Cao (Bitmask, Tree DP & Digit DP)
Để đạt giải Nhất Tỉnh hoặc giải Quốc gia (VOI), thí sinh cần bứt phá ở các bài toán Quy hoạch động nâng cao. Dấu hiệu đặc trưng: giới hạn $N$ nhỏ ($N \le 20$) gợi ý Bitmask DP, dữ liệu dạng cây tự do gợi ý Tree DP, hoặc đếm số lượng số trong khoảng $[A, B]$ thỏa mãn tính chất gợi ý Digit DP.
Quy Hoạch Động Trạng Thái Bit (Bitmask DP)
Sử dụng các bit nhị phân $0$ và $1$ của một số nguyên biểu diễn tập hợp con của $N$ phần tử ($N \le 20$). Số trạng thái là $2^N$. Các thao tác bit: kiểm tra phần tử $i$ có trong mask: (mask >> i) & 1; thêm phần tử $i$: mask | (1 << i); tắt phần tử: mask & ~(1 << i). Điển hình: Bài toán người du lịch (TSP) $O(2^N \times N^2)$.
Quy Hoạch Động Trên Cây (Tree DP & Rerooting)
Thực hiện DFS duyệt cây từ dưới lên (Bottom-up). Trạng thái dp[u] được tính dựa trên kết quả của tất cả các nút con dp[v] của $u$. Kỹ thuật Rerooting DP (Quy hoạch động đổi gốc) giúp tính đáp án cho mọi đỉnh đóng vai trò là gốc cây trong thời gian tổng $O(N)$ thay vì $O(N^2)$.
Bài Tập Trắc Nghiệm Thuật Toán (Bài 6)
Câu 6.1: Biểu thức thao tác bit nào trong C++ dùng để kiểm tra xem bit thứ $k$ (tính từ 0) của số nguyên mask có đang bật (bằng 1) hay không?
Câu 6.2: Trong bài toán đếm số lượng các số nguyên thuộc đoạn $[A, B]$ ($1 \le A \le B \le 10^{18}$) có tổng các chữ số chia hết cho 13, phương pháp nào là chuẩn mực?
Câu 6.3: Độ phức tạp thời gian khi giải bài toán Người du lịch (TSP) có $N \le 20$ đỉnh bằng Quy hoạch động Bitmask là:
Câu 6.4: Trong một cây tự do $N$ đỉnh, ta cần tính tổng khoảng cách từ đỉnh $u$ đến tất cả các đỉnh còn lại cho mọi $u \in [1, N]$. Kỹ thuật nào tối ưu nhất?
Lý Thuyết Đồ Thị Cơ Bản (Graph: BFS, DFS, Dijkstra & Kruskal)
Lý thuyết đồ thị là một nửa linh hồn của lập trình thi đấu. Một bài thi HSG Tin học THPT hầu như luôn có ít nhất 1 bài thuần đồ thị hoặc quy về mô hình đồ thị. Thí sinh phải cài đặt trơn tru danh sách kề vector<pair<int, int>> adj[], Dijkstra với hàng đợi ưu tiên và cấu trúc dữ liệu các tập không giao nhau DSU.
| Thuật toán | Mục đích bài toán | Độ phức tạp | Lưu ý quan trọng |
|---|---|---|---|
| BFS (Breadth-First Search) | Đường đi ngắn nhất trên đồ thị trọng số bằng nhau (hoặc trọng số 0-1 dùng deque) | O(V + E) | Dùng std::queue, đánh dấu visited ngay khi đẩy vào queue |
| Dijkstra | Đường đi ngắn nhất nguồn đơn từ đỉnh S trên đồ thị trọng số không âm | O((V + E) log V) | Dùng priority_queue<..., greater>, kiểm tra if (d > dist[u]) continue; |
| Kruskal (MST) + DSU | Cây khung nhỏ nhất (Minimum Spanning Tree) | O(E log E) | Cài DSU với Path Compression và Union by Rank ($O(\alpha(V))$) |
| Topological Sort (Kahn) | Thứ tự thực hiện công việc trên đồ thị có hướng không chu trình (DAG) | O(V + E) | Dùng mảng bán bậc vào in_degree[] và hàng đợi |
Bài Tập Trắc Nghiệm Thuật Toán (Bài 7)
Câu 7.1: Thuật toán Dijkstra tìm đường đi ngắn nhất có thể cho kết quả sai trong trường hợp nào sau đây?
Câu 7.2: Trong Cấu trúc dữ liệu các tập không giao nhau (Disjoint Set Union - DSU), hai kỹ thuật tối ưu hóa nào giúp giảm thời gian mỗi phép tìm kiếm và hợp nhất xuống gần như hằng số $O(alpha(N))$?
Câu 7.3: Trên đồ thị vô hướng có trọng số các cạnh chỉ nhận một trong hai giá trị là $0$ hoặc $1$, thuật toán tìm đường đi ngắn nhất nào tối ưu nhất với độ phức tạp tuyến tính $O(V + E)$?
Câu 7.4: Để kiểm tra xem một đồ thị vô hướng có phải là Đồ thị hai phía (Bipartite Graph / 2-colorable) hay không, ta sử dụng thuật toán nào?
Đồ Thị Nâng Cao (Tarjan Khớp-Cầu, SCC & Tổ Tiên Chung LCA)
Các chuyên đề đồ thị nâng cao là thước đo phân hóa huy chương trong kỳ thi chọn Học sinh giỏi Quốc gia (VOI) và VNOI Cup. Hai thuật toán nổi bật nhất là Thuật toán Tarjan (tìm Khớp, Cầu, Thành phần liên thông mạnh SCC trong $O(V + E)$) và Nhảy nhị phân (Binary Lifting) tìm Tổ tiên chung gần nhất (LCA) trên cây trong $O(log N)$.
Tarjan: Cầu & Khớp (Bridges & Articulation Points)
Xây dựng DFS Tree và gán nhãn thời gian thăm tin[u] cùng giá trị low[u] (thời gian thăm nhỏ nhất của đỉnh mà từ con cháu của $u$ có thể đi tới qua cạnh ngược Back-edge). Cạnh $(u, v)$ là Cầu khi và chỉ khi low[v] > tin[u]. Đỉnh $u$ là Khớp khi $u$ là gốc có $\ge 2$ con độc lập, hoặc $u$ không là gốc và tồn tại con $v$ sao cho low[v] ≥ tin[u].
Nhảy Nhị Phân & LCA (Binary Lifting)
Khởi tạo bảng up[u][j] là tổ tiên thứ $2^j$ của đỉnh $u$: up[u][j] = up[up[u][j - 1]][j - 1] trong $O(N \log N)$. Để tìm LCA của $(u, v)$, trước hết nâng đỉnh sâu hơn lên cùng độ cao với đỉnh nông hơn, sau đó đồng thời nhảy các bước lũy thừa của 2 từ lớn đến nhỏ. Thời gian truy vấn mỗi cặp đỉnh chỉ mất $O(\log N)$.
Bài Tập Trắc Nghiệm Thuật Toán (Bài 8)
Câu 8.1: Trong thuật toán Tarjan trên đồ thị vô hướng, điều kiện để cạnh nối từ nút cha $u$ đến nút con $v$ ($v$ là con của $u$ trên cây DFS) là một "CẦU" (Bridge) là gì?
Câu 8.2: Khi thu gọn từng Thành phần liên thông mạnh (SCC) của một đồ thị có hướng thành một siêu đỉnh (Condensation Graph), đồ thị thu được luôn luôn có tính chất gì?
Câu 8.3: Cho cây $N$ đỉnh. Để tìm Tổ tiên chung gần nhất (LCA) của $Q$ truy vấn cặp đỉnh $(u, v)$ ($N, Q \le 2 \times 10^5$), phương pháp Nhảy nhị phân (Binary Lifting) có độ phức tạp thời gian là:
Câu 8.4: Khoảng cách (số cạnh) giữa hai đỉnh $u$ và $v$ bất kỳ trên cây có gốc với mảng độ sâu depth[] được tính qua LCA là:
Cấu Trúc Dữ Liệu Nâng Cao (Fenwick Tree, Segment Tree & Trie)
Nếu mảng cộng dồn chỉ hỗ trợ truy vấn nhanh khi mảng tĩnh, thì Cây Fenwick (Binary Indexed Tree - BIT) và Cây phân đoạn (Segment Tree / Interval Tree) cho phép cập nhật phần tử và truy vấn đoạn liên tục trong thời gian $O(log N)$. Đặc biệt, kỹ thuật Lazy Propagation (Cập nhật lười) là "chìa khóa vàng" giải các bài toán cập nhật đoạn và truy vấn đoạn trong đề thi VOI.
| Cấu trúc | Dung lượng bộ nhớ | Cập nhật điểm / Truy vấn đoạn | Cập nhật đoạn / Truy vấn đoạn | Ưu điểm & Nhược điểm |
|---|---|---|---|---|
| Fenwick Tree (BIT) | O(N) (1 mảng duy nhất) | O(log N) | O(log N) (cần 2 cây BIT) | Cực kỳ ngắn gọn (chỉ ~10 dòng code), hằng số tốc độ siêu nhỏ; khó áp dụng cho phép toán không có tính khả nghịch. |
| Segment Tree thường | O(4N) | O(log N) | O(N log N) nếu lặp từng điểm | Đa năng: giải quyết được Max, Min, GCD, Tổng, Matrix Multi; code dài hơn BIT. |
| Segment Tree + Lazy Propagation | O(4N) (cần mảng tree[] và lazy[]) | O(log N) | O(log N) | Vũ khí tối thượng xử lý Range Update & Range Query; cần cẩn trọng kỹ thuật đẩy nhãn pushDown(). |
| Trie (Cây tiền tố & Bitwise Trie) | O(Tổng độ dài chuỗi) với bảng con truy cập O(1); bộ nhớ có thể O(số nút * Alphabet) | O(|S|) thêm chuỗi | O(31) tìm max XOR cặp số | Tra cứu tiền tố từ điển, giải quyết bài toán XOR lớn nhất của 2 số trong mảng $O(31 \times N)$. |
#include <bits/stdc++.h>
using namespace std;
struct FenwickTree {
int n;
vector<long long> bit;
FenwickTree(int n) : n(n), bit(n + 1, 0) {}
// Cộng thêm delta vào phần tử vị trí idx (1-indexed)
void add(int idx, long long delta) {
for (; idx <= n; idx += idx & (-idx)) {
bit[idx] += delta;
}
}
// Tính tổng các phần tử từ vị trí 1 đến idx
long long query(int idx) {
long long sum = 0;
for (; idx > 0; idx -= idx & (-idx)) {
sum += bit[idx];
}
return sum;
}
// Tính tổng đoạn [l, r]
long long queryRange(int l, int r) {
return query(r) - query(l - 1);
}
};Bài Tập Trắc Nghiệm Thuật Toán (Bài 9)
Câu 9.1: Biểu thức bitwise idx & (-idx) trong cấu trúc Cây Fenwick (BIT) có ý nghĩa toán học là gì?
Câu 9.2: Khi cài đặt Cây phân đoạn (Segment Tree) bằng mảng 1D cho mảng dữ liệu ban đầu có $N$ phần tử, kích thước tối thiểu an toàn để khai báo mảng tree[] nhằm tránh lỗi tràn bộ nhớ (Out of bounds) là:
Câu 9.3: Bản chất của kỹ thuật "Lazy Propagation" (Cập nhật lười) trong Cây phân đoạn là gì?
Câu 9.4: Để tìm cặp 2 số trong mảng $N$ phần tử ($N \le 2 \times 10^5$, $a_i < 2^{30}$) có phép XOR ($a_i \oplus a_j$) đạt giá trị lớn nhất, cấu trúc dữ liệu nào giúp giải trong thời gian $O(30 \times N)$?
Xử Lý Chuỗi, Hình Học Tọa Độ & Chiến Lược 180 Phút Phòng Thi
Chuyên đề cuối cùng trang bị 2 mảng kiến thức nâng cao là Thuật toán chuỗi (Rolling Hash, KMP, Z-algo), Hình học tính toán (Bao lồi Convex Hull, Tích có hướng) cùng bộ cẩm nang chiến lược quản lý thời gian thi đấu để tối đa hóa từng điểm số subtask.
Băm Chuỗi Đa Thức (Double Rolling Hash)
Chuyển chuỗi thành mã băm tiền tố $hash[i] = (hash[i-1] \times B + s[i]) \pmod M$. Lấy mã băm đoạn con $[L, R]$ trong $O(1)$: $hash(L, R) = (hash[R] - hash[L-1] \times B^{R-L+1}) \pmod M$. Nên cân nhắc dùng hai hàm băm độc lập (ví dụ $M_1 = 10^9+7, M_2 = 10^9+9$) để giảm rủi ro đụng độ trong mô hình băm phù hợp; double hash không loại bỏ hoàn toàn đụng độ hay tấn công có chủ đích.
Hình Học: Tích Có Hướng (Cross Product)
Cho 3 điểm $A, B, C$. Tích có hướng $\vec{AB} \times \vec{AC} = (B_x - A_x)(C_y - A_y) - (B_y - A_y)(C_x - A_x)$. Nếu $> 0$: $C$ rẽ trái; $< 0$: $C$ rẽ phải; $= 0$: thẳng hàng. Đây là nền tảng xây dựng thuật toán Bao lồi (Monotone Chain / Graham Scan) trong $O(N \log N)$.
Chiến Lược Vàng Phân Bổ 180 Phút Phòng Thi HSG
long long, tên file INP/OUT, xóa lệnh in debug thừa.
Bài Tập Trắc Nghiệm Thuật Toán (Bài 10)
Câu 10.1: Vì sao trong các kỳ thi học sinh giỏi, khi sử dụng thuật toán Băm chuỗi (Rolling Hash) so khớp chuỗi, thí sinh được khuyến cáo nên dùng "Double Hash" (2 mod khác nhau) thay vì "Single Hash" (1 mod như $10^9+7$)?
Câu 10.2: Thuật toán KMP (Knuth-Morris-Pratt) tìm kiếm chuỗi mẫu độ dài $M$ trong văn bản độ dài $N$ có độ phức tạp thời gian trong trường hợp xấu nhất là bao nhiêu?
Câu 10.3: Trong hình học tính toán, giá trị tích có hướng (Cross Product) của hai vectơ $\vec{u} \times \vec{v} = 0$ mang ý nghĩa gì?
Câu 10.4: Trong một bài toán khó của đề thi HSG Quốc gia mà bạn chưa nghĩ ra thuật toán tối ưu $100%$ điểm, chiến thuật khôn ngoan nhất để đạt điểm cao là gì?
Sẵn Sàng Chinh Phục Đỉnh Cao Học Sinh Giỏi Tin Học THPT!
Bạn đã đi qua toàn bộ 10 chuyên đề thuật toán cốt lõi: từ nền tảng C++20 tối ưu, kỹ thuật hai con trỏ, chặt nhị phân, số học, quy hoạch động đa chiều, lý thuyết đồ thị chuyên sâu, cấu trúc dữ liệu Segment Tree / Fenwick đến xử lý chuỗi và chiến thuật phòng thi 180 phút. Hãy kiên trì luyện tập trên các nền tảng online judge uy tín như VNOJ, Codeforces, AtCoder và CSES Problem Set để biến kiến thức thành phản xạ vô điều kiện!