Editorial for Bedao Regular Contest 01 - ZSTRING


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Đầu tiên để có thể tạo được một chuỗi ta cần có những điều kiện sau:

  • Chuỗi có ~1~ phần tử thì phần tử đầu luôn luôn là 'z'
  • Chuỗi được tạo ra thì các ký tự luôn có thứ tự từ điển bé hơn hoặc bằng 'z'lớn hơn hoặc bằng 'a'
  • Nếu ~A_1~ = ~1~ và ~2~ ~\leq~ n thì ta không thể tạo được chuỗi nào phù hợp

Bằng phương pháp tham lam ta có thể tạo được chuỗi có thứ tự từ điển nhỏ nhất khi :

  • Đối với ~i~ lẻ ta rút ra nhận xét rằng với từ đầu tiên được thêm vào dãy trong lúc xử lý thì từ đó phụ thuộc vào thứ tự từ điển từ cuối cùng của lần xét ~i-1~ trước trừ đi cho ~1~ và ~A_i-1~ phần tử còn lại là một dãy ký tự giảm dần liên tiếp có kết thúc là ký tự 'a' ( luôn thỏa mãn ký tự đứng sau có thứ tự từ điển bé hơn ký tự đứng trước )

Vậy việc cần làm của chúng ta đối với lần xét i lẻ ta chỉ cần thêm ký tự đầu tiên vào dãy theo quy luật bằng phần tử cuối của lần xử lý ~i-1~ trừ ~1~ và sao đó ta duyệt ~A_i-1~ lần thêm lần lượt các ký tự từ 'a'+~A_i-2~ đến 'a' ( vì đã thêm ~1~ ký tự và đây là chuỗi liên tiếp có ~A_i-1~ phần tử có thứ tự từ điển giảm dần và có kết thúc tại 'a' ) và điều kiện để chuỗi đó thỏa mãn là 'a'+~A_i-2~ luôn có thứ tự từ điển bé hơn phần tử đầu tiên được thêm vào.

  • Đối với ~i~ chẵn ta rút ra nhận xét rằng đây chỉ là là dãy liên tiếp tăng dần với từ đầu tiên luôn bằng 'b' vì ta luôn có từ cuối của dãy sau khi xét ~i~ lẻ là 'a'. Ta chỉ cần duyệt ~A_i~ lần và mỗi lần lặp ta thêm lần lượt các ký tự tăng dần bắt đầu từ 'b' ( luôn thỏa mãn ký tự đứng sau có thứ tự từ điển lớn hơn ký tự đứng trước ) và ta cần xét xem các thứ tự từ điển của ký tự đấy có nằm trong đoạn từ 'a' đến 'z' hay không.

Lưu ý: Ta phải quan tâm với phần tử cuối sau khi xét thì kiểm tra xem từ đó có lớn hơn hoặc bằng ~A_{i+1}+~ 'a' hay không ( mục đích tạo thêm tiếp ~A_{i+1}~ ký tự có quy luật được ). Nếu có thì giữ nguyên còn nếu không thì thay ký tự đó bằng ký tự có thứ tự từ điển là ~A_{i+1}~+ 'a' .


Comments

Please read the guidelines before commenting.


There are no comments at the moment.