Aida Nana

NKPALIN – SPOJ

April 3, 2016 by Aida Nana 2 Comments

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

Thuật toán:

Gọi F[i][j] là độ dài xâu đối xứng dài nhất trong đoạn S[i..j]. Khi đó:

F[i,j] = F[i+1,j-1]+2 nếu S[i] = S[j]
F[i,j] = max(F[i+1,j],F[i,j-1]) nếu S[i] <> S[j]

Bạn có thể đọc code bên dưới để hiểu hơn.

Code:

Program Xaucon;
Var s,st,st1:ansistring;
    i,j:integer;
    F: Array[1..2000,1..2000] Of Integer;

Procedure nhap;
 Begin
  Readln(s);
  For i:=1 to length(s) do F[i,i]:=1;
  Writeln;Writeln;
 end;

Function max(a,b:integer):integer;
 Begin
  If a>b then exit(a) else exit(b);
 End;


Procedure Solve;
 Begin
  For i:=length(s) downto 1 do
   For j:=i+1 to length(s) do
     If s[i]=s[j] then
         F[i,j]:=F[i+1,j-1]+2
     else F[i,j]:= max(F[i+1,j],F[i,j-1]);
   End;

Procedure PrintResult;
 Begin
  i:=1;
  j:=length(s);
    While (i<=j) do
    Begin
     If s[i]=s[j] then
       Begin
         st:=st+s[i];
         st1:=s[j]+st1;
         inc(i);
         dec(j);
       end
     Else
       If F[i+1,j]=F[i,j] then inc(i) else dec(j);
    End;
     If F[1,length(s)] mod 2 =1 then delete(st1,1,1);
    st:=st+st1;
  Writeln(st);
  end;

 Begin
 nhap;
 Solve;
 PrintResult;
readln
end.

Chủ đề: Phương pháp, Quy hoạch động, SPOJ Mức độ: NKPALIN SPOJ, QHĐ

VOMARIO – SPOJ

February 22, 2016 by Aida Nana Leave a Comment

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

Thuận toán: Sử dụng Interval Tree để quản lí tập các đoạn thẳng. Có thể dễ dàng tìm được công thức QHĐ O(N^2) với F(i) = số năng lượng max đến lượt chơi thứ i. Để giảm độ phức tạp thì có thể dùng IT để cập nhật nhanh.

Code:

#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 * 2;
const int INF = 1e9 + 7;

using namespace std;
int n;
long long x[MAXN], w[MAXN], e[MAXN], a[MAXN], v[MAXN], b[MAXN];
long long f[MAXN];
struct line{
    long long a, b;
} it[MAXN * 4];
long long Get(line d, long long pos)
{
    return d.a * v[pos] + d.b;
}

long long query(int x, int l, int r, long long pos)
{
    //cout << it[x].a<<" "< r) return 0;
    long long ans = Get(it[x], pos);
    if (l == r) return ans;
    int mid = (l + r) / 2;
    ans = max(ans, query(2 * x, l, mid, pos));
    ans = max(ans, query(2 * x + 1, mid + 1, r, pos));
    return ans;
}

void update(int x, int l, int r, int u, int v, line val)
{
    int mid = (l + r) / 2;
    if (r < u || v < l) return;
    if (u <= l && r <= v){
    // do something
    if (Get(it[x], l) >= Get(val, l) && Get(it[x], r) >= Get(val, r)){
        return;
    }
    if (Get(it[x], l) <= Get(val, l) && Get(it[x], r) <= Get(val, r)){
        it[x] = val;
        return;
    }
    if (Get(it[x], l) >= Get(val, l) && Get(it[x], mid) >= Get(val, mid)){
        update(2 * x + 1, mid + 1, r, u, v, val);
        return;
    }
    if (Get(it[x], l) <= Get(val, l) && Get(it[x], mid) <= Get(val, mid)){
        update(2 * x + 1, mid + 1, r, u, v, it[x]);
        it[x] = val;
        return;
    }
    if (Get(it[x], mid + 1) >= Get(val, mid + 1) && Get(it[x], r) >= Get(val, r)){
        update(2 * x, l, mid, u, v, val);
        return;
    }
    if (Get(it[x], mid + 1) <= Get(val, mid + 1) && Get(it[x], r) <= Get(val, r)){
        update(2 * x, l, mid, u, v, it[x]);
        it[x] = val;
        return;
    }
    }
    update(2 * x, l, mid, u, v, val);
    update(2 * x + 1, mid + 1, r, u, v, val);
}

map M;
long long pos[MAXN];

void trau()
{
    f[0] = 0;
    FORE(i, 1, n) FORE(j, 0, i - 1) if (f[j] >= w[j] * abs(x[i] - x[j]))
            f[i] = max(f[i], f[j] - w[j] * abs(x[i] - x[j]) + e[i]);
    cout << f[n] << endl;
    //FORE(i, 1, n) cout << f[i]<<" ";cout<> n;
    FORE(i, 1, n){
        cin >> x[i] >> w[i] >> e[i];
        a[i] = x[i];
    }
    //trau();
    sort(a, a + n + 1);

    FORE(i, 0, n) b[i] = lower_bound(a, a + n + 1, x[i]) - a;
    FORE(i, 0, n) v[b[i]] = x[i], M[x[i]] = b[i];
    FORE(i, 0, n) pos[i] = M[a[i]];
    int top = *max_element(b, b + n + 1);
    FORE(i, 1, MAXN * 4 - 1) it[i].a = 0, it[i].b = 0;
    update(1, 0, top, 0, top, (line){0, 0});
    //FORE(i, 1, n + 1) cout << b[i] <<" "<

Chủ đề: IT, SPOJ Mức độ: IT, VOMARIO SPOJ

VODIVIDE – SPOJ

February 22, 2016 by Aida Nana Leave a Comment

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

Thuật toán: Bài này có thể giải bằng phương pháp Quy hoạch động hoặc CTDL Heap. Ở đây giải theo phương pháp Quy hoạch động.

Gọi F[i,j] là tổng số tiền lớn nhất mà Sơn nhận được khi xét i đồng và Sơn được j đồng
```
F[i,j]:=max(f[i-1,j],f[i-1,j-1]+b[i]);
```

Code:

uses    math;
const   fi='';
        fo='';
        maxn=5000+2;
var     f:array[0..maxn,0..maxn] of longint;
        a,b,cs:array[1..maxn] of longint;
        res:array[1..maxn] of longint;
        dem,n,i,j:Longint;
        free:array[1..maxn] of boolean;
procedure nhap;
begin
    assign(input,fi);reset(Input);
    readln(n);
    for i:=1 to n do read(a[i]);
    for i:=1 to n do read(b[i]);
    close(input);
end;
procedure init;
begin
    for i:=1 to n do cs[i]:=i;
end;
procedure swap(var x,y:longint);
var     w:longint;
begin
    w:=x;x:=y;y:=w;
end;
procedure qs(l,r:longint);
var     i,j,x:longint;
begin
    i:=l;j:=r;
    x:=a[(l+r) div 2];
    repeat
        while xa[j] do dec(j);
        if i<=j then
                begin
                    swap(a[i],a[j]);
                    swap(b[i],b[j]);
                    swap(cs[i],cs[j]);
                    inc(i);dec(j);
                end;
    until i>j;
    if il then qs(l,j);
end;
procedure xuly;
begin
    {f[1,0]:=b[1];}
    qs(1,n);
    for i:=2 to n do
        for j:=1 to i div 2 do
                begin
                    f[i,j]:=max(f[i-1,j],f[i-1,j-1]+b[i]);
                end;
end;
procedure trace;
begin
    i:=n; j:=n div 2;
    while (i<>0) and (j<>0) do
        begin
            if f[i,j]=f[i-1,j-1]+b[i] then
                begin
                        inc(dem);
                        res[dem]:=i;
                        free[i]:=true;
                        dec(i);dec(j);
                end else dec(i);
        end;
end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);
    writeln(f[n,n div 2]);
    for i:=1 to dem do
        begin

            for j:=res[i]-1 downto 1 do
                if free[j]=false then
                        begin
                            write(cs[j],' ');
                            free[j]:=true;
                            break;
                        end;
            write(cs[res[i]],' ');
            writeln;
        end;
    close(output);
end;
begin
    nhap;
    init;
    xuly;
    trace;
    inkq;
end.

Chủ đề: Phương pháp, Quy hoạch động, SPOJ Mức độ: hsg qg, QHĐ, VODIVIDE

VOMOVREC – SPOJ

February 22, 2016 by Aida Nana Leave a Comment

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

Thuật toán: Ta sẽ tìm kiếm nhị phân kết quả của bài toán. Với mỗi giá trị chia nhị phân V, ta sẽ “nở” các hình chữ nhật ra về bốn phía một độ dài bằng V. Lúc này điều kiện cần và đủ để tất cả các hình chữ nhật ban đầu có thể di chuyển với khoảng cách không quá V thỏa mãn yêu cầu là tất cả các hình chữ nhật đã được nở có phần giao. Điều kiện N hình chữ nhật có phần giao chung hay không là max(X1) < min(X2) và max(Y1) < min(Y2).

Code:

uses math;
const
  fi='';//vomovrec.inp';
  fo='';//vomovrec.out';
  maxn=trunc(1e6);
  oo=trunc(1e9)*3;
type
  rect = record
    x1,y1,x2,y2 : int64;
    end;
var
  m,n,i,j : longint;
  a : array[1..maxn] of rect;
  d,c,g : int64;
function ok(k : int64) : boolean;
  var i : longint;
      x,y,u,v : int64;
  begin
    x := a[1].x1 - k;
    y := a[1].y1  - k;
    u := a[1].x2  +k;
    v := a[1].y2 + k;
    for i := 2 to n do
      with a[i] do
      begin
        x := max(x, x1-k);
        y := max(y, y1-k);
        u := min(u, x2+k);
        v := min(v, y2+k);
      end;
    if (xc) and (g<>d) do
    begin
      if ok (g) then c := g else d := g;
      g := (d+c) div 2;
    end;if ok(d) then
      begin
        write(d);
        exit;
      end;
     writeln(c);
  close(input);
  close(output);
end.

Chủ đề: SPOJ, Thuật toán, Tìm kiếm nhị phân Mức độ: tknp, VOMOVREC spoj

HBTLCA – SPOJ

February 20, 2016 by Aida Nana Leave a Comment

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

Thuật toán:

(đang cập nhập)

Code:

const
    tfi='';//hbtlca.inp';
    tfo='';//hbtlca.out';

var
    fi,fo:Text;
    n,jmax,dem1,goc,dem2:longint;
    ke,nx:array[-100000..100000] of longint;
    hd,num,thoat,d:array[0..100000] of longint;
    f:array[0..100000,0..20] of longint;

procedure nhap;
    var i,u,v:longint;
    begin
        read(fi,n);
        fillchar(hd,sizeof(hd),0);
        for i:=1 to n-1 do
            begin
                read(fi,u,v);
                ke[i]:=v;
                nx[i]:=hd[u];
                hd[u]:=i;
                ke[-i]:=u;
                nx[-i]:=hd[v];
                hd[v]:=-i;
            end;
        for i:=0 to 20 do if 1 shl i<=n then jmax:=i+1;
    end;

procedure DFS(u:longint);
    var i,j,v:longint;
    begin
        inc(dem1);
        num[u]:=dem1;
        for j:=1 to jmax do
            f[u,j]:=f[f[u,j-1],j-1];
        j:=hd[u];
        while j<>0 do
            begin
                v:=ke[j];
                if v<>f[u,0] then
                    begin
                        f[v,0]:=u;
                        d[v]:=d[u]+1;
                        DFS(v);
                    end;
                j:=nx[j];
            end;
        inc(dem2);
        thoat[u]:=dem2;
    end;

function cha(x,y:longint):boolean;
    begin
        cha:=(num[x]<=num[y]) and (thoat[y]<=thoat[x]);
    end;

function lca(x,y:longint):longint;
    var j:longint;
    begin
        if cha(x,y) then exit(x);
        if cha(y,x) then exit(y);
        for j:=jmax downto 0 do
            if not cha(f[x,j],y) then x:=f[x,j];
        exit(f[x,0]);
    end;

procedure check(u,v:longint);
    var pa,pa1,pa2:longint;
    begin
        pa:=lca(u,v);
        pa1:=lca(goc,u);
        pa2:=lca(goc,v);
        if (d[pa]>=d[pa1]) and (d[pa]>=d[pa2]) then writeln(fo,pa)
        else
        if (d[pa1]>=d[pa2]) and (d[pa1]>=d[pa]) then writeln(fo,pa1)
        else writeln(fo,pa2);
    end;

procedure xuli;
    var i,j,q,u,v:longint;
        ch:char;
    begin
        while true do
        begin
        nhap;
        if n=0 then exit;
        dem1:=0;
        dem2:=0;
        f[1,0]:=1;
        DFS(1);
        readln(fi,q);
        goc:=1;
        for i:=1 to q do
            begin
                read(fi,ch);
                if ch='!' then
                    begin
                        readln(fi,goc);
                    end
                else
                if ch='?' then
                    begin
                        readln(fi,u,v);
                        check(u,v);
                    end;
            end;
        end;
    end;

begin
    assign(fi,tfi);
    assign(fo,tfo);
    reset(fi);
    rewrite(fo);
    xuli;
    close(fo);
end.

Chủ đề: LCA, SPOJ Mức độ: HBTLCA spoj, lca

MOVE12 – SPOJ

February 16, 2016 by Aida Nana Leave a Comment

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

Thuật toán:

Chặt nhị phân thời gian gặp nhau
Kiểm tra có thỏa mãn không (sử dụng heap). Bạn có thể đọc cdoe bên dưới sẽ hiểu hơn.

Code:

const
        tfi='';//move12.inp';
        tfo='';//move12.out';

var
        fi,fo:text;
        n,nh:longint;
        a,b,h,pos,c,t,v:array[0..10000]of longint;

procedure nhap;
        var i:longint;
        begin
                read(fi,n);
                for i:=1 to n do read(fi,c[i],t[i]);
        end;


procedure swap(var x,y:longint);
        var tg:longint;
        begin
                tg:=x;
                x:=y;
                y:=tg;
        end;

procedure upheap(i:longint);
        var j:longint;
        begin
                j:=i div 2;
                if (i>1) and (b[h[i]]nh) then exit;
                if (jkey do dec(j);
                        if i<=j then
                                begin
                                        swap(a[i],a[j]);
                                        swap(b[i],b[j]);
                                        inc(i);
                                        dec(j);
                                end;
                until i>j;
                if i0 then u:=pop else u:=0;
                        if b[u]

Chủ đề: Heap, SPOJ, Tìm kiếm nhị phân Mức độ: heap, MOVE12 SPOJ, tknp

HIREHP – SPOJ

February 16, 2016 by Aida Nana 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 độ: duyen hai, hirehp, IT, spoj

NKMINES – SPOJ

February 12, 2016 by Aida Nana 1 Comment
Đề bài: http://vn.spoj.com/problems/NKMINES/

Thuật toán:

Duyệt trạng thái hàng 1 và cột 1 từ đó lần ra được các ô khác.

Nếu trạng thái mìn thỏa mãn thì xuất ra và dừng chương trình luôn.

Code:

const h1: array[1..8] of integer = (1, -1, 0, 0, 1, -1, 1, -1); h2: array[1..8] of integer = (0, 0, 1, -1, 1, -1, -1, 1); var a, res: array[0..201, 0..201] of byte; m, n: byte; procedure init; var i, j: integer; begin fillchar(res, sizeof(res), 0); readln(m, n); for i:= 1 to m do begin for j:= 1 to n do read(a[i, j]); readln; end; end; function count(i, j: byte): byte; var tmp, k: byte; begin tmp:= 0; for k:= 1 to 8 do if res[i + h1[k], j + h2[k]] = 1 then inc(tmp); exit(tmp); end; function fill(i, j: byte): boolean; var t1, t2: integer; begin if (i = 1) or (j = 1) then exit(true); if (i > m) or (j > n) then exit(true); res[i, j]:= 0; t1:= a[i - 1, j - 1] - count(i - 1, j - 1); if t1 < 0 then exit(false); if t1 > 1 then exit(false); {if j = n then begin t2:= a[i - 1, j] - count(i - 1, j); if t2 <> t1 then exit(false); end; if i = m then begin t2:= a[i, j - 1] - count(i, j - 1); if t2 <> t1 then exit(false); end;} res[i, j]:= t1; exit(true); end; procedure printres; var i, j: byte; begin for i:= 1 to m do begin for j:= 1 to n do write(res[i, j],' '); writeln; end; halt; end; procedure attempt(i: byte); var p, q, u: byte; ok: boolean; begin for p:= 0 to 1 do for q:= 0 to 1 do begin res[i, 1]:= p; res[1, i]:= q; ok:= true; for u:= 1 to i do if (not fill(u, i)) or (not fill(i, u)) then begin ok:= false; break; end; if not ok then continue; if (i >= m) and (i >= n) then printres; attempt(i + 1); end; end; begin init; attempt(1); end.

Chủ đề: Đệ quy, SPOJ, Thuật toán Mức độ: NKMINES spoj

NKPALIN – SPOJ

CREC01 – SPOJ

NKSTEP – SPOJ

VOMARIO – SPOJ

VODIVIDE – SPOJ

VOMOVREC – SPOJ

HBTLCA – SPOJ

MOVE12 – SPOJ

HIREHP – SPOJ

NKMINES – SPOJ

Recent Posts

Recent Comments

Archives

Categories

Meta