Hướng dẫn giải của Wooden Sticks
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; a,b,f:array[1..5000] of longint; procedure sort(l,r:longint); var i,j,x,y,t:longint; begin i:=l; j:=r; x:=a[(i+j) shr 1]; y:=b[(i+j) shr 1]; repeat while (a[i]<x) or ((a[i]=x) and (b[i]<y)) do inc(i); while (a[j]>x) or ((a[j]=x) and (b[j]>y)) do dec(j); if i<=j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; t:=b[i]; b[i]:=b[j]; b[j]:=t; inc(i); dec(j); end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; procedure rf; var i:longint; begin read(n); for i:=1 to n do read(a[i],b[i]); sort(1,n); 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); read(test); for it:=1 to test do begin rf; pr; end; close(input); end.
Code mẫu của happyboy99x
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MXV = 10000, N = 5000; pair<int, int> a[N]; int n, lst[N]; void enter() { scanf("%d", &n); for(int i = 0; i < n; ++i) scanf("%d%d", &a[i].first, &a[i].second); } void solve() { sort(a, a+n); int maxlen = 1; lst[0] = a[n-1].second; for(int i = n-2; i >= 0; --i) { int dp = lower_bound(lst, lst+maxlen, a[i].second) - lst; if(dp == maxlen) ++maxlen, lst[dp] = a[i].second; else lst[dp] = min(lst[dp], a[i].second); } printf("%d\n", maxlen); } int main() { int tc; scanf("%d", &tc); while(tc--) enter(), solve(); return 0; }
Code mẫu của ladpro98
program mstick; uses math; type e=record l,r:longint; end; const fi=''; maxN=5555; var b:array[1..maxN] of e; a,f:array[1..maxN] of longint; tt,t,n,d:longint; inp:text; procedure openF; begin assign(inp,fi); reset(inp); readln(inp,t); end; procedure input; var i:longint; begin readln(inp,n); for i:=1 to n do read(inp,b[i].l,b[i].r); end; procedure swap(i,j:longint); var t:e; begin t:=b[i]; b[i]:=b[j]; b[j]:=t; end; procedure sort(l,r:longint); var p:e; i,j:longint; begin if l>=r then exit; p:=b[random(r-l+1)+l]; i:=l;j:=r; repeat while (b[i].l<p.l) or ((b[i].l=p.l) and (b[i].r<p.r)) do inc(i); while (b[j].l>p.l) or ((b[j].l=p.l) and (b[j].r>p.r)) do dec(j); if i<=j then begin if i<j then swap(i,j); inc(i);dec(j); end; until i>j; sort(l,j);sort(i,r); end; procedure init; var i:longint; begin for i:=1 to n do a[i]:=b[i].r; 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 a[f[m]]<=key then begin k:=m; r:=m-1; end else l:=m+1; end; exit(k); end; procedure dp; var i:longint; begin f[1]:=1; d:=1; for i:=2 to n do begin if a[i]>=a[f[1]] then f[1]:=i else if a[i]<a[f[d]] then begin inc(d); f[d]:=i; end else f[find(d,a[i])]:=i; end; end; begin openF; for tt:=1 to t do begin input; sort(1,n); init; dp; writeln(d); end; end.
Code mẫu của RR
{$R+,Q+} {$Mode objFPC} uses math; const FINP=''; FOUT=''; MAXN=20111; var f1,f2:text; c,a,b:array[1..MAXN] of longint; sl,n,test:longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var i:longint; begin read(f1,n); for i:=1 to n do read(f1,a[i],b[i]); end; procedure swap(var a,b:longint); var temp:longint; begin temp:=a; a:=b; b:=temp; end; procedure sort(l,r:longint); inline; var i,j,ma,mb,key:longint; begin key:=random(r-l+1)+l; i:=l; j:=r; mb:=b[key]; ma:=a[key]; repeat while (b[i]<mb) or ((b[i]=mb) and (a[i]<ma)) do inc(i); while (b[j]>mb) or ((b[j]=mb) and (a[j]>ma)) do dec(j); if i<=j then begin swap(a[i],a[j]); swap(b[i],b[j]); inc(i); dec(j); end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; function find(key:longint):longint; var l,r,mid,kq:longint; begin l:=1; r:=sl; repeat mid:=(l+r)>>1; if c[mid]<=key then begin kq:=mid; r:=mid-1; end else l:=mid+1; until l>r; exit(kq); end; procedure solve; var u,i:longint; begin sl:=1; c[1]:=a[1]; for i:=2 to n do if a[i]<c[sl] then begin inc(sl); c[sl]:=a[i]; end else begin u:=find(a[i]); c[u]:=a[i]; end; end; begin openF; read(f1,test); for test:=1 to test do begin inp; sort(1,n); solve; writeln(f2,sl); end; closeF; end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> void Quicksort(long A[],long a[],long x,long y) { long t=A[(x+y)/2]; long i=x; long j=y; while(i<=j) { while(A[i]<t) i++; while(A[j]>t) j--; if(i<=j) { long tg=A[i]; A[i]=A[j]; A[j]=tg; long tga=a[i]; a[i]=a[j]; a[j]=tga; i++; j--; } } if(j>x) Quicksort(A,a,x,j); if(i<y) Quicksort(A,a,i,y); } main() { long T,n,A[5002],B[5002],Free[5002],dem=0,t,u,v,chay; scanf("%ld",&T); for(long i=0;i<T;i++) { scanf("%ld",&n); dem=0; for(long j=1;j<=n;j++) { scanf("%ld %ld",&A[j],&B[j]); Free[j]=0; } A[n+1]=0; Quicksort(A,B,1,n); chay=1; while(chay!=n&&chay!=n+1) { if(A[chay+1]>A[chay]) chay++; else { u=chay;v=chay+1; while(A[v+1]==A[v]) v++; Quicksort(B,Free,u,v); chay=v+1; } } for(long j=1;j<=n;j++) { if(Free[j]==1) continue; t=j; //printf("%ld",t); for(long k=j+1;k<=n;k++) { if(B[k]>=B[t]&&Free[k]==0) { Free[k]=1; t=k; } } dem++; } printf("%ld\n",dem); } //getch(); }
Code mẫu của ll931110
Program MSTICK; Const input = ''; output = ''; maxn = 5000; Var l,w: array[1..maxn] of integer; a: array[1..maxn] of integer; t,i,n,num: integer; fi,fo: text; Procedure openfile; Begin Assign(fi, input); Reset(fi); Assign(fo, output); Rewrite(fo); End; Procedure init; Var i: integer; Begin Readln(fi, n); For i:= 1 to n do read(fi, l[i], w[i]); End; Procedure swap(var x,y: integer); Var t: integer; Begin t:= x; x:= y; y:= t; End; Procedure BubbleSort; Var i,j,t: integer; Begin For i:= 1 to n - 1 do For j:= i + 1 to n do if w[i] > w[j] then Begin swap(w[i], w[j]); swap(l[i], l[j]); End else if w[i] = w[j] then if l[i] > l[j] then swap(l[i], l[j]); End; Procedure solve; Var i,k: integer; Begin num:= 1; a[1]:= l[1]; For i:= 2 to n do if a[num] > l[i] then Begin inc(num); a[num]:= l[i]; End else Begin k:= 1; While a[k] > l[i] do inc(k); a[k]:= l[i]; End; Writeln(fo, num); End; Procedure closefile; Begin Close(fo); Close(fi); End; Begin openfile; Readln(fi, t); For i:= 1 to t do Begin init; BubbleSort; solve; End; closefile; End.
Code mẫu của khuc_tuan
//{$A8,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q+,R+,S+,T-,U-,V+,W-,X+,Y+,Z1} // {$APPTYPE CONSOLE} {$mode delphi} uses math; type Data = class l, w : integer; constructor init(l, w : integer); end; constructor Data.init(l, w : integer); begin self.l := l; self.w := w; end; var i, j, n, st, t : integer; a : array[1..5000] of Data; b : array[1..10000] of integer; function get(i : integer) : integer; var r : integer; begin r := 0; while i > 0 do begin inc(r, b[i]); dec(i, i and (-i)); end; get := r; end; procedure update(i, v : integer); begin while i <= 10000 do begin inc(b[i], v); inc(i, i and (-i)); end; end; function findlast(i : integer) : integer; var le, ri, mi : integer; begin le := 1; ri := i; while le < ri do begin mi := (le + ri) div 2 + 1; if get(i) - get(mi-1) > 0 then le := mi else ri := mi - 1; end; findlast := le; end; function nhohon(a, b : Data) : boolean; begin nhohon := (a.l < b.l) or ((a.l = b.l) and (a.w < b.w)); end; procedure sort(l, r : integer); var i, j : integer; x, t : Data; begin if l>=r then exit; i := l; j := r; x := a[(l+r) div 2]; repeat while nhohon(a[i], x) do inc(i); while nhohon(x, a[j]) do dec(j); if i<=j then begin t := a[i]; a[i] := a[j]; a[j] := t; inc(i); dec(j); end; until i > j; sort(l,j); sort(i,r); end; begin read(st); for t:=1 to st do begin read(n); for i:=1 to n do begin a[i] := Data.Create; read(a[i].l, a[i].w); end; sort( 1, n); fillchar( b, sizeof(b), 0); for i:=1 to n do begin if get(a[i].w) > 0 then begin j := findlast(a[i].w); update( j, -1); end; update( a[i].w, 1); end; writeln(get(10000)); end; end.
Bình luận