Kiểm soát dịch bệnh
Xem PDFĐể phòng ngừa dịch cúm gia cầm mới, Bộ Nông nghiệp và phát triển nông thôn nghiên cứu,
tìm hiểu cách thức lây lan của một loại virus mới, làm cơ sở để lên phương án phòng chống.
Qua một thời gian nghiên cứu các nhà khoa học phát hiện ra cơ chế lây lan rất đơn giản sau
đây: Trước hết, vùng lãnh thổ khảo sát được biểu diễn bởi một bảng kích thước \(𝑛 × 𝑚\) được
chia thành lưới ô vuông đơn vị. Các cột của bảng được đánh số từ 1 tới \(𝑛\), từ trái qua phải và
các dòng của bảng được đánh số từ 1 tới \(𝑚\), từ dưới lên trên. Ô nằm trên giao của cột \(𝑖\) và
dòng \(𝑗\) được gọi là ô (\(𝑖,𝑗\)). Khi tại ô (\(𝑖,𝑗\)) có virus thì sau một đơn vị thời gian virus sẽ lây lan
sang các ô chung cạnh và chung đỉnh với ô đó.
Trên vùng lãnh thổ khảo sát, người ta quy hoạch \(𝑘\) khu đất để nuôi gia cầm. Mỗi khu là một
hình chữ nhật chiếm trọn một số ô của bảng và các cạnh song song với cạnh của bảng. Khu
thứ \(𝑖\) xác định bởi ô trái dưới (\(𝑎_𝑖, 𝑏_𝑖\)) và ô phải trên (\(𝑐_𝑖, 𝑑_𝑖\)). Các hình chữ nhật này không nhất
thiết rời nhau vì có một số gia cầm có thể sống chung trên một vùng đất.
Yêu cầu: Với cơ chế lây lan của virus đã biết và bản đồ các khu đất đã quy hoạch để nuôi các
gia cầm, hãy viết một chương trình để trả lời nhanh câu hỏi: Sau thời điểm \(𝑡\) tính từ lúc phát
hiện virus tại ô (\(𝑥_0, 𝑦_0\)) có bao nhiêu ô trong các khu quy hoạch bị lây virus. Giả thiết rằng ô
(\(𝑥_0, 𝑦_0\)) không nằm trong bất kỳ khu đất quy hoạch nào và thời điểm xuất hiện virus được
tính là 0.
Input
- Dòng đầu là 5 số \(𝑛, 𝑚, 𝑘, 𝑥_0\) và \(𝑦_0\) (\(1 \leq 𝑥_0 \leq 𝑛; 1 \leq 𝑦_0 \leq 𝑚\));
- Dòng thứ \(i\) trong \(k\) dòng tiếp theo chứa 4 số \(𝑎_𝑖, 𝑏_𝑖, 𝑐_𝑖, 𝑑_𝑖\) (\(1 \leq 𝑎_𝑖 \leq 𝑐_𝑖 \leq 𝑛; 1 \leq 𝑏_𝑖 \leq 𝑑_𝑖 \leq 𝑚\));
- Dòng tiếp theo chứa số \(𝑞\) là số các câu hỏi cần trả lời (\(1 \leq 𝑞 \leq 𝑚𝑎𝑥(𝑛, 𝑚)\));
- Dòng cuối cùng chứa \(q\) số \(𝑡_1,𝑡_2, … ,𝑡_𝑞\) là thời điểm tương ứng với các câu hỏi, mỗi số có giá trị không lớn hơn \(10^6\).
Output
- Gồm một dòng chứa \(𝑞\) số lần lượt là kết quả trả lời của 𝑞 câu hỏi.
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(𝑛, 𝑚 \leq 1000; 1 \leq 𝑘 \leq 100; 1 \leq 𝑞 \leq 100\);
- Subtask \(2\) (\(50\%\) số điểm): \(𝑛, 𝑚 \leq 10^6; 1 \leq 𝑘 \leq 400\);
Example
Test 1
Input
6 6 2 1 1
2 2 4 4
4 4 6 6
3
2 5 4 Output
4 17 12Note
Bình luận
cho mình xin sol bài này với ạ :((
-
0
SPyofgame
4:36 p.m. 28 Tháng 6, 2020
←
đã chỉnh sửa
→
-
6
HilG
11:19 a.m. 29 Tháng 6, 2020
-
1
SPyofgame
2:32 p.m. 29 Tháng 6, 2020
←
chỉnh sửa 5
→
-
6
HilG
3:16 p.m. 29 Tháng 6, 2020
-
1
SPyofgame
4:54 p.m. 29 Tháng 6, 2020
4 bình luận nữaApproach: Rời rạc hóa ma trận ạ :v
Đpt tối ưu nhất em biết được hiện tại là \(O(k^2 + polylog(max(n, m)) + q)\) mà hình như opt thêm tí nữa được
Dạ anh giải thích chi tiết hơn được ko ạ? Rời rạc hóa ma trận là gì và em có thể đọc ở đâu ạ? Với lại polylog là như thế nào ạ? Em cảm ơn.
Rời rạc hóa ma trận là việc mình chia nó thành các hình con nhỏ hơn để tiện xử lí tính toán (nhưng mình không có tài liệu ở đâu cả 😢 )
\(O(Polylog())\) ở đây mình chỉ một độ phức tạp có dạng đa thức logarit, ví dụ \(O(log^5(k) + log(k \times n))\)
Dạ anh có thể chi tiết về việc áp dụng cái rời rạc hóa ma trận vào bài này ko ạ? Hay share code cho em đọc tham khảo với được ko ạ? Em cảm ơn
Mình không biết làm dạng tổng quát đâu :'(( riêng bài này mình mới học thuật rời rạc hóa và đang viết editorial cho anh em, nhưng đợi mình viết bài khác trước đã ạ 🙁