SUBSTR – SPOJ

August 26, 2016 by Leave a Comment

Đề bài: http://yeulaptrinh.de/319/substr-spoj/

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.
    Chủ đề: Hashing, SPOJ Mức độ:

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

    August 21, 2016 by 1 Comment

    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:

    http://yeulaptrinh.de/312/coin34-spoj/
    http://yeulaptrinh.de/673/vector-spoj/

    Chủ đề: Duyệt phân tập, Tài liệu, Thuật toán

    COIN34 – SPOJ

    August 21, 2016 by 1 Comment

    Đề 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 (xj;
    if i
    Chủ đề: Duyệt phân tập, SPOJ Mức độ: