LUBENICA – spoj

Đề bài:

Thuật toán:

  • LCA

Code:

uses    math;
const   fi='';
        fo='';
        maxk=20;
        maxn=trunc(1e5)+3;
        oo=2*trunc(1e9);
 
type    arr1    =array[1..maxn] of longint;
        arr2    =array[1..maxn,0..maxk] of longint;
 
var     mi,ma,p         :arr2;
        depth,dad       :arr1;
        i,j,n,m,q       :longint;
        link,head,ke,ts :array[-maxn..maxn] of longint;
        resma,resmi     :longint;
        cx      :array[1..maxn] of boolean;
procedure add(i,u,v,w:longint);
begin
        link[i]:=head[u];
        head[u]:=i;
        ke[i]:=v;
        ts[i]:=w;
end;
 
procedure enter;
var     u,v,w   :longint;
begin
        readln(n);
        for i:=1 to n-1 do
        begin
                read(u,v,w);
                add(i,u,v,w);
                add(-i,v,u,w);
        end;
end;
 
procedure dfs(u:longint);
var     i,v     :longint;
begin
        cx[u]:=false;
        i := head[u];
        while i<>0 do
                begin
                        v:=ke[i];
                        if cx[v] then
                                begin
                                        depth[v]:=depth[u]+1;
                                        dad[v]:=u; ma[v,0] := ts[i]; mi[v,0] := ts[i];
                                        dfs(v);
                                end;
                        i:=link[i];
                end;
end;
 
procedure init;
var     i,j     :longint;
begin
        fillchar(cx,sizeof(cx),true);
        dad[1] := 1; depth[1] :=1;
        dfs(1);
        for i:=1 to n do
                begin
                        p[i,0] := dad[i];
                end;
        for j:=1 to maxk do mi[1,0] := oo;
        for j:=1 to maxk do ma[1,0] := -oo;
        for j:=1 to maxk do
                for i:=1 to n do
                        begin
                                p[i,j] := p[p[i,j-1],j-1];
                                ma[i,j] := max(ma[i,j-1],ma[p[i,j-1],j-1]);
                                mi[i,j] := min(mi[i,j-1],mi[p[i,j-1],j-1]);
                        end;
end;
procedure lca(u,v:longint);
var     i,j     :longint;
begin
        for i:=maxk downto 0 do
                if depth[p[u,i]]>=depth[v] then
                        begin
                                resma := max(resma,ma[u,i]);
                                resmi := min(resmi,mi[u,i]);
                                u := p[u,i];
                        end;
        for i:=maxk downto 0 do
                if depth[p[v,i]]>=depth[u] then
                        begin
                                resma := max(resma,ma[v,i]);
                                resmi := min(resmi,mi[v,i]);
                                v := p[v,i];
                        end;
        if u=v then exit;
        for i:=maxk downto 0 do
                if p[u,i]<>p[v,i] then
                        begin
                                resma := max(resma,ma[v,i]);
                                resmi := min(resmi,mi[v,i]);
                                resma := max(resma,ma[u,i]);
                                resmi := min(resmi,mi[u,i]);
                                v := p[v,i];
                                u := p[u,i];
                        end;
        resma := max(resma,ma[v,0]);
        resmi := min(resmi,mi[v,0]);
        resma := max(resma,ma[u,0]);
        resmi := min(resmi,mi[u,0]);
end;
procedure process;
var     u,v,qq  :longint;
begin
        read(q);
        for qq:=1 to q do
                begin
                        read(u,v);
                        if u=v then begin writeln(0,' ',0); continue; end;
                                resmi := oo;
                                resma := -oo;
                                lca(u,v);
                        writeln(resmi,' ',resma);
                end;
end;
procedure print;
begin
 
end;
 
begin
        assign(input,fi);reset(input);
        assign(output,fo);rewrite(output);
                enter;
                init;
                process;
                print;
        close(input);close(output);
end

VOTREE – spoj

Đề bài:

Giải thích ví dụ

votree-yeulaptrinh
Truy vấn 1: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 2 đến 5, ở đây có thể thấy 2 là tổ tiên chung gần nhất của các đỉnh 2,3,4,5.
Truy vấn 2: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 1 đến 3, ở đây có thể thấy 1 là tổ tiên chung gần nhất của các đỉnh 1,2,3.
Truy vấn 3: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 4 đến 5, ở đây có thể thấy 3 là tổ tiên chung gần nhất của các đỉnh 4,5.

Thuật toán:

    Có thể nhận thấy rằng tổ tiên chung gần nhất ( LCA ) của 3 đỉnh a,b,c sẽ bằng với LCA(a,LCA(c,b)). Dựa trên tính chất nãy ta có thể sử dụng Interval Tree để tìm LCA của 1 đoạn liên tiếp bằng cách tổ chức cây IT sẽ lưu LCA của các phần tử trong đoạn quản lý.

    Các phần cơ bản của cây IT:

    IT[id] = phần tử đang được quản lý khi đoạn quản lý gồm 1 phần tử.

    IT[id] = LCA(IT[id*2],IT[id*2+1] ).

    P/s : Có rất nhiều cách để tìm LCA ví dụ như : Sparse Table, Heavy Light Decomposition, Interval Tree, …

Code:

const
        tfi='';
        tfo='';
 
var
        fi,fo:Text;
        ke,nx:array[-70000..70000] of longint;
        num,thoat,hd:array[0..70000] of longint;
        f:array[0..70000,0..20] of longint;
        n,q,jmax,dem,dem1:longint;
        t:array[0..3000000] of longint;
 
procedure nhap;
        var i,j,u,v:longint;
        begin
                read(fi,n,q);
                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 j:=1 to 20 do if 1 shl j<=n then jmax:=j+1;
        end;
 
procedure DFS(u:longint);
        var j,v:longint;
        begin
                inc(dem);
                num[u]:=dem;
                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 f[v,0]=0 then
                                        begin
                                                f[v,0]:=u;
                                                DFS(v);
                                        end;
                                j:=nx[j];
                        end;
                inc(dem1);
                thoat[u]:=dem1;
        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 init(i,l,r:longint);
        var mid:longint;
        begin
            if l=r then
                begin
                        t[i]:=l;
                        exit;
                end;
            mid:=(l+r) div 2;
            init(i*2,l,mid);
            init(i*2+1,mid+1,r);
            t[i]:=lca(t[i*2],t[i*2+1]);
        end;
 
function get(i,l,r,u,v:longint):longint;
        var mid:longint;
        begin
                if (l>v) or (r<u) then exit(u);
                if (u<=l) and (r<=v) then exit(t[i]);
                mid:=(l+r) div 2;
                get:=lca(get(i*2,l,mid,u,v),get(i*2+1,mid+1,r,u,v));
        end;
 
procedure xuli;
        var i,u,v,pa,j:longint;
        begin
                f[1,0]:=1;
                DFS(1);
                init(1,1,n);
                for i:=1 to q do
                        begin
                                read(fi,u,v);
                                writeln(fo,get(1,1,n,u,v));
                        end;
 
        end;
 
begin
        assign(fi,tfi);
        assign(fo,tfo);
        reset(fi);
        rewrite(fo);
        nhap;
        xuli;
        close(fo);
end.

MINROAD – spoj

Đề bài

Thuật toán

Ta lưu 2*n điểm vào mảng T:

  • T[i].d là khoảng cách đến vị trí bắt đầu của con đường
  • T[i].k là 1 nếu là cây tùng, là 2 nếu là cây trúc

Sắp xếp mảng T theo thứ tự tăng dần T[i].d

Với mỗi T[i], ta phải tìm vị trí X sao cho từ T[i] đến T[x] có ít nhất a cây tùng và b cây trúc. Đặt F[i]=X.

Dễ dàng nhận thấy: F[i] <= F[i+1] nên ta có thể sử dụng 2 vòng For để tính toán kết quả như sau:

For i=1 to 2*N do 
 For j=F[i-1] to 2*N do ……..
Thay vì dùng mảng F, bạn hoàn toàn có thể sử dụng biến chạy mà thôi

Độ phức tạp: O(N log N).

Code

uses    math;
const   fi='';
        fo='';
        maxn=300000;
type    arra=array[0..maxn] of longint;
var     tung,cuc,d,tu,cu:arra;
        kieu:array[0..maxn] of byte;
        i,j,n,a,b:longint;
        f:text;
        res,tmp:longint;
procedure QS(l,r:longint);
Var i,j,x,w:longint;
Begin
x:=d[(l+r) div 2];
  i:=l;j:=r;
  Repeat
    While(d[i]<x) do i:=i+1;
     While (x<d[j]) do j:=j-1;
      If i<=j then
        Begin
          w:=kieu[i];kieu[i]:=kieu[j];kieu[j]:=w;
          w:=d[i];d[i]:=d[j];d[j]:=w;
          i:=i+1;j:=j-1;
        End;
 until i>j;
 If l<j then QS(l,j);
 If i<r then QS(i,r);
End;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n,a,b);
    for i:=1 to n do
        readln(f,d[i],kieu[i]);
    close(f);
end;
procedure xuly;
var     t,c,k:longint;
begin
    t:=0; c:=0;
    qs(1,n);
    for i:=1 to n do
        if kieu[i]=1 then begin inc(t); tung[t]:=i; end
        else begin inc(c); cuc[c]:=i; end;
    for i:=1 to n do
    begin
        tu[i]:=tu[i-1];
        cu[i]:=cu[i-1];
        if kieu[i]=1 then inc(tu[i]);
        if kieu[i]=2  then inc(cu[i]);
    end;
if (tu[n]<a) or(cu[n]<b) then exit;
    i:=max(tung[a],cuc[b]);
    k:=min(tung[tu[i]-a+1],cuc[cu[i]-b+1]);
    res:=d[i]-d[k];
    inc(i);
    while i<=n do
    begin
        tmp:=min(tung[tu[i]-a+1],cuc[cu[i]-b+1]);
        if d[i]-d[tmp]<res then res:=d[i]-d[tmp];
        inc(i);
    end;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    if res=0 then writeln(f,-1) else
    writeln(f,res);
    close(f);
end;
begin
    nhap;
    xuly;
    xuat;
end.

NKLINEUP – spoj

Đề bài:

Thuật toán:

  • Interval tree

Code:

#include <bits/stdc++.h>
using namespace std;
 
int n,q;
vector<int> a;
vector< pair<int,int> > node;
int resmax, resmin;
 
void Init_Tree(int k, int l, int r, int i)
{
    if(l>i || r<i) return;
    if(l==r)
    {
        node[k]=make_pair(a[i],a[i]);
        return;
    }
    int m=(l+r)/2;
    Init_Tree(2*k,l,m,i);
    Init_Tree(2*k+1,m+1,r,i);
    node[k]=make_pair(max(node[2*k].first, node[2*k+1].first),min(node[2*k].second, node[2*k+1].second));
}
 
void Init()
{
    scanf("%d%d",&n,&q);
    a.resize(n+2);
    node.resize(4*n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        Init_Tree(1,1,n,i);
    }
}
 
void Query(int k, int l, int r, int A, int B)
{
    if(l>B || r<A) return;
    if(A<=l && B>=r)
    {
        resmax=max(resmax,node[k].first);
        resmin=min(resmin,node[k].second);
        return;
    }
    int m=(l+r)/2;
    Query(2*k,l,m,A,B);
    Query(2*k+1,m+1,r,A,B);
}
 
void Solve()
{
    for (int i=1;i<=q;i++)
    {
        int A, B;
        scanf("%d%d",&A,&B);
        resmax=0;
        resmin=10000000;
        Query(1,1,n,A,B);
        printf("%dn",resmax-resmin);
    }
}
 
int main()
{
    Init();
    Solve();
}
uses    math;
const   fi='';
        fo='';
        maxn=50000;
        maxq=200000;
type    arrp=record
                dau:longint;
                cuoi:longint;
                end;
var     i,j,n,q:longint;
        f:text;
        res1,res2:longint;
        a:array[1..maxn] of longint;
        p:array[1..maxq] of arrp;
        mind,maxd:array[1..maxn*4] of longint;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n,q);
    for i:=1 to n do readln(f,a[i]);
    for i:=1 to q do readln(f,p[i].dau,p[i].cuoi);
    close(f);
end;
procedure update(k,l,r:longint);
var     mid:longint;
begin
    if l=r then
    begin
        maxd[k]:=a[l];
        mind[k]:=a[l];
    end
    else
    begin
        mid:=(l+r) div 2;
        update(k*2,l,mid);
        update(k*2+1,mid+1,r);
        mind[k]:=min(mind[k*2],mind[k*2+1]);
        maxd[k]:=max(maxd[k*2],maxd[k*2+1]);
    end;
end;
procedure find(k,l,r:longint);
var     mid:longint;
begin
    if (l>j) or (r<i) then exit;
    if (i<=l) and (j>=r) then
    begin
        res1:=min(res1,mind[k]);
        res2:=max(res2,maxd[k]);
        exit;
    end;
    mid:=(l+r) div 2;
    find(k*2,l,mid);
    find(k*2+1,mid+1,r);
end;
procedure xuat;
var     k:longint;
begin
    assign(f,fo);
    rewrite(f);
    update(1,1,n);
    for k:=1 to q do
    begin
        res1:=high(longint);
        res2:=0;
        i:=p[k].dau;
        j:=p[k].cuoi;
        find(1,1,n);
        writeln(f,res2-res1);
    end;
    close(f);
end;
begin
    nhap;
    xuat;
end.

Thuật toán Kruskal tìm cây khung nhỏ nhất

Định nghĩa cây khung – Cây khung nhỏ nhất

Cho đồ thị vô hướng, cây khung (spanning tree) của đồ thị là một cây con chứa tất cả các đỉnh của đồ thị. Nói cách khác, cây khung là một tập hợp các cạnh của đồ thị, không chứa chu trình và kết nối tất cả các đỉnh của đồ thị.

Trong đồ thị có trọng số, cây khung nhỏ nhất là cây khung có tổng trọng số các cạnh nhỏ nhất. Định nghĩa tương tự với cây khung lớn nhất.

Thuật toán Kruskal

Ban đầu mỗi đỉnh là một cây riêng biệt, ta tìm cây khung nhỏ nhất bằngcách duyệt các cạnh theo trọng số từ nhỏ đến lớn, rồi hợp nhất các cây lại với nhau.

Cụ thể hơn, giả sử cạnh đang xét nối 2 đỉnh u và v nếu 2 đỉnh này nằm ở 2 cây khác nhau thì ta thêm cạnh này vào cây khung, đồng thời hợp nhất 2 cây chứa u và v.

Để thực hiện thao tác trên một cách nhanh chóng, ta sử dụng cấu trúc Disjoint Set, độ phức tạp của toàn bộ thuật toán là O(M log M) với M là số cạnh.

Cài đặt

Đoạn code dưới cài đặt thuật toán Kruskal, có thể dùng để nộp bài

QBMST.

#include <iostream>
#include <vector>
#include <algorithm> // Hàm sort
using namespace std;
 
// Cấu trúc để lưu cạnh đồ thị,
// u, v là 2 đỉnh, w là trọng số cạnh
struct edge {
    int u, v, w;
};
// Hàm so sánh để dùng trong hàm sort ở dưới
bool cmp(const edge &a, const edge &b) {
    return a.w < b.w;
}
 
// Số đỉnh tối đa trong đề bài
#define N 10005
 
// 2 mảng sử dụng trong Disjoint Set
int cha[N], hang[N];
 
// Tìm xem u thuộc cây nào
int find(int u) {
    if (cha[u] != u) cha[u] = find(cha[u]);
    return cha[u];
}
 
// Hợp nhất 2 cây chứ u và v,
// Trả về false nếu không thể hợp nhất
bool join(int u, int v) {
    u = find(u); v = find(v);
    if (u == v) return false;
    if (hang[u] == hang[v]) hang[u]++;
    if (hang[u] < hang[v]) cha[u] = v;
    else cha[v]=u;
    return true;
}
 
int main() {
    // Thêm dòng này để cin, cout chạy nhanh
    ios::sync_with_stdio(false); cin.tie(0);
 
    // Nhập vào số đỉnh và số cạnh
    int n, m; cin >> n >> m;
 
    // Nhập danh sách các cạnh
    vector<edge> edges(m);
    for (edge &e: edges) cin >> e.u >> e.v >> e.w;
 
    // Sắp xếp lại các cạnh theo trọng số tăng dần
    sort(edges.begin(), edges.end(), cmp);
 
    // Khởi tạo cấu trúc Disjoint Set
    for (int i=1; i<=n; i++) {
        cha[i] = i;
        hang[i] = 0;
    }
 
    // Lưu tổng trọng số các cạnh trong cây khung nhỏ nhất
    int mst_weight = 0;
 
    // Duyệt qua các cạnh theo thứ tự đã sắp xếp
    for (edge &e: edges) {
        // Thử hợp nhất 2 cây chứa u và v
        if (join(e.u, e.v)) {
            // Hợp nhất thành công, ta thêm e và kết quả
            mst_weight += e.w;
        }
    }
 
    // Xuất kết quả
    cout << mst_weight;
    return 0;
}

DTTUI1 – spoj

Đề bài:


Thuật toán:


  • Duyệt phân tập kết hợp Chặt nhị phân
  • Bạn có thể tham khảo thuật toán Duyệt phân tập tại đây

Code:


Program DTtui1;
CONST
        fin='';
        fon='';
        maxn=40;
        maxth=1048576;
Type
        Opt=Record
                kl,gt:longint;          //Khoi luong, Gia tri
        End;
        ToHop=array [1..maxth] of Opt;
Var
        o:array [1..2] of ToHop;
        dem:array [1..2] of longint;
        amax:array [1..maxth] of longint;
        w,v:array [1..maxn] of longint;   //Weight, Value
        m,i,j,sw,sv,sum:longint;
        n,mid:byte;
        f:text;
//--------------------------------------------------
        Procedure Nhap;
        Var i:byte;
        Begin
                Assign(f,fin);
                Reset(f);
                Readln(f,n,m);
                For i:=1 to n do
                        Readln(f,w[i],v[i]);
                Close(f);
        ENd;
        //------------------------------------------
 
                Procedure Sort(l,r:longint);
                Var i,j,x:longint;
                        y:Opt;
                Begin
                        i:=l;
                        j:=r;
                        x:=o[2,l+random(r-l+1)].kl;
                        Repeat
                                While o[2,i].kl<x Do inc(i);
                                While o[2,j].kl>x do dec(j);
                                If not(i>j) Then
                                        Begin
                                        y:=o[2,i];
                                        o[2,i]:=o[2,j];
                                        o[2,j]:=y;
                                        inc(i);
                                        dec(j);
                                        ENd;
                        Until i>j;
                        If i<r Then sort(i,r);
                        If l<j Then sort(l,j);
                End;
        //-----------------------------------------
        Procedure Luu(x:byte);
        Var k:longint;
        Begin
                inc(dem[x]);
                k:=dem[x];
                o[x,k].kl:=sw;
                o[x,k].gt:=sv;
        End;
        //----------------------------------------
        Procedure Duyet(bit,i,k:byte);
        Var j:byte;
        Begin
                If sw>m Then Exit;
                For j:=0 to 1 do
                        Begin
                        sw:=sw+j*w[i];
                        sv:=sv+j*v[i];
                        If i=k Then
                                Begin
                                If sw<=m Then Luu(bit);
                                End
                        else Duyet(bit,i+1,k);
                        sw:=sw-j*w[i];
                        sv:=sv-j*v[i];
                        End;
        End;
        //-------------------------------------
        Procedure CheckMax;
        Var i,max:longint;
        Begin
                amax[1]:=1;
                max:=1;
                For i:=2 to dem[2] do
                        Begin
                        If o[2,i].gt>o[2,max].gt Then max:=i;
                        amax[i]:=max;
                        End;
        End;
        //-----------------------------------
        Function Find(bit:byte; x:longint):longint;
        Var dau,giua,cuoi:longint;
        Begin
                dau:=1;
                cuoi:=dem[bit]+1;
                Repeat
                        giua:=(dau+cuoi) div 2;
                        If o[bit,giua].kl <= x Then dau:=giua
                        else cuoi:=giua;
                Until dau+1=cuoi;
                Exit(dau);
        End;
        //------------------------------------
        Procedure Xuat;
        Begin
                Assign(f,fon);
                Rewrite(f);
                Writeln(f,sum);
                Close(f);
        End;
Begin
        Randomize;
        Nhap;
        mid:=n div 2;
        Duyet(1,1,mid);
        Duyet(2,mid+1,n);
        sort(1,dem[2]);
        CheckMax;
 
        For i:=1 to dem[1] do
                Begin
                j:=Find(2,m-o[1,i].kl);
                If o[1,i].gt + o[2,amax[j]].gt > sum Then sum:=o[1,i].gt + o[2,amax[j]].gt;
                End;
        Xuat;
End.

Tổng hợp tài liệu Java cơ bản

Hưởng dẫn dịch chương trình Java: http://uet.vnu.edu.vn/~chauttm/guides/BuildingFirstJavaProgram.pdf

Head First Java: https://zimslifeintcs.files.wordpress.com/2011/12/head-first-java-2nd-edition.pdf

How to Program Java: http://mobile.skku.ac.kr/lecture/2017_1/CEL/how%20to%20program%20Java.pdf