Hướng dẫn giải của Khối Phô Mai Của FJ

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

Lời giải: Khối Phô Mai Của FJ

Hướng tiếp cận

Theo dõi số khối phô mai còn lại trên mỗi đường thẳng song song với các trục tọa độ.

Nhận xét quan trọng

Viên gạch $1 \times 1 \times N$ chỉ có 3 hướng đặt: song song với trục $x$ , $y$ , hoặc $z$ . Với mỗi hướng, viên gạch chiếm trọn một hàng $N$ ô liên tiếp. Viên gạch đặt được khi và chỉ khi toàn bộ $N$ ô trên hàng đó đã bị cắt hết.

Thuật toán

Duy trì 3 mảng 2D kích thước $N \times N$ :

xy[x][y]: số ô phô mai còn lại trên đường song song trục $z$ qua $(x, y)$
xz[x][z]: số ô còn lại trên đường song song trục $y$ qua $(x, z)$
yz[y][z]: số ô còn lại trên đường song song trục $x$ qua $(y, z)$

Khi cắt ô $(x, y, z)$ : giảm 3 bộ đếm tương ứng. Mỗi khi bộ đếm về $0$ , tăng đáp án thêm $1$ .

Độ phức tạp

Thời gian: $O (N^{2} + Q)$
Bộ nhớ: $O (N^{2})$

Bình luận

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