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

COIN34 – SPOJ

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

Thuật toán:

Code:

uses math;
const
  fi='';
  fo='';
  maxs=2*trunc(1e6);
  maxn=17;
var
  st,d : array[1..maxs] of longint;
  c : array[1..maxn*2] of longint;
  i,j,n,res,s1,s2,x,d1,c1,top : longint;
procedure enter;
  begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);
    c[1] :=2; c[2] := 3; c[3] := 5;
    for i:=4 to 34 do
      c[i] := c[i-1]+c[i-2]+c[i-3];
  end;
procedure up1;
  begin
    //if c1=x then begin res := max(res,d1); exit; end;
    //if c1>x then exit;
    inc(top); st[top] := c1;
    d[top] := d1;
  end;
procedure try1( i : longint);
  var j : longint;
  begin
    for j:=0 to 1 do
      begin
        if j=1 then begin c1 := c1+c[i]; inc(d1) end;
        if i=s1 then up1 else try1(i+1);
        if j=1 then begin c1 := c1-c[i]; dec(d1) end;
      end;
  end;
procedure up2;
  var dau,cuoi,giua,xx : longint;
  begin
    if x=c1 then begin res := max(res,d1); exit; end;
    if c1>x then exit;
    xx := x-c1;
    dau:=1;cuoi:=top;
    giua:=(dau+cuoi) div 2;
    while (giua<>dau) and (giua<>cuoi) do
      begin
        if st[giua]>=xx then cuoi :=giua else dau := giua;
        giua :=(dau+cuoi) div 2;
      end;
    for giua := dau to cuoi do
      if st[giua]=xx then break;
    if st[giua]=xx then res := max(res,d1+d[giua]);
  end;
procedure try2( i :longint);
  var j : longint;
  begin
    for j:=1 downto 0 do
      begin
        if j=1 then begin c1 := c1+c[i]; inc(d1); end;
        if i=34 then up2 else try2(i+1);
        if j=1 then begin c1 := c1-c[i]; dec(d1); end;
      end;
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg:=x;x:=y;y:=tg;
  end;
procedure qs1(l,r : longint);
  var i,j,x,y : longint;
  begin
    i :=l;j:=r;
    x:=st[(l+r) div 2];
    y:=d[(l+r) div 2];
    repeat
      while (x>st[i]) or((x=st[i]) and (d[i]>y)) do inc(i);
      while (x<st[j]) or((x=st[j]) and (d[j]<y)) do dec(j);
      if i<=j then
        begin
          swap(st[i],st[j]);
          swap(d[i],d[j]);
          inc(i);dec(j);
        end;
    until i>j;
    if i<r then qs1(i,r);
    if l<j then qs1(l,j);
  end;
procedure init;
  begin
    s1 := 20; s2 := 21;
    try1(1);
    qs1(1,top);
    //try2(21);
  end;
procedure process;
  var t,tt : longint;
  begin
    readln(t);
    for tt:=1 to t do
      begin
        res := -1;
        readln(x);
        d1 := 0; c1 := 0;
        try2(21);
        writeln('Case #',tt,': ',res);
      end;
  end;
begin
  enter;
  init;
  process;
end.

MYSTERY – SPOJ

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

Thuật toán:

  • (đang cập nhập)

Code:

const
    x=20122007;
type int64 = qword;
 
var
    n,i : longint;
    f : array[0..1000000] of longint;
    res : int64;
 
function getVal(a:longint):longint;
var
    p,q,i : longint;
    g : int64;
begin
    if a<=1000000 then exit(f[a])
    else
    begin
        p:=a mod 1000000;
        q:=a div 1000000;
        g:=f[p];
        for i:=1 to q do g:=(g*f[1000000]) mod x;
        exit(g);
    end;
end;
 
begin
    readln(n);
 
    f[0]:=1;
    for i:=1 to 1000000 do f[i]:=(f[i-1]*3) mod x;
 
    res:=1;
    if sqr(trunc(sqrt(n))) = n then
    begin
      for i:=1 to trunc(sqrt(n))-1 do
      if n mod i=0 then
      res:=(((res*(getVal(i)-1)) mod x)*(getVal(n div i)-1)) mod x;
 
      res:=(res*(getVal(trunc(sqrt(n)))-1)) mod x;
  end else
  begin
    for i:=1 to trunc(sqrt(n)) do
      if n mod i=0 then
        res:=(((res*(getVal(i)-1)) mod x)*(getVal(n div i)-1)) mod x;
  end;
 
    writeln(res);
end.

KDEL – SPOJ

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

Thuật toán: 

  • (đang cập nhập)

Code:

const fi='';
      fo='';
      maxn=700000;
var   i,j:longint;
      f:text;
      n,k,d:longint;
      tam:array[1..maxn] of boolean;
      ngto:array[1..50000] of longint;
      hold,res:ansistring;
procedure nhap;
begin
    assign(f,fi);reset(f);
    readln(f,n,k);
    close(f);
end;
procedure sang;
begin
    tam[1]:=true;
    for i:=2 to trunc(sqrt(maxn)) do
      if tam[i]=false then
        begin
             j:=i*i;
             while j<=maxn do
                   begin
                       tam[j]:=true;
                       j:=j+i;
                   end;
        end;
    d:=0;
    for i:=2 to maxn do
      if tam[i]=false then
         begin
             inc(d);
             ngto[d]:=i;
             if d=n then exit;
         end;
end;
procedure xuly;
var       tmp,tam:ansistring;
          le,leres:int64;
begin
    sang;
 
 
 
 
    for i:=1 to n do
      begin
          str(ngto[i],tmp);
          hold:=hold+tmp;
      end;
 
    le:=length(hold);
    leres:=le-k;
 
    for i:=1 to le do
      begin
          while (k>0) and (length(res)>0) and (res[length(res)]<hold[i]) do
                begin
                    delete(res,length(res),1);
                    dec(k);
                end;
          res:=res+hold[i];
      end;
 
    while length(res)>leres do
        begin
            delete(res,length(res),1);
        end;
 
 
end;
procedure xuat;
begin
    assign(f,fo);rewrite(f);
    writeln(f,res);
    close(f);
end;
begin
    nhap;
    xuly;
    xuat;
end.