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.

NKMINES – SPOJ

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

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

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.