CREC01 – SPOJ

Đề bài:

Thuật toán:

  • Bài này ta sử dụng kỹ thuật deque. Thuật toán cũng không có gì phức tạp. Bạn có thể đọc code bên dưới để hiểu thêm

Code:

Pascal : https://ideone.com/swTkml

const   fi      ='';
        fo      ='';
        oo      =1000;
 
var     a       :array[0..oo,0..oo] of 0..1;
        l,h,dem:array[0..oo+1] of int64;
        m, n    :longint;
 
procedure Optimize;
var     i, j    :longint;
        ans     :int64;
begin
        fillchar(h, sizeof(h),0);
        ans:=0;
        for i:=1 to m do
                begin
                        for j:=1 to n do
                                begin
                                        if a[i,j]=1 then begin
                                        l[j]:=j;
                                        h[j]:=h[j]+1;
                                        while h[l[j]-1]>h[j] do
                                                l[j]:=l[l[j]-1];
                                        dem[j]:=h[j]*(j-l[j]+1)+dem[l[j]-1];
                                        ans:=ans+dem[j];
                                        //writeln(ans,'==');
                                        //if (i=3) and (j=2) then writeln(dem[1]);
                                        end
                                        else begin
                                                dem[j]:=0;
                                                l[j]:=0;
                                                h[j]:=0;
                                        end;
 
                                end;
 
                end;
        writeln(ans);
end;
 
procedure run;
var     i, j, tg    :longint;
        s       :ansistring;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(m, n);
        for i:=1 to m do
                begin
                        readln(s);
                        for j:=1 to n do
                                        val(s[j],a[i,j]);
                end;
        Optimize;
        close(input);close(output);
 
end;
 
begin
        run;
end.

C++ : https://ideone.com/S0t4zZ

using namespace std;
#include<bits/stdc++.h>
 
#define BG begin()
#define ED end()
#define st first
#define nd second
#define PB push_back
#define PF push_front
#define FOR(i,a,b) for (long long i=a;i<b;i++)
#define FORE(i,a,b) for (long long i=a;i<=b;i++)
#define FORD(i,a,b) for (long long i=a;i>=b; i--)
#define ri(n)({\
    int neg=0;\
    n=0;\
    char ch;\
    for(ch=getchar(); ch<'0' || ch>'9'; ch=getchar()) if (ch=='-') neg=1-neg;\
    n=ch-48;\
    for(ch=getchar(); ch>='0' && ch<='9'; ch=getchar()) n=(n<<3)+(n<<1)+ch-48;\
    if (neg) n=-n;\
})
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> II;
typedef pair<ll,ll> LL;
const ll INF=1000000000+7;
const double esp=1e-13;
const double pi=3.141592653589;
 
 
ll m, n, a[1001][1001], H[1001], dem[1001], L[1001];
 
int main()
{
    //freopen("CREC01.inp", "r", stdin);
    //freopen("CREC01.out", "w", stdout);
    cin>>m>>n;
    char ch;
    FORE(i, 1, m)
        FORE(j, 1, n) {
            cin>>ch;
            a[i][j] = ch - '0';
        }
    memset(H, 0, sizeof(H));
    memset(L, 0, sizeof(L));
    memset(dem, 0, sizeof(dem));
    long long ans = 0;
    FORE(i, 1, m)
        FORE(j, 1, n) {
            //cout<<i<<" "<<j<<" "<<a[i][j]<<endl;
            if (a[i][j] == 1) {
                H[j]++;
                int k = j;
                while ( (k > 1) && (a[i][k-1] == 1) && (H[ k - 1 ] >= H[j]) ) k = L[k - 1];
                L[j] = k;
                dem[j] = H[j]*(j - L[j] + 1) + dem[L[j] - 1];
                ans += dem[j];
                //cout<<i<<"=="<<j<<"=="<<"=="<<H[j]<<"=="<<ans<<endl;
            }
            else
            {
                H[j] = 0;
                dem[j]= 0;
                L[j] = 0;
            }
        }
    cout<<ans;
}

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;
}

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.

BGMINE – SPOJ

Đề bài:

http://vn.spoj.com/problems/BGMINE/

Thuật toán:

Theo yêu cầu đề bài thì mình cần tìm một số hang liên tiếp mà có tổng số đá lớn hơn hoặc bằng độ dài các hang và có tổng số vàng lớn nhất đó: Sumr[j] – Sumr[i-1] >= x[j] – x[i] với (j >= i).

Ta biến đổi điều kiện trên thành: Sumr[j] – x[j] >= Sumr[i-1] – x[i] với (j >= i).

Ta sử dụng ctdl BIT để tính nhanh hơn. Ta cần rời rạc hóa giá trị Sumr[i] – x[i] và Sumr[i-1] – x[i] để lưa được trên cây BIT.

ĐPT: O(nlogn)

Code:

Pascal

uses math;
Const
  Fi='';
  Fo='';
  maxn=trunc(1e5)+3;
  oo=trunc(1e9);
var
  g,r,x : array[1..maxn] of longint;
  a  : array[1..2*maxn] of int64;
  cs,b,t : array[0..2*maxn] of longint;
  i,j,n : longint;
  best : int64;
  sr,sg : array[0..maxn] of int64;
procedure enter;
  begin
    assign(input,fi);reset(input);
    read(n);
    for i:=1 to n do read(x[i],g[i],r[i]);
    close(input);
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg := x; x:= y;y :=tg;
  end;
procedure qs(l,r : longint);
  var i,j :longint;
      x : int64;
  begin
    i := l;j :=r;
    x := a[cs[(l+r) div 2]];
    repeat
      while a[cs[i]]<x do inc(i);
      while a[cs[j]]>x do dec(j);
      if i<=j then
        begin
          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 init;
  begin
    for i:=1 to n do sr[i] := sr[i-1] + r[i];
    for i:=1 to n do sg[i] := sg[i-1] + g[i];
  end;
procedure sub1;
  begin
    for i := 1  to n do
      for j:= i to n do
        begin
          if sr[j] - sr[i-1] >= x[j] - x[i] then
            begin
              best := max(best,sg[j]-sg[i-1]);
            end;
        end;
  end;
procedure roirac;
  var i,hold : longint;
  begin
    for i:=1 to n do a[i] := sr[i]-x[i];
    for i:=1 to n do a[n+i] := sr[i-1]-x[i];
    for i:=1 to 2*n do cs[i] := i;
    qs(1,2*n);
    b[cs[1]]  := 1; hold := 1;
    for i:=2 to 2*n do
      begin
        if a[cs[i]] = a[cs[i-1]] then
          begin
            b[cs[i]] := hold;
          end;
        if a[cs[i]] <> a[cs[i-1]] then
          begin
            inc(hold);
            b[cs[i]] := hold;
          end;
      end;
  end;
procedure update(i,x : longint);
  begin
    while i<=2*n do
      begin
        t[i] := min(t[i],x);
        i := i + i and (-i);
      end;
  end;
function get(i : longint) : longint;
  var res : longint;
  begin
    res := oo;
    while i>0 do
      begin
        res := min(res,t[i]);
        i := i - i and (-i);
      end;
    exit(res);
  end;
procedure sub2;
  var i,tg : longint;
  begin
    roirac;
    for i := 0 to 2*n+3 do t[i] := oo;
    for i:=1 to n do
      begin
        update(b[n+i],i);
        tg := get(b[i]);
        if tg<>oo then
          begin
            best := max(best, sg[i]-sg[tg-1]);
          end;
      end;
  end;
procedure process;
  begin
    sub2;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(best);
    close(output);
  end;
begin
  enter;
  init;
  process;
  print;
end.

C++

using namespace std;
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define FORE(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
const int MAXN = 5*1e5;
const int INF = 1e9 + 7;
 
int n;
int x[MAXN], a[MAXN], r[MAXN];
long long sr[MAXN], sx[MAXN], sg[MAXN];
void sub1()
{
    FORE(i, 1, n) sr[i] = sr[i - 1] + r[i];
    FORE(i, 1, n) sx[i] = sx[i - 1] + x[i];
    FORE(i, 1, n) sg[i] = sg[i - 1] + a[i];
    long long ans = 0;
    FORE(i, 1, n) FORE(j, 0, i - 1) if (sr[i] - sr[j] >= x[i] - x[j + 1]){
        ans = max(ans, sg[i] - sg[j]);
        //if (ans == 99) cout<<i<<" "<<j<<endl;
    }
    cout<< ans <<endl;
}
 
long long b[MAXN], T[MAXN], c[MAXN], sa[MAXN];
int get(int x)
{
    long long ans = INF;
    for(; x; x -= x & -x){
        ans = min(ans, T[x]);
    }
    return ans;
}
void update(int x, long long v)
{
    for(; x < MAXN; x+= x & -x) T[x] = min(T[x], v);
}
 
void sub2()
{
    sr[0] = 0;
    sa[0] = 0;
    FORE(i, 1, n){
        sa[i] = sa[i - 1] + a[i];
        sr[i] = sr[i - 1] + r[i];
        b[i] = sr[i] - x[i];
        b[i + n] = sr[i - 1] - x[i];
        c[i] = b[i];
        c[i + n] = b[i + n];
    }
    b[n + n + 1] = -x[1];
    c[n + n + 1] = -x[1];
    sort(c + 1, c + n + n + 2);
    FORE(i, 1, n + n + 1) b[i] = lower_bound(c + 1, c + n + n + 2, b[i]) - c;
    FOR(x, 0, 1e5 * 5) T[x] = INF;
    update(b[n + n + 1], 1);
    long long ans = 0;
    FORE(i, 1, n){
        int j = get(b[i]);
        //if (i == 41) cout<<j<<"wtf"<<endl;
        ans = max(ans, 1LL * a[i]);
        if (j != INF)
            ans = max(ans, sa[i] - sa[j - 1]);
        update(b[i + n], i);
    }
    cout << ans << endl;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("MINE.inp", "r", stdin);
    freopen("MINE.out", "w", stdout);
    #endif // ONLINE_JUDGE
    //MIKELHPDATKE;
    cin >> n;
    FORE(i, 1, n) cin >> x[i] >> a[i] >> r[i];
    if (n <= 5000) sub1();
    else
    sub2();
    return 0;
}