Editorial for Chia dãy


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;
    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;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.