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 = (x
1
, x
2
, , x
n
). Dãy y = (x
i1
, x
i2
, , x
ik
) đượ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

*)
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;

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;

}

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) {

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";

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
j = c[k].b; // xet cac dinh j ke dinh i
if (mark[j] == 0) {
len[j] = len[i]+1; mark[j] = 1;
d[j] = d[i]; q[++v] = j;
}
else if (mark[j] == 1) {
if (len[i]+1 == len[j]) d[j]++;
}
} // 2
} // 1
for (i = 1; i <= n; ++i) cout << d[i] << " ";
}

if (Sanh(c[j].a,c[j].b,u,v) < 0) { ++k; c[k].a = u; c[k].b
= v; }
else {
memmove(&c[j+1], &c[j], (k-j+1)*sizeof(cung));// <mem.h>
c[j].a = u; c[j].b = v; ++k;
}
}
}
f.close();
m = k;
}
// Ondinh.CPP Phuong an cu
// 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;

}

void Ghi() {
int i, k = 0;
for (i = 1; i <= n; ++i)
if (s[i] > 1) ++k;
ofstream g(gn);
g << k;
g.close();
}

int XuLi() {
int i, imin, j, k;
memset(d,0,sizeof(d));
for (i = 2; i <= n; ++i) s[i] = 0;
s[x] = 1;
p[0] = n+2; p[x] = 0;
for (i = 2; i <= n; ++i) p[i] = n+1;
for (i = 1; i <= n; ++i) {
imin = Minp();
for (k = BinSearch(c,m,imin,0); c[k].a == imin; ++k) {
j = c[k].b;
if (!d[j]) {
if (p[imin]+1 < p[j]) { p[j] = p[imin]+1; s[j] =
s[imin]; }
else if (p[imin]+1 == p[j]) ++s[j];
}
}
}
}

= v; }
else {
memmove(&c[j+1], &c[j], (k-j+1)*sizeof(cung));// <mem.h>
c[j].a = u; c[j].b = v; ++k;
}
}
}
f.close();
m = k;
}

Mã số thuế
Xét tập S gồm tất cả các số 1 n trong hệ 36, 36

n

10
16
. Cho số m: 3

m

70. Xét dãy số nguyên 1 < c
1

< c
2
< < c
k
< 36, k =

, ,a
j-1
, a
j
), 1

i <= j

n. Hãy tìm
đoạn dài nhất gồm các phần tử đôi một khác nhau.
1

n, a
i


100000.
Dữ liệu vào: Tệp văn bản diff.inp
 Dòng đầu tiên: số n.
 Từ dòng thứ hai trở đi: dãy số a.
Dữ liệu ra: Tệp văn bản diff.out chứa 2 số:
 imax

chỉ số đầu tiên của đoạn dài nhất tìm được trong dãy a
 dmax

số phần tử của doạn dài nhất.
Các số trên cùng dòng cách nhau qua dấu cách.

diff.inp diff.out

p[2] = 2/7 cho biết số 2 lúc đầu xuất hiện tại vị trí 2 trong dãy a, sau đó
xuất hiện tại vị trí 7 trong dãy a. p[8] = p[10] = 0 cho biết các số 8 và 10
không xuất hiện trong dãy a.

Ta gọi p là dãy trỏ ngược hay dãy vị trí của dãy a. Ta xử lý từng đoạn d của a
i
như sau. Mỗi đoạn d sẽ bao
gồm một dãy liên tiếp các phần tử đôi một khác nhau tính từ chỉ số i đến j. Thí dụ trên cho ta lần lượt 3
đoạn sau:
 Đoạn thứ nhất d = a[1 4] = (5, 2, 4, 1), i = 1, j = 4,
 Đoạn thứ hai d = a[2 6] = (2, 4, 1, 5, 3), i = 2, j = 6,
 Đoạn thứ ba d = a[3 10] = (4, 1, 5, 3, 2, 7, 6, 9), i = 3, j = 10.
Mỗi đoạn d được xác định như sau: Mỗi khi gặp phần tử a
j
đầu tiên trùng với một phần tử trong dãy tính từ
i thì ta cắt ra được đoạn d = a[i j1].
Với mỗi đoạn d[i j] ta tính số phần tử của đoạn đó là ji+1 và cập nhật giá trị dmax. Để khởi trị cho đoạn
tiếp theo, ta đặt i = p[a
j
]+1. Chú ý rằng p[a
j
] là vị trí xuất hiện của giá trị lặp a
j
.
Độ phức tạp
O(n)
Chương trình Pascal
(* diff.pas
Tim doan dai nhat gom cac
phan tu doi mot khac nhau

istart := p[v]+1;
end;
p[v] := i;
end;
close(f);
i := n+1;
if (i-istart > dmax) then
begin
dmax := i-istart; imax := istart;
end;
assign(g,gn); rewrite(g);
write(g, imax, nl, dmax);
close(g);
end;

BEGIN
Run;
write(nl, ' Fini '); readln;
END.
Chương trình CPP
/* DevC++: Diff.cpp
Tim doan dai nhat gom cac
phan tu doi mot khac nhau
*/

#include <fstream>
#include <iostream>

using namespace std;


f >> v; // v phan tu dau day
p[v] = 1; istart = 1;
for (i = 2; i <= n; ++i) {
f >> v;
if (p[v] >= istart) { // so v co trong doan istart i
if (i-istart > dmax) {
dmax = i-istart; imax = istart;
}
istart = p[v]+1;
}
p[v] = i;
}
f.close();
i = n+1;
if (i-istart > dmax) {
dmax = i-istart; imax = istart;
}
ofstream g(gn); g << imax << endl << dmax;
}

Hoán vị 1k
Cho dãy a gồm n số nguyên dương đôi một khác nhau. Hãy tìm đoạn dài nhất gồm các phần tử tạo thành
một hoán vị của dãy (1, 2 , , k), 1

n, a
i


100000.
Dữ liệu vào: Tệp văn bản hv1k.inp

của dãy a và kí hiệu set(x) là tập chứa các phần
tử (khác nhau) của dãy x. Với thí dụ đã cho ta có, a[1 5] = (5, 2, 4, 1, 5) và do đó set(a[1 5]) = {1, 2, 4,
5}. Gọi p là dãy vị trí (trỏ ngược) của dãy a. Vì dãy a gồm các phần tử đôi một khác nhau nên p cũng chứa
các chỉ số đôi một khác nhau. Khi đó a chứa một đoạn là hoán vị của k số tự nhiên đầu tiên (1,2, ,k) khi và
chỉ khi tìm được hai chỉ số s và e thỏa đồng thời hai tính chất sau:
 es+1 = k, và
 set(a[s e]) = {1, 2, , k}.
Trong thí dụ trên ta tìm được s = 3, e = 8, k = 6, a[3 8] = (4, 1, 5, 3, 2, 6), và do đó set(a[3 8]) = {1, 2, 3, 4,
5, 6}.
Xét dãy chỉ số 1, 2, , i thỏa tính chất  j: 1  j  i: p[j] ≠ 0.
Để ý rằng điều kiện p[j] ≠ 0 tương đương với điều kiện giá trị j của dãy a xuất hiện tại vị trí p[j]. Đặt s =
min p[1 i] = min {p[1], p[2], , p[i]} và e = max p[1 i] = max {p[1], p[2], , p[i]}. Ta thấy a chứa một
đoạn là hoán vị của dãy (1,2, ,i) khi và chỉ khi es+1 = i.
Độ phức tạp
O(n).
Chương trình Pascal
(*
hv1k.pas
Tim doan dai nhat trong day so
doi mot khac nhau tao thanh mot
hoan vi 1 k
*)

const fn = 'hv1k.inp'; gn = 'hv1k.out';
mn = 1000002; nl = #13#10; bl = #32;
var p: array[0 mn] of longint;
n: longint;
imax, dmax: longint;
f,g: text;


if (p[i] = 0) then break;
pmin := Min(pmin,p[i]);
pmax := Max(pmax,p[i]);
if (pmax - pmin + 1 = i) then
begin
imax := pmin;
dmax := pmax - pmin + 1;
end;
end;
end;

procedure Ghi;
begin
assign(g,gn); rewrite(g);
writeln(g, imax,nl,dmax);
close(g);
end;

procedure Run;
begin
Doc; Hv; Ghi;
end;

BEGIN
Run;
write(nl,' Fini '); readln;
END.

Chương trình CPP
/*


int main() {
Run();
cout << endl;
system("PAUSE");
return EXIT_SUCCESS;
}

void Doc() {
int i, v;
ifstream f(fn);
memset(p,0,sizeof(p));
f >> n;
for (i = 1; i <= n; ++i) {
f >> v;
p[v] = i;
}
f.close();
}

int Min(int a, int b) { return (a <= b) ? a : b; }

int Max(int a, int b) { return (a >= b) ? a : b; }

void Hv() {
int i, pmin = n+1, pmax = 0;
imax = 0; dmax = 0;
for (i = 1; i <= n; ++i) {
if (p[i] == 0) break;
pmin = Min(pmin,p[i]);

 Từ dòng thứ hai trở đi: dãy số a.
Dữ liệu ra: Tệp văn bản hvsk.out chứa 2 số:
 imax

chỉ số đầu tiên của đoạn dài nhất tìm được trong dãy a
 dmax

số phần tử của đoạn dài nhất.
Các số trên cùng dòng cách nhau qua dấu cách.

hvsk.inp hvsk.out

Giải thích
7
12 1 4 7 8
5 6
3
5
Tính từ phần tử thứ 3 trong dãy
a có 5 số liên tiếp tạo thành một
hoán vị của 4 8 là a[3 7]:
4
7 8 5 6

Thuật toán
Gọi p là dãy trỏ ngược của dãy a. Vì dãy a gồm các phần tử đôi một khác nhau nên p cũng chứa các chỉ số
đôi một khác nhau. Khi đó a chứa một đoạn là hoán vị của dãy số tự nhiên liên tiếp s k khi và chỉ khi tìm
được hai chỉ số i và j thỏa đồng thời hai tính chất sau:
 ji = ks, và
 set(a[i j]) = {s, s+1, , k}.

Chương trình CPP
/*
hvsk.cpp
Tim doan dai nhat trong day so
doi mot khac nhau tao thanh mot
hoan vi cua day so tu nhien lien tiep
s, s+1, ,k
*/
#include <fstream>
#include <iostream>

using namespace std;

// D A T A A N D V A R I A B L E S

const char * fn = "hvsk.inp";
const char * gn = "hvsk.out";
const int mn = 100002;
int p[mn];
int pmin, pmax;
int vmin, vmax;
int n;
int imax, dmax;

// P R O T O T Y P E S

int main();
void Doc();
int Min(int, int);
int Max(int, int);


void Hv() {
int i, istart, q = 0; // trang thai q
dmax = 0; ++vmax;
for (i = vmin; i <= vmax; ++i) {
switch(q) {
case 0: // duyet doan toan 0
if (p[i] > 0) { // Khoi tri khi gap so khac 0
pmin = pmax = p[i];
istart = i; q = 1;
}
break;
case 1: // duyet doan khac 0
if (p[i] > 0) {
pmin = Min(pmin,p[i]);
pmax = Max(pmax,p[i]);
if (pmax-pmin == i-istart && pmax-pmin+1 > dmax){
dmax = pmax-pmin+1;
imax = pmin;
}
}
else q = 0;
break;
} // end switch
} // end for
}

void Ghi() {
ofstream g(gn);
g << imax << endl << dmax;
hv1kmax.inp hv1kmax.out

Giải thích
10
12 1 4 1 5
3 2 3 1 2
3
5
Tính từ phần tử thứ 3 trong dãy
a có 5 số liên tiếp tạo thành một
hoán vị của 1 5 là a[3 7]:
4 1 5 3 2 Thuật toán
Duyệt dãy, dựa theo bài diff, xác định từng đoạn ứng viên a[d c] chứa tối đa các phần tử liên tiếp nhau
trong dãy a và đôi một khác nhau. Với mỗi đoạn ứng viên, dựa theo bài Hv1k, gọi thủ tục Hv(d,c) xác định
và cập nhật đoạn dài nhất trong a[d c] tạo thành một hoán vị của dãy số tự nhiên 1 k.
Độ phứ
c
tạp
Chương trình Pascal
(* hv1kmax.pas: Tim doan dai nhat gom cac
phan tu tao thanh mot hoan vi cua 1 k *)

const fn = 'hv1kmax.inp'; gn = 'hv1kmax.out';
mn = 100002; bl = #32; nl = #13#10;


end;

procedure Ghi;
begin
assign(g,gn); rewrite(g);
writeln(g,imax, nl, dmax); close(g);
end;

procedure Run;
var i, v , istart: longint;
begin
fillchar(p,sizeof(p),0);
imax := 0; dmax := 0;
assign(f,fn); reset(f);
readln(f,n);
read(f,v); { v – phan tu dau day a }
p[v] := 1; istart := 1; { chi so dau doan }
for i := 2 to n do
begin
read(f,v);
if (p[v] >= istart) then { gap phan tu trung lap }
begin
if (i-istart > dmax) then Hv(istart, i-1);
istart := p[v]+1; { Khoi tri dau doan moi }
end;
p[v] := i;
end;
close(f);
if (n+1-istart > dmax) then Hv(istart,n);
Ghi;

void Run();
int Min(int, int);
int Max(int, int);
void Hv(int, int); // Sliding window
void Ghi();

// I M P L E M E N T A T I O N

int main() {
Run();
cout << endl;
system("PAUSE");
return EXIT_SUCCESS;
}

int Min(int a, int b) { return (a <= b) ? a : b; }

int Max(int a, int b) { return (a >= b) ? a : b; }

// tim hoan vi 1 n trong doan
// gom cac phan tu khac nhau doi mot
void Hv(int d, int c) {
int i, pmin = c+1, pmax = d-1;
int n = c-d+1;
for (i = 1; i <= n; ++i) {
if (p[i] < d || p[i] > c) break;
pmin = Min(pmin,p[i]);
pmax = Max(pmax,p[i]);
if (i > dmax) {
if (pmax - pmin + 1 == i) {

Ghi();
}
Hoán vị sk dài nhất
Cho dãy a gồm n số nguyên dương. Hãy tìm đoạn dài nhất gồm các phần tử tạo thành một hoán vị của dãy
số nguyên dương liên tiếp s, s+1, ,k; 1

n, a
i


100000.
Dữ liệu vào: Tệp văn bản hvskmax.inp
 Dòng đầu tiên: số n.
 Từ dòng thứ hai trở đi: dãy số a.
Dữ liệu ra: Tệp văn bản hvskmax.out chứa 2 số:
 imax

chỉ số đầu tiên của đoạn dài nhất tìm được trong dãy a
 dmax

số phần tử của đoạn dài nhất.
Các số trên cùng dòng cách nhau qua dấu cách. hvskmax.inp hvskmax.out

Giải thích
10
5 1 9 7 5
8

#include <iostream>

using namespace std;

// D A T A A N D V A R I A B L E S

const char * fn = "hvskmax.inp";
const char * gn = "hvskmax.out";
const int mn = 100002;
int p[mn]; // p[v] - noi xuat hien gia tri v trong day
int a[mn];
int n;
int imax, dmax;

// P R O T O T Y P E S

int main();
void Run();
int Min(int, int);
int Max(int, int);
void Hv(int, int); // Sliding window
void Ghi();

// I M P L E M E N T A T I O N

int main() {
Run();
cout << endl;
system("PAUSE");
return EXIT_SUCCESS;

}
}
else q = 0;
break;
} // end switch
} // end for
}

void Ghi() {
ofstream g(gn);
g << imax << endl << dmax;
g.close();
}

void Run() {
int i, v , istart;
memset(p,0,sizeof(p));
imax = 0; dmax = 0;
ifstream f(fn);
f >> n;
f >> v; a[1] = v; p[v] = 1; istart = 1;
for (i = 2; i <= n; ++i) {
f >> v; a[i] = v;
if (p[v] >= istart) {
if (i-istart > dmax) Hv(istart, i-1);
istart = p[v]+1;
}
p[v] = i;
}
f.close();

int n;
int imax, dmax;

// P R O T O T Y P E S
void Run();
void Sang(int);
void Duyet();

// I M P L E M E N T A T I O N
int main() {
Run();
cout << endl << " Fini ";
cin.get();
return 0;
}

void Sang(int n) {
int can = (int) sqrt(n);
int i, j, k;
p[0] = p[1] = 1;
for (i = 2; i <= can; ++i)
if (p[i]==0)
for (k = n/i, j = i; j <= k; ++j) p[i*j] = 1;
}

void Duyet() {
int i, x, d;
imax = 0; dmax = 0; d = 0;
ifstream f(fn);
f >> n;