Editorial for Wooden Sticks
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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.
Comments