Thi HSG Quốc gia 2010
CCKLK: Dãy con chung không liền kề dài nhất
Cho dãy số nguyên dương x = (x1, x2, ..., xn). Dãy y = (xi1, xi2, ..., xik) được gọi là dãy con không liền kề của
dãy x nếu 1
i1 < i2
1 < ... < ik
1
n. Cho 2 dãy số nguyên a gồm n phần tử và b gồm m phần tử. Xác
định chiều dài k của dãy con chung không liền kề dài nhất của a và b. 2
m, n
1000, 1
ai, bi
10000.
CCKLK.INP CCKLK.OUT Giải thích
5 6
1 5 3 8 2
2 1 3 4 2 6
2 CCKLK.INP: Dòng đầu: n m. Từ dòng thứ hai trở đi: Dãy số a,
tiếp đến là dãy số b.
CCKLK.OUT: k.
Thuật toán
Quy hoạch động.
Gọi d(i,j) là đáp số của bài toán khi xét hai dãy a[1..i] và b[1..j]. Ta có:
Nếu i ≤ 0 thì ta quy ước d(i,j) = 0,
Nếu a[i] = b[j] thì d(i,j) = d(i−2,j−2),
Nếu a[i] ≠ b[j] thì d(i,j) = max { d(i−1,j), d(i,j−1) }.
Để cài đặt ta dùng 3 mảng một chiều x, y và z với ý nghĩa x[j] = d(i−2,j), y[j] = d(i−1,j) và z[j] = d(i,j). Khi
đó hệ thức trên được viết là:
Nếu i ≤ 0 thì ta quy ước d(i,j) = 0,
Nếu a[i] = b[j] thì d(i,j) = d(i−2,j−2) ứng với z[j] = x[j−2],
Nếu a[i] ≠ b[j] thì d(i,j) = max { d(i−1,j), d(i,j−1) } ứng với z[j] = max { y[j], z[j−1] }.
Muốn tránh các phép copy dữ liệu từ y sang x; từ z sang y và từ x sang z ta chỉ cần tráo đổi các con trỏ
mảng.
Độ phức tạp
O(n.m)
Chương trình Pascal
(* CCKLK.PAS
k: chieu dai day con chung khong lien ke dai nhat
cua hai day so nguyen duong a[1..n], b[1..m]
*)
const fn = 'ccklk.inp'; gn = 'ccklk.out';
bl = #32; nl = #13#10; mn = 1001;
type int = integer;
mi1 = array[0..mn] of int;
var
n, m: int;
a, b: mi1;
function Max(a,b: int): int;
begin if a >= b then Max := a else Max := b; end;
procedure Doc;
var i: int;
f: text;
begin
assign(f,fn); reset(f);
read(f,n, m);
writeln(n,bl,m);
for i := 1 to n do read(f,a[i]);
for i := 1 to m do read(f,b[i]);
write(nl, 'a: ');
for i := 1 to n do write(a[i],bl);
write(nl, 'b: ');
for i := 1 to n do write(b[i],bl);
close(f);
end;
procedure Ghi(k: int);
var g: text;
begin
assign(g,gn); rewrite(g);
writeln(g,k); close(g);
end;
(*
d(i,j) = dap so cua bai toan voi a[1..i], b[1..j]
d(i,j) = d(i-2,j-2) + 1, if a[i] = b[j]
= Max begin d(i,j-1), d(i-1,j) end;, elsewhere
= 0, if i < 1 || j < 1
*)
function QHD: int;
var i, j, v: int;
c: array[1..3] of mi1;
x, y, z, t: int;
begin
x := 1; y := 2; z := 3;
{ Init i = 0 }
fillchar(c[x],sizeof(c[x]), 0);
{ Init i = 1 }
c[y][0] := 0; v := 0;
for j := 1 to m do
begin
if (a[1] = b[j]) then v := 1;
c[y][j] := v;
end;
v := 0;
for i := 2 to n do
begin
c[z][0] := 0;
if (a[i] = b[1]) then v := 1;
c[z][1] := v;
for j := 2 to m do
if (a[i] = b[j]) then c[z][j] := c[x][j-2]+1
else c[z][j] := Max(c[z][j-1],c[y][j]);
t := x; x := y; y := z; z := t;
end;
QHD := c[y][m];
end;
BEGIN
Doc;
Ghi(QHD);
write(nl,' Fini ');
readln;
END.
Chương trình CPP
/* DevC++ CCKLK.CPP
k: chieu dai day con chung khong lien ke dai nhat
cua hai day so nguyen duong a[1..n], b[1..m]
*/
#include <fstream>
#include <iostream>
using namespace std;
// D A T A A N D V A R I A B L E
const char * fn = "ccklk.inp";
const char * gn = "ccklk.out";
const int mn = 1001;
int n, m;
int a[mn],b[mn];
// P R O T O T Y P E S
void Doc();
int QHD(); // Quy hoach dong
void Ghi(int);
int Max(int,int);
// I M P L E M E N T A T I O N
int main() {
Doc();
Ghi(QHD());
cout << endl << " Fini ";
cin.get();
return 0;
}
int Max(int a, int b) { return (a >= b) ? a : b; }
void Doc() {
int i;
ifstream f(fn);
f >> n >> m;
cout << endl << n << " " << m;
for (i = 1; i <= n; ++i) f >> a[i];
for (i = 1; i <= m; ++i) f >> b[i];
cout << endl << "a: ";
for (i = 1; i <= n; ++i) cout << a[i] << " ";
cout << endl << "b: ";
for (i = 1; i <= m; ++i) cout << b[i] << " ";
f.close();
}
void Ghi(int k) {
ofstream g(gn);
g << k;
g.close();
}
/*
d(i,j) = dap so cua bai toan voi a[1..i], b[1..j]
d(i,j) = d(i-2,j-2) + 1, if a[i] = b[j]
= Max { d(i,j-1), d(i-1,j) }, elsewhere
= 0, if i < 1 || j < 1
*/
int QHD() {
int *x, *y, *z, *t;
int i, j , m1 = m+1, v ;
x = new int[m1];
y = new int[m1];
z = new int[m1];
// Init i = 0
memset(x,0,sizeof(int)*m1);
// Init i = 1
y[0] = 0; v = 0;
for (j = 1; j <= m; ++j) {
if (a[1] == b[j]) v = 1;
y[j] = v;
}
v = 0;
for (i = 2; i <= n; ++i) {
z[0] = 0;
if (a[i]==b[1]) v = 1;
z[1] = v;
for (j = 2; j <= m; ++j)
z[j] = (a[i] == b[j]) ? x[j-2]+1 : Max(z[j-1],y[j]);
t = x; x = y; y = z; z = t;
}
v = y[m];
delete x; delete y; delete z;
return v;
}
Ổn định
Cho đồ thị có hướng gồm n đỉnh và m cung (u,v). Cho trước đỉnh s. Một đỉnh d ≠ s được gọi là ổn định đối
với s nếu có ít nhất hai đường đi ngắn nhất từ s tới d. Hãy tính k là số lượng đỉnh ổn định đối với đỉnh s.
2
n
10000, 1
m
50000.
ONDINH.INP ONDINH.OUT Giải thích
6 7 1
1 2
1 4
2 3
2 5
4 5
2 3
5 6
2 ONDINH.INP: Dòng đầu: n m s. Từ dòng thứ hai trở đi:m cung
dạng u v. Có thể có các cung trùng nhau (dư thừa).
ONDINH.OUT: k.
Thí dụ cho biết: có 3 đỉnh ổn định đối với đỉnh 1 là các đỉnh 5
và 6.
1 → 2 → 5; 1 → 4→ 5;
1 → 2 → 5→ 6; 1 → 4→ 5→ 6.
Thuật toán
Dùng một biến thể của thuật toán Dijkstra.
// Ondinh.CPP
// HSG 2010
#include <string.h>
#include <fstream>
#include <iostream>
//#include <mem.h>
using namespace std;
// D A T A A N D V A R I A B L E S
char * fn = "ondinh.inp";
char * gn = "ondinh.out";
const int mn = 10001;
const int mm = 50001;
typedef struct { int a, b; } cung;
cung c[mm];
int len[mn]; // len[i] chieu dai s => i
char mark[mn]; // mark[i] danh dau dinh i:
// Chua xet 0; Co trong hang doi q 1; Da xu li 2
int d[mn]; // d[i] so luong duong ngan nhat s => i
int q[mn]; // hang doi
int n, m, s ; // so dinh n, so cung m, dinh xuat phat s
// P R O T O T Y P E S
int main();
void Doc();
int XuLi();
int Min(int, int);
int BinSearch(cung [], int, int, int);
int Sanh(int,int,int,int);
void Ghi();
int main(){
Doc(); XuLi(); Ghi();
cout << endl << " Fini"; cin.get();
return 0;
}
int Min(int a, int b) { return (a <= b) ? a : b; }
void Ghi() {
int i, k = 0;
for (i = 1; i <= n; ++i)
if (d[i] > 1) ++k;
ofstream g(gn);
g << k;
g.close();
}
int XuLi() {
int i, j, k, v, r;
v = 0; r = 0;
memset(mark,0,sizeof(mark));
memset(d,0,sizeof(d));
len[s] = 0; d[s] = 1;
q[++v] = s;
while (r < v) { // 1
i = q[++r]; cout << endl << " Xet dinh " << i;
mark[i] = 2;
for (k = BinSearch(c,m,i,0); c[k].a == i; ++k) { // 2