Hướng dẫn giải của Following Directions

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: Following Directions

Hướng tiếp cận

Duy trì mảng 2D $A [i] [j]$ đếm số bò đi qua mỗi ô. Khi đổi biển chỉ hướng, chỉ cần cập nhật các ô trên đường đi cũ và mới.

Thuật toán

Khởi tạo ( $O (N^{2})$ ): Tính $A [i] [j]$ cho tất cả các ô bằng cách lan truyền theo hướng biển.
Truy vấn (O(N)): Khi đổi biển ở (i,j):
- Trừ $A [i] [j]$ trên đường đi cũ (từ ô kế tiếp đến máng).
- Đổi hướng biển.
- Cộng $A [i] [j]$ trên đường đi mới.
- Cập nhật tổng chi phí.

Độ phức tạp

Thời gian: $O (N^{2} + N 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.