Bài toán về sự tương thích
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (135.76 KB, 15 trang )
Bài toán về sự tương thích
Nguyễn Duy Khương
Có rất nhiều bài toán cần kiểm tra hoặc buộc phải kiểm tra tính giống nhau của hai thành
phần nào đó với yêu cầu tốc độ cao. Muốn 'ăn' hết test bạn cần phải có một thuật giải tốt.
Tôi xin nêu ra một cách làm tương đối hay như sau:
Trước tiên, ta phát biểu dạng tổng quát của bài toán:
Cho hai đối tương A, B (là các đồ thị, dãy số...). Hai phần tử A, B gọi là tương thích nếu
A, B cùng thoả mãn tính chất nào đó. Bài toán yêu cầu kiểm tra sự tương thích giữa hai đối
tương A, B.
Thuật giải: Xây dựng một quy tắc mã hoá thoả mãn: Tất cả các đối tượng có cùng tính chất
thì kết quả mã hoá phải giống nhau.
Xét các ví dụ:
Bài 1:
Cho hai cây A, B gồm N đỉnh (1 ≤ N ≤ 1000), gốc R1, R2. A, B gọi là tương đương nếu
chỉ cần thay đổi nhãn các đỉnh của B thì thu được A.
Yêu cầu: Hãy xác định A, B có tương đương không?
Input: TREE.IN
- Dòng đầu ghi N.
- Dòng hai ghi R1 là gốc cây A.
- N - 1 dòng tiếp mô tả các cạnh của cây A.
- Dòng tiếp theo ghi R2 là gốc của B.
- N - 1 dòng tiếp mô tả các cạnh của cây A.
Ouput: TREE.OUT
- Dòng đầu ghi là YES nếu tương đương, NO nếu không.
- Dòng thứ hai gồm N số, số thứ I là nhãn nút của cây B tương ứng với nút I của A.
Nhận xét:
- Theo như đề bài hai gốc sẽ giữ cùng nhãn.
- Như vậy ta sẽ phải sắp xếp các nút con theo một trật tự để tương đương. Bạn có thể duyệt
đến khoảng 100, nhưng > 1000 một thuật toán tối ưu hơn.
Thuật giải: Xây dựng quy tắc mã hoá một cây sau:
- Bắt đầu từ nút gốc. Ta xây dựng đệ quy như sau: Tại mỗi nút, số đầu tiên của dãy mã hoá
nút đó là: S là số nút con của đỉnh đó. Tiếp sau là dãy mã hoá nhỏ nhất của các nút con nó,
và tiếp tục lớn dần.
- Như vậy ta thấy rằng: 1 dạng cây có duy nhất một cách mã hoá, và ngược lại một cách
mã hoá xác định 1 dạng cây duy nhất. Hai cây tương đương khi và chỉ khi dãy mã hoá của
chúng là giống nhau.
{$N+,Q+,R+,S+}
{$M 60384,0,655360}
Const
Tfi = 'TREE.IN';
Tfo = 'TREE.OUT';
MaxN = 1001;
Type Pnode = ^Tnode;
Tnode = Record
x : Integer;
Next : Pnode; End;
Arr1p = Array[0..MaxN] of Pnode;
Arr1i = Array[0..MaxN] of Integer;
Var Q1, Q2 : Arr1p;
Code : Array [1..2] of Arr1p;
Tr1, Tr2 : Pnode;
Order, Nson1, Nson2 : Arr1i;
Visit : Array [0..MaxN] of Byte;
N, R1, R2 : Integer;
Fi, Fo : Text;
Procedure Push (x : Integer; Var Last : Pnode);
Var p : Pnode;
Begin
New (p);
p^.x := x;
p^.Next := Last;
Last := p;
End;
Procedure Readlist;
Var i, x, y : Integer;
Begin
Assign (Fi, Tfi); Reset (Fi);
Readln (Fi, N);
Readln (Fi, R1);
For i := 1 to N - 1 do
Begin
Readln (Fi, x, y);
Push (x, Q1[y]);
Push (y, Q1[x]);
End;
Readln (Fi, R2);
For i := 1 to N - 1 do
Begin
Readln (Fi, x, y);
Push (x, Q2[y]);
Push (y, Q2[x]);
End;
Close (Fi);
End;
Procedure MakeCode (Root : Integer;
Var Q : Arr1p; Var Son : Arr1i; Var Tree : Pnode);
Procedure InitNumSon (x : Integer);
Var p : Pnode;
Begin
Visit[x] := 1;
p := Q[x];
Son[x] := 1;
While p <> Nil do
Begin
If Visit[p^.x] = 0 Then
Begin
InitNumSon (p^.x);
Son[x] := Son[p^.x] + Son[x];
End;
p := p^.Next;
End;
End;
Procedure Swapi (Var x, y : Integer);
Var i : Integer;
Begin
i := x; x := y; y := i;
End;
Function Kind (r1, r2 : Pnode) : Byte;
Begin
Kind := 0;
While r1 <> Nil do
Begin
If Son[r1^.x] <> Son[r2^.x] Then
Begin
If Son[r1^.x] > Son[r2^.x] Then Kind := 1 Else Kind := 2;
Exit;
End;
r1 := r1^.Next;
r2 := r2^.Next;
End;
End;
Procedure Sort (l, r : Integer);
Var i, j : Integer;
tr : Pnode;
Begin
If l >= r Then Exit;
i := l + Random (r - l + 1);
tr := Code[1, Order[i]];
i := l;
j := r;
Repeat
While Kind (Code[1, Order[i]], tr) = 1 do i := i + 1;
While Kind (Code[1, Order[j]], tr) = 2 do j := j - 1;
If i <= j Then
Begin
Swapi (Order[i], Order[j]);
i := i + 1;
j := j - 1;
End;
Until i > j;
Sort (i, r);
Sort (l, j);
End;
Procedure BuildCode (x : Integer);
Var p : Pnode; i, All : Integer;
Begin
All := 0;
Visit[x] := 1;
p := Q[x];
While p <> Nil do
Begin
If Visit[p^.x] = 0 Then BuildCode (p^.x);
p := p^.Next;
End;
Visit[x] := 2;
p := Q[x];
While p <> Nil do
Begin
If Visit[p^.x] = 2 Then
Begin
Inc (All);
Order[All] := p^.x;
End;
p := p^.Next;
End;
Sort (1, All);
p := Nil;
Push (x, p);
p^.Next := Code[1, Order[All]];
Code[1, x] := p;
For i := All downto 2 do
Code[2, Order[i]]^.Next := Code[1, Order[i - 1]];
If All >= 1 Then Code[2, x] := Code[2, Order[1]] Else Code[2, x] := p;
End;
Begin
Fillchar ( Visit, sizeof (Visit), 0);
InitNumSon (root);
Fillchar ( Visit, sizeof (Visit), 0);
BuildCode (root);
Tree := Code[1, Root];
End;
Function Check (R1, R2 : Pnode) : Boolean;
Var i : Integer;
Begin
Check := False;
For i := 1 to N do
Begin
If NSon1[R1^.x] <> Nson2[R2^.x] Then Exit;
R1 := R1^.Next;
R2 := R2^.Next;
End;
Check := True;
End;
Procedure Print;
Var i : Integer; p1, p2 : Pnode;
Begin
Assign (Fo, Tfo); Rewrite (Fo);
If Check (Tr1, Tr2) Then
Begin
Writeln (Fo, 'YES');
p1 := Tr1;
p2 := Tr2;
For i := 1 to N do
Begin
Order[p1^.x] := p2^.x;
p1 := p1^.Next;
p2 := p2^.Next;
End;
For i := 1 to N do
Write (Fo, Order[i], ' ');
Writeln (Fo);
End Else Writeln (Fo, 'NO');
Close (Fo);
End;
Begin
Readlist;
MakeCode (R1, Q1, Nson1, Tr1);
MakeCode (R2, Q2, Nson2, Tr2);
Print;
End.
Bài 2:
Cho hai dãy số nguyên {a
n
}, {bn} (1& le; N ≤ 100000, 1 ≤ a
i
, b
i
≤ 8000). Hai dãy số gọi là
tương thích nếu:
+) nếu vị trí I có hai giá trị ai, bi thì bất kỳ j <> i mà a
i
= a
j>
=> b
i
= b
j
.
