Bitmask Là Gì

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 Online


Xem 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: .