Bài viết tổng hợp các giải pháp và mã nguồn cho một số bài toán trong quá trình luyện tập hướng tới kỳ thi NOI 2026. Các thuật toán được thiết kế tối ưu về độ phức tạp và sử dụng kỹ thuật nâng cao như Boruvka, DDP, Trie, phân tích cấu trúc cây, và xử lý truy vấn offline.
A. Giao tiếp đa chiều (Boruvka + nén thông tin)
Sử dụng thuật toán Boruvka để xây dựng cây khung nhỏ nhất trong môi trường giao tiếp hạn chế. Mỗi vòng lặp, mỗi nút gửi thông tin về thành phần liên thông hiện tại và cạnh nhỏ nhất ra ngoài. Tận dụng không gian bit để nén dữ liệu, giảm số vòng truyền từ 9 xuống còn 5–6 nhờ tối ưu hóa đầu cuối.
#include <bits/stdc++.h>
#include "multi.h"
using namespace std;
using ull = unsigned long long;
const ull INF = (1LL << 48) - 1;
struct Edge {
ull weight;
int from, to;
};
vector<ull> strategy(int n, int round, int self, vector<ull> a, vector<ull> b) {
if (round == 0) {
vector<Edge> edges;
for (int j = 0; j < n; ++j)
if (j != self) edges.push_back({a[j], j, self});
sort(edges.begin(), edges.end(), [](auto& x, auto& y) { return x.weight < y.weight; });
if (edges.size() > 1) edges.resize(2);
return vector<ull>(n, (edges[1].weight << 16) | (edges[1].from << 8) | edges[0].from);
}
vector<int> parent(n), used(n);
iota(parent.begin(), parent.end(), 0);
auto find_root = [&](int u) {
while (parent[u] != u) u = parent[u] = parent[parent[u]];
return u;
};
ull total_weight = (round > 1 ? b[self] >> 8 : 0);
if (round == 5) {
int comp_count = b[self] & 255;
vector<Edge> inter_edges;
for (int i = 0, idx = 1; i < comp_count; ++i)
for (int j = i + 1; j < comp_count; ++j, ++idx)
inter_edges.push_back({b[idx], i, j});
sort(inter_edges.begin(), inter_edges.end(), [](auto& x, auto& y) { return x.weight < y.weight; });
for (auto& e : inter_edges)
if (find_root(e.from) != find_root(e.to)) {
parent[find_root(e.from)] = find_root(e.to);
total_weight += e.weight;
}
return {total_weight};
}
// Xử lý các vòng lặp trung gian với cập nhật cây khung
// ... (logic tương tự nhưng rút gọn và đổi tên biến)
return {};
}
B. Cây lưới (Cân bằng cây nhị phân)
Kiểm tra điều kiện hợp lệ của cây: tại mỗi độ sâu i, số nút không vượt quá i+1. Sử dụng cây Cartesian hoặc treap để duy trì mảng sai phân, hỗ trợ thao tác chèn/xóa và truy vấn giá trị lớn nhất hiệu quả.
void dfs(int node) {
if (!child[node][0]) return;
for (int kid : child[node]) {
dfs(kid);
max_depth[node] = max(max_depth[node], max_depth[kid] + edge_weight[kid]);
}
// Cập nhật offset và hợp nhất hai nhánh con
// ...
}
C. Sắp xếp (Cấu trúc cây so sánh)
Xây dựng cây so sánh bằng cách chọn hai gốc X, Y sao cho a[X] ≥ a[Y], đảm bảo gốc không nằm trong tập độc lập lớn nhất. Sau đó áp dụng kỹ thuật trộn (merge sort) trên các vị trí chẵn/lẻ, giảm số lần hỏi xuống O(log²n).
void merge_phase(int depth) {
if (depth == 0) {
// So sánh từng cặp kề
return;
}
// Chia dãy, đệ quy, rồi trộn lại
// ...
}
D. Cửa sổ trượt cuối cùng (Cây Fenwick 2D)
Sử dụng cây BIT kép để xử lý truy vấn dạng "tổng giá trị trong vùng giao giữa cây Cartesian và đoạn [L,R]". Phân tách truy vấn thành các sự kiện thêm/xóa và xử lý offline theo thứ tự tăng dần của chỉ số phải.
E. Tô màu XOR (Trie phân tầng)
Duyệt trie theo bit cao nhất. Nếu bit đó của X là 0, xử lý độc lập hai nhánh. Nếu là 1 và tồn tại cả hai loại bit trong B, tính số phần tử có thể tô cùng màu ở hai bên. Trường hợp chỉ có một loại, xử lý đệ quy với cờ đánh dấu.
F. Vòng tròn bò (Quy hoạch động tuyến tính)
Mỗi trạng thái là một hoán vị vòng quanh. Dùng cây phân đoạn để duy trì mảng DP, trong đó mỗi nút lưu đa thức đặc trưng cho xác suất dịch chuyển. Kết quả thu được bằng cách đếm số lần cạnh (n-1,0) được đi qua.
G. Mưa rơi tam giác (ODT + bao phủ hình chữ nhật)
Với mỗi tam giác biểu diễn dưới dạng x≥a, y≥b, x+y≤c, dùng kỹ thuật quét theo c giảm dần. Duy trì danh sách các đoạn thẳng y = f(x) bằng ODT (Ordered Dynamic Tree). Khi thêm hình chữ nhật mới, cập nhật vùng giao và lan truyền sang lớp k+1.
H. Hành trình JOI 2 (Phân khối + tiền xử lý)
Biểu diễn đường đi trên cây bằng dãy DFS in/out. Với mỗi truy vấn, tách thành tổ hợp các đường đến gốc. Dùng kỹ thuật phân khối: khối nguyên xử lý offline bằng mảng đếm, khối lẻ xử lý trực tuyến. Độ phức tạp O(n√m + nq).
I. 262144 Nâng cao (DP khoảng + Segment Tree)
Định nghĩa f[v][l] là vị trí r xa nhất sao cho đoạn [l, r-1] có thể gộp thành giá trị ≤v. Khi tăng v lên 1, thực hiện f[l] = f[f[l]]. Dùng segment tree để cập nhật hàng loạt các đoạn có cùng giá trị, đảm bảo tổng số lần cập nhật là O(n log n).
J. Đường hầm (DP ngược + Stack đơn điệu)
Từ đáy lên, tính số bước cần để thoát khỏi mỗi ô. Cấu trúc tương đương: hợp nhất hai ô x,y thành max(x,y)+1. Dùng stack đơn điệu để mô phỏng quá trình: luôn hợp nhất phần tử nhỏ nhất với hàng xóm nhỏ hơn nó.
K. Sóc bay 2 (WQS nhị phân + Hall’s theorem)
Chuyển bài toán thành ghép cặp hai phía với ràng buộc tăng dần. Áp dụng định lý Hall và WQS binary search để tìm chi phí nhỏ nhất cho mỗi số lượng điểm đen k. Dùng segment tree duy trì điều kiện Hall và cập nhật khi thêm/xóa cạnh.
L. Máy kỳ diệu (Segment Tree bán nhóm)
Biểu diễn mỗi thao tác như một hàm f: {0,1} → {0,1} kèm chi phí. Tổng hợp các hàm bằng phép nhân bán nhóm. Kiểm tra tính khả thi dựa vào chẵn lẻ tổng XOR và giá trị cực đại có thể đạt được.
M. Bài toán gốc nâng cao 2 (Sàng nguyên tố + Danh sách liên kết)
Tìm (p,k) sao cho số phần tử ≡k mod p là lớn nhất. Với p³ ≤ n, duyệt trực tiếp. Với p lớn, chỉ xét các cặp trong cùng nhóm 8 phần tử. Dùng danh sách liên kết đôi để xử lý thêm/xóa động, đảm bảo chỉ kiểm tra O(1) số nguyên tố mỗi lần.
N. Hậu trường (Cơ sở vector 2D)
Biểu diễn đồ thị bằng cây khung và các chu trình cơ bản. Duy trì cơ sở vector 2D gồm hai vector (a,b) và (0,c). Khi thêm vector mới, dùng extended GCD để giảm bậc. Truy vấn kiểm tra xem vector đích có biểu diễn được qua cơ sở hay không.
O. Lễ hội JOI 3 (DDP + Treap nhẹ)
Dùng Dynamic DP trên cây: mỗi nút lưu thông tin từ các con nhẹ bằng treap, con nặng bằng segment tree. Khi cập nhật, lan truyền thay đổi dọc theo chuỗi nặng. Hỗ trợ truy vấn thời gian kích hoạt sớm nhất từ cha hoặc con.