VOSSEQ – spoj

Đề bài:

Thuật toán:

  • Đọc kỹ đề bài nhé.
  • Đề yêu cầu tìm dãy A có thứ tự từ điển bé nhất chứ không phải có độ dài bé nhất nhé.
  • Ta sẽ sử dụng Heap Min. Trong code bên dưới, mình chuyển các giá trị nguyên dương thành nguyên âm nên Heap Max chuyển thành Heap Min

Code:

#include <bits/stdc++.h>
#define taskname "VOSSEQ"
#define oo INT_MAX
#define maxn 1000001
using namespace std;
//const int maxn =1000001;
int m,k,maxa=-oo,u,a[maxn],d[maxn],res[maxn];
vector <int> v[maxn];
priority_queue <int> q;
void nhap()
{
    cin >> m;
    for(int i=1;i<=m;i++)
    {
        cin >> k;
        for(int i=1;i<=k;i++)
        {
            cin >> a[i];
            maxa=max(maxa,a[i]);
        }
        for(int i=1;i<k;i++)
        {
            v[a[i]].push_back(a[i+1]);
            d[a[i+1]]++;  
        }
    }
}
void xuli()
{
    int cnt=0;
    for(int i=1;i<=maxa;i++)
        if(!d[i]) q.push(-i);
    while(!q.empty())
    {
        u=-q.top();
        q.pop();
        res[++cnt]=u;
        for(int i=0;i<v[u].size();i++)
        {
            d[v[u][i]]--;
            if(!d[v[u][i]]) q.push(-v[u][i]);
        }
    }
    for(int i=1;i<=maxa;i++) cout << res[i] << " ";
}
int main()
{
    //freopen(taskname".INP","r",stdin);
    //freopen(taskname".OUT","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);
    nhap();
    xuli();
    return 0;
}

Cấu trúc dữ liệu Heap và ứng dụng

Heap là một trong những cấu trúc dữ liệu đặc biệt quan trọng, nó giúp ta có thể giải được nhiều bài toán trong thời gian cho phép. Độ phức tạp thông thường khi làm việc với Heap là O(logN). CTDL Heap được áp dụng nhiều trong các bài toán tìm đường đi ngắn nhất, tìm phần tử max, min… và trong lập trình thi đấu. Vậy Heap là gì? Cài đặt Heap như thế nào?

Heap là gì?

Heap thực chất là một cây cân bằng thỏa mãn các điều kiện sau

  • Một nút có không quá 2 nút con.
  • Với Heap Max thì nút gốc là nút lớn nhất, mọi nút con đều không lớn hơn nút cha của nó. Với Heap Min thì ngược lại.

Mặc dù được mô tả như cây nhưng Heap có thể được biểu diễn bằng mảng. Nút con của nút i là 2*i và 2*i+1. Do Heap là cây cân bằng nên độ cao của 1 nút luôn <= logN.

Ứng dụng chủ yếu của Heap là tìm Min, Max trong 1 tập hợp động (có thể thay đổi, thêm, bớt các phần tử) nhưng như vậy đã là quá đủ.

heap-yeulaptrinh

(Mô hình biểu diễn Heap bằng cây nhị phân và bằng mảng)

Các thao tác với Heap

Ở đây mình hướng dẫn các bạn với Heap Max còn với Heap Min thì tương tự

Khai báo

Ở ví dụ này, Heap sẽ là mảng một chiều kiểu LongInt, nHeap là số phần tử của mảng.

Const
  maxn = 100000;
Var
  nHeap : LongInt;
  Heap : array[0..maxn] of LongInt;

1. UpHeap

Nếu 1 nút lớn hơn nút cha của nó thì di chuyển nó lên trên:
upheap-yeulaptrinh

Procedure UpHeap(i : LongInt);
Begin
  if (i = 1) or (Heap[i] < Heap[i div 2]) then exit; // Nếu i là nút gốc hoặc  nhỏ hơn nút cha thì không làm việc
  swap(Heap[i] , Heap[i div 2]); // Đổi chỗ 2 phần tử trong Heap;
  UpHeap(i div 2); // Tiếp tục di chuyển lên trên
end;

2. DownHeap

downheap-1downheap-2

downheap-3

Procedure DownHeap(i : LongInt);
  Var
    j : LongInt;
  Begin
    j := i*2;
    if j > nHeap then exit; // Nếu i không có nút con thì không làm việc
    if (j < nHeap) and (Heap[j] < Heap[j+1]) then Inc(j); // Nếu i có 2 nút con thì chọn nút ưu tiên hơn
    if Heap[i] < Heap[j] then // Nếu nút cha nhỏ hơn nút con
      begin
        swap(Heap[i] , Heap[j]); // Đổi chỗ 2 phần tử trong Heap
        DownHeap(j); // Tiếp tục di chuyển xuống dưới
      end;
  end;

3. Push

Đưa 1 phần tử mới vào Heap: Thêm 1 nút vào cuối Heap và tiến hành UpHeap từ đây:

Procedure Push(x : LongInt);
  Begin
    Inc(nHeap); // Tăng số phần tử của Heap
    Heap[nHeap] := x; // Thêm x vào Heap
    UpHeap(nHeap);
  End;

4. Pop

Rút ra 1 phần tử ở vị trí v trong Heap: Gán Heap[v] := Heap[nHeap] rồi tiến hành chỉnh lại Heap:

Function Pop(v : LongInt) : LongInt;
  Begin
    Pop := Heap[v]; // Lấy phần tử ở vị trí v ra khỏi Heap
    Heap[v] := Heap[nHeap]; // Đưa phần tử ở cuối Heap vào vị trí v
    Dec(nHeap); // Giảm số phần tử của Heap đi 1
    {Chỉnh lại Heap}
    UpHeap(v);
    DownHeap(v);
  End;

Nguồn: không rõ

QBHEAP – spoj

Đề bài:

Thuật toán:

  • Với C++ bạn có thể dùng sẵn CTDL Priority Queue (hàng đợi ưu tiên). Còn với Pascal thì bạn phải tự viết CTDL Heap

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 20000;
string s;
priority_queue <int> h;
char key;
int num, a[MAXN];
 
bool cmp(int a, int b) {
    return (a > b);
}
 
int main() {
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    // solve
    getline(cin, s);
    do {
        key = s[0];
        if (key == '+') {
            s.erase(0,1);
            num = atoi(s.c_str());
            if (h.size()<15000) h.push(num);
        } else if (!h.empty())
        {
            num = h.top();
            while (!h.empty() && h.top()==num) h.pop();
        }
        getline(cin, s);
    } while (s != "");
    // pop
    int res = 0;
    while (!h.empty()) {
        res++;
        a[res] = h.top();
        while (!h.empty() && h.top()==a[res]) h.pop();
    }
    // print
    cout << res << endl;
    for (int i = 1; i <= res; i++) cout << a[i] << endl;
    return 0;
}
const   fi='';
        fo='';
        maxn=15000+3;
var     h:array[1..maxn] of longint;
        i,j:longint;
        res:array[0..maxn] of longint;
        nh,n,ans:longint;
procedure swap(var x,y:longint);
var     tg:longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure qs(l,r:longint);
var     x,i,j:longint;
begin
            i:=l;j:=r;
            x:=res[(i+j) div 2];
            repeat
                while res[i]>x do inc(i);
                while res[j]<x do dec(J);
                if i<=j then
                        begin
                            swap(res[i],res[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 downheap(i:longint);
var     j:longint;
begin
        j:= i + i;
        if j>nh then exit;
        if (j<nh) and (h[j]<h[j+1]) then inc(j);
        if h[j]>h[i] then
                begin
                        swap(h[i],h[j]);
                        downheap(j);
                end;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:=i div 2;
        if i>1 then
        if h[i]>h[j] then
                begin
                        swap(h[i],h[j]);
                        upheap(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 xuat;
begin
        for i:=1 to n do
                if res[i]<>res[i-1] then writeln(res[i]);
end;
procedure main;
var     tam,s:string;
        x,err:longint;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);
 
    while not seekeof(input) do
        begin
            readln(s);
            if s[1]='+' then
            begin
              if nh<15000 then
                begin
                    tam:=copy(s,2,length(s));
                    val(tam,x,err);
                    push(x);
                end
                end
                ELSE
                if nh>0 then
                begin
                        if nh>0 then x:=pop;
                        while (nh>0) and (h[1]=x) do pop;
                end;
        end;
        for i:=1 to nh do
                begin
                        res[i]:=pop;
                        inc(n);
                end;
        qs(1,n);
        res[0]:=-1;
        for i:=1 to n do
                if res[i]<>res[i-1] then inc(ans);
        writeln(ans);
        xuat;
 
    close(input);close(output);
end;
begin
    main;
end.

MPILOT – SPOJ

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

Thuật toán:

  • Đây là bài tập về thuật toán Heap cơ bản
  • Ta đưa yêu cầu bài toán thành chọn các lái phụ có chênh lệch giữa lương lái chính và lương lái phụ là lớn nhất mà vẫn đảm bảo yêu cầu có thể ghép được n/2 cặp mà tuổi lái phụ < lái chính
  • Heap sẽ lưu độ chênh lệch giữa lương lái phục và chính của mọi người
  • Duyệt i=1..n, đẩy i vào, nếu i lẻ thì lấy ở heap ra 1 thằng làm lại phụ
  • Các bạn hãy đọc code để rõ hơn

Code: [xem code]

const   fi='';
        fo='';
        maxn=10000+3;
var     p,h:array[1..maxn] of longint;
        i,j,n,res,sum:longint;
        a,c:array[1..maxn] of longint;
        nh:longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);
        for i:=1 to n do read(a[i],c[i]);
        close(input);
end;
procedure swap(var x,y:longint);
var     tg:longint;
begin
        tg:=x;x:=y;y:=tg;
end;
function tinh(x:longint):longint;
begin
        exit(a[x]-c[x]);
end;
procedure downheap(i:longint);
var     j:longint;
begin
        j:=i + i;
        if j>nh then exit;
        if (j<nh) and ( tinh(h[j+1]) > tinh(h[j]) ) then inc(j);
        if tinh(h[i]) < tinh(h[j]) then
                begin
                        swap(h[i],h[j]);
                        downheap(j);
                end;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:= i div 2;
        if i>1 then
        if tinh(h[i]) > tinh(h[j]) then
                begin
                        swap(h[i],h[j]);
                        upheap(j);
                end;
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        dec(nh);
        downheap(1);
end;
procedure push(i:longint);
begin
        inc(nh);
        h[nh]:=i;
        upheap(nh);
end;
procedure process;
begin
        for i:=1 to n do
                begin
                        inc(sum,a[i]);
                        push(i);
                        if i mod 2 = 1 then inc(res,tinh(pop) );
                end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(sum-res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

CENTRE28 – SPOJ

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

Thuật toán:

  • Tìm đường đi ngắn nhất giữa đỉnh 1 đến mọi đỉnh và giữa đỉnh n đến mọi đỉnh sử dụng thuật toán Dijkstra. Đồng thời ta tính số đường đi ngắn nhất.
  • Gọi d1[i] là đường đi ngắn nhất từ đỉnh 1 đến i
  • Gọi d2[i] là đường đi ngắn nhất từ đỉnh n đến i
  • Gọi f1[i] là số đường đi ngắn nhất từ đỉnh 1 đến i
  • Gọi f2[i] là số đường đi ngắn nhất từ đỉnh n đến i
  • Điều kiện để đỉnh i có thể làm trung tâm kinh tế thứ 3 là: (d1[i]+dn[i]<>d1[n]) hoặc (f1[i]*fn[i]<>f1[n])

Code:

Pascal

const   fi      ='';
        fo      ='';
        maxn    =30000+3;
        maxc    =trunc(1e9)+3;
        maxm    =trunc(1e5);
type    arrd    =array[1..maxn] of longint;
        arrf    =array[1..maxn] of int64;
        arrk    =array[-maxm..maxm] of longint;
        arrh    =array[1..maxn] of longint;
var     d1,dn,d   :arrd;
        f1,fn,f   :arrf;
        n,i,j,m   :longint;
        res     :longint;
        ans     :arrd;
        head :array[1..maxn] of longint;
        link,ts,ke    :arrk;
        // dijkstra heap;
        h,p     :array[1..maxn] of longint;
        nh      :longint;
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
        assign(input,fi);reset(input);
        readln(n,m);
        for i:=1 to m do
                begin
                        read(u,v,w);
                        add(i,u,v,w);
                        add(-i,v,u,w);
                end;
        close(input);
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 then
        if d[h[i]] < d[h[j]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]],p[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 (d[h[j]] > d[h[j+1]]) then inc(j);
        if d[h[j]] < d[h[i]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]],p[h[j]]);
                        downheap(j);
                end;
end;
procedure push(i:longint);
begin
        inc(nh);
        h[nh]:=i;
        p[i]:=nh;
        upheap(nh);
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        p[h[1]]:=1;
        dec(nh);
        downheap(1);
end;
procedure update(i:longint);
begin
        if p[i]=0 then push(i) else upheap(p[i]);
end;
procedure dijkstra(s:longint);
var     u,v,i:longint;
begin
        fillchar(h,sizeof(f),0);
        fillchar(p,sizeof(p),0);
        nh:=0;
        fillchar(f,sizeof(f),0);
        for i:=1 to n do d[i]:=maxc;
        d[s]:=0;
        f[s]:=1;
        push(s);
        repeat
                u:=pop;
                i:=head[u];
                while i<>0 do
                        begin
                                v:=ke[i];
                                if d[v]>d[u]+ts[i] then
                                        begin
                                                d[v]:=d[u]+ts[i];
                                                f[v]:=f[u];
                                                update(v);
                                        end
                                        else
                                if d[v]=d[u]+ts[i] then
                                        begin
                                                f[v]:=f[u]+f[v];
                                        end;
                                i:=link[i];
                        end;
        until nh=0;
end;
procedure process;
begin
        dijkstra(1);
        f1:=f;
        d1:=d;
        dijkstra(n);
        fn:=f;
        dn:=d;
        for i:=1 to n do
                if (d1[i]+dn[i]<>d1[n])
                or (f1[i]*fn[i]<>f1[n]) then
                        begin
                                inc(res);
                                ans[res]:=i;
                        end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        {for i:=1 to n do writeln(d1[i]);}
        writeln(res);
        for i:=1 to res do writeln(ans[i]);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

C++

#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 * 5;
const int INF = 1e9 + 7;
 
using namespace std;
int n, m;
struct data{
    int u, w;
    bool operator <(const data &op) const
    {
        return w > op.w;
    }
};
vector< data > adj[MAXN];
priority_queue<data, vector<data> > q;
int d[3][MAXN];
long long f[3][MAXN];
void min_path(int cs, int s)
{
    FORE(u, 1, n) d[cs][u] = INF;
    d[cs][s] = 0; f[cs][s] = 1;
    q.push((data){s, 0});
    while (q.size()){
        int u = q.top().u;
        int cost_to_u = q.top().w;
        q.pop();
        if (cost_to_u != d[cs][u]) continue;
        FOR(i, 0, adj[u].size()){
            int v = adj[u][i].u;
            int w = adj[u][i].w;
            if (d[cs][v] > d[cs][u] + w){
                d[cs][v] = d[cs][u] + w;
                f[cs][v] = f[cs][u];
                q.push((data){v, d[cs][v]});
            }
            else
            if (d[cs][v] == d[cs][u] + w) f[cs][v] += f[cs][u];
        }
    }
}
vector< int > ans;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("CENTRE.inp", "r", stdin);
    freopen("CENTRE.out", "w", stdout);
    #endif //MIKELHPDATKE
    cin >> n >> m;
    int u, v, w;
    FORE(i, 1, m){
        cin >> u >> v >> w;
        adj[u].push_back((data){v, w});
        adj[v].push_back((data){u, w});
    }
    min_path(1, 1);
    min_path(2, n);
    FORE(u, 1, n) if (d[1][u] + d[2][u] > d[1][n] || (d[1][u] + d[2][u] == d[1][n] && 1ll * f[1][u] * f[2][u] < f[1][n])) ans.push_back(u);
    cout << ans.size() << endl;
    FOR(i, 0, ans.size()) cout << ans[i]<<endl;
    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.