Thành phố Cuồng loạn

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 Boruvk ...

Cây Trie Cây Trie là gì? Cây Trie, hay còn gọi là cây từ điển, là một cấu trúc dữ liệu dạng cây dùng để lưu trữ tập hợp các chuỗi ký tự. Cụ thể, nó có một nút gốc không có ý nghĩa (thường được đánh số là 0 hoặc 1), và tất cả các chuỗi được lưu trữ đều có thể đi theo một đường cố định từ nút gốc xuống và kết nối các ký tự trên các nút. Các thao ...

Các cấu trúc như trie, radix tree và rax tree đều là những biến thể của cây tiền tố (prefix tree), được thiết kế để tối ưu hóa hiệu suất truy vấn và tiết kiệm bộ nhớ theo từng giai đoạn phát triển. Trie truyền thống Mỗi nút trong trie chỉ lưu một ký tự duy nhất, toàn bộ khóa được tạo thành bởi chuỗi đường đi từ gốc đến lá. Độ phức tạp tìm kiếm ...

Duyệt Cây function duyetTruoc(goc) { if (goc) { duyetPath.push(goc.giaTri); duyetTruoc(goc.trai); duyetTruoc(goc.phai); } } function duyetGiua(goc) { if (goc) { duyetGiua(goc.trai); duyetPath.push(goc.giaTri); duyetGiua(goc.phai); } } function duyetSau(goc) { if (goc) { ...