Advertisement
trungore10

minmov_notAC

Feb 11th, 2019
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.07 KB | None | 0 0
  1. minmov :
  2. - Giả sử ta đã sort các điểm lại theo pair
  3. - Truy vấn (S, T) : với S, T là 2 vị trí trên dãy sau khi sort và S < T
  4. - Nhận thấy các bước di chuyển từ S -> T chắc chắn phải có dạng LRLR hoặc RLRL
  5. +, giả sử đi 2 bước LL liên tục thì ta nhận thấy răng 2 bước đó là không cần thiết chỉ cần đi một bước L để đến mà thôi
  6.  
  7. - Xây trước set<int> : Set[x] là tập các điểm có hoành độ là x
  8.  
  9. - Xét bước L :
  10. +, Nhận thấy nếu tồn tại (x1, y1), (x2, y2) : x1 <= x2 && y1 <= y2 thì ta luôn nhảy đến (x1, y1)
  11. +, Vậy nếu ta đang ở vị trí (u, v) thì ta sẽ xây các tập điểm nhờ bước L thỏa mãn
  12. * i < j, Xi < Xj, Yi < Yj
  13. +, Ta có thể bỏ tập đó vào set để xử lí dễ dàng hơn.
  14. +, Với mỗi truy vấn (u, v) thì ta sẽ for lại trong tập của mình và xóa phần tử thỏa mãn (x, y) <= (u, v), và bổ sung
  15. thêm vào tập hợp hiện tại của mình thằng kế tiếp trong Set[x]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement