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.



  • 0
    lelam   commented on Oct. 1, 2022, 3:30 p.m.

    Em đọc editorial của sub3 vẫn chưa hiểu lắm, ai giải thích cho em với. Dạ em cảm ơn


    • 4
      khanhphucscratch   commented on Oct. 17, 2022, 7:33 p.m.

      Ý tưởng đó chính là: mình không cần quan tâm đến xâu như thế nào, mình chỉ quan tâm đến các kí tự đã xuất hiện chẵn hay lẻ bao nhiêu lần. Thì mình có thể phân biệt các xâu đó bằng bitmask, ý tưởng giống kiểu cắt xâu ra, đếm số xâu có thể cắt để xâu còn lại là xâu đẹp (số bit 1 nhỏ hơn 2), còn công thức xác định bitmask của xâu cuối cùng sau khi cắt thì như trên, sử dụng phép toán XOR. Còn nếu bạn băn khoăn tại sao số bit 1 nhỏ hơn 2 thì xâu lại đẹp, thì bạn để ý là nếu số bit 1 là 1, chứng tỏ có 1 kí tự xuất hiện lẻ lần, thì bạn đặt kí tự đó ở tâm, rồi xếp đối xứng các kí tự còn lại. Còn nếu không có bit 1, thì bạn có thể xếp đối xứng luôn