§Ò thi häc sinh giái toµn tØnh
líp 11 n¨m häc 2006-2007
C©u 1: (4 ®iÓm) Nút cha chung gần nhất
ANCES.PAS
Cây là một cấu trúc dữ liệu quen thuộc trong tin học. Ví dụ ta có cây với 16 nút
như hình bên dưới.
Các nút được đánh số từ 1 đến 16. Nút 8 là
gốc. Nút x được gọi là nút cha của y, nếu tồn
tại một đường dẫn từ gốc tới y đi qua x. Ví dụ,
nút 4 là nút cha của nút 16, nút 10 cũng là nút
cha của 16. Một nút đồng thời là nút cha của
chính mình. Như vậy, các nút 8, 4, 10 và 16 là
nút cha của 16. Nút x được gọi là nút cha
chung của hai nút khác nhau y và z, nếu nó
vừa là nút cha của y, vừa là nút cha của z. Ví
dụ, các nút 8 và 4 đều là nút cha chung của
các nút 7 và 16. Nút x được gọi là nút cha chung gần nhất của y và z, nếu nó là nút
cha chung của hai nút này và trên đường dẫn từ x tới y không còn nút cha chung nào
khác của y và z. Ở cây đang xét, 4 là nút cha chung gần nhất của 7 và 16.
Yêu cầu: Hãy lập trình tìm nút cha chung gần nhất của hai nút khác nhau của một cây
có N nút, các nút được đánh số từ 1 tới N.
Dữ liệu vào: Cho trong file văn bản ANCES.INP:
Dòng 1: Ghi số 2 nguyên N K, trong đó N là số nút của cây, K là nút gốc. Hai số ghi
cách nhau bởi dấu cách. 2≤N≤10000.
N-1 dòng tiếp theo: Mỗi dòng ghi 2 số nguyên là 2 nút liên tiếp của cây.
Dòng cuối cùng: Ghi 2 số nguyên, là 2 nút cần tìm nút cha chung gần nhất.
Dữ liệu ra: Ghi ra file văn bản ANCES.OUT, theo cấu trúc:
Dòng 1: Ghi một số nguyên, là nút cha chung gần nhất tìm được.
Ví dụ:
ANCES.INP
ANCES.OUT
16 8
4
1 14
85
10 16
59
46
84
4 10
1 13
6 15
10 11
67
10 2
16 3
81
16 12
16 7
C©u 2: (6 ®iÓm) §o¹n gèi dµi nhÊt
DOANGOI.PAS
Cho N ®o¹n th¼ng ®îc ®¸nh sè tõ 1 ®Õn N. Mçi ®o¹n th¼ng ®îc x¸c ®Þnh bëi
gi¸ trÞ ®iÓm ®Çu a vµ gi¸ trÞ ®iÓm cuèi b trªn trôc sè (a<=b).
Yªu cÇu: H·y x¸c ®Þnh mét tËp nhiÒu nhÊt c¸c ®o¹n th¼ng sao cho kh«ng cã hai ®o¹n
th¼ng nµo ®«i mét giao nhau (kÓ c¶ hai ®Çu mót).
D÷ liÖu vµo: Cho trong file DOANGOI.INP, theo cÊu tróc nh sau
Dßng 1: Ghi sè nguyªn d¬ng N lµ sè ®o¹n th¼ng. (1 <= N <= 1000)
N dßng tiÕp theo: Mçi dßng ghi 2 sè nguyªn a b, hai sè ghi c¸ch nhau mét dÊu c¸ch
(-32767 <= a,b <= 32767).
D÷ liÖu ra: Ghi ra file DOANGOI.OUT, theo cÊu tróc nh sau:
Dßng 1: Ghi sè nguyªn d¬ng M lµ sè lîng lín nhÊt c¸c ®o¹n th¼ng t×m ®îc
Dßng 2: Ghi chØ sè cña M ®o¹n th¼ng t×m ®îc theo thø tù t¨ng dÇn cña täa ®é ®iÓm
®Çu.
VÝ dô
DOANGOI.INP
3
3 9
1 2
5 10
2
2
DOANGOI.OUT
1
Híng dÉn chÊm thi häc sinh giái toµn tØnh
líp 11 n¨m häc 2006-2007
I/ Ph¬ng ph¸p chung
- Gi¸m kh¶o t¹o c¸c bé d÷ liÖu vµo, tÝnh to¸n kÕt qu¶. Ch¹y ch¬ng tr×nh cña häc sinh
vµ so s¸nh kÕt qu¶. Trong trêng hîp bµi to¸n cã nhiÒu kÕt qu¶ ®óng, kÕt qu¶ cña häc
sinh kh¸c ®¸p ¸n nhng vÉn dóng th× gi¸m kh¶o vÉn cho ®iÓm tèi ®a.
- Gi¸m kh¶o cã thÓ sö dông ch¬ng tr×nh mÉu ®Ó tÝnh kÕt qu¶ cña d÷ liÖu vµo.
- Ch¬ng tr×nh häc sinh ch¹y ®óng mçi bé test, gi¸m kh¶o cho 0.5 ®iÓm. Nh vËy, nÕu
c©u hái cã 3 ®iÓm th× gi¸m kh¶o ph¶i t¹o ®îc 6 bé test.
- NÕu ch¬ng tr×nh ch¹y sai test nµo th× gi¸m kh¶o cho 0 ®iÓm ®èi víi test ®ã.
II/ Ch¬ng tr×nh mÉu
ANCES.PAS
const fi='ances.in2';
fo='ances.ou2';
type mmc=array[1..10000] of word;
var tr,a,b:mmc; f:text; n,k,y,z,v:word;
procedure nhap;
var i:word;
begin
assign(f,fi);
reset(f);
readln(f,n,k);
tr[k]:=k;
for i:=1 to n-1 do
begin
readln(f,y,z);
tr[z]:=y;
end;
readln(f,y,z);
close(f);
end;
procedure xuly;
var d1,d2,i,j:word;
begin
d1:=0;
d2:=0;
repeat
inc(d2);
z:=tr[z];
b[d2]:=z;
until z=k;
repeat
INC(D1);
y:=tr[y];
a[d1]:=y;
for i:=1 to d2 do
if b[i]=a[d1] then
begin
v:=a[d1];y:=k;break;
end;
until y=k;
end;
procedure xuat;
begin
assign(f,fo);
rewrite(f);
writeln(f,v);
close(f);
end;
begin
nhap;xuly;xuat;
end.
DOANGOI.PAS
Program CAU1H;
Const fi='doangoi.in0';
fo='doangoi.ou0';
Type m1c=array[0..1000] of integer;
Var qh,d,c,t,cs,k:m1c; n,max,l:integer;
Procedure Nhap;
var f:text;
i:integer;
begin
assign(f,fi);
reset(f);
readln(f,n);
for i:=1 to n do readln(f,d[i],c[i]);
close(f);
end;
Procedure KhoiTao;
var i:integer;
begin
for i:=1 to n do qh[i]:=1;
fillchar(t,sizeof(t),0);
for i:=1 to n do cs[i]:=i;
end;
Procedure hv(var x,y:integer);
var t:integer;
begin
t:=x;x:=y;y:=t;
end;
Procedure SapXep;
var i,j:integer;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if d[i]>d[j] then
begin
hv(d[i],d[j]);
hv(c[i],c[j]);
hv(cs[i],cs[j]);
end;
end;
{!}
Procedure XuLy;
var i,j:integer;
begin
for i:=2 to n do
for j:=1 to i-1 do
if (c[j]
- Xem thêm -
.DOC 
5 
173 
69 
