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.

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

KPLANK – spoj

Đề bài:

Thuật toán:

  • Sừ dụng thuật toán tìm max/min trên một đoạn tịnh tiến.

Code:

uses math;
const
  fi='';
  fo='';
  maxn=trunc(1e6)+3;
var
  st : array[1..maxn] of longint;
  a,l,r : array[1..maxn] of longint;
  i,j,n : longint;
  res : int64;
  top : longint;
procedure enter;
  begin
    assign(input,fi);reset(input);
    readln(n);
    for i:=1 to n do read(a[i]);
  end;
procedure push(x : longint);
  begin
    inc(top);
    st[top] := x;
  end;
function get: longint;
  begin
    get := st[top];
  end;
procedure process;
  begin
    top :=0 ;
    for i:=1 to n do
      begin
        while (top<>0) and (a[get]>=a[i]) do dec(top);
        if top=0 then l[i] := 0 else l[i] := get;
        push(i);
      end;
    top := 0;
    for i:=n downto 1 do
      begin
        while (top<>0) and (a[get]>=a[i]) do dec(top);
        if top=0 then r[i]:=n+1 else r[i] := get;
        push(i);
      end;
    for i:=1 to n do
      if r[i]-l[i]-1>=a[i] then
        res := max(res, a[i]);
end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(res);
  end;
begin
  enter;
  process;
  print;
end.

QBRECT – spoj

Đề bài:

Thuật toán:

Sau đây là cách tìm hình chữ nhật lớn nhất trong thời gian O(n^2):

Với mỗi ô j trên hàng i, ta tìm f(j) là số ô 1 liên tiếp trên cột j, tính từ hàng i trở lên. Sau đó, với mỗi cột j, ta tiếp tục tìm ô gần nhất bên trái và ô gần nhất bên phải có f nhỏ hơn f(j), sau đó tính diện tích hình chữ nhật ở cột j là S=f(j)×(r−l−1) với l,r là chỉ số 2 ô bên trái và bên phải nói trên.
Hình minh hoạ khi tính f(4):
deque-yeulaptrinh.pw
Để tìm l,r nhanh, ta dùng kĩ thuật sử dụng Deque tìm Min/Max trên đoạn tịnh tiến.

Code:

uses    math;
const   fi='';
        fo='';
        maxn=1000;
var     a:array[1..maxn,1..maxn] of byte;
        i,j,m,n,res,top:longint;
        h,s,left,right:array[1..maxn] of integer;
procedure nhap;
begin
    assign(input,fi);reset(input);
    readln(m,n);
    for i:=1 to m do
        for j:=1 to n do read(a[i,j]);
    close(input);
end;
procedure push(x:integer);
begin
    inc(top);
    s[top]:=x;
end;
function get:integer;
begin
    exit(s[top]);
end;
procedure pop;
begin
    dec(top);
end;
procedure xuly;
begin
    for i:=1 to m do
     begin
        for j:=1 to n do
           if a[i,j]=1 then
                begin
                    h[j]:=h[j]+1;
                end else h[j]:=0;
        top:=0;
        for j:=1 to n do
            begin
                while (top<>0) and (h[j]<=h[get]) do pop;
                if top=0 then left[j]:=0 else left[j]:=get;
                push(j);
            end;
        top:=0;
        for j:=n downto 1 do
                begin
                    while (top<>0) and (h[j]<=h[get]) do pop;
                    if top=0 then right[j]:=n+1 else right[j]:=get;
                    push(j);
                end;
        for j:=1 to n do
                begin
                    res:=max(res,h[j]*(right[j]-left[j]-1));
                end;
     end;
end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);
    writeln(res);
    close(output);
end;
begin
    nhap;
    xuly;
    inkq;
end.

CROSS12 – spoj

Đề bài:


Thuật toán:


Đầu tiên ta cần tính thời gian qua cầu của mỗi người (khi đi một mình). Có thể tính bằng tham lam như cách được sử dụng trong code ở trên hoặc kết hợp quy hoạch động với deque để tìm min trên đoạn tịnh tiến.

Độ phức tạp khi tính là $O(m)$ cho mỗi người, vì $r$ chỉ dao động từ 1 đến 100 nên ta dùng một mảng phụ để cache giá trị đã tính lại.

Sau khi tính xong, gọi thời gian qua cầu của $n$ người là $A(n)$, ta sắp xếp $A$ tăng dần.

Gọi $F(i)$ là thời gian ít nhất để những người từ 1 đến i qua cầu, ta có công thức:

$ F(1) = A(1) \ F(2) = A(2) \ F(i) = min \begin{cases} F(i-2) + A(1) + 2A(2) + A(i) & \quad (1)\ F(i-1) + A(1) + A(i) & \quad (2)\ \end{cases} $

Trong trường hợp $(1)$, ta cho $A(2)$ quay về, sau đó $A(i)$ và $A(i-1)$ qua cầu, sau đó $A(1)$ từ bên kia cầu quay về, $A(1)$ và $A(2)$ cùng qua cầu.

Trong trường hợp $(2)$, $A(1)$ quay về sau đó cùng $A(i)$ qua cầu.

Code:


#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int time(int r, int m, const char *bridge) {
    int i = 0, res = 1;
    while (i + r <= m) {
        res++;
        i += r;
        while (bridge[i] == '1') i--;
    }
    return res;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<int> a(n);
    for (auto &x: a) cin >> x;
    string bridge; cin >> bridge;
    bridge = '0' + bridge + '0';
    vector<int> cache(101, 0);
    for (auto &x: a) {
        if (!cache[x]) x = cache[x] = time(x, m, bridge.data());
        else x = cache[x];
    }
    sort(a.begin(), a.end());
    if (n == 1) cout << a[0];
    else if (n == 2) cout << a[1];
    else {
        int f0 = a[0], f1 = a[1];
        for (int i=2; i<n; i++) {
            int f2 = min(f0 + a[0] + 2*a[1] + a[i], f1 + a[0] + a[i]);
            f0 = f1, f1 = f2;
        }
        cout << f1;
    }
    return 0;
}

P172SUMD – SPOJ

Đề bài: http://www.spoj.com/PTIT/problems/P172SUMD/

Thuật toán:

Nhập và thêm phần tử  vào queue. Nếu gặp remove thì xem phần tử được nhập ở phần trước có giống phần tử ở top của queue không. Nếu có thì pop,  nếu không thì cũng pop và tăng biến đếm lên 1.

Source code:  https://ideone.com/xpCnbh

Cấu trúc dữ liệu BIT – Binary Indexed Tree (Fenwick Tree)

Giới thiệu về cây Fenwick (hay còn được gọi là BIT)
BIT-yeulaptrinh.pw

Tổng quát, đặt m = 2k.p (với p là số lẻ). Hay nói cách khác, k là vị trí của bít 1 bên phải nhất của m. Trong Fenwick-Tree, nút có số hiệu m sẽ là nút gốc của một cây con gồm 2k nút có số hiệu từ m- 2k+1 đến m.

Ví dụ:

    – 8 = 23.1, vậy 8 là nút gốc của các nút 1, 2, 3, …, 8.

    – 12 = 22.3, vậy 12 là nút gốc của các nút  9, 10, 11, 12

    – 10 = 21.5, vậy 10 là nút gốc của các nút  9, 10.

    – 7 = 20.7, vậy 7 là nút gốc của chỉ nút  7.

    – 16 = 24.1, vậy 16 là nút gốc của các nút 1, 2, 3, …, 16.

Trong Fenwick-Tree, nút gốc đại diện cho tất cả các nút con của nó. Ý nghĩa của từ đại diện ở đây thường dùng là nút gốc lưu tổng giá trị của các nút con. Vì vậy khi tính toán, ta chỉ cần truy xuất nút gốc là đủ mà không cần thiết phải truy xuất đến các nút con. Xét ví dụ:

       Cho mảng gồm n phần tử a1, a2, …, an. Hãy tính tổng Am =  a1 + a2 + … + am (m ≤ n).

Thay vì sử dụng vòng lặp từ 1 đến m để truy xuất từng phần tử ai một (độ phức tạp O(m)), ta sử dụng cấu trúc FENWICK-TREE như sau:

    – t1 = a1

    – t2 = a1 + a2

    – t3 = a3

    – t4 = a1 + a2 + a3 + a4

    – t5 = a5

    – t6 = a5 + a6

    – t7 = a7

    – t8 = a1 + a2 + a3 + a4+ a5 + a6 + a7 + a8

    – …

    – t12 = a9 + a10 + a11 + a12

    – … (tiếp tục như vậy theo cách xây dựng Fenwick-Tree)

 

    * Để tính A15 (m=15), thay vì phải duyệt từ a1 đến a15, ta chỉ cần tính t8 + t12 + t14 + t15 .

    * Để tính A10, chỉ cần tính t8 + t10

    * Để tính A13, chỉ cần tính t8 + t12 + t13

    * Để tính A16, lấy ngay giá trị t16

Tổng quát với m bất kỳ, biểu diễn m thành dạng nhị phân, sau đó lần lượt xóa các bít 1 của m theo thứ tự từ phải sang trái, tại mỗi bước trung gian chính là chỉ số nút cần truy xuất trong Fenwick-Tree.

Ví dụ: m = 13 có biểu diễn nhị phân là 1101:

     1) 1101 -> truy xuất nút 13

     2) Xóa bít 1 bên phải nhất còn 1100 -> truy xuất nút 12

     3) Xóa bít 1 bên phải nhất còn 1000 -> truy xuất nút 8

     4) Xóa bít 1 bên phải nhất và dừng.

Thao tác truy xuất các nút như trên được gọi là getFENWICK-TREE. May mắn là ta có một công thức rất đơn giản để xóa bít 1 bên phải dùng phép toán AND. Thủ tục getFENWICK-TREE như sau:

int getFENWICK-TREE(int m)
{
            int result = 0;
            for(; m> 0; m &= m-1
            {
                        result += t[m];
            }
            return result;
}

Độ phức tạp của getFENWICK-TREE là O(log2m)

Vấn đề còn lại là làm thế nào để xây dựng được Fenwick-Tree như trên? Cách thực hiện là ban đầu khởi tạo các nút của Fenwick-Tree là 0. Sau đó ứng với mỗi giá trị am thì cập nhật các nút cha liên quan trong cây. Ví dụ:

    – Cập nhật giá trị a5 -> cần cập nhật các nút t5, nút cha t6, nút cha t8, nút cha t16,….

    – Cập nhật giá trị a9 -> cần cập nhật các nút t9, nút cha t10, nút cha t12, nút cha t16,…

    – Cập nhật giá trị a4 -> cần cập nhật các nút t4, nút cha t8, nút cha t16,…

Tổng quát với m bất kỳ, biểu diễn m thành dạng nhị phân, nếu cộng 1 vào bít bên phải nhất của m thì ta được nút cha của m.

Ví dụ, m = 5 có biểu diễn nhị phân là 101:

    1) 101 -> cập nhật nút 5

    2) Cộng 1 vào bít phải nhất thành 0110 -> cập nhật nút 6

    3) Cộng 1 vào bít phải nhất thành 1000 -> cập nhật nút 8

    4) Cộng 1 vào bít phải nhất thành 10000 -> cập nhật nút 16.

Thao tác cập nhật các nút từ con đến cha như trên được gọi là updateFENWICK-TREE. Ta cũng có một công thức rất đơn giản để cộng 1 vào bít 1 bên phải nhất dùng phép toán AND. Thủ tục updateFENWICK-TREE như sau:

void updateFENWICK-TREE(int m, int value)
{
   for(; m<= n; m += m & -m)
   {
        t[m] += value;
   }
}

Độ phức tạp của updateFENWICK-TREE là O(log2n)

Trên đây là lý thuyết về Binary Indexed Tree. Bây giờ ta sẽ áp dụng FENWICK-TREE để giải bài Dãy nghịch thế và Dĩa nhạc 3.

Dãy nghịch thế: (Theo cách vét cạn thì cần xét tất cả các cặp, độ phức tạp là O(n2))

Phác thảo thuật toán:

– Dùng một mảng đếm t[100.000], t[u] cho biết hiện giờ có bao nhiêu số nhỏ hơn u.

– Đầu tiên khởi tạo các phần tử mảng t là 0.

– Duyệt từ cuối mảng lên đầu mảng (i từ n->1), ứng với mỗi ai thực hiện hai thao tác:

    1) Kiểm tra xem hiện giờ có bao nhiêu số nhỏ hơn ai (truy xuất t[ai]).

    2) Cập nhật ai vào mảng t, nghĩa là tăng các phần tử từ t[ai+1] đến t[100.000], mỗi phần tử thêm 1.

Tuy nhiên trong thao tác 2 việc cập nhật như vậy tổng thể độ phức tạp vẫn là O(n2). Bây giờ ta sẽ chuyển mảng t thành cấu trúc FENWICK-TREE. Đối với thao tác 1 dùng getFENWICK-TREE, đối với thao tác 2 dùng updateFENWICK-TREE.

Chương trình hoàn chỉnh

cin>>n;
for(i= 1; i<= n; i++) cin>>a[i];
kq = 0;
for(i= n; i>= 1; i–)
{
            kq += getFENWICK-TREE(a[i]);
            updateFENWICK-TREE(a[i]+1, 1);
}
cout<<kq;

Độ phức tạp là O(nlog2n)