Editorial for Giải mã
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Cách 1:
Gọi ~ST~ là xâu đã được mã hóa, ~M~ là số dòng của mảng sau khi phân phối xâu ~ST~ vào mảng.
~N~ là độ dài của khóa ~K~ và ~t~ độ dài của ~ST~, tính ~M=\frac{N}{t}~.
Phân phối xâu ~ST~ vào mảng ~A~ có ~M~ dòng, ~N~ cột theo thứ tự các cột được mô tả trong khóa ~K~.
Duyệt mảng ~A~ theo thứ tự từ trái qua phải, từ trên xuống dưới sẽ thu được kết quả.
Cách 2:
Nhận thấy nếu ta cắt chuỗi từ trái sang phải thành ~M~ chuỗi con mỗi chuỗi con có đúng ~N~ kí tự. Viết mỗi chuỗi con trên một hàng ta có một bảng gồm ~M~ hàng ~N~ cột kí tự thì trong bảng mới kí tự cột ~j~, hàng ~i~ có vị trí trong chuỗi cũ là ~j+N(i-1)~. Từ đó giải bài toán bằng cách duyệt xâu ~ST~ để tìm xâu ban đầu.
Comments