Bài 1: Trùng khớp chuỗi với hoán vị vòng quanh
Để xác định số lần một chuỗi xuất hiện dưới dạng dịch vòng trong một chuỗi khác, ta có thể tận dụng kỹ thuật Rolling Hash. Đầu tiên, nối chuỗi nguồn với chính nó và dùng cửa sổ trượt kích thước bằng độ dài gốc để tính hash cho mọi biến thể vòng quanh, lưu kết quả vào tập hợp tìm kiếm. Sau đó, áp dụng cùng kích thước cửa sổ lên chuỗi đích, kiểm tra từng giá trị hash đã tính có tồn tại trong tập hợp hay không để tích lũy kết quả. Phép cộng tự nhiên của kiểu số nguyên không dấu giúp xử lý modulo ngầm định, đơn giản hóa việc cài đặt.
Xem mã nguồn
#include <iostream>
#include <set>
#include <string>
using namespace std;
set<unsigned long long> hash_pool;
const int BASE = 31337;
unsigned long long pow_base[2000005];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int test_cases;
cin >> test_cases;
pow_base[0] = 1;
for (int i = 1; i <= 2000000; ++i) pow_base[i] = pow_base[i - 1] * BASE;
while (test_cases--) {
hash_pool.clear();
string src, target;
cin >> src >> target;
int len_src = src.length();
int len_tgt = target.length();
src = src + src;
src = " " + src;
target = " " + target;
unsigned long long current_hash = 0;
for (int i = 1; i < len_src; ++i) {
current_hash = current_hash * BASE + (unsigned char)(src[i]) - 'A' + 1;
}
for (int i = 1; i <= len_src; ++i) {
int end_idx = i + len_src - 1;
current_hash = current_hash * BASE + (unsigned char)(src[end_idx]) - 'A' + 1;
hash_pool.insert(current_hash);
current_hash -= pow_base[len_src - 1] * ((unsigned char)(src[i]) - 'A' + 1);
}
current_hash = 0;
long long match_count = 0;
for (int i = 1; i < len_src; ++i) {
current_hash = current_hash * BASE + (unsigned char)(target[i]) - 'A' + 1;
}
for (int i = 1; i + len_src - 1 <= len_tgt; ++i) {
int end_idx = i + len_src - 1;
current_hash = current_hash * BASE + (unsigned char)(target[end_idx]) - 'A' + 1;
match_count += hash_pool.count(current_hash);
current_hash -= pow_base[len_src - 1] * ((unsigned char)(target[i]) - 'A' + 1);
}
cout << match_count << "\n";
}
return 0;
}Bài 2: Lập quy hoạch động dạng Nạp balo đa lựa chọn
Bài toán có thể chuyển về mô hình Nạp balo với ràng buộc chính xác. Mỗi vật phẩm cung cấp đúng bốn tùy chọn khối lượng (1, 2, 3, 4 đơn vị) kèm theo chi phí tương ứng. Ta xây dựng bảng trạng thái `memo[i][j]` lưu chi phí tối thiểu để đạt trọng lượng chính xác `j` sau khi xét `i` vật phẩm đầu. Quá trình cập nhật bảng sẽ duyệt qua tất cả các tùy chọn khả thi, lấy giá trị nhỏ nhất từ trạng thái trước đó cộng với chi phí hiện tại. Khởi tạo bảng với giá trị vô hạn và gán `memo[0][0] = 0` để đảm bảo tính đúng đắn.
Xem mã nguồn
#include <iostream>
using namespace std;
#define int long long
const int INF = 4e18;
int memo[1005][4005];
int cost_options[1005][5];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int N, K;
cin >> N >> K;
for (int i = 0; i <= N; ++i)
for (int j = 0; j <= K; ++j)
memo[i][j] = INF;
memo[0][0] = 0;
for (int i = 1; i <= N; ++i) {
for (int k = 1; k <= 4; ++k) {
cin >> cost_options[i][k];
}
}
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= 4000; ++j) {
memo[i][j] = memo[i - 1][j];
for (int k = 1; k <= 4; ++k) {
if (j >= k && memo[i - 1][j - k] != INF) {
memo[i][j] = min(memo[i][j], memo[i - 1][j - k] + cost_options[i][k]);
}
}
}
}
cout << memo[N][K] << "\n";
}
return 0;
}Bài 3:树上启发式合并 kết hợp Fenwick Tree
Biểu thức mục tiêu chứa hàm `max` và giá trị tuyệt đối, khiến việc tính toán trực tiếp trở nên phức tạp. Bằng cách tách biệt các khoảng giá trị, ta nhận thấy chỉ cần duy trì bốn thông tin thống kê đối với mỗi ngưỡng tham chiếu `val`: số lượng, tổng, và tổng bình phương của các phần tử nhỏ hơn và lớn hơn `val`. Điều này cho phép cập nhật giá trị mục tiêu trong thời gian `O(1)` khi thêm hoặc xóa phần tử. Kết hợp kỹ thuật DSU on Tree để quản lý không gian con của cây với cấu trúc Fenwick Tree kép (một cho tiền tố, một cho hậu tố), độ phức tạp toàn cục được đẩy xuống `O(n log^2 n)`.
Xem mã nguồn
#include <iostream>
#include <vector>
using namespace std;
#define int long long
#define lowbit(x) ((x) & (-(x)))
int N;
unsigned long long node_val[500005];
vector<int> adj[500005];
int sub_size[500005], heavy_child[500005];
int entry_time[500005], exit_time[500005], timer;
int flat_tree[500005];
void dfs_build(int u, int p) {
sub_size[u] = 1;
entry_time[u] = ++timer;
flat_tree[timer] = u;
for (int v : adj[u]) {
if (v != p) {
dfs_build(v, u);
sub_size[u] += sub_size[v];
if (sub_size[v] > sub_size[heavy_child[u]])
heavy_child[u] = v;
}
}
exit_time[u] = timer;
}
struct FenwickPair {
pair<unsigned long long, unsigned long long> prefix[1000005];
pair<unsigned long long, unsigned long long> suffix[1000005];
pair<unsigned long long, unsigned long long> query_prefix(int idx) {
pair<unsigned long long, unsigned long long> res(0, 0);
for (; idx; idx -= lowbit(idx)) {
res.first += prefix[idx].first;
res.second += prefix[idx].second;
}
return res;
}
pair<unsigned long long, unsigned long long> query_suffix(int idx) {
pair<unsigned long long, unsigned long long> res(0, 0);
for (; idx <= 1000000; idx += lowbit(idx)) {
res.first += suffix[idx].first;
res.second += suffix[idx].second;
}
return res;
}
void update(int idx, unsigned long long val) {
unsigned long long base = idx;
for (int i = idx; i <= 1000000; i += lowbit(i)) {
prefix[i].first += val;
prefix[i].second += base * val;
}
for (int i = idx; i; i -= lowbit(i)) {
suffix[i].first += base * val;
suffix[i].second += base * base * val;
}
}
} fenwick;
unsigned long long current_score = 0;
void apply_node(int u, int sign = 1) {
unsigned long long val = node_val[u];
auto lower = fenwick.query_prefix(val - 1);
auto upper = fenwick.query_suffix(val + 1);
current_score += sign * (val * (val * lower.first - lower.second) + upper.second - val * upper.first);
fenwick.update(val, (unsigned long long)sign);
}
void add_subtree(int u) {
for (int i = entry_time[u]; i <= exit_time[u]; ++i) apply_node(flat_tree[i], 1);
}
void remove_subtree(int u) {
for (int i = entry_time[u]; i <= exit_time[u]; ++i) apply_node(flat_tree[i], -1);
}
unsigned long long final_answer = 0;
void dfs_heavy(int u, int p, bool keep) {
for (int v : adj[u]) {
if (v != p && v != heavy_child[u])
dfs_heavy(v, u, false);
}
if (heavy_child[u]) dfs_heavy(heavy_child[u], u, true);
apply_node(u, 1);
for (int v : adj[u]) {
if (v != p && v != heavy_child[u]) add_subtree(v);
}
final_answer ^= current_score * 2;
if (!keep) remove_subtree(u);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
for (int i = 0; i < N - 1; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= N; ++i) cin >> node_val[i];
dfs_build(1, 0);
dfs_heavy(1, 0, false);
cout << final_answer << "\n";
return 0;
}Bài 4: Chia để trị trên đoạn với Rollback DSU có Lazy Tag
Áp dụng phương pháp Segment Tree Divide & Conquer để xử lý các truy vấn trên khoảng thời gian rời rạc. Tại mỗi nút của cây phân đoạn, ta cần một cấu trúc liên kết hỗ trợ hoàn trạng thái (Rollback DSU). Yếu tố then chốt là yêu cầu cộng dồn một giá trị cố định cho toàn bộ tập hợp. Giải pháp sử dụng cơ chế đánh dấu trì hoãn (lazy tag) gắn kèm theo gốc tập. Khi tách một tập con ra khỏi tập mẹ, giá trị lazy sẽ được đẩy xuống tập con. Ngược lại, khi hợp nhất hai tập, ta trừ đi giá trị lazy của tập mẹ khỏi tập con trước khi nối, nhằm loại bỏ ảnh hưởng trùng lặp lên các phần tử mới tham gia. Kỹ thuật này duy trì khả năng hoàn trạng thái đồng thời đảm bảo tính chính xác của các phép cập nhật hàng loạt.
Bài 6: Đếm dãy con đồng nhất ba chiều
Bài toán yêu cầu tìm số cách chọn ba dãy con có nội dung giống hệt nhau từ ba mảng đồng nhất. Đây là dạng mở rộng của bài toán đếm dãy con chung. Định nghĩa trạng thái `dp[i][j][k]` là số lượng cách khớp khi xét đến vị trí thứ `i, j, k` của ba mảng. Để tránh độ phức tạp quá cao khi chuyển trạng thái, ta sử dụng nguyên lý bao-hoại để tính tổng tiền tố ba chiều. Công thức cập nhật sẽ cộng dồn các trạng thái liền kề, trừ đi phần giao chồng chéo, và thêm trực tiếp vào kết quả nếu giá trị tại ba vị trí hiện tại trùng khớp. Phép toán modulo được áp dụng xuyên suốt để ngăn tràn số.
Xem mã nguồn
#include <iostream>
using namespace std;
#define int long long
const int MOD = 998244353;
int N;
int dp[255][255][255];
int arr[255];
int normalize(int val) {
return (val % MOD + MOD) % MOD;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
for (int i = 1; i <= N; ++i) cin >> arr[i];
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
for (int k = 1; k <= N; ++k) {
int base = dp[i - 1][j][k] + dp[i][j - 1][k] + dp[i][j][k - 1]
- dp[i - 1][j - 1][k] - dp[i - 1][j][k - 1] - dp[i][j - 1][k - 1]
+ dp[i - 1][j - 1][k - 1];
dp[i][j][k] = normalize(base);
if (arr[i] == arr[j] && arr[j] == arr[k]) {
dp[i][j][k] = normalize(dp[i][j][k] + dp[i - 1][j - 1][k - 1] + 1);
}
}
}
}
cout << dp[N][N][N] << "\n";
return 0;
}Bài 7: Đếm tam giác có hướng bằng phương pháp bù trừ
Thay vì đếm trực tiếp các tam giác có hướng, ta áp dụng tư duy bù trừ. Tổng số bộ ba đỉnh bất kỳ trong đồ thị là `n*(n-1)*(n-2)/6`. Một bộ ba không tạo thành chu trình khi và chỉ khi tồn tại một đỉnh trong bộ đó nhận đúng hai cung vào từ hai đỉnh còn lại. Việc đếm các cấu hình "hư" này quy về bài toán thống kê bậc vào theo hai chiều tọa độ. Ta sử dụng kỹ thuật CDQ Divide & Conquer kết hợp với Cây Fenwick để xử lý thứ tự ba chiều một cách hiệu quả. Sau khi thu được số lượng bộ ba không đóng, chỉ cần trừ khỏi tổng ban đầu là ra đáp án chính xác.
Xem mã nguồn
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long
#define lowbit(x) ((x) & (-(x)))
int N;
struct Element {
int id, x, y;
} data[200005];
int left_count[200005], right_count[200005];
int *current_counts;
struct Fenwick {
int tree[200005];
void add(int idx, int val) {
for (; idx <= 200000; idx += lowbit(idx)) tree[idx] += val;
}
int query(int idx) {
int res = 0;
for (; idx; idx -= lowbit(idx)) res += tree[idx];
return res;
}
void clear(int idx) {
for (; idx <= 200000; idx += lowbit(idx)) tree[idx] = 0;
}
} fenwick;
void cdq_solve(int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
cdq_solve(l, mid);
cdq_solve(mid + 1, r);
int ptr = l;
for (int i = mid + 1; i <= r; ++i) {
while (ptr <= mid && data[ptr].x < data[i].x) {
fenwick.add(data[ptr].y, 1);
++ptr;
}
current_counts[data[i].id] += fenwick.query(data[i].y - 1);
}
for (int i = l; i < ptr; ++i) fenwick.clear(data[i].y);
sort(data + l, data + r + 1, [](const Element &a, const Element &b) {
return a.x < b.x;
});
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
if (N <= 2) {
cout << 0 << "\n";
return 0;
}
for (int i = 1; i <= N; ++i) cin >> data[i].x;
for (int i = 1; i <= N; ++i) cin >> data[i].y, data[i].id = i;
current_counts = left_count;
cdq_solve(1, N);
sort(data + 1, data + N + 1, [](const Element &a, const Element &b) {
return a.id > b.id;
});
for (int i = 1; i <= N; ++i) {
data[i].x = N - data[i].x + 1;
data[i].y = N - data[i].y + 1;
}
current_counts = right_count;
cdq_solve(1, N);
int total_triples = N * (N - 1) * (N - 2) / 6;
for (int i = 1; i <= N; ++i) {
int L = left_count[i];
int R = N - i - right_count[i];
total_triples -= L * (L - 1) / 2 + R * (R - 1) / 2 + L * R;
}
cout << total_triples << "\n";
return 0;
}Bài 8: Phân tích tổ hợp theo từng bit
Tính chất độc lập từng bit của các phép toán bitwise cho phép tách bài toán thành nhiều bài con nhỏ hơn. Xét từng vị trí bit của tham số đầu vào, nếu bit đó bằng `0` thì số cách cấu hình hợp lệ tại vị trí đó là `4`. Ngược lại, nếu bit bằng `1` thì số cách là `12`. Do các vị trí bit không ảnh hưởng lẫn nhau, đáp án cuối cùng chính là tích của số cách chọn trên tất cả các vị trí bit được yêu cầu xử lý. Việc thực hiện chỉ cần một vòng lặp đơn giản duyệt qua các bit.
Xem mã nguồn
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, bits;
cin >> n >> bits;
long long result = 1;
for (int b = 0; b < bits; ++b) {
if ((n >> b) & 1) {
result *= 12;
} else {
result *= 4;
}
}
cout << result << "\n";
}
return 0;
}Bài 12: Rời rạc hóa tọa độ kết hợp tổ hợp chập k
Không gian hình học được rời rạc hóa bằng cách gom các tọa độ trùng lặp hoặc liền kề để giảm kích thước xuống mức có thể xử lý được. Sử dụng mảng hiệu 2 chiều kết hợp với tính tiền tố để xác định chính xác số lần mỗi ô đơn vị bị bao phủ bởi các hình chữ nhật. Các khu vực có cùng số lần bao phủ sẽ đóng góp đồng đều vào kết quả, nên ta gom nhóm chúng lại theo tần suất. Cuối cùng, duyệt qua từng giá trị `k` mục tiêu và áp dụng công thức tổ hợp chập `k` để tính tổng đóng góp. Bảng giai thừa và nghịch đảo modulo được tiền xử lý để các phép tính tổ hợp được thực hiện nhanh chóng trong `O(1)`.
Xem mã nguồn
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define int long long
const int MOD = 998244353;
int N;
int x1[2005], y1[2005], x2[2005], y2[2005];
vector<int> coords_x, coords_y;
int grid[4005][4005];
int area_by_cov[2005];
int fact[4005], inv[4005], ifact[4005];
void precompute_comb(int limit) {
fact[0] = inv[0] = ifact[0] = 1;
for (int i = 1; i <= limit; ++i) {
fact[i] = fact[i - 1] * i % MOD;
inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
ifact[i] = ifact[i - 1] * inv[i] % MOD;
}
}
int nCr(int n, int r) {
if (r < 0 || r > n) return 0;
return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
precompute_comb(4000);
cin >> N;
for (int i = 1; i <= N; ++i) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
coords_x.push_back(x1[i]); coords_x.push_back(x2[i]);
coords_y.push_back(y1[i]); coords_y.push_back(y2[i]);
}
sort(coords_x.begin(), coords_x.end());
coords_x.erase(unique(coords_x.begin(), coords_x.end()), coords_x.end());
sort(coords_y.begin(), coords_y.end());
coords_y.erase(unique(coords_y.begin(), coords_y.end()), coords_y.end());
auto get_idx = [&](const vector<int>& vec, int val) {
return lower_bound(vec.begin(), vec.end(), val) - vec.begin() + 1;
};
map<int, int> comp_x, comp_y;
for (int i = 0; i < (int)coords_x.size(); ++i) comp_x[coords_x[i]] = i + 1;
for (int i = 0; i < (int)coords_y.size(); ++i) comp_y[coords_y[i]] = i + 1;
for (int i = 1; i <= N; ++i) {
int ux1 = comp_x[x1[i]], uy1 = comp_y[y1[i]];
int ux2 = comp_x[x2[i]], uy2 = comp_y[y2[i]];
grid[ux1][uy1]++;
grid[ux2][uy1]--;
grid[ux1][uy2]--;
grid[ux2][uy2]++;
}
int nx = comp_x.size(), ny = comp_y.size();
for (int i = 1; i <= nx; ++i) {
for (int j = 1; j <= ny; ++j) {
grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1];
}
}
for (int i = 1; i < nx; ++i) {
for (int j = 1; j < ny; ++j) {
long long area = (long long)(coords_x[i] - coords_x[i - 1]) * (coords_y[j] - coords_y[j - 1]);
area_by_cov[grid[i][j]] += area;
}
}
for (int k = 1; k <= N; ++k) {
int total = 0;
for (int c = 1; c <= N - k; ++c) {
if (area_by_cov[c] == 0) continue;
int ways = nCr(N - c, N - k);
total = (total + area_by_cov[c] % MOD * (MOD + 1 - ways) % MOD) % MOD;
}
for (int c = N - k + 1; c <= N; ++c) {
total = (total + area_by_cov[c]) % MOD;
}
cout << total << "\n";
}
return 0;
}