AZNET – spoj

Đề bài:

Thuật toán:

Code:

Const   inp = '';
        out = '';
        maxn = 10001;
        maxm = 100001;
 
Var     n,m,ntest,min,max,k,res     :       longint;
        x,y,id :       array [1..2,1..maxm] of longint;
        lab :       array [1..2,1..maxn] of longint;
        sl      :   array [1..2] of longint;
        a,b :       array [0..maxn] of longint;
{***************************************************************************}
function getroot(t,u : longint) : longint;
  begin
      while lab[t,u] > 0 do u := lab[t,u];
      exit(u);
  end;
{***************************************************************************}
procedure union(t,r1,r2 : longint);
var x : longint;
  begin
      x := lab[t,r1]+lab[t,r2];
      if lab[t,r1] > lab[t,r2] then
       begin
           lab[t,r1] := r2;
           lab[t,r2] := x;
       end
      else begin
               lab[t,r2] := r1;
               lab[t,r1] := x;
           end;
  end;
{****************************************************************************}
procedure main;
var i,j,dem,u,v,r1,r2,r3,r4 : longint;
  begin
      for i := 1 to n do
        begin
            lab[1,i] := -1;
            lab[2,i] := -1;
        end;
      max := 0;
      for i := 1 to sl[1] do
        begin
           u := x[1,i]; v := y[1,i];
           r1 := getroot(1,u); r2 := getroot(1,v);
           if r1 <> r2 then
             begin
                 inc(max);
                 union(1,r1,r2);
             end;
        end;
      min := 0;
      for i := 1 to sl[2] do
        begin
            u := x[2,i]; v := y[2,i];
            r1 := getroot(1,u); r2 := getroot(1,v);
            if r1 <> r2 then
              begin
                inc(min);
                union(1,r1,r2);
                r3 := getroot(2,u); r4 := getroot(2,v);
                union(2,r3,r4);
              end;
        end;
      for i := 1 to sl[2] do
        begin
            u := x[2,i]; v := y[2,i];
            r1 := getroot(2,u); r2 := getroot(2,v);
            if r1 <> r2 then
              begin
                  inc(min);
                  union(2,r1,r2);
              end;
        end;
      min := n-1-min;
      res := maxlongint;
      for i := min to max do
        if a[i]+b[n-1-i] < res then
          begin
              res := a[i]+b[n-1-i];
              k := i;
          end;
      for i := 1 to n do
        begin
            lab[1,i] := -1; lab[2,i] := -1;
        end;
      for i := 1 to sl[1] do
        begin
           u := x[1,i]; v := y[1,i];
           r1 := getroot(1,u); r2 := getroot(1,v);
           if r1 <> r2 then union(1,r1,r2);
        end;
      dem := 0;
      for i := 1 to sl[2] do
        begin
            u := x[2,i]; v := y[2,i];
            r1 := getroot(1,u); r2 := getroot(1,v);
            if r1 <> r2 then
              begin
                write(id[2,i],' ');
                inc(dem);
                union(1,r1,r2);
                r3 := getroot(2,u); r4 := getroot(2,v);
                union(2,r3,r4);
              end;
        end;
      if dem < n-1-k then
        begin
           for i := 1 to sl[2] do
            begin
                u := x[2,i]; v := y[2,i];
                r1 := getroot(2,u); r2 := getroot(2,v);
                if r1 <> r2 then
                 begin
                     inc(dem);
                     write(id[2,i],' ');
                     union(2,r1,r2);
                     if dem=n-1-k then break;
                 end;
            end;
        end;
      for i := 1 to sl[1] do
        begin
          u := x[1,i]; v := y[1,i];
          r1 := getroot(2,u); r2 := getroot(2,v);
          if r1 <> r2 then
            begin
                write(id[1,i],' ');
                union(2,r1,r2);
            end;
        end;
      writeln;
  end;
{***************************************************************************}
procedure nhap;
var i,j,u,v,k : longint;
  begin
      assign(input,inp); reset(input);
      assign(output,out); rewrite(output);
      readln(ntest);
      while ntest > 0 do
       begin
           dec(ntest);
           readln(n,m);
           for i := 1 to n-1 do read(a[i]);
           for i := 1 to n-1 do read(b[i]);
           sl[1] := 0; sl[2] := 0;
           for i := 1 to m do
             begin
                 readln(u,v,k);
                 inc(sl[k]);
                 x[k,sl[k]] := u; y[k,sl[k]] := v;
                 id[k,sl[k]] := i;
             end;
           main;
       end;
  end;
{****************************************************************************}
begin
     nhap;
end.

C11TRCNT – spoj

Đề bài:

Thuật toán:

  • Bài toán đưa về: kiểm tra 3 điểm có thẳng hàng hay không

Code:

const   fi='';
        fo='';
type    dinh=record
                x,y:longint;
                end;
var     i,j,k:integer;
        d,max,min:int64;
        kq,n:byte;
        p:array[1..200] of dinh;
        dem:array[1..200] of int64;
        f:text;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n);
    for i:=1 to n do readln(f,p[i].x,p[i].y);
    close(f);
end;
function kt(x1,y1,x2,y2,x3,y3:longint):boolean;
begin
        if x1*y3-x1*y2+x2*y1-x2*y3+x3*y2-x3*y1=0
        then exit(false) else exit(true);
end;
procedure xuly;
begin
    d:=0; min:=1000000000000000;
    for i:=1 to n do
    begin
        for j:=1 to n do
        if i<>j then
                for k:=1 to n do
                if (i<>k) and (j<>k) then
                                if kt(p[i].x,p[i].y,p[j].x,p[j].y,p[k].x,p[k].y)  then
                                begin
                                        inc(dem[i]);
                                        if (i<j) and (k>j) then inc(d);
                                end;
        if dem[i]<min then begin min:=dem[i]; kq:=i; end;
    end;
end;
procedure inkq;
begin
    assign(f,fo);
    rewrite(f);
    writeln(f,d,' ',kq);
    close(f);
end;
begin
    nhap;
    xuly;
    inkq;
end.

LCS2X – spoj

Đề bài:

Thuật toán:

  • Gọi L[i,j] là độ dài dãy con chung bội hai dài nhất với số cuối cùng là A[i] và B[j]1) Với A[i] <> B[j] thì L[i,j] = 0

    2) Với A[i] = B[j] thì L[i,j] = max(L[x,y] + 1) ( với x<i, y<j, A[x]*2 <= A[i] )

  • Để tính max(L[x,y]) nhanh chóng, ta sử dụng mảng F với ý nghĩa:F[y] = max(L[x,y])   =>Kết quả là max(F[j]) (với 1<=j<=n)

    Gọi ma=max(F[y]) ( với y<j, B[y]*2 <= A[i] )

    Khi đó ta có đoạn code phần xử lý sẽ là:

    for (i=1;i<=m;++i){
        ma=0;
        for (j=1;j<=n;++j){
            matruocj=ma;
            if (b[j]*2<=a[i]) ma=max(ma,f[j]);
            if (a[i]==b[j]) f[j]=max(f[j],matruocj+1);
        }
    }
  • Với cách này thì bạn chỉ cần dùng mảng 1 chiềuĐộ phức tạp: O(M*N)

Code:

uses    math;
const   fi      ='';
        fo      ='';
        oo      =trunc(1e4);
 
var     a, b, f :array[0..oo] of longint;
        ma,matruocj     :longint;
        ans     :longint;
        m, n    :longint;
procedure Optimize;
var     i, j    :longint;
begin
        fillchar(f, sizeof(f),0);
        for i:=1 to m do
                begin
                        ma:=0;
                        for j:=1 to n do
                                begin
                                        matruocj:=ma;
                                        if b[j]*2<=a[i] then ma:=Max(ma,f[j]);
                                        if b[j]=a[i] then f[j]:=max(f[j],matruocj+1);
                                end;
                 end;
 
end;
 
Procedure run;
var     i, t,l :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(t);
        for l:=1 to t do
                begin
                        readln(m, n);
                        for i:=1 to m do read(a[i]);
                        for i:=1 to n do read(b[i]);
                        Optimize;
                        ans:=0;
                        for i:=1 to n do
                                if f[i]>ans then ans:=f[i];
                        writeln(ans);
                end;
        close(input);close(output);
end;
 
begin
        run;
end.

Đề thi, đáp án, kết quả PreVOI 2016