Hướng dẫn cho Bedan Contest #05 - C - Xâu đối xứng

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: flo

Cách giải

Hint

Nếu xâu $s$ là một xâu đối xứng thì xâu con từ vị trí $2$ đến $|s|-1$ của nó cũng sẽ là xâu đối xứng. Để dễ hình dung thì nếu abba là xâu đối xứng thì bb cũng là xâu đối xứng, zsusz là xâu đối xứng thì sus cũng là xâu đối xứng.

Solution

Từ nhận xét trên, một đoạn $[l, r]$ sẽ có một cặp $(i, j)$ $(l \le i < j \le r)$ thỏa mãn $s_is_{i+1}...s_j$ là xâu đối xứng khi tồn tại một vị trí $i$ $(l \le i)$ mà $s_i = s_{i+1}$ $(i < r)$ $(1)$ hoặc $s_i = s_{i+2}$ $(i < r-1)$ $(2)$ .
Với nhận xét trên, ta sẽ gọi $a$ và $b$ lần lượt là $2$ dãy chứa các vị trí $i$ của xâu $s$ thỏa mãn điều kiện $(1)$ và $(2)$ . Sau đó, ta sẽ sắp xếp $2$ dãy này theo thứ tự tăng dần. Với mỗi l r của mỗi truy vấn, ta chỉ việc chặt nhị phân trên $2$ dãy này và kiểm tra có phần tử nào thuộc đoạn $[l, r]$ thỏa mãn điều kiện còn lại của điều kiện $(1)$ hoặc $(2)$ hay không.
Độ phức tạp của ý tưởng trên là $O(n + q \times log_2n)$ .

Bình luận

Không có bình luận nào.