Link Sub: http://www.spoj.com/PTIT/problems/PTIT124G/
Người Gửi: Dương Lee
- Problem:
8 2 3 5 6 4 7 1 9Cho một tập bài gồm n lá bài đánh số từ 1 tới n theo thứ tự từ trên xuống dưới. Đầu tiên người ta viết vào mỗi lá bài một số nguyên là số thứ tự lá bài đó. Xét phép tráo S(i,j): Rút ra lá bài ghi số nguyên i và chèn lên trên lá bài mang số nguyên j (i≠j). Ví dụ: Với n=9:
Input
- Dòng 1 chứa hai số nguyên dương n,x ≤ 105
- x dòng tiếp theo, dòng thứ k chứa hai số nguyên dương ik , jk cho biết phép tráo thứ k là S(ik , jk) (ik ≠ jk, 1 ≤ ik , jk ≤n)
Output
Một dòng gồm n số nguyên là các số ghi trên lá bài theo thứ tự từ trên xuống dưới.
Example:
Một dòng gồm n số nguyên là các số ghi trên lá bài theo thứ tự từ trên xuống dưới.
Input
9 3
8 2
4 7
1 9
Output:
8 2 3 5 6 4 7 1 9
- Solution:
Bài này mặc dù không phải cài đặt double link list. Nhưng nó là ví dụ dễ hiểu và cơ bản nhấy của cách hoạt động của danh sách liên kết kép.
Ta sẽ dựa trên tư tưởng double link list để thực hiện:
- Mỗi số sẽ có 2 giá trị đó là: giá trị trước (front), giá trị sau (behind)
VD với khởi tạo ban đầu: n=9 ta có: [1](front = 0, behind = 2); [2](front = 1, behind = 3);... [9](front = 8, behind = 11);
- Với mỗi truy vấn S (i, j) ta sẽ xóa liên kết xung quanh (i) là (i_front và i_back) và nối (i) vào giữa (j_front và j).
- Cuối cùng là tìm giá trị đầu và cuối và in danh sách.
* Xem hình vẽ để rõ hơn về danh sách liên kết kép (double link list).