Bình luận

• 
  

  -10

  

  xero2409  đã bình luận lúc 28, Tháng 4, 2023, 5:03 ← sửa 4 →

  Thuật chuẩn:

  xài chặt nhị phân

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

• 
  

  -5

  

  PM  đã bình luận lúc 23, Tháng 7, 2023, 2:39

  ? đòi đú:))

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

• 
  

  29

  

  marvinthang  đã bình luận lúc 19, Tháng 3, 2022, 14:38 ← chỉnh sửa →

  Thuật chuẩn:

  ~Binary Search~

  Check bằng quy hoạch động

  ~F_i~: có tồn tại trạng thái 1 người ở nhà thứ i không, nếu có tìm j lớn nhất thỏa mãn khoảng cách từ ~X_{i + 1}, .. X_j~ đến ~X_i \leq D~ thì ~ F_{i + 1}, .., F_j = true~.

  ĐPT: ~O(N^2 * \log_2 N~)

  Cải tiến:

  Sử dụng ~Sparse Table~ kết hợp ~Binary Search~ để tìm j, j thỏa mãn khi khoảng cách từ ~max(X_{i + 1}, .., X_j)~ và ~min(X_{i + 1}, .., X_j)~ đến ~X_i \leq D~.

  ĐPT ~O(N * log_2^2 N~)

  Code mẫu: Ideone