C11SEQ – spoj

September 27, 2016 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/C11SEQ/

Thuật toán:

  • Gọi S[i] là tổng từ a[1] đến a[i]
  • Ta biến đổi yêu cầu đề bài 
    • <span class="coMULTI">L &lt;= a[i] + a[i+1] + ... + a[j] &lt;= R</span>
    • <span class="coMULTI">=&gt;    L&lt;=s[i] - s[j-1]&lt;=R</span>
    • =>        s[j-1]>=s[i]-r;
                   s[j-1]<=s[i]-l;
  • Lưu các giá trị s[i] – r và s[i] – l và mảng kt 2*n ——> rời rạc hóa thành mảng b[1..2*n] ——> lưa vào cây BIT để tính:
    <span class="st0">ans := ans + get(b[i]) - get(b[n+i]);</span>

Code:

const
  fi='';//c11seq.inp';
  fo='';//c11seq.out';
  maxn=trunc(1e5);
var
  s,sr,sl : array[0..maxn] of int64;
  a  : array[0..maxn*3] of int64;
  b,cs,t  : array[0..maxn*3] of longint;
  i,j,n,l,r : longint;
  ans : int64;
procedure enter;
  begin
    assign(input,fi);reset(input);
    read(n,l,r);
    for i:=1 to n do read(a[i]);
    for i:=1 to n do if (l<=a[i]) and (r>=a[i]) then inc(ans);
    close(input);
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg := x;x:=y;y:=tg;
  end;
procedure qs(l,r : longint);
  var i,j : longint;
      x : int64;
  begin
    i :=l;j:=r;
    x := a[cs[(l+r) div 2]];
    repeat
      while a[cs[i]]<x do inc(i);
      while a[cs[j]]>x do dec(j);
      if i<=j then
        begin
          swap(cs[i],cs[j]);
          inc(i);dec(j);
        end;
    until i>j;
    if i<r then qs(i,r);
    if j>l then qs(l,j);
  end;
procedure init;
  var i,hold : longint;
  begin
    for i := 1 to n do s[i] := s[i-1] + a[i];
    for i := 1 to n do sl[i] := s[i] - l;
    for i := 1 to n do sr[i] := s[i] - r - 1;
    for i := 1 to n do
      begin
        a[i] := sl[i];
        a[n+i] := sr[i];
        a[n+n+i] := s[i-1];
      end;
    //a[2*n+1] := s[0] - l;
    //a[2*n+2] := s[0] - r;
    for i:=1 to 3*n do cs[i] := i;
    qs(1,3*n);
    b[cs[1]] := 1; hold := 1;
    for i:=2 to n*3 do
      if a[cs[i]] = a[cs[i-1]] then
        begin
          b[cs[i]] := hold;
        end
        else
        begin
          inc(hold);
          b[cs[i]] := hold;
        end;
  end;
procedure update(i : longint);
  begin
    while i<=3*n do
      begin
        t[i] := t[i] + 1;
        i := i + i and (-i);
      end;
  end;
function get(i : longint) : longint;
  begin
    get := 0;
    while i>0 do
      begin
        get := get + t[i];
        i := i - i and (-i);
      end;
  end;
procedure process;
  var i : longint;
  begin
    for i:=1 to n do
      begin
        ans := ans + get(b[i]) - get(b[n+i]);
        update(b[2*n+i]);
      end;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(Output);
    writeln(ans);
    close(output);
  end;
begin
  enter;
  init;
  process;
  print;
end.
Chủ đề: BIT, Nén số (rời rạc hóa mảng) Mức độ:

VDANGER – spoj

September 27, 2016 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/VDANGER/

Thuật toán:

  • Gợi ý là sử dụng thuật toán Floyd rồi cộng lại ra kết quả bài toán

Code:

VAR
  a :array[1..10000] of byte;
  c :array[1..100,1..100] of longint;
  t :array[1..100,1..100] of byte;
  n :byte;
  m :word;
 
procedure Enter;
  var i,j :word;
  begin
    readln(n,m);
    for i:=1 to m do readln(a[i]);
    for i:=1 to n do
      begin
        for j:=1 to n do
          begin
            read(c[i,j]); t[i,j]:=j;
          end;
        readln;
      end;
  end;
 
procedure Optimize;
  var i,j,k :byte;
  begin
    for k:=1 to n do
    for i:=1 to n do
    for j:=1 to n do
    if (c[i,j]>c[i,k]+c[k,j]) then
      begin
        c[i,j]:=c[i,k]+c[k,j];
        t[i,j]:=t[i,k];
      end;
  end;
 
procedure Quit;
  var
    i :word;
    sum :longint;
  begin
    sum:=0;
    if (a[1]<>1) then sum:=sum+c[1,a[1]];
    for i:=2 to m do sum:=sum+c[a[i-1],a[i]];
    if (a[m]<>n) then sum:=sum+c[a[m],n];
    write(sum);
  end;
 
BEGIN
  assign(input,''); reset(input);
  assign(output,''); rewrite(output);
  Enter;
  Optimize;
  Quit;
  close(input); close(output);
END.
Chủ đề: Floyd Mức độ:

COUNTPL – spoj

September 27, 2016 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/COUNTPL/

Thuật toán:

  • Tính trước mảng pan[i][j] = true nếu xâu s[i..j] là palindrome và ngược lại
  • Gọi f[i][j]=true nếu xâu s[1..i] có thể chia làm j xâu palindrome và ngược lại
  • Code đoạn tính f[i][j] cho các bạn dễ hiểu:
        f[0,0] := true;
        res := oo;
        for i:=1 to n do
                for j:=1 to i do
                        begin
                                for k:=i downto 1 do
                                        begin
                                                if pan[k,i] then
                                                        if f[k-1,j-1] then
                                                                f[i,j] :=true;
                                        end;
                                if i=n then if f[i,j] then res := min(res,j);
                        end;

Code:

uses    math;
const   fi='';
        fo='';
        maxn=300;
        oo=1000;
var     pan     :array[1..maxn,1..maxn] of boolean;
        i,j,n   :longint;
        s       :string;
        f       :array[0..maxn,0..maxn] of boolean;
        res     :longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(s);
        close(input);
end;
function check(i,j      :longint):boolean;
var     tg      :string;
begin
        tg := copy(s,i,j-i+1);
        for i :=1 to length(tg) div 2 do
                if tg[i]<>tg[length(tg)-i+1] then exit(false);
        exit(true);
end;
procedure process;
var     i,j,k   :longint;
begin
        n := length(s);
        for i:=1 to n do
                for j:=i to n do
                        if check(i,j) then pan[i,j] := true;
        f[0,0] := true;
        res := oo;
        for i:=1 to n do
                for j:=1 to i do
                        begin
                                for k:=i downto 1 do
                                        begin
                                                if pan[k,i] then
                                                        if f[k-1,j-1] then
                                                                f[i,j] :=true;
                                        end;
                                if i=n then if f[i,j] then res := min(res,j);
                        end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.
Chủ đề: Quy hoạch động Mức độ:

ROBOCON – vn.spoj.com

September 27, 2016 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/ROBOCON/

Thuật toán:

  • Bạn loang con robot 1 trong khi loang robot 1 bạn cũng đồng thời loang robot 2. Ta phải suy luận ra một số trường hợp để mà dừng loang
  • Bạn có thể đọc code của mình để hiểu thêm. Mình viết rất dễ hiểu, bạn đọc có thể hiểu ngay

Code:

const
  fi='';
  fo='';
  maxn=501;
  maxq=20*maxn*maxn;
  oo=trunc(1e9);
type
  point = record
    x,y,d : longint;
  end;
var
  dau1,cuoi1,dau2,cuoi2,i,j,n,m : longint;
  a : array[0..maxn,0..maxn] of boolean;
  q1,q2 : array[1..maxq] of point;
  d1,d2 : array[1..maxn,1..maxn] of longint;
  nowd,res : longint;
  kt : boolean;
 
procedure enter;
var u,v : longint;
begin
  assign(input,fi);reset(input);
  fillchar(a , sizeof(a) , false);
  readln(n,m);
  for i:=1 to n do for j:=1 to n do a[i,j] := true;
  for i:=1 to m do
    begin
      read(u,v);
      a[u,v] := false;
    end;
end;
procedure push1(x,y,z : longint);
begin
  inc(cuoi1);
  q1[cuoi1].x := x;
  q1[cuoi1].y := y;
  q1[cuoi1].d := z;
  d1[x,y] := z;
  if d2[x,y]=z then
    begin
      res := z;
      kt:=true;
      exit;
    end;
end;
procedure push2(x,y,z : longint);
begin
  inc(cuoi2);
  q2[cuoi2].x := x;
  q2[cuoi2].y := y;
  q2[cuoi2].d := z;
  d2[x,y] := z;
end;
procedure bfs2(dd : longint);
var u : point;
    i,j : longint;
begin
  while dau2<=cuoi2 do
    begin
      u := q2[dau2]; inc(dau2);
      if u.d>dd then begin dec(dau2); exit; end;
      i:=u.x;j:=u.y;
      if a[i,j-1] and (d2[i,j-1]<>dd+1) then push2(i,j-1,dd+1);
      if a[i+1,j] and (d2[i+1,j]<>dd+1) then push2(i+1,j,dd+1);
      if a[i+1,j-1] and (d2[i+1,j-1]<>dd+1) then push2(i+1,j-1,dd+1);
    end;
end;
procedure bfs1;
var u : point;
    i,j : longint;
begin
  fillchar(d1,sizeof(d1),255);
  fillchar(d2,sizeof(d2),255);
  kt := false;
  dau1 :=1; cuoi1 := 0;
  dau2 := 1; cuoi2 := 0;
  push1(1,1,0); push2(1,n,0);
  nowd := 0;
  while dau1<=cuoi1 do
    begin
      if kt then break;
      u := q1[dau1]; inc(dau1);
      if u.d=nowd then
        begin
          bfs2(nowd);
          inc(nowd);
        end;
      i := u.x ; j:=u.y;
      if a[i+1,j] and (d1[i+1,j]<>u.d+1) then push1(i+1,j,u.d+1);
      if a[i,j+1] and (d1[i,j+1]<>u.d+1) then push1(i,j+1,u.d+1);
      if a[i+1,j+1] and (d1[i+1,j+1]<>u.d+1) then push1(i+1,j+1,u.d+1);
    end;
end;
procedure process;
begin
  res := oo;
  bfs1;
end;
procedure print;
begin
  assign(output,fo);rewrite(output);
  writeln(res);
  close(output);
end;
begin
  enter;
  process;
  print;
end.
Chủ đề: BFS Mức độ: ,

MATCH1 – SPOJ

September 27, 2016 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/MATCH1/

Thuật toán:

Code:

const
  fi='';
  fo='';
  maxn=100;
var
  a : array[1..maxn,1..maxn] of boolean;
  match : array[1..maxn] of longint;
  i,j,n,m,res : longint;
procedure enter;
  var u,v : longint;
  begin
    assign(input,fi);reset(input);
    readln(n,m);
    while not eof(input) do
      begin
        readln(u,v);
        a[u,v] := true;
      end;
  end;
procedure process;
  var found : boolean;
      nlist,i,j,old : longint;
      list : array[1..maxn] of longint;
      cx : array[1..maxn] of boolean;
  procedure dfs(u : longint);
    var i,v : longint;
    begin
      for v:=1 to m do
        if a[u,v] then
          if cx[v] then
          begin
            cx[v] := false;
            if match[v]=0 then found := true else dfs(match[v]);
            if found then
              begin
                match[v] := u;
                exit;
              end;
          end;
    end;
  begin
    nlist := n;
    for i:=1 to n do list[i ] := i;
    repeat
      old := nlist;
      fillchar(cx,sizeof(cx),true);
      for i:=nlist downto 1 do
        begin
          found := false;
          dfs(list[i]);
          if found then
            begin
              list[i] := list[nlist];
              dec(nlist);
            end;
        end;
    until old = nlist;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    for i:=1 to m do if match[i]<>0 then inc(res);
    writeln(res);
    for i:=1 to m do if match[i]<>0 then writeln(match[i],' ',i);
    close(output);
  end;
begin
  enter;
  process;
  print;
end.
Chủ đề: Cặp ghép Mức độ: ,

QUEENNB – SPOJ

September 10, 2016 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/QUEENNB/

Thuật toán:

  • Thuật toán cũng không có gì phức tạp. Mình chỉ duyệt 2 lần: lần 1 từ đầu đến cuối bảng, lần 2 từ cuối về đầu bảng
  • Còn mỗi lần duyệt mình làm gì thì các bạn hãy đọc code vì mình viết code rất dễ hiểu

Code:

const   fi='';
        fo='';
        maxn=1000+3;
 
type    arrf    =array[0..maxn,0..maxn] of longint;
 
var     f       :arrf;
        h,c,d,d2   :arrf;
        i,j,n,m :longint;
        a       :array[1..maxn,1..maxn] of byte;
 
procedure enter;
var     tam     :char;
begin
        assign(input,fi);reset(input);
        readln(m,n);
        for i:=1 to m do
        begin
                for j:=1 to n do
                        begin
                                read(tam);
                                if tam='.' then a[i,j] := 1 else a[i,j] := 0;
                        end;
                readln;
        end;
        close(input);
end;
 
procedure process;
begin
        for i:=1 to m do
                for j:=1 to n do
                        begin
                                if a[i,j]=0 then
                                        begin
                                                h[i,j]:=0;
                                                c[i,j]:=0;
                                                d[i,j]:=0;
                                                d2[i,j] := 0;
                                                continue;
                                        end;
                                h[i,j] := h[i,j-1]+1;
                                c[i,j] := c[i-1,j]+1;
                                d[i,j] := d[i-1,j-1]+1;
                                d2[i,j] := d2[i-1,j+1]+1;
                                f[i,j] := h[i,j]+c[i,j]+d[i,j]+d2[i,j]-4;
                        end;
        fillchar(h,sizeof(h),0);
        fillchar(c,sizeof(c),0);
        fillchar(d,sizeof(d),0);
        fillchar(d2,sizeof(d2),0);
        for i:=m downto 1 do
                for j:=n downto 1 do
                        begin
                                if a[i,j]=0 then
                                        begin
                                                h[i,j] := 0;
                                                c[i,j] := 0;
                                                d[i,j] := 0;
                                                d2[i,j] := 0;
                                                continue;
                                        end;
                                h[i,j] := h[i,j+1]+1;
                                c[i,j] := c[i+1,j]+1;
                                d[i,j] := d[i+1,j+1]+1;
                                d2[i,j] := d2[i+1,j-1]+1;
                                inc(f[i,j] , h[i,j]+c[i,j]+d[i,j]+d2[i,j]-3 );
                        end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        for i:=1 to m do
        begin
                for j:= 1 to n do
                        write(f[i,j],' ');
                writeln;
        end;
        close(output);
end;
begin
        enter;
        process;
        print;
end.
Chủ đề: SPOJ

TJALG – SPOJ

September 10, 2016 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/TJALG/

Thuật toán:

  • Bài này thuần sử dụng thuật toánn Tarjan. Thuật toán Tarjan đơn thuần dựa trên thuật toán duyệt đồ thị DFS.
  • Các bạn có thể tham khảo thuầ toán Tarjan trong sách của thầy Lê Minh Hoàng

Code:

uses math;
const
  fi='';//spa.inp';
  fo='';//spa.out';
  maxn=trunc(1e5);
  maxm=trunc(1e6);
  oo=trunc(1e9);
var
  i,j,n,m,tpltm,top,tg,count : longint;
  link,head,ke : array[1..maxm] of longint;
  low,num : array[1..maxn] of longint;
  st : array[1..maxm*10] of longint;
  cx : array[1..maxn] of boolean;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
procedure enter;
  var u,v : longint;
  begin
    assign(input,fi);reset(input);
    readln(n,m);
    for i:=1 to m do
      begin
        read(u,v);
        add(i,u,v);
      end;
  end;
function pop : longint;
  begin
    pop := st[top];
    dec(top);
  end;
procedure push(x : longint);
  begin
    inc(top);
    st[top] := x;
  end;
procedure dfs(u : longint);
  var i,v : longint;
  begin
    inc(count);
    num[u] := count;
    low[u] := count;
    push(u);
    i := head[u];
    while I<>0 do
      begin
        v := ke[i];
        if cx[v] then
        if num[v]=0 then
          begin
            dfs(v);
            low[u] := min(low[u],low[v]);
          end
          else
          begin
            low[u] := min(low[u],num[v]);
          end;
        i := link[i];
      end;
    if low[u]=num[u] then
      begin
        inc(tpltm);
        repeat
          v := pop;
          cx[v] := false;
        until v=u;
      end;
  end;
procedure process;
  var i : longint;
  begin
    fillchar(cx,sizeof(cx),true);
    for i:=1 to n do
      if num[i]=0 then
        begin
          dfs(i);
        end;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(tpltm);
    close(output);
  end;
begin
  enter;
  process;
  print;
end.
Chủ đề: DFS, SPOJ Mức độ: ,