Editorial for Educational Backtracking: Xâu đầy đủ

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.
  • Ta có nhận xét rằng, nếu sử dụng cách sinh nhị phân các xâu được chọn ra rồi ghép từng xâu vào để kiểm tra sẽ cho độ phức tạp ~O(2^n*n)~, với ~n = 25~ thì sẽ dẫn tới chạy quá thời gian.
  • Để tối ưu thuật toán, ta thấy rằng mỗi xâu có thể được lưu dưới dạng một số nguyên ~mask~ gồm ~26~ bit, nếu bit thứ ~i~ bật thì nghĩa là trong xâu đó có xuất hiện kí tự thứ ~i~ trong bảng chữ cái (kí tự ~'a'~ được tính là kí tự thứ ~0~).
  • Như vậy, ta cần tìm cách chọn ra một tập xâu sao cho tổng ~or~ của các ~mask~ đại diện cho xâu đó bằng với ~2^{26}-1~.
  • Để tránh việc ta phải sinh ra một dãy nhị phân rồi mới bắt đầu xét từng phần tử trong đó để tính tổng ~or~, ta có thể tạo một hàm:
void ql(int id, int val) {
    // id là vị trí xâu đang xét tới, val là tổng or của các xâu đã được chọn
    // nếu val = 2^(26)-1 thì tăng kết quả lên 1
    if (val == need) res++;
    // thực hiện quay lui nhị phân như bình thường
    if (id > n) return;
    // nếu chọn xâu id
    ql(id + 1, val | mask\[id\]);
    // nếu không chọn xâu id
    ql(id + 1, val);
}

Như vậy ta sẽ thu được thuật toán có độ phức tạp ~O(2^n)~.

Comments

Please read the guidelines before commenting.