Archives for Tháng Tám 2016

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.