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.

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

Please read the guidelines before commenting.


There are no comments at the moment.