Embedded Files
Giới thiệu
Giới thiệu
Đúng như tên gọi, thuật toán đường quét, hay có thể gọi là kỹ thuật đường quét mô tả một hướng tiếp cận giải quyết vấn đề bằng cách quét qua các sự kiện trong một mặt phẳng. Ban đầu kỹ thuật này được dùng để giải quyết các bài toán hình học trong CP. Tuy nhiên, do khả năng xử lý mạnh của nó nên ngày nay được dùng giải quyết rộng hơn ở nhiều bài toán khác. Chuyên đề này sẽ thảo luận qua một lớp các bài toán có thể xử lý bằng kỹ thuật này.
Tài liệu tham khảo
Tài liệu tham khảo
Competitive Programmer’s Handbook, Antti Lacksonen, 2019. Chapter 30 (Page 275 - 279)
Tài liệu chuyên đề hội thảo khoa học các trường chuyên Duyên Hải Bắc Bộ
Bài toán mở đầu
Bài toán mở đầu
Một công ty có n nhân viên, do đặc thù công việc, mỗi nhân viên có một khung giờ vào và ra khỏi công ty khác nhau. Hãy tính số nhân viên tối đa có mặt ở công ty.
Ví dụ
Nguồn bài và hình: CP's handbook, Antti Lacksonen
Cách 1 - Bài toán có thể dễ dàng giải bằng cách tự nhiên là xét từng khung giờ. Cứ mỗi khung giờ ta duyệt qua hết các nhân viên để xem giờ vào, ra của nhân viên đó có chứa khung giờ đang xét không, nếu có ta tăng biến đếm lên 1 và cập nhật max. Cứ như vậy lặp lại cho đến khung giờ cao nhất.
Độ phức tạp thời gian: O(T*N), trong đó T là thời gian cao nhất được cho. Cách này sẽ không hiệu quả khi T quá lớn (Mô tả bài toán chỉ mang tính biểu trưng, T lớn nhất không phải là 24 theo giờ thực tế)
Cách 2 - Ta sẽ mô hình hóa mỗi nhân viên thành cặp sự kiên vào, ra tương ứng với giờ vào, ra của họ. Sau đó sắp xếp tăng dần theo giờ vào. Dùng một đường quét chạy từ trái sang phải, cứ gặp sự kiện vào thì ta tăng biến đếm lên 1 và cập nhật max, gặp sự kiện ra ta giảm biến đếm đi 1.
Nếu tại một vị trí mà đường quét quét qua ta gặp vừa sự kiện vào, ra thì ta ưu tiên xử lý sự kiện vào trước ra sau.
Có thể xem hình minh họa sau:
Sắp xếp các sự kiện vào, ra theo thứ tự tăng dần
Nguồn: CP's Handbook, Antti Lacksonen
Dùng đường quét chạy từ trái qua phải, tăng đếm khi gặp sự kiện vào và giảm khi gặp sự kiện ra. Thao tác cập nhật Max thực hiện khi tăng đếm.
Độ phức tạp:
Sắp xếp: O(nlogn)
Quét qua các sự kiện: O(n)
Thời gian tổng thể: O(nlogn)
Cài đặt:
Việc cài đặt dựa trên kỹ thuật sweepline có nhiều cách, quan trọng nhất là cách chúng ta lưu các sự kiện. Trong trường hợp này có thể dùng một vector <pair <int, int>> để lưu sự kiện. Mỗi pair chứa hai thông tin <thời điểm, loại sự kiện> trong đó 0 là vào, 1 là ra. Các em hoàn toàn có thể sử dụng cách khác để lưu, miễn sao đảm bảo mô hình được sự kiện như vậy.
Nhận xét:
Nhận xét:
Như vậy để giải quyết bài toán bằng kỹ thuật sweepline, ta quan tâm tới những vấn đề sau:
Mô hình hóa sự kiện: các đối tượng chính trong bài toán sẽ có những sự kiện gì theo mô tả của đề.
Xử lý sự kiện: khi đường sweepline chạy đến gặp sự kiện thì ta làm gì, mỗi sự kiện có một cách xử lý khác nhau.
Kết quả bài toán được tính vào thời điểm nào, được cập nhật vào thời điểm nào.
Nhìn chung, ý tưởng mô hình hóa sự kiện là giúp chúng ta xác định các thời điểm quan trọng nào cần xử lý để giảm thiểu thời gian xử lý. Và vì kỹ thuật dựa trên đường quét nên các sự kiện cũng mang tính thứ tự, do đó đa phần các bài toán giải quyết bằng sweepline thường đi kèm với thao tác sắp xếp các sự kiện.
Một số bài toán luyện tập
Một số bài toán luyện tập
Các bài toán sau đây có cùng mức độ như bài trên, các thao tác xử lý cũng tương tự. Tuy nhiên, trước khi sử dụng đường quét cần tiền xử lý các sự kiện một chút.
Nhiệm vụ 3. Robot giao hàng
(Tuyển sinh 10 - TP HCM 2023)
Tóm tắt:
Một Robot có nhiệm vụ đi từ vị trí 0, đến từng điểm nhận và giao cho mỗi đơn hàng rồi kết thúc hành trình của mình tại điểm M. Hay tính đoạn đường di chuyển ngắn nhất để Robot hoàn thành nhiệm vụ của mình. Biết rằng các điểm nhận và giao đều nằm trong khoảng từ 0 đến M.
Input:
Dòng đầu chứa hai số nguyên N, M là số đơn hàng và địa điểm đi về sau khi xong nhiệm vụ
N dòng tiếp theo, mỗi dòng chứa hai số nguyên là điểm nhận vào giao của mỗi đơn hàng
Output:
Một số nguyên duy nhất là đoạn đường di chuyển tối thiểu
Nhiệm vụ 4 - Những tòa nhà bị cô lập
(Olp Sinh viên 2023 - Đại học công nghệ Hà Nội - Vòng sơ tuyển)
Tóm tắt:
Cho N tòa nhà nằm san sát nhau với độ cao lần lược a1, a2, ..., aN. Mỗi ngày mực nước biển dân lên 1m. Tòa nhà nào có độ cao thấp hơn mực nước biển thì coi như bị ngập, các tòa còn lại tạo thành những vùng cô lập. Cho Q ngày, người ta muốn biết vào ngày thứ i trong Q ngày đó, mỗi ngày có bao nhiêu vùng cô lập.
Input:
Dòng đầu chứa hai số nguyên N, Q là số tòa nhà và số ngày cần tính vùng cô lập
Dòng thứ 2 chứa N số nguyên là chiều cao các tòa nhà
Dòng thứ 3 chứa Q số nguyên là những ngày cần tính vùng cô lập
Output:
Một dòng duy nhất chứa Q số nguyên, số thứ t là số vùng cô lập tại ngày thứ t
Ràng buộc
Ví dụ
Nhiệm vụ 5 - Chia kẹo
(Chuyên đề hội thảo khoa học các trường Chuyên duyên Hải Bắc Bộ 2021)
Tóm tắt:
Có N em bé được xếp thành một vòng tròn, được đánh số từ 1 đến N theo chiều kim đồng hồ. Người ta tổ chức chia kẹo cho các em bé trong M lượt, mỗi lượt xác định một cặp chỉ số L, R. Tất cả các em bé được đánh số từ L đến R theo chiều kim đồng hồ sẽ được nhận 1 cái kẹo. Hỏi sau M lượt chia kẹo, thì số kẹo lớn nhất mà một em bé có thể nhận được là bao nhiêu và có bao nhiêu em bé nhận được số kẹo như vậy?
Nhiệm vụ 6 - Điều phối không lưu - FlyMode
(Chuyên đề hội thảo khoa học các trường Chuyên duyên Hải Bắc Bộ 2021)
Tóm tắt:
Hệ thống Kiểm soát không lưu có trách nhiệm điều hướng, đảm bảo an toàn cho các chuyến bay từ lúc cất cánh đến khi hạ cánh. Một máy bay nhận được các tín hiệu điều khiển từ Hệ thống yêu cầu tăng, giảm độ cao đến độ cao
𝐻𝑖 để tránh va chạm, các độ cao liên tiếp đảm bảo khác nhau. Cơ trưởng ghi lại nhật kí điều khiển liên tiếp trong một khoảng thời gian. Hỏi số lần nhiều nhất có thể mà máy bay bay qua độ cao nào đó.
Nhiệm vụ 7 - Diện tích bao phủ - Cover 1
(Chuyên đề hội thảo khoa học các trường Chuyên duyên Hải Bắc Bộ 2021)
Tóm tắt:
Cho N hình miếng vải hình chữ nhật đặt trên trục Ox có toạ độ đều là số nguyên, hỏi diện tích phần mà chúng che phủ trên mặt đất là bao nhiêu? Cho N <= 10^5, các toạ độ nguyên không quá 10^5
Các bài toán nâng cao
Các bài toán nâng cao
Qua một số bài cơ bản ở trên, chúng ta đã làm quen dần được cách nhận diện và mô hình hóa các sự kiện cũng như xử lý sự kiện tại thời điểm đường quét đi qua. Tuy nhiên, khi xử lý các sự kiện tại đường quét, đa phần cần nhiều kỹ năng kết hợp trong việc lưu trữ, tính toán các giá trị và cập nhật các giá trị tại thời điểm đó.
Ví dụ như sự thay đổi liên tục giá trị trong một vùng cần tính nên cần lưu dữ liệu bằng các cấu trúc cây như cây phân đoạn (Segment Tree), cây nhị phân (BIT Tree), DSU, ...
Để xử lý tính toán điều kiện tại đường quét lại cần các kỹ thuật khác như tìm kiểm nhị phân, các kiến thức hình học giải tích,....
Chúng ta cùng đi qua các bài toán sau đây:
Nhiệm vụ 8. Closest Pair-Cặp điểm gần nhất
Nhiệm vụ 9. Light - Chiếu sáng
Nhiệm vụ 10. Intersetions - Số giao điểm
Nhiệm vụ 11. Diện tích các hình chữ nhật - Area
Nhiệm vụ 12. Bao lồi của tập điểm
Nhiệm vụ 13. Thực hiện contest ngắn - Sweepline 1
Page updated
Google Sites
Report abuse