Editorial for Bedao Mini Contest 11 - BEAUTYSTR


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: bedao

Nhận xét #1: Ta định nghĩa frequency của 1 ký tự là số lần xuất hiện của ký tự đó trong xâu, ví dụ như frequency của ký tự "a" trong xâu "abcad" là ~2~. Một xâu là đẹp khi và chỉ khi tồn tại tối đa ~1~ ký tự trong trong xâu có frequency là số lẻ.

Nhận xét #2: Tối đa ~36~ loại ký tự có thể xuất hiện trong xâu ~S~.

Subtask #1 (xâu S chỉ gồm 2 loại ký tự "a" và "b"):

  • Dễ thấy một substring là không đẹp nếu như frequency của ~2~ loại ký tự "a" và "b" ở xâu ~S~ trong đoạn ~[l,r]~ đều là số lẻ, nói cách khác một substring là không đẹp nếu nó có độ dài chẵn nhưng số lần xuất hiện của ký tự "a" lại lẻ.

  • Ta dễ dàng tính được số substring không đẹp bằng cách xây ~1~ tổng tiền tố trong ~O(n)~ và chia trường hợp để đảm bảo độ dài của substring luôn chẵn, từ đây ta có thể tính loại trừ để ra được số substring đẹp.

Subtask #2 (n ≤ 2000):

  • Ta duyệt qua tất cả ~\frac{n \times (n+1)}{2}~ substring của xâu ~S~ và đồng thời duy trì ~1~ mảng để đếm frequency của các loại ký tự, substring ~S[l, r]~ đang xét là đẹp nếu như tồn tại tối đa ~1~ loại ký tự có frequency lẻ trong xâu ~S[l, r]~. Độ phức tạp của cách làm này là ~O(n^2)~.

Subtask #3 :

  • Vì có tối đa ~36~ loại ký tự khác nhau và ta chỉ quan tâm đến frequency của chúng là chẵn hay lẻ, ta có thể lưu thông tin vào bitmask với bit thứ ~i~ bằng ~1~ nếu loại ký tự thứ ~i~ có frequency là số lẻ và bằng ~0~ nếu là số chẵn. Gọi ~mask(l, r)~ là hàm trả về bitmask tương ứng của xâu ~S[l, r]~, ta có công thức sau : ~mask(l, r) = mask(1, l-1) \oplus mask(1, r)~ với ~\oplus~ là phép toán XOR .

  • Vậy substring ~S[l, r]~ được coi là đẹp nếu như trong biểu diễn nhị nhân của ~mask(l, r)~ có nhiều nhất ~1~ bit bật, nói cách khác với mỗi vị trí ~r~ cố định ta cần đếm xem có bao nhiêu vị trí ~(l-1)~ thỏa mãn : ~mask(1, l-1) \oplus mask(1, r) = 0~ hoặc ~2^k~ (với ~k~ là một số nguyên không âm bất kỳ).

  • Vậy ta sẽ duyệt qua từng tiền tố của xâu ~S~, tính bitmask tương ứng của chúng rồi lưu vào cấu trúc dữ liệu std::map, độ phức tạp của cách làm này là ~O(nlogn \times A)~ với ~A~ là số loại ký tự khác nhau (dễ thấy trong bài này ~A = 36~).


Comments

Please read the guidelines before commenting.


There are no comments at the moment.