Thành phố Cuồng loạn

Bài 1: Máy bay và kỳ vọng Đề bài yêu cầu tính kỳ vọng số bước đi để kết thúc trò chơi. Dùng quy hoạch động với hàm f[i] là kỳ vọng từ ô thứ i đến đích. Tuy nhiên, có vấn đề ở 6 ô cuối do ảnh hưởng ngược (hiệu ứng lặp). Giải pháp là xây dựng hệ phương trình tuyến tính cho 5 ô cuối và giải bằng phương pháp Gauss. Công thức kỳ vọng để bắt đầu: x ...

Cây đoạn (Segment Tree) là một cấu trúc dữ liệu phổ biến trong lập trình thi đấu, đặc biệt hiệu quả cho các bài toán yêu cầu thực hiện xen kẽ các thao tác cập nhật đoạn và truy vấn đoạn trên dãy số. Cấu trúc này có thể xử lý hiệu quả các phép toán trên đoạn với độ phức tạp O(log n) cho mỗi thao tác cập nhật hoặc truy vấn. Nguyên lý hoạt động ...

Phần phân tích thuật toán root decomposition sẽ không được trình bày ở đây, tập trung vào chi tiết code: #include <bits/stdc++.h> using namespace std; const int MAXN = 50005; const int MAXM = 200005; const int LOG = 17; int n, m, queryCount; inline int fastRead() { int x = 0; char c = getchar(); while (c < '0' || c > ...

Tối ưu hóa xây dựng đồ thị bằng cấu trúc dữ liệu Trong một số trường hợp, chúng ta cần nối tất cả các đỉnh có chỉ số trong đoạn [L, R] với tất cả các đỉnh có chỉ số trong đoạn [L', R']. Nếu thực hiện trực tiếp sẽ dẫn đến độ phức tạp O(n²m). Do đó, chúng ta cần phân chia đoạn thành các khối nhỏ để xử lý thống nhất. Chúng ta cần xây dựng một cây ...