Bình luận

• 
  

  1

  dangluu2013    11:24 a.m. 27 Tháng 4, 2024 ← đã chỉnh sửa →

  Mình xin phép trình bày editioral của mình cho bài này như sau:

  Sub1: Gọi là a
  a là tổng mã màu của m
  m hạt cườm. Vì phải chọn đúng m-1 hạt nên ta có thể sử dụng r(m)
  r(m) để kiểm tra: nếu a−z𝑖=aa−z i
  =a thì tăng biến đếm lên

  Sub2: Sử dụng quay lui bình thường, với mỗi lần quay phải kiểm tra 2
  2 điều kiện là phải chọn đúng b
  b hạt và tổng mã màu phải bằng a
  a

  Sub3: Kết hợp phân tập. 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
  2 phần chênh lệch nhỏ nhất có thể. VD mảng 5
  5 phần tử thì chia làm mảng 2
  2 và 3
  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
  1 mảng

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

  Sắp xếp lại 2
  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
  Do đây là lần đầu tiên mình làm editioral nên có sai sót gì thì các bạn giúp mình chứ đừng có downvote mình nha 🙁

• 
  

  0

  huyhau6a2    7:01 p.m. 4 Tháng 7, 2022

  Tố cáo Mancha27 if test

• 
  

  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

  1 phản hồi