intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Ôn tập thi học sinh giỏi quốc gia môn Toán - Tin 2010: Dãy con chung không liền kề dài nhất

Chia sẻ: TRÚC LÂM | Ngày: | Loại File: PDF | Số trang:72

105
lượt xem
14
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Hãy tham khảo tài liệu ôn tập thi học sinh giỏi môn Toán - Tin năm 2010: Dãy con chung không liền kề dài nhất sẽ giúp các bạn học sinh có thêm tư liệu chuẩn bị ôn luyện và bổ trợ kiến thức cho kỳ thi sắp tới cũng như bổ trợ kiến thức cho giáo viên ra đề thi. Mời các bạn học sinh và quý thầy cô giáo cùng tham khảo.

Chủ đề:
Lưu

Nội dung Text: Ôn tập thi học sinh giỏi quốc gia môn Toán - Tin 2010: Dãy con chung không liền kề dài nhất

  1. 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 2 CCKLK.INP: Dòng đầu: n m. Từ dòng thứ hai trở đi: Dãy số a, 1 5 3 8 2 tiếp đến là dãy số b. 2 1 3 4 2 6 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);
  2. 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 ');
  3. 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 #include 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 > n >> m; cout
  4. = 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
  5. #include #include //#include 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
  6. 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 >> m >> s; cout > v; j = BinSearch(c,k,u,v); if (Sanh(c[j].a,c[j].b,u,v) != 0) { 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));// c[j].a = u; c[j].b = v; ++k; } } } f.close(); m = k; }
  7. // Ondinh.CPP Phuong an cu // HSG 2010 #include #include #include //#include 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 p[mn]; char d[mn]; int s[mn]; int n, m, x; // so dinh n, so cung m, dinh xuat phat x // P R O T O T Y P E S int main(); void Doc(); int XuLi(); int Minp(); int Min(int, int); int BinSearch(cung [], int, int, int); int Sanh(int,int,int,int); void Ghi(); int main(){ Doc(); XuLi(); Ghi(); cout
  8. int XuLi() { int i, imin, j, k; memset(d,0,sizeof(d)); for (i = 2; i > n >> m >> x; // The first edge (u,v) f >> u >> v; ++k; c[k].a = u; c[k].b = v; for (i = 2; i > u >> v; j = BinSearch(c,k,u,v); if (Sanh(c[j].a,c[j].b,u,v) != 0) { 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));// c[j].a = u; c[j].b = v; ++k; } } } f.close();
  9. 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  1016. Cho số m: 3  m  70. Xét dãy số nguyên 1 < c1 < c2 < ... < ck < 36, k = (m1)/2 , x là số nguyên lớn nhất không vượt quá x. Chọn các số chứa các chữ số < c1 cấp cho 2 nhóm 1 và 2 rồi xóa các số này. Chọn các số chứa các chữ số < c2 cấp cho 2 nhóm 3, 4.... Các số còn lại cấp cho 1 hoặc 2 nhóm cuối. Nhóm le: từ nhỏ, nhóm chẵn: từ lớn. Cho các số hệ 10: n, m, ci, p và q. Xác định mã (hệ 36) cấp cho ng thứ q nhóm p. Thí dụ: n = 50, m = 3, p = 2, q = 2, c1 = 16. 1d Căt đoạn Cho hình chữ nhật OABC, OA = n, OC = m, coi O là gốc tọa độ (0,0). Trong hình CN cho k đoạn thẳng đứng. Tìm điểm P trên BA hoặc BC để đoạn OP cắt nhiều đoạn nhất. Đoạn khác nhau Cho dãy a gồm n số nguyên dương. Một đoạn của dãy a, kí hiệu a[i..j] là dãy gồm các phần tử đứng liên tiếp nhau trong dãy a, kể từ phần tử ai đến phần tử aj, a[i..j] = (ai, ai+1,...,aj-1, aj), 1  i
  10. 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 ai 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ử aj đầ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[aj]+1. Chú ý rằng p[aj] là vị trí xuất hiện của giá trị lặp aj. Độ 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 *) const fn = 'diff.inp'; gn = 'diff.out'; bl = #32; nl = #13#10; mn = 100001; var p: array[0..mn] of longint; n: longint; imax, dmax: longint; { imax - chi so dau tien cua doan dai nhat dmax - so phan tu cua doan dai nhat } f,g: text; procedure Run; var i, j, v, istart: longint; begin imax := 0; dmax := 0; fillchar(p,sizeof(p),0); assign(f,fn); reset(f); readln(f,n); read(f,v); { phan tu dau tien trong day } p[v] := 1; istart := 1; for i := 2 to n do begin read(f,v); if (p[v] >= istart) then begin if (i-istart > dmax)then begin dmax := i-istart; imax := istart; end; istart := p[v]+1;
  11. 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 #include using namespace std; // D A T A A N D V A R I A B L E S const char * fn = "diff.inp"; const char * gn = "diff.out"; const int mn = 100001; int p[mn]; // p[v] = i: noi xuat hien so v trong day int n; int imax; // chi so dau tien cua doan dai nhat int dmax; // so phan tu cua doan dai nhat // P R O T O T Y P E S int main(); void Run(); // I M P L E M E N T A T I O N int main() { Run(); cout
  12. memset(p,0,sizeof(p)); ifstream f(fn); f >> n; f >> v; // v phan tu dau day p[v] = 1; istart = 1; for (i = 2; i > 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
  13. 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; procedure Doc; var i, v: longint; begin assign(f,fn); reset(f); fillchar(p,sizeof(p),0); readln(f,n); for i := 1 to n do begin read(f,v); p[v] := i; end; close(f); end; function Min(a,b: longint): longint; begin if (a = b) then Max := a else Max := b end; procedure Hv; var i, pmin, pmax: longint; begin pmin := n+1; pmax := 0; imax := 0; dmax := 0; for i := 1 to n do begin if (p[i] = 0) then break;
  14. 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 /* -------------------------------------- devCPP: hv1k.cpp Tim doan dai nhat trong day so doi mot khac nhau tao thanh mot hoan vi 1..k -----------------------------------------*/ #include #include using namespace std; // D A T A A N D V A R I A B L E S const char * fn = "hv1k.inp"; const char * gn = "hv1k.out"; const int mn = 100002; int p[mn]; 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(); void Ghi();
  15. void Run(); // I M P L E M E N T A T I O N int main() { Run(); cout > n; for (i = 1; i > v; p[v] = i; } f.close(); } int Min(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
  16. Dữ liệu vào: Tệp văn bản hvsk.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 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 3 Tính từ phần tử thứ 3 trong dãy 12 1 4 7 8 5 a có 5 số liên tiếp tạo thành một 5 6 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}. Trong thí dụ trên ta tìm được i = 3, j = 7, s = 4, k = 8, a[3..7] = (4, 7, 8, 5, 6), và do đó set(a[3..7]) = {4, 5, 6, 7, 8}. Khi đọc dữ liệu ta đồng thời xác định hai giá trị cận vmin và vmax của dãy a. Để ý rằng p[vmin..vmax] gồm các đoạn toàn 0 và đoạn khác 0 đan xen nhau. Thí dụ trên cho ta ai 1 2 3 4 5 6 7 8 9 10 11 12 p 2 0 0 3 6 7 4 5 0 0 0 1 vmin = 1. vmax = 12 Khi duyệt p[vmin..vmax] ta xét 2 trạng thái 0 và 1 như sau: Trạng thái 0: Duyệt đoạn p toàn 0, p[2..3] và p[9..11]. Nếu gặp p[i] > 0 thì khởi trị cho trạng thái duyệt đoạn khác 0, p[istart..]:  Ghi nhận chỉ số đầu đoạn khác 0: istart = i,  Khởi trị cac giá trị pmin = min p[istart..k1] và pmax = max p[istart..k1] cho đoạn này: pmin = pmax = p[i],  Chuyển qua trạng thái 1. Trạng thái 1: Duyệt đoạn p khác 0, p[1..1], p[4..8] và p[12..12]. Nếu p[i] > 0 thì cập nhật các chỉ số pmin và pmax. Kiểm tra đẳng thức pmaxpmin = iistart để cập nhật chỉ số đầu tiên của đoạn hoán vị trong dãy a, imax và chiều dài của đoạn hoán vị, dmax. Nếu p[i] = 0 thì kết thúc việc duyệt đoạn p[isstart..i1] này, chuyển qua trạng thái 0. Độ phức tạp O(n).
  17. Chương trình Pascal 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 #include 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(); // Sliding window void Ghi(); void Run(); // I M P L E M E N T A T I O N int main() { Run(); cout > n; for (i = 1; i > v; p[v] = i; vmin = Min(vmin,v); vmax = Max(vmax,v);
  18. } f.close(); } int Min(int a, int b) { return (a = b) ? a : b; } void Hv() { int i, istart, q = 0; // trang thai q dmax = 0; ++vmax; for (i = vmin; 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
  19.  Từ dòng thứ hai trở đi: dãy số a. Dữ liệu ra: Tệp văn bản hv1kmax.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. hv1kmax.inp hv1kmax.out Giải thích 10 3 Tính từ phần tử thứ 3 trong dãy 12 1 4 1 5 5 a có 5 số liên tiếp tạo thành một 3 2 3 1 2 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; var p: array[0..mn] of longint; { p[v] - noi xuat hien gia tri v trong day } n: longint; imax, dmax: longint; f, g: text; function Min(a,b: longint): longint; begin if (a = b) then Max := a else Max := b; end; procedure Hv(d,c: longint); var i, pmin, pmax: longint; begin pmin := c+1; pmax := d-1; for i := 1 to c-d+1 do begin if (p[i] < d ) or (p[i] > c) then break; pmin := Min(pmin,p[i]); pmax := Max(pmax,p[i]); if (i > dmax) then begin if (pmax - pmin + 1 = i) then
  20. begin imax := pmin; dmax := i; end end end; 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; end; BEGIN Run; write(nl,' Fini '); readln; END. Chương trình CPP /* DevC++: hv1kmax.cpp Tim doan dai nhat gom cac phan tu tao thanh mot hoan vi cua 1..k */ #include #include using namespace std; // D A T A A N D V A R I A B L E S
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2