Hướng dẫn bài EXIT - Tìm đường thoát khỏi mê cung

Trùm CUỐI 2022-01-10 16:48:48

Link đến trang bài tập

Trước tiên ta nhận xét rằng theo cách đánh số qui ước thì nếu ở mức i vùng giới hạn là [L,R] thì ở mức i+1 vùng giới hạn là [2L,2R+1] . Bằng cách này ta có thể qui đổi về vùng giới hạn các nút lá ở độ sâu h .

Bài toán qui về là bắt đầu với khoảng tìm kiếm là [2^{h-1},2^h-1] ta có một loạt các truy vấn loại L,R,1 có nghĩa là số tìm kiếm nằm trong khoảng [L,R] và các truy vấn loại L,R,0 có nghĩa là số tìm kiếm không thuộc [L,R] . Hỏi rằng số tìm kiếm là số nào?

Khới đầu khoảng tìm kiếm là l=2^{h-1},r=2^h-1

  • Nếu gặp truy vấn L,R,1 : thì thu hẹp khoảng tìm kiếm l=max⁡(l,L),r=min⁡(r,R) ;
  • Nếu gặp truy vấn L,R,0 : thì ghi nhớ đoạn này.

Ta cần loại bỏ khoảng [l,r] các phần tử thuộc các đoạn thẳng đã được ghi nhớ. Để làm điều này trước tiên sắp xếp các đoạn ghi nhớ [a_i,b_i] sao cho a_1≤a_2≤\ldots≤a_k .

  • Lần lượt xét các đoạn [a_i,b_i]\ i=1,…,k nếu a_i≤l≤b_i thì đặt lại l=b_i+1
  • Lần lượt xét các đoạn [a_i,b_i]\ i=k,k-1,…,2,1 nếu a_i≤r≤b_i đặt lại r=a_i-1

Cuối cùng nếu đoạn rỗng thì thông báo "No", nếu đoạn có 1 điểm thì đây chính là lá có cửa thoát và nếu đoạn có hơn 1 điểm thì thông báo là "Multi"