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.

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.