Editorial for Biến đổi dãy nhị phân
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.
Thuật \(O(n^2)\)
Ta làm giống như bubble sort. Đi từ trái sang phải, nếu gặp 2 số liền kề là \(1\) và \(0\) thì hoán đổi chúng. Thực hiện thao tác trên \(n\) lần ta được một dãy tăng dần.
Thuật \(O(n)\)
Với mỗi số \(0\) ta cần đếm xem nó được hoán đổi bao nhiêu lần. Số lần nó được hoán đổi = số lượng số \(1\) đứng trước nó. Nói cách khác, đáp số = số lượng subsequence \("10"\) trong dãy.
Comments