Hướng dẫn cho HackDream Orange 07-D: Tên sản phẩm
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Solution : Tên sản phẩm
Ta luôn biến đổi một nửa xâu bên này giống với nửa xâu đối diện. Dễ dàng đưa ra nhận xét rằng con trỏ đang nằm ở nửa xâu bên nào thì ta sẽ biến đổi luôn nửa xâu bên đó. Rõ ràng hơn với n là độ dài xâu, ta chia xâu thành 2 phần bằng nhau gọi là xâu bên trái và bên phải thì:
- Với ~p <= n / 2~ : Ta sẽ biến đổi nửa xâu bên trái thành giống với nửa xâu bên phải
- Với ~p > n / 2~ : Ta sẽ biến đổi nửa xâu bên phải thành giống với nửa xâu bên trái
Khi đó, sẽ có 2 cách di chuyển con trỏ, một là đi sang trái trước rồi đi sang phải và ngược lại. Thử cả 2 phương án để tìm ra phương án tối ưu và được đáp án.
Bình luận