Hướng dẫn giải của Chia dãy
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const fi=''; var test,it,n,re:longint; b,f:array[1..100000] of longint; procedure rf; var i:longint; begin read(n); for i:=1 to n do read(b[i]); end; function bs(x:longint):longint; var l,r,m,i:longint; begin l:=1; r:=re; while l<=r do begin m:=(l+r) shr 1; if f[m]<=x then r:=m-1 else l:=m+1; end; for i:=m-1 to m+1 do if (i>0) and (i<=re) and (f[i]<=x) then exit(i); end; procedure pr; var i,x:longint; begin re:=1; f[1]:=b[1]; for i:=2 to n do if b[i]<f[re] then begin re:=re+1; f[re]:=b[i]; end else begin x:=bs(b[i]); f[x]:=b[i]; end; writeln(re); end; begin assign(input,fi); reset(input); rf; pr; close(input); end.
Code mẫu của ladpro98
program qbdivseq; uses math; const fi=''; maxN=100005; var a,f:array[1..maxN] of longint; n,d:longint; procedure input; var f:text; i:longint; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do readLN(f,a[i]); close(f); end; function find(r,key:longint):longint; var l,m,k:longint; begin l:=1; while l<=r do begin m:=(l+r) shr 1; if f[m]<=key then begin k:=m; r:=m-1; end else l:=m+1; end; exit(k); end; procedure process; var i:longint; begin d:=1; for i:=1 to n do if a[i]<f[d] then begin inc(d); f[d]:=a[i]; end else f[find(d,a[i])]:=a[i]; end; begin input; process; write(d); end.
Code mẫu của RR
{$R+,Q+} const FINP=''; FOUT=''; MAXN=100001; var a,b:array[1..MAXN] of longint; k,n:longint; f1,f2:text; procedure openF; inline; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; inline; begin close(f1); close(f2); end; procedure inp; inline; var i:longint; begin read(f1,n); for i:=1 to n do read(f1,a[i]); end; procedure ans; inline; begin writeln(f2,k); end; var mid,gt:longint; function find(l,r:longint):longint; inline; begin if (b[l]<=gt) and (b[l-1]>gt) then exit(l); if (b[r]<=gt) and (b[r-1]>gt) then exit(r); mid:=(l+r)>>1; if (b[mid]<=gt) and (b[mid-1]>gt) then exit(mid) else if b[mid]<=gt then exit(find(l,mid-1)) else exit(find(mid+1,r)); end; procedure solve; var i,j:longint; begin k:=1; b[1]:=a[1]; for i:=2 to n do begin if a[i]<b[k] then begin inc(k); b[k]:=a[i]; end else if a[i]>=b[1] then b[1]:=a[i] else begin gt:=a[i]; j:=find(2,k); b[j]:=a[i]; end; end; end; begin openF; inp; solve; ans; closeF; end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> int main() { int n,f[100001],a[100001],t; scanf("%d",&n); for(int i = 1;i<=n;i++) scanf("%d",&a[i]); t = 1; f[1] = a[1]; for(int i = 2;i<=n;i++) { if(a[i]<f[t]) { t++; f[t] = a[i]; } else if(a[i]>=f[1]) f[1] = a[i]; else { int u = 1,v = t,r; while(v-u>1) { r = (u+v)/2; if(a[i]<f[r]) u = r; else v = r; } f[v] = a[i]; } } printf("%d",t); //getch(); }
Code mẫu của ll931110
{$MODE DELPHI} Program QBDIVSEQ; Const input = ''; output = ''; maxn = 100000; Var a,s: array[1..maxn] of integer; n,k: integer; Procedure init; Var f: text; i: integer; Begin Assign(f, input); Reset(f); Readln(f, n); For i:= 1 to n do readln(f, a[i]); Close(f); End; Procedure update(i: integer); Var inf,sup,med,r: integer; Begin If s[k] > a[i] then Begin inc(k); s[k]:= a[i]; exit; End; inf:= 1; sup:= k; r:= 0; Repeat med:= (inf + sup) div 2; If s[med] = a[i] then exit; If s[med] > a[i] then inf:= med + 1 else Begin r:= med; sup:= med - 1; End; Until inf > sup; s[r]:= a[i]; End; Procedure optimize; Var i: integer; Begin k:= 1; s[1]:= a[1]; For i:= 2 to n do update(i); End; Procedure printresult; Var f: text; Begin Assign(f, output); Rewrite(f); Writeln(f, k); Close(f); End; Begin init; optimize; printresult; End.
Code mẫu của khuc_tuan
#include <iostream> #include <vector> using namespace std; int main() { int n; scanf("%d", &n); vector<int> v; for(int i=0;i<n;++i) { int x; scanf("%d", &x); vector<int> :: iterator p = lower_bound(v.begin(), v.end(), x, greater<int>()); if(p==v.end()) v.push_back(x); else *p = x; } cout << v.size() << endl; return 0; }
Bình luận