Tóm tắt đề: Cho một ma trận
chỉ gồm các sô
. Mỗi thao tác bạn có thể đảo bất kì hàng, hoặc cột nào. Yêu cầu tìm số lượng số
nhỏ nhất còn lại khi thực hiện một số thao tác đảo hàng hoặc cột.
Hướng dẫn:
Giải thuật
: Nhận xét mỗi hàng hoặc cột chỉ thực hiện đảo nhiều nhất là
lần vì nếu đảo
lần thì coi như không đảo. Dùng dãy bit
độ dài
để biểu diễn trạng thái của các hàng – bit thứ
bằng
thì đảo hàng
.
Bạn đang xem:
Bitmask là gìXem thêm:
Tải Game Hoa Quả Nổi Giận 2 Mobile, Game Hoa Quả Nổi Giận OnlineXem thêm:
Trang Chủ Chính Thức - Chuỗi Sự Kiện Sẵn Sàng Sinh Nhật Lmht Tương tự ta dùng dãy bit độ dài
để đại diện cho từng cột, với các bit tương ứng với bảng đã cho ban đầu. Trước hết ta cần duyện qua
trạng thái của dãy bit đại diện các hàng, giả sử mask là số biểu diễn trạng thái của các hàng hiện tại, và
là dãy bit đại diện cho cột i ban đầu. Vì bit thứ
trong mask bằng
tương ứng với việc đảo hàng
nên ta phải đảo các bit
trong
, việc này có thể thực hiện bằng bằng biểu thức logic đơn giản
. Dĩ nhiên ở cột
ta cũng có 2 trạng thái đó là đảo hoặc không, dễ thấy nếu không đảo thì số bit
sau khi đảo các hàng trong mask chính là số bit
của
với
, còn nếu đảo cội
thì số bit
sau khi đảo sẽ bằng số bit
trong
. Ta có cách cài đặt đơn giản đó là duyệt mask từ
đến
và tính:
.