Bình luận

• 
  

  0

  

  dangminh  đã bình luận lúc 1, Tháng 7, 2026, 4:09

  Solution bài này:

  dễ thấy cách làm bài này là đếm số cách chọn 1 cặp sao cho ghép lại thì tất cả kí tự đều có tần số là chẵn hoặc chỉ có 1 kí tự có tần số lẻ để ghép lại đối xứng => Bài toán chỉ xét tần số chẵn lẻ của các kí tự

  THUẬT TOÁN TRÂU (sub 1 & 2):

  Tiền xử lý tần số bằng mảng freq[i][c] là tần suất của kí tự (đứng thứ c trong bảng chữ cái) trong xâu i

  duyệt từ 2 vòng lặp i j để so sánh đếm cặp và ghép theo điều kiện

  Độ phức tạp tổng quát O(N * LEN + N ^ 2 * 26) với LEN là chiều dài của xâu (N * LEN <= 1e6)

  TỐI ƯU:

  nhận thấy độ phức tạp khá lớn do vòng lặp so sánh tổng tần suất các kí tự của 2 chuỗi

  Chỉ có 2 TH là tần suất chẵn hoặc lẻ

  Nhận xét có 26 kí tự và chỉ có 2 giá trị là chẵn (0) hoặc lẻ (1) nên có thể sử dụng bitmask để thao tác 2 ^ 26 khoảng 6.8e7 (k bị mle)

  chuyển tất cả các xâu thành bitmask rồi đếm bằng cách lưu vào vector mp[2^26] (có thể dùng map nhưng vector tối ưu hơn về thời gian)

  TH 1: các xâu có tần suất giống nhau thì chắc chắn cho ra tất cả tần suất đều chẵn nên sẽ cộng tất cả TH có tần suất giống nhau

  TH 2: các xâu có tần suất chỉ lệch đúng 1 tần suất thì sẽ có 1 bit khác. ta có mask1 ^ mask2 = (1 << i) thì theo tính chất bitmask ta cũng suy ra được mask1 ^ (1 << i) = mask2. vậy để tìm mask2 thỏa mãn thì ta duyệt qua mọi mask chỉ có bit i bật. mà tối đa số bit chỉ có 26 nên ta duyệt i từ 1 -> 26. ĐỘ PHỨC TẠP O(n * 26)

  CODE THAM KHẢO