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

ADBRACK – SPOJ

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

Thuật toán

  • Bài này sử dụng phương pháp đệ quy có nhớ kết hợp với thuật toán xử lý số lớn
  • Các bạn có thể đọc code bên dưới để hiểu hơn

Code:

const   fi='';
        fo='';
        maxn=100+3;
var     f       :array[-maxn..maxn,-maxn..maxn] of ansistring;
        i,j,n,k :longint;
        st      :ansistring;
        p       :longint;
        res     :ansistring;
        stack   :array[1..maxn] of char;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n,k);
        readln(st);
        close(input);
end;
procedure init;
begin
        for i:=0 to n+1 do
                for j:=0 to n+1 do f[i,j]:='-1';
end;
function cong (a,b: ansistring): ansistring;
var     nho,tam,i:longint;
        res     :ansistring;
begin
        while length(a)<length(b) do a:='0'+a;
        while length(b)<length(a) do b:='0'+b;
        nho:=0; res:='';
        for i:=length(a) downto 1 do
                begin
                        tam:=ord(a[i])+ord(b[i])-96+nho;
                        nho:=tam div 10;
                        tam:=tam mod 10;
                        res:=chr(tam+48)+res;
                end;
        if nho>0 then res:='1'+res;
        exit(res);
end;
function tinh(i,c:longint):ansistring;
var     sl      :ansistring;
begin
        if f[i,c]<>'-1' then exit(f[i,c]);
        if i>n then
                if c=0 then
                        begin
                                f[i,c]:='1';
                                exit('1')
                        end
                        else
                        begin
                                f[i,c]:='0';
                                exit('0');
                        end;
        sl:= '0';
                if c<k then
                begin
                stack[c+1]:='(';
                sl := cong( sl, tinh(i+1,c+1) );
                stack[c+1]:='[';
                sl := cong( sl, tinh(i+1,c+1) );
                stack[c+1]:='{';
                sl := cong( sl, tinh(i+1,c+1) );
                end;
                if c>0 then
                sl := cong( sl, tinh(i+1,c-1) );
        f[i,c]:=sl;
        exit(sl);
end;
procedure timkq(i,c:longint);
begin
        if i>n then
                begin
                        res:=cong(res,'1');
                        writeln(res);
                        halt;
                end;
        if st[i]='(' then
                begin
                        stack[c+1]:='(';
                        timkq(i+1,c+1);
                end
        else
                if c<k then
                begin
                        stack[c+1]:='(';
                        res:=cong(res, tinh(i+1,c+1));
                end;
        if st[i]=')' then
                begin
                        timkq(i+1,c-1);
                end
        else
                begin
                        if c>0 then
                        if stack[c]='(' then
                        res:=cong(res,tinh(i+1,c-1));
                end;
        if st[i]='[' then
                begin
                        stack[c+1]:='[';
                        timkq(i+1,c+1) ;
                end
        else
                if c<k then
                begin
                        stack[c+1]:='[';
                        res:=cong(res, tinh(i+1,c+1));
                end;
        if st[i]=']' then
                begin
                        timkq(i+1,c-1) ;
                end
        else
                begin
                        if c>0 then
                        if stack[c]='[' then
                        res:=cong(res,tinh(i+1,c-1));
                end;
        if st[i]='{' then
                begin
                        stack[c+1]:='{';
                        timkq(i+1,c+1);
                end
        else
                if c<k then
                begin
                        stack[c+1]:='{';
                        res:=cong(res,tinh(i+1,c+1));
                end;
        if st[i]='}' then
                begin
                        timkq(i+1,c-1);
                end
        else
                begin
                        if c>0 then
                        if stack[c]='{' then
                        res:=cong(res,tinh(i+1,c-1));
                end;
end;
procedure process;
var     tam:ansistring;
begin
assign(output,fo);rewrite(output);
        tam := tinh(1,0);
        res:='0';
        stack:='';
        timkq(1,0);
close(output);
end;
begin
        enter;
        init;
        process;
end.

TFIELD – SPOJ

Đề bài:


Thuật toán:


    Ngay từ đầu đề bài đã đề cập đến phần hình học.

    – Ta cần biết vị trí của các khoang theo đúng thứ tự (ví dụ từ trong ra ngoài). Ta có nhận xét là đa giác của khoang trong luôn có diện tích nhỏ hơn đa giác của khoang ngoài. Vì thế, ta chỉ cần sắp xếp các đa giác theo diện tích của chúng. Công thức tính diện tích 1 đa giác bất kì:

    S=1/2 ∑(x[i]-x[i+1])*(y[i]+y[i+1]) (với i=[1..n], quy ước điểm thứ n+1 chính là điểm 1).

    – Sau khi sắp xếp, ta có thể tính được diện tích từng khoang (diện tích khoang thứ i=s[i]-s[i-1]).

    – Bài toán đặt ra bây giờ là tìm đoạn khoang có diện tích lớn nhất nằm giữa 2 đa giác. Ta dùng đếm phân phối để giải quyết. Đầu tiên, ta cố định điểm trái của vùng cần xét O(m). Từ điểm này, tìm điểm phải nhất có số khoang cần đổi màu không quá k (nói cách khác là c-st<=k, với c là tổng số khoang của vùng, st là số khoang cùng màu của vùng) O(m). – Kết quả bài toán là kết quả tối ưu trong các giá trị đã xét. Độ phức tạp ~O(m^2).

Code:


uses    math;
const   fi='';
        fo='';
        maxn=1000+3;
type
        dinh    =record
                        x,y:longint;
                        end;
        arr1    =array[1..maxn] of dinh;
var     a       :array[1..maxn,1..maxn] of dinh;
        s       :array[1..maxn] of int64;
        i,j,n,m,k       :longint;
        c       :array[1..maxn] of longint;
        sodinh  :array[1..maxn] of longint;
        khoang  :array[1..maxn] of int64;
        res     :int64;
        dem     :array[1..maxn] of longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        read(m,k);
        for i:=1 to m do
                begin
                        read(sodinh[i],c[i]);
                        for j:=1 to sodinh[i] do read(a[i,j].x,a[i,j].y);
                end;
        close(input);
end;
procedure swap(var x,y:int64);
var     tg      :int64;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure swap2(var x,y:longint);
var     tg      :longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure qs(l,r:longint);
var     x:extended;
        i,j:longint;
begin
        i:=l;j:=r;
        x:=s[(l+r) div 2];
        repeat
                while x<s[i] do inc(i);
                while x>s[j] do dec(j);
                if i<=j then
                        begin
                                swap(s[i],s[j]);
                                swap2(c[i],c[j]);
                                inc(i);dec(j);
                        end;
        until i>j;
        if i<r then qs(i,r);
        if j>l then qs(l,j);
end;
function dientich(p:arr1;n:longint):int64;
var     i       :longint;
begin
        dientich := 0;
        p[n+1] := p[1];
        for i:=1 to n do
                dientich:= dientich + int64( (p[i+1].x-p[i].x) )*(p[i+1].y+p[i].y);
        dientich:= abs(dientich){/2};
end;
procedure tinhs;
var     i:longint;
begin
        for i:=1 to m do
                s[i]:=dientich(a[i],sodinh[i]);
end;
procedure chuanbi;
begin
        sodinh[n+1]:=4;
        a[n+1,1].x:=1;
        a[n+1,1].y:=1;
        a[n+1,2].x:=1;
        a[n+1,2].y:=1;
        a[n+1,3].x:=1;
        a[n+1,3].y:=1;
        a[n+1,4].x:=1;
        a[n+1,4].y:=1;
end;
procedure process;
var     maxc,sokhoang        :longint;
        dientich        :int64;
begin
        tinhs;
        s[m+1]:=0;
        qs(1,m+1);
        for i:=1 to m do
                khoang[i]:=s[i]-s[i+1];
        for i:=1 to m do
                begin
                        fillchar(dem,sizeof(dem),0); dientich := 0; maxc :=1; sokhoang :=1;
                        inc(dem[c[i]]);
                        dientich := dientich + khoang[i]; if dientich>res then res := dientich;
                        for j := i+1 to m do
                        begin
                                inc(dem[c[j]]); inc(sokhoang);
                                maxc := max(maxc,dem[c[j]]);
                                if sokhoang-maxc<=k then
                                        begin
                                                dientich := dientich + khoang[j];
                                                if dientich>res then res := dientich;
                                        end else break;
                        end;
                end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        write(res{:0:1} div 2);
        if odd(res) then
                write('.5') else write('.0');
        close(output);
end;
begin
        enter;
        process;
        print;
end.
#include<bits/stdc++.h>
#define db double
#define fs first
#define sc second
#define maxn 1005
#define ll long long
using namespace std;
int n,k,d[maxn],sum[maxn];
struct data
{
            ll s;
            int c;
};
data a[maxn];
ll res;
typedef pair<int,int> II;
II c[maxn][maxn];
void tinh(int k)
{
            d[k]++;
            c[k][d[k]].fs=c[k][1].fs;
            c[k][d[k]].sc=c[k][1].sc;
            for (int i=2; i<=d[k]; ++i)
            {
                        a[k].s+=((ll)(c[k][i].fs-c[k][i-1].fs)*(c[k][i].sc+c[k][i-1].sc));
            }
            if (a[k].s<0) a[k].s=-a[k].s;
}
bool cmp(const data &a,const data &b)
{
            return a.s<b.s;
}
int main()
{
            //freopen("TFIELD.inp","r",stdin);
            ios::sync_with_stdio(0);
            cin.tie(0);
            cout.tie(0);
            cin>>n>>k;
            for (int i=1; i<=n; ++i)
            {
                        cin>>d[i]>>a[i].c;
                        for (int j=1; j<=d[i]; ++j)
                                    cin>>c[i][j].fs>>c[i][j].sc;
            }
            for (int i=1; i<=n; ++i) tinh(i);
            sort(a+1,a+n+1,cmp);
            sum[n+1]=1000000000;
            for (int i=1; i<=n; ++i)
            {
                        sum[0]=0;
                        for (int j=1; j<=n; ++j)
                                    if (a[j].c!=i) sum[j]=sum[j-1]+1;
                                    else sum[j]=sum[j-1];
                        int r=1;
                        for (int l=1;l<=n;++l)
                        {
                                    while(sum[r+1]-sum[l-1]<=k)
                                                ++r;
                                    res=max(res,a[r].s-a[l-1].s);
                        }
            }
            cout<<res/2;
            if (res%2) cout<<".5";
            else cout<<".0";
            return 0;
}

SPOJ – CRYPTKEY

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

Thuật toán:

  • (đang cập nhập)

Code

const
  fi='';
  fo='';
  maxn=50003;
var
  a : array[1..maxn] of int64;
  b : array[1..maxn] of int64;
  c : array[1..100000] of int64;
  uoc : array[1..100000] of int64;
  sl : array[1..100000] of longint;
  i,j,n,t,tt : longint;
  duoc : longint;
  kt : boolean;
  res,k : int64;
procedure enter;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
end;
procedure pt(x : int64);
  var i,j,dem : longint;
  begin
    for i:=2 to trunc(sqrt(x)) do
      if x mod i = 0 then
        begin
          dem := 0;
          while x mod i = 0 do
            begin
              inc(dem);
              x := x div i;
            end;
          duoc := duoc +1;
          uoc[duoc] := i;
          sl[duoc] := dem;
        end;
    if x>1 then
      begin
        inc(duoc);
        uoc[duoc] := x;
        sl[duoc] := 1;
      end;
  end;
function power(x,y:longint):int64;
  var i : longint;
  begin
    power:=1;
    for i:=1 to y do power := power * x;
  end;
function gcd(a,b : int64) : int64;
  var r : int64;
  begin
      while b<>0 do
        begin
          r := a mod b;
          a:=b;
          b:=r;
        end;
      exit(a);
  end;
function lcm(a,b : int64) : int64;
  var x,y : int64;
  begin
    {x := a; y:=b;}
    lcm := (a div gcd(a,b)) *b;
  end;
procedure sol;
var i,j : longint;
    tg : int64;
    dem : longint;
begin
  read(t);
  for tt :=1 to t do
    begin
      fillchar(a,sizeof(a),0);
      fillchar(uoc,sizeof(uoc),0);
      fillchar(sl,sizeof(sl),0);
      kt := true;
      read(n);
      for i:=1 to n do read(a[i]);
      readln(k);
      pt(k);
      for i:=1 to duoc do
      begin
        tg := power(uoc[i],sl[i]);
        dem := 0;
        for j:=1 to n do
          if a[j] mod tg = 0 then
           begin
             inc(dem); b[dem] := a[j];
           end;
        if dem=0 then begin kt := false; break; end;
        tg := b[1];
        for j:=2 to dem do
          tg := gcd(tg,b[j]);
        c[i] := tg;
      end;
      if not kt then begin writeln('NO'); continue; end;
      res := c[1];
      for i:=2 to duoc do res := lcm(res,c[i]);
      if res=k then
      writeln('YES') else writeln('NO');
    end;
  close(input);close(output);
end;
begin
  enter;
  sol;
end.

GRAPH_ – SPOJ

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

Thuật toán: Đây là bài tập cơ bản về thuật toán tìm cầu, khớp. Bạn có thể tham khảo thuật toán trong ebook Giải thuật và lập trình của thầy Lê Minh Hoàng.

Code:

uses math;
const
  fi='';
  fo='';
  maxn=10000;
  maxm=50000;
  oo=trunc(1e9);
var
  link,head,ke : array[-maxm..maxm] of longint;
  i,j,n,m,kq1,kq2 : longint;
  cau,khop : longint;
  iscut : array[1..maxn] of boolean;
  count : longint;
  cha,num,low : array[1..maxn] of longint;
  free : array[-maxm..maxm] of boolean;
  nchild : array[1..maxn] of longint;
procedure add(i,u,v:longint);
begin
    link[i] :=head[u];
    head[u] := i;
    ke[i]:=v;
end;
procedure enter;
var u,v : longint;
begin
   assign(input,fi);reset(input);
   readln(n,m);
   for i:=1 to m do
     begin
         read(u,v);
         add(i,u,v);
         add(-i,v,u);
     end;
   close(input);
end;
procedure dfs(u:longint);
var i,j,v : longint;
begin
   inc(count);
   num[u]:=count;
   low[u]:=oo;
   i := head[u];
   while i<>0 do
     begin
         if free[i] then
         begin
         v := ke[i];
         free[-i] := false;
         if cha[v]=0 then
           begin
               cha[v]:=u;
               dfs(v);
               low[u] := min(low[v],low[u]);
           end
           else
           begin
               low[u] := min(low[u],num[v]);
           end;
         end;
         i := link[i];
     end;
end;
procedure process;
var i,u,v : longint;
begin
    fillchar(free,sizeof(free),true);
    fillchar(cha,sizeof(cha),0);
    for i:=1 to n do
        if cha[i]=0 then
          begin
              cha[i] := -1;
              dfs(i);
          end;
    for v:=1 to n do
      begin
          u:=cha[v];
          if (u<>-1) and (low[v]>=num[v]) then
                begin
                    inc(cau);
                end;
      end;
    for v:=1 to n do
      if cha[v]<>-1 then
        begin
          inc(nchild[cha[v]]);
        end;
    fillchar(iscut,sizeof(iscut),false);
    for v:=1 to n do
        if cha[v] <> -1 then
        begin
          u := cha[v];
          if low[v]>=num[u] then
            iscut[u]:= iscut[u] or (cha[u]<>-1) or (nchild[u]>=2);
        end;
    for v:=1 to n do
      if iscut[v] then inc(khop);
end;
procedure print;
begin
    assign(output,fo);rewrite(output);
    writeln(khop,' ',cau);
    close(output);
end;
begin
    enter;
    process;
    print;
end.

SPOJ – DHTABLE2

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

Thuật toán:

  • (đang cập nhập)

Code:

var t:int64;
    n:integer;
    f:text;
procedure nhap;
begin
   assign(f,'');reset(f);
   read(f,n,t);
   close(f);
end;
 
procedure xuli;
var i:longint;
    x,l:string;
    mu,k,m
    :int64;
begin
    assign(f,'');rewrite(f);
    mu:=1; i:=0;
    while t>9*mu*(i+1) do
          begin
              dec(t,9*mu*(i+1));
              inc(i);
              mu:=mu*10;
          end;
    inc(i);
    k:=mu+(t-1) div i;
    t:=t mod i;
    x:='';
    while (length(x)<n) and (k>0) do
        begin
            m:=k;
            str(m,l);
            x:=l+x;
            if t>0 then
               begin
                   delete(x,t+1,i-t);
                   t:=0;
               end;
            dec(k);
        end;
    while length(x)>n do delete(x,1,1);
    while length(x)<n do x:=' '+x;
    write(f,x);
    close(f);
end;
 
begin
  nhap;
  xuli;
end.