Archives for Tháng Hai 2016

NKSTEP – SPOJ

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

Thuật toán:

  • (đang cập nhập)

Code:

const   fi='';
        fo='';
        maxn=100000;
var     t:longint;
        a,l,c:array[1..maxn] of int64;
        x,y,hold,tmp,max,k,w:int64;
        i,j:longint;
        res:int64;
        f:text;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,t);
    max:=-1;
    for i:=1 to t do
        begin
            readln(f,x,y);
            a[i]:=abs(x-y);
            if a[i]>max then max:=a[i];
        end;
    close(f);
end;
procedure xuly;
begin
        l[1]:=1; l[2]:=2;
        c[1]:=1;
        tmp:=1;
        hold:=2;
        w:=2;
        while w<max do
        begin
            inc(tmp);
            c[tmp]:=c[tmp-1]+tmp;
            w:=c[tmp]*2;
            inc(hold);
            l[hold]:=w-tmp;
            inc(hold);
            l[hold]:=w;
        end;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    for i:=1 to t do
        for j:=1 to hold do
        if l[j]>=a[i] then begin writeln(f,j); break; end;
    close(f);
end;
begin
    nhap;
    xuly;
    xuat;
end.

VOMARIO – SPOJ

Đề 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 <bits/stdc++.h>
#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<<" "<<it[x].b<<" :"<<l<<" "<<r<<endl;
    if (pos < l || pos > 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<long long, long long> 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<<endl;
    memset(f, 0, sizeof(f));
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("VOMARIO.inp", "r", stdin);
    freopen("VOMARIO.out", "w", stdout);
    #endif //YEULAPTRINH.PW
    cin >> 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] <<" "<<v[b[i]]<<endl;
    //FORE(i, 1, n + 1) cout<<a[i]<<" ";cout<<endl;
    //b[0] = b[n + 1];
/*
    update(1, 0, top, 0, 2, (line){-1, -1});
    update(1, 0, top, 0, 0, (line){1, 9});
    update(1, 0, top, 5, 5, (line){-4, 26});
    update(1, 0, top, 5, 5, (line){4, -6});
    cout << top << endl;
    cout << query(1, 0, top, 2)<<"wtf"<<endl;
    */
    //FORE(i, 0, n) cout << a[i]<<" ";cout<<endl;
    //FORE(i, 0, n) cout << b[i]<<" ";cout<<endl;
    long long ans = 0;
    FORE(i, 1, n){
        f[i] = query(1, 0, top, b[i]) + e[i];
        ans = max(ans, f[i]);
        long long l, r;
        if (w[i] == 0) r = top, l = 0;
        else{
            //if (i == 2) cout << (x[i] + f[i] / w[i])<<"wtf"<<endl;
            r = upper_bound(a, a + n + 1, x[i] + f[i] / w[i]) - a - 1;
            //cout << x[i] + f[i] / w[i]<<"???"<<r<<"<<<<<"<<b[r]<<endl;
            r = pos[r];
            l = lower_bound(a, a + n + 1, x[i] - f[i] / w[i]) - a;
            l = pos[l];
 
            //cout <<l<<" "<<r<<endl;
        }
        long long mid = b[i];
        update(1, 0, top, mid, r, (line){-w[i], f[i] + w[i] * x[i]});
        update(1, 0, top, l, mid, (line){w[i],  f[i] - w[i] * x[i]});
        //cout<<i<<"=+"<<b[i]<<"??"<<f[i]<<endl;
        //cout << mid <<" "<<r<<"line"<<-w[i]<<" "<<f[i] + w[i] * x[i]<<endl;
        //cout << l <<" "<<mid<<"line"<<w[i]<<" "<<f[i] - w[i] * x[i]<<endl;
    }
    cout << ans;
 
    return 0;
}

VODIVIDE – SPOJ

Đề bài:

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 x<a[i] do inc(i);
        while x>a[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 i<r then qs(i,r);
    if j>l 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.

VOMOVREC – SPOJ

Đề 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 (x<u) and (y<v) then exit(true) else exit(false);
  end;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  read(n);
  for i := 1 to n do
    with a[i] do
      begin
        read(x1,y1,x2,y2);
      end;
  d := 0; c := oo;
  g := (d+c) div 2;
  while (g<>c) 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.

HBTLCA – SPOJ

Đề 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.

MOVE12 – SPOJ

Đề 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]]<b[h[j]]) then
                        begin
                                swap(h[i],h[j]);
                                upheap(j);
                        end;
        end;
 
procedure downheap(i:longint);
        var j:longint;
        begin
                j:=i+i;
                if (j>nh) then exit;
                if (j<nh) and (b[h[j]]>b[h[j+1]]) then inc(j);
                if b[h[i]]>b[h[j]] then
                        begin
                                swap(h[i],h[j]);
                                downheap(j);
                        end;
        end;
 
procedure push(x:longint);
        begin
                inc(nh);
                h[nh]:=x;
                upheap(nh);
        end;
 
 
function pop:longint;
        begin
                pop:=h[1];
                h[1]:=h[nh];
                dec(nh);
                downheap(1);
        end;
 
procedure sort(l,r:longint);
        var i,j,key:longint;
        begin
                i:=l;
                j:=r;
                key:=a[l+random(r-l+1)];
                repeat
                        while a[i]<key do inc(i);
                        while a[j]>key 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 i<r then sort(i,r);
                if l<j then sort(l,j);
        end;
 
function check(x:longint):boolean;
        var i,j,u:longint;
        begin
                nh:=0;
                for i:=1 to  n do
                        begin
                                a[i]:=c[i]-(x div t[i]);
                                b[i]:=c[i]+(x div t[i]);
                        end;
                sort(1,n);
                i:=0;
                j:=1;
                for i:=1 to n do
                begin
                while (a[j]<=i)  and (j<=n) do
                        begin
                                push(j);
                                inc(j);
                        end;
                        if nh>0 then u:=pop else u:=0;
                        if b[u]<i then exit(false);
                end;
                exit(true);
        end;
 
 
procedure xuli;
        var l,r,mid,res:longint;
        begin
 
                l:=0;
                r:=10000*10000;
                while l<=r do
                        begin
                                mid:=(l+r) div 2;
                                if check(mid) then
                                        begin
                                                res:=mid;
                                                r:=mid-1;
                                        end
                                else l:=mid+1;
                        end;
                writeln(fo,res);
        end;
 
 
begin
        assign(fi,tfi);
        assign(fo,tfo);
        reset(fi);
        rewrite(fo);
        nhap;
        xuli;
        close(fo);
end.

HIREHP – SPOJ

Đề bài:

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<l) then exit(oo);
    if (i<=l) and (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.