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
Bình luận
Tố cáo Mancha27 if test
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