Editorial for Bedao Mini Contest 09 - FIRE


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Subtask 1 : ~(q = 1, n \times m \leq 10^6)~

Bài toán cần giải quyết trong subtask : Cho ~1~ bảng hình chữ nhật kích cỡ ~n \times m~, hỏi có bao nhiêu đường đi từ góc trái trên xuống góc phải dưới của bảng mà không đi qua các ô bị cấm ?

Đây là bài quy hoạch động cơ bản, bạn có thể đặt ~F(i, j)~ là số đường đi từ góc trái trên đến ô có tọa độ ~(i, j)~ trong bảng, công thức truy hồi sẽ là :

  • ~F(i, j) = 0~ nếu ~(i, j)~ là ô bị cấm.
  • ~F(i, j) = F(i-1, j) + F(i, j-1)~ vì để đi đến ô ~(i, j)~ thì cần đi qua ô ~(i-1, j)~ hoặc ~(i, j-1)~.

Subtask 2 : ~(q = 1, x < 0)~

Bạn có thể tham khảo một bài toán tương tự với subtask 2: Link

Subtask 3 :

Đầu tiên bạn cần giải quyết bài toán đếm số đường đi giữa ~2~ điểm trên mặt phẳng mà khoảng cách Manhattan của chúng bé hơn hoặc bằng ~2 \times 10^6~. Đây là bài cơ bản và bạn có thể đọc về nó tại VNOI Wiki - Số học 5

Nhận xét 1: Vùng liên thông chứa các ô bị cháy luôn có dạng hình vuông với góc trái dưới là ~(x-t, x-t)~ và góc phải trên là ~(x+t, x+t)~

Nhận xét 2: Giả sử hình vuông chứa các ô bị cháy nằm gọn trong hình chữ nhật có góc trái trên ~(0, a)~ và góc phải dưới ~(b, 0)~. Nếu ~1~ con đường đi từ ~A~ đến ~B~ và đi qua ít nhất ~1~ ô bị cháy thì con đường đó chắc chắc phải đi qua ~1~ ô thuộc đường chéo phụ của hình vuông trên ( tham khảo hình bên dưới ).

Dễ thấy trong trường hợp tổng quát ( hình vuông chứa các ô bị cháy có thể không hoàn toàn nằm trong hình chữ nhật ), Nhận xét 2 vẫn đúng. Mặt khác, mọi ô thuộc đường chéo phụ phải nằm thẳng hàng với ~2~ điểm ~(x-t, x-t)~ và ~(x+t, x+t)~, có nghĩa tọa độ của chúng luôn có dạng ~(i, i)~

hình

Từ các nhận xét trên, dễ thấy với mỗi truy vấn ta không nhất thiết phải xét hết mọi ô bị cháy mà chỉ cần xét các ô có tọa độ dạng ~(i, i)~. Mỗi truy vấn trong bài được viết lại như sau : Cho ~1~ cặp số ~x-t~ và ~x+t~, hỏi có bao nhiêu đường đi mà trên đó không tồn tại ô có tọa độ ~(i, i)~ thỏa mãn ~x-t \leq i \leq x+t~.

Vậy với mọi ô có tọa độ ~(i, i)~ thỏa mãn ~0 \leq i \leq min(a, b)~, ta đếm số đường đi có dạng ~A → (i, i) → B~ rồi lưu vào Prefix sum để trả lời các truy vấn.

Lưu ý: Vì trong bài này ~x-t~ và ~x+t~ có thể âm hoặc rất lớn nên khi cài đặt thuật toán hãy cẩn thận để tránh lỗi.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.