DEMSO – SPOJ

May 5, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • Bài này sử dụng phương pháp đệ quy có nhớ
  • (thuật toán đang cập nhập)

Bạn có thể đọc code để hiểu rõ hơn.

Code:

Pascal

const
  fi='';
  fo='';
  maxn=20;
var
  a,b,tg1,tg2 : int64;
  aa : array[1..maxn] of longint;
  i,j,n,k,d : longint;
  f : array[0..maxn,0..maxn,0..maxn,false..true,false..true] of int64;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg:=x;x:=y;y:=tg;
  end;
procedure chuanbi(x : int64; var n : longint);
  var i,j : longint;
  begin
    n := 0;
    while x>0 do
      begin
        inc(n); aa[n] := x mod 10;
        x := x div 10;
      end;
    i:=1; j:=n;
    while (i -1 then exit(f[i,tr,sl,big0,small]);
    if i>n then
      if (sl<=k) and (small)  then exit(1) else exit(0);
    dem := 0;
    if not small then
      begin
        for j := 0 to aa[i] do
          begin
            if big0 then tg := sl + ord(abs(j-tr)<=d) else tg := 0;
            dem := dem + tinh(i+1,j,tg,big0 or (j>0),small or (j0),small or (j

C++


#include 
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 5;
const int INF = 1e9 + 7;

using namespace std;

long long l, r, D, K, n;
long long f[20][10][20][2][2];
int a[20];

bool check(long long x)
{
    bool ans = 1;
    int top = 0;
    int tmp = x;
    while (tmp){
        a[++top] = tmp % 10;
        tmp /= 10;
    }
    reverse(a + 1, a + top + 1);
    int dem = 0;
    FORE(i, 2, top) if (abs(a[i] - a[i - 1]) <= D) dem++;
    //if (x == 103) cout << dem<<" "< n){
        return (worse <= K && greater0 > 0);
    }
    if (f[i][dig][worse][ok][greater0] > -1) return f[i][dig][worse][ok][greater0];

    long long ans = 0;
    if (i == 1){
        FORE(x, 0, a[i]) ans += duyet(i + 1, x, worse, ok | (x < a[i]), (x > 0));
    } else {
        int last = 9;
        if (ok == 0) last = a[i];
        int wnext;
        //if (i == 3) cout << last << "??"< 0));
        }
    }
    f[i][dig][worse][ok][greater0] = ans;
    return ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("DEMSO.inp", "r", stdin);
    freopen("DEMSO.out", "w", stdout);
    #endif //MIKELHPDATKE
    cin >> l >> r >> D >> K;
    //trau();

    long long tmp = r, top = 0;
    while (tmp){
        a[++top] = tmp % 10;
        tmp /= 10;
    }
    reverse(a + 1, a + top + 1); n = top;
    memset(f, -1, sizeof(f));

    long long ans = duyet(1, 0, 0, 0, 0);
   // cout << ans << endl;

    tmp = l - 1, top = 0;
    while (tmp){
        a[++top] = tmp % 10;
        tmp /= 10;
    }
    reverse(a + 1, a + top + 1); n = top;
    memset(f, -1, sizeof(f));
    if (l - 1 == 0) cout << ans;
    else{
        ans -= duyet(1, 0, 0, 0, 0);
        cout << ans;
    }
    //cout<
Chủ đề: Đệ quy có nhớ, Phương pháp, SPOJ Mức độ: , , , ,

QBSEQ – SPOJ

May 4, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • Gọi F[i][j] là độ dài dãy con dài nhất của dãy A[1..i] có tổng các phần tử chia k dư j.

Các bạn có thể tham khảo thuật toán chi tiết ở trang 162 quyển “Giải thuật và lập trình” của thầy Lê Minh Hoàng.

Code:

uses math;
const
  fi='';
  fo='';
  maxn=1000;
  maxk=50;
var
  f : array[0..maxn,0..maxk] of longint;
  a : array[1..maxn] of longint;
  i,j,n,k : longint;
procedure enter;
  begin
    assign(input,fI);reset(input);
    readln(n,k);
    for i:=1 to n do read(a[i]);
    close(input);
  end;
function calc ( x,y : longint) : longint;
  var tg : longint;
  begin
    tg := (x-y) mod k ;
    if tg<0 then tg := tg+k;
    exit(tg);
  end;
procedure solve;
  begin
    for i:=0 to n do
      for j:=0 to k-1 do
        f[i,j] := -maxn*maxn;
    f[0,0] := 0;
    for i:=1 to n do
      for j:=0 to k-1 do
        f[i,j] := max(f[i-1,j],f[i-1,calc(j,a[i])] +1);
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(f[n,0]);
    close(output);
  end;
begin
  enter;
  solve;
  print;
end.
Chủ đề: Phương pháp, Quy hoạch động, SPOJ Mức độ: , , ,

DHFRBUS – SPOJ

April 18, 2016 by Leave a Comment

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

Thuật toán:

  • Sử dụng thuật toán tìm đường đi ngắn nhất dijkstra.
  • Gọi d[u,x] là quãng đường ngắn nhất đi từ s đến u khi dùng x vé xe miến phí
  • Kết quả là d[t,k].

Code:

{$inline on}

const   fi      ='';
        fo      ='';
        maxN    =trunc(1e5)*2;
        maxM    =trunc(1e5)*10;
        maxK    =5;
        oo       =2*trunc(1e12);
type    Tadj    =record
                v,w,link:int64;
        end;

        THeap   =record
                v1,v2:int64;
        end;

        Arr1    =array[0..maxN] of int64;
        Arr2    =array[0..maxM] of Tadj;
        Arr4    =array[0..maxN*maxK] of THeap;
        Arr5    =array[0..maxN,0..maxK] of int64;

var     n, m, k :longint;
        Adj     :arr2;
        Head    :arr1;
        s, t    :longint;
        d       :arr5;
        Pos     :arr5;
        H       :arr4;
        nHeap   :longint;
        c       :longint;
//heapmin;
procedure hv(var a, b:int64);
var     tg      :int64;
begin
        tg:=a;a:=b;b:=tg;
end;

procedure UpHeap(i:longint);
begin

        if (i<=1) or (d[H[i div 2].v1,H[i div 2].v2]<=d[H[i].v1,H[i].v2]) then exit;
        hv(Pos[H[i div 2].v1,H[i div 2].v2],Pos[H[i].v1,H[i].v2]);
        hv(H[i div 2].v1,H[i].v1);
        hv(H[i div 2].v2,H[i].v2);
        UpHeap(i div 2);
end;

procedure DownHeap(i:longint);
var     j :longint;
begin
        j:=i*2;
        if j>nHeap then exit;
        if (j0 do
                begin
                        v:=adj[i].v;
                        w:=adj[i].w;
                        if d[v,x]>d[u,x]+w then
                        begin
                                d[v,x]:=d[u,x]+w;
                                Update(v,x);
                        end;
                        if (xd[u,x]) then
                        begin
                                d[v,x+1]:=d[u,x];
                                Update(v,x+1);
                        end;
                        i:=adj[i].link;
                end;
        until nHeap=0;
        ans:=oo;
        ans:=d[t,k];
        {for x:=0 to k do
                if d[t,x]
Chủ đề: Dijkstra, SPOJ, Thuật toán Mức độ: , , , ,

HIREHP – SPOJ

February 16, 2016 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/HIREHP/
Thuật toán: Dùng cây IT lưu giá trị tối ưu tại mỗi thời gian. Với bài này khi cập nhập thì cập nhập từ lá lên gốc
Code:

uses math;
const
  fi='hirehp.inp';
  fo='hirehp.out';
  maxn=5*trunc(1e5);
  oo=trunc(1e18);
var
  tree : array[1..4*maxn] of int64;
  idleaf : array[1..maxn] of longint;
  i,j,n : longint;
  f : array[1..maxn] of int64;
  t,p : array[1..maxn] of longint;
procedure build(k,l,r : longint);
  var m : longint;
  begin
    if l = r then
      begin
        idleaf[l] := k;
        exit;
      end;
    m := (l+r) div 2;
    build(k*2,l,m);
    build(k*2+1,m+1,r);
  end;
procedure update(j: longint; x : int64);
  begin
    i := idleaf[j];
    while i > 0 do
      begin
        tree[i] := min(tree[i] , x);
        i := i div 2;
      end;
  end;
function get(k,l,r,i,j : longint) : int64;
  var m  :  longint;
      tg1,tg2 : int64;
  begin
    if (i>r) or (j=r) then exit(tree[k]);
    m := (l+r) div 2;
    tg1 := get(k*2,l,m,i,j);
    tg2 := get(k*2+1,m+1,r,i,j);
    get := min(tg1,tg2);
  end;
procedure main;
var i : longint;
begin
//  assign(input,fi);reset(input);
//assign(output,fo);rewrite(output);
  read(n);
  for i := 1 to n do read(t[i] , p[i]);
  for i := 1 to 4*n do tree[i] := oo;
  build(1,1,n);
  update(t[1] , p[1]);
  f[1] := p[1];
  for i := 2 to n do
    begin
      f[i] := get(1,1,n,i-1,n) + p[i];
      update(t[i] , f[i]);
    end;
  writeln(get(1,1,n,n,n));
  //close(input);close(output);
end;
begin
  main;
end.
Chủ đề: Cấu trúc dữ liệu, IT, SPOJ Mức độ: , , ,

SPOJ – DHLOCO

February 11, 2016 by Leave a Comment

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

Thuật toán:

  • Sub2: QHĐ f[i] = f[i-1]+f[i-2]+f[i-3];
  • Sub3: Nhân ma trận

Code:

const
  fi='dhloco.inp';
  fo='dhloco.out';
  mt1 : array[1..3,1..3] of int64=((0,0,1) , (1,0,1) , (0,1,1));
  mt2 : array[1..3,1..3] of int64=((1,2,4) , (0,0,0) , (0,0,0));
type
  matrix = array[1..3,1..3] of int64;
var
  n : int64;
  i,j,k,m : longint;
function mul(a,b :matrix) : matrix;
  var c : matrix;
      i,j,k : longint;
  begin
    for i := 1 to 3 do
      for j := 1 to 3 do
        begin
          c[i,j] := 0 ;
          for k := 1 to 3 do
            c[i,j] := (c[i,j] + a[i,k] * b[k,j]) mod m;
        end;
    exit(c);
  end;
function power(a : matrix; y : int64) : matrix;
  var tg : matrix;
  begin
    if y = 1 then exit(a);
    tg := power(a,y shr 1);
    if y mod 2 = 0 then exit(mul(tg , tg)) else exit(mul(mul(tg,tg),a));
  end;
procedure main;
var a,b,c : matrix;
begin
 // assign(input,fi);reset(input);
 // assign(output,fo);rewrite(output);
  read(n,m);
  if n=1 then begin writeln(1 mod m); exit; end;

  if n=2 then begin writeln(2 mod m); exit; end;

  if n=3 then begin writeln(4 mod m); exit; end;
  a := mt1;
  b := mt2;
  a := power(a , n-3);
  c := mul(b,a);
  writeln(c[1,3]);
  //close(input);close(output);
end;
begin
  main;
end.
Chủ đề: Nhân ma trận, Quy hoạch động, SPOJ Mức độ: , , ,