Editorial for Xâu con đặc biệt
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Cách 1 (trâu): Duyệt mọi xâu con và kiểm tra xem xâu có thỏa mãn một trong hai điều kiện không và đếm.
Cách 2: Độ phức tạp \(O(n)\)
Dùng mảng cộng dồn đếm số lượng nguyên âm, phụ âm thuộc xâu phía sau vị trí kí tự \(i\). Sau khi đếm được như vậy, duyệt xâu từ đầu tới cuối, với mỗi phụ âm, ta cộng thêm số nguyên âm phía sau nó và kết quả. Tương tự như vậy đối với mỗi phụ âm.
Comments