Bình luận

• 
  

  11

  huyhau6a2    2:20 p.m. 4 Tháng 7, 2022 ← đã chỉnh sửa →

  Mình xin phép đóng góp editioral cho bài này như sau:

  • Sub 1: Gọi \(S\) là tổng mã màu của \(n\) hạt cườm. Vì phải chọn đúng n-1 hạt nên ta có thể sử dụng \(O(n)\) để kiểm tra: nếu \(S-C_i=s\) thì tăng biến đếm lên

  • Sub 2: Áp dụng quay lui bình thường, với mỗi lần quay phải kiểm tra \(2\) điều kiện là phải chọn đúng \(m\) hạt và tổng mã màu phải bằng \(s\)

  • Sub 3: Kết hợp phân tập. Ở đây mình xin phép giải thích về cách làm này:

  • Với cách làm này, ta sẽ chia đôi mảng làm \(2\) phần chênh lệch nhỏ nhất có thể. VD mảng \(5\) phần tử thì chia làm mảng \(2\) và \(3\) phần tử

  • Với từng mảng thì ta sẽ quay lui rồi lưu kết quả thu được vào \(1\) mảng

  • Sau khi quay lui xong ta có thể áp dụng \(1\) trong \(2\) cách:

    • Sắp xếp lại \(2\) mảng rồi áp dụng chặt nhị phân hoặc hai con trỏ(cách này sẽ lâu hơn cách ở dưới)

    • Giải trực tiếp khi thực hiện quay lui nửa mảng còn lại

  Vậy là bài toán đã được giải quyết xong! Nếu các bạn có vấn đề gì hãy comment cho mình nha

• 
  

  0

  dbthuan208    7:55 p.m. 24 Tháng 6, 2023

  cảm ơn idol hậu ❤️
2 bình luận nữa