COUNTPL – spoj

Đề 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.

ROBOCON – vn.spoj.com

Đề 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.

MATCH1 – SPOJ

Đề 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.

QUEENNB – SPOJ

Đề 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.

TJALG – SPOJ

Đề 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.

SUBSTR – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
  fi='';
  fo='';
  maxn=trunc(1e6);
  base=trunc(1e9)+7;
  pp=307;
var
  f : array[0..maxn] of int64;
  i,j,n,m : longint;
  hb : int64;
  a,b : array[1..maxn] of byte;
  ha,pow : array[0..maxn] of int64;
procedure enter;
var x : ansistring;
begin
  assign(input,fi);reset(input);
  readln(x);
  m := length(x);
  for i := 1 to m do a[i] := ord(x[i])-48;
  readln(x);
  n := length(x);
  for i := 1 to n do b[i] := ord(x[i])-48;
  close(input);
end;
function gethash(l,r : longint) : int64;
begin
  gethash := (ha[r]-ha[l-1]*pow[r-l+1] + base*base) mod base;
end;
procedure process;
begin
  assign(output,fo);rewrite(output);
  ha[0] := 0;
  for i:=1 to m do ha[i] := (ha[i-1]*pp + a[i]) mod base;
  pow[0] := 1;
  for i:=1 to m do pow[i] := pow[i-1]*pp mod base;
  hb := 0;
  for i:=1 to n do hb := (hb*pp + b[i]) mod base;
  for i:=1 to m-n+1 do
    if hb = gethash(i,i+n-1) then
      write(i,' ');
  close(output);
end;
begin
  enter;
  process;
end.

Thuật toán duyệt phân tập

Bài toán cơ bản:

Cho mảng A[1..n] đếm số dãy con của mảng có tổng bằng S với n<=40.

  • Inp: n, S, mảng A.
  • Out: kết quả bài toán.

Inp:

4 4

1 2 3 4

Out:

2

Các dãy con: (4) , (1,3)

Phân tích: 

  • Thuật toán ta nghĩ ra ngay là duyệt dãy nhị phân 01
  • Nhưng duyệt chỉ giải quyết được với n <= 20. Chính vì vậy phải dùng thuật toán duyệt phân tập mới có thể ăn full test 🙂

Tư tưởng thuật toán duyệt phân tập:

  • Chia mảng A làm 2 mảng nhỏ độ dài n/2
  • Khi đó max(n/2)=20 => duyệt
  • Khi duyệt các mảng nhỏ ta lưu tổng các dãy con của mảng nhỏ vào các mảng riêng S1[] và S2[]
  • Với mỗi giá trị S1[] ta tìm kiếm nhị phần trong S2[] phần tử có giá trị S-S1[i] (cộng res với số gt S-S1[i] trong S2[]
  • res là kết quả bài toán

Các bài tập luyện tập thêm:

COIN34 – SPOJ

VECTOR – spoj

DTTUI1 – spoj