Hướng dẫn giải của Lớp Biến Hình

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Hướng tiếp cận

Bài toán yêu cầu tìm số phép biến hình ít nhất để biến bảng $A$ thành bảng $B$ , trong đó mỗi phép biến hình chọn ô $(r, c)$ và đảo toàn bộ hình chữ nhật từ $(r, c)$ đến $(N, M)$ . Lời giải dựa trên mảng sai phân XOR 2D.

Nhận xét quan trọng

Gộp hai bảng: Đặt $D [i] [j] = A [i] [j] \oplus B [i] [j]$ . Bài toán trở thành: tìm số phép ít nhất để biến $D$ thành toàn 0.
Mảng sai phân XOR 2D: Định nghĩa:
$d [i] [j] = D [i] [j] \oplus D [i - 1] [j] \oplus D [i] [j - 1] \oplus D [i - 1] [j - 1]$
(với $D [i] [j] = 0$ khi $i < 1$ hoặc $j < 1$ ). Mảng $d$ có tính chất: $D$ có thể được phục hồi từ $d$ bằng tiền tố XOR 2D.
Tác động của phép biến hình: Phép biến hình tại $(r, c)$ đảo tất cả $D [i] [j]$ với $i \geq r, j \geq c$ . Trong mảng sai phân, thao tác này chỉ thay đổi đúng 1 ô $d [r] [c]$ (toggle giá trị tại đó), vì các thay đổi ở các ô khác triệt tiêu nhau.
Kết quả: Mỗi phép biến hình toggle đúng 1 ô trong $d$ . Để đưa $D$ về toàn 0, ta cần $d$ cũng toàn 0. Vậy số phép tối thiểu bằng số ô có giá trị 1 trong mảng sai phân $d$ .

Thuật toán

Đọc hai bảng $A$ và $B$ .
Với mỗi ô $(i, j)$ , tính: $d [i] [j] = (A [i] [j] \oplus B [i] [j]) \oplus (A [i - 1] [j] \oplus B [i - 1] [j]) \oplus (A [i] [j - 1] \oplus B [i] [j - 1]) \oplus (A [i - 1] [j - 1] \oplus B [i - 1] [j - 1])$
Đếm số ô có $d [i] [j] = 1$ . Đó là đáp án.

Độ phức tạp

Thời gian: $O (N M)$ - duyệt qua mỗi ô đúng 1 lần.
Bộ nhớ: $O (N M)$ - lưu hai bảng $A$ và $B$ .

Bình luận

Không có bình luận tại thời điểm này.