Link Sub: http://www.spoj.com/PTIT/problems/GOODFRIE/
Người Gửi: Dương Lee
- Problem:
Trong một lớp học, cô giáo xếp hạng N học sinh theo thứ tự điểm số từ cao xuống thấp. Hai học sinh sẽ là bạn nếu thứ tự của họ là gần nhau, tức là khác biệt giữa thứ tự không quá K. Ví dụ: nếu K = 1, thì chỉ có 2 học sinh ở trước và sau danh sách là bạn của 1 học sinh. Thêm nữa, hai học sinh gọi là bạn tốt nếu họ là bạn và tên của họ có cùng độ dài. Viết chương trình tính số các cặp bạn tốt trong lớp.
Input
Dòng đầu chứ N (3<=N<=300 000) và K (1<= K <=N).
N dòng tiếp theo, mỗi dòng chứa tên một học sinh theo danh sách xếp hạng (từ 2 đến 20 chữ cái tiếng Anh in hoa).
Output
Số cặp bạn tốt.
Example:
Số cặp bạn tốt.
Input
4 2
IVA
IVO
ANA
TOM
Output:
5
Input
6 3
CYNTHIA
LLOYD
STEVIE
KEVIN
MALCOLM
DABNEY
Output:
2
- Solution:
Quy hoạch mảng arr có dạng:
tất cả độ dài của xâu_i có arr[i] = tất cả độ dài của xâu_(i-1) arr[i-1] + 1 (của độ dài xâu_i).
VD:
3
IV
IVO
AN
->
arr[0] = {at[0]=0, at[1]=0, at[2]=0,...};
arr[1] = arr[0] + arr[0]{at[2]++} = {at[0]=0, arr[1]=0, arr[2]=1, arr[3]=0,...};
arr[2] = arr[1] + arr[1]{at[3]++} = {at[0]=0, arr[1]=0, arr[2]=1, arr[3]=1,...};
arr[3] = arr[2] + arr[2]{at[2]++} = {at[0]=0, arr[1]=0, arr[2]=2, arr[3]=1,...};
-> Như vậy: arr[i].at[j] lưu lại số lượng xâu có độ dài là j từ xâu: 1->i;
-> Tại mỗi xâu ta có thể xác định số cặp có thể ghép được với xâu đó bằng phép tính: (arr[i].at[len] - arr[i-k-1].at[len] - 1);Input
6 3
CYNTHIA
LLOYD
STEVIE
KEVIN
MALCOLM
DABNEY
Output:
2