Editorial for Xử lí bit cơ bản

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: UltimateWiener

tag: dynamic programming, trie, small to large, centroid decomposition.

Đầu tiên, cho mình xin lỗi vì đề bài ngu của LKT.

Tóm tắt ngắn gọn lại đề bài: Cho một cây gồm $N$ đỉnh, độ tuyệt vời của cặp đỉnh $(u, v)$ là tổng xor của đường đi đơn từ $u$ đến $v$ . Bạn cần tìm độ tuyệt vời lớn nhất của mọi cặp $(u, v)$ và đếm xem có bao nhiêu cặp có độ tuyệt vời bằng độ tuyệt vời lớn nhất đấy.

Subtask 1

Làm gì cũng được.

ĐPT: $O (h i o)$

Subtask 2

Với mỗi đỉnh $u$ ta tiến hành dfs hoặc bfs để tính độ đẹp của đỉnh $u$ tới mọi đỉnh $v$ khác, sau đó tính đáp án theo đề bài.

ĐPT: $O (N^{2})$

Subtask 3

Vì $A_{i} \leq 1$ , nên độ tuyệt vời lớn nhất của đồ thị chính là $1$ . Nên nếu không tồn tại một đường đi có độ tuyệt vời là $1$ thì độ tuyệt vời của đồ thị sẽ bằng $0$ và số cặp thỏa mãn sẽ là $N^{2}$ . Nếu có tồn tại, chúng ta sẽ tiến hành đếm số đường đi có độ tuyệt vời là $1$ như sau:

Gọi $s (u, v)$ là độ đẹp của cặp $(u, v)$ , $f_{u}$ là số đỉnh con $v$ sao cho $s (u, v) = 1$ , $g_{u}$ là số đỉnh con $v$ sao cho $s (u, v) = 0$ .

Ta dễ dàng tính $f_{u}$ và $g_{u}$ bằng công thức sau:

Nếu $A_{u} = 1$ :
- $f_{u} = 1 + \sum g_{v}$
- $g_{u} = \sum f_{v}$
Nếu $A_{u} = 0$ :
- $f_{u} = \sum f_{v}$
- $g_{u} = 1 + \sum g_{v}$

Trong đó, $v$ là đỉnh con trực tiếp của $u$ .

Khi có được $f_{u}$ và $g_{u}$ , ta có thể dễ dàng tính được đáp án (mời bạn đọc tự tính do mình lười).

ĐPT: $O (N)$

Subtask 4

Gọi $f_{u, i}$ là số đỉnh con $v$ sao cho $s (u, v) = i$ .

Ta dễ dàng tính được $f_{u, i}$ bằng công thức sau: $f_{u, i} = \sum f_{v, j}$ với mọi $j, v$ thỏa mản $j \oplus A_{u} = i$ và $v$ là đỉnh con trực tiếp của $u$ (Tất nhiên, $f_{u, A_{u}}$ được cộng thêm $1$ ).

(Mình quên mất phần sau nên mình mời bạn đọc làm tiếp subtask này).

ĐPT: $O (N \times 32^{2})$

Subtask 5

Để giải quyết được subtask cuối cùng, chúng ta cần giải quyết được bài toán dễ hơn:

"Cho $1$ dãy gồm $N$ số không âm, tìm tổng xor lớn nhất của một đoạn liên tiếp của mảng này".

Duyệt trâu thông thường sẽ có ĐPT là $O (N^{2})$ , sẽ không qua được giới hạn của bàn toán. Để tối ưu hóa, chúng ta để ý rằng tổng xor của đoạn $[l . . . r]$ là $p r e f_{r} \oplus p r e f_{l - 1}$ với $p r e f_{i}$ là tổng xor của đoạn $[1. . . i]$ . Ta cố định $p r e f_{r}$ , với mỗi $r$ $(1 \leq r \leq N)$ ta cần tìm $l$ $(l \leq r)$ sao cho $p r e f_{r} \oplus p r e f_{l - 1}$ lớn nhất. Ta duy trì một trie lưu các giá trị $p r e f_{1}, p r e f_{2}, . . ., p r e f_{r}$ , rồi xét từ bit lớn nhất tới bit nhỏ nhất, mỗi lần như vậy ta kiểm tra xem có tồn tại $p r e f_{i}$ sao cho bit lớn thứ $j$ $\oplus$ bit lớn thứ $j$ của $p r e f_{r}$ có bằng $1$ hay không. Với cách làm này, ta giảm ĐPT từ $O (N^{2})$ xuống $O (N \times l o g_{2} (max (A_{i})))$ . VNOI wiki cũng có phần nói về bài này Link.

Trở về bài toán chính, với mỗi đỉnh $u$ chúng ta có thể lưu một trie chứa các giá trị $s (u, v)$ . Để gộp trie một cách hiệu quả, ta sử dụng kỹ thuật small to large. Trong quá trình gộp, ta lấy toàn bộ giá trị ở trie nhỏ hơn, rồi coi thử xem giá trị xor lớn nhất với trie lớn hơn là bao nhiêu bằng tư duy trên.

ĐPT: $O (N \times l o g_{2} (max (A_{i}))^{2})$

Tài liệu tham khảo

Comments

Please read the guidelines before commenting.

There are no comments at the moment.