Queue (hàng đợi) trong C++

Queue là một loại cấu trúc dữ liệu và một loại container adaptor, được thiết kế để hoạt động theo kiểu FIFO (First – in first – out) (vào trước ra trước), tức là một kiểu danh sách mà việc bổ sung được thực hiển ở cuối danh sách và loại bỏ ở đầu danh sách.

Trong queue, có hai vị trí quan trọng là vị trí đầu danh sách (front), nơi phần tử được lấy ra, và vị trí cuối danh sách (back), nơi phần tử cuối cùng được thêm vào.

Khai báo: #include <queue>

Các hàm thành viên:

  • size : trả về kích thước hiện tại của queue. ĐPT O(1).
  • empty : true nếu queue rỗng, và ngược lại. ĐPT O(1).
  • push : đẩy vào cuối queue. ĐPT O(1).
  • pop: loại bỏ phần tử (ở đầu). ĐPT O(1).
  • front : trả về phần tử ở đầu. ĐPT O(1).
  • back: trả về phần tử ở cuối. ĐPT O(1).

Chương trình demo:

#include 

#include

using namespace std;

queue q;

int i;

main() {
for (i=1;i<=5;i++) q.push(i); // q={1,2,3,4,5} q.push(100); // q={1,2,3,4,5,100} cout << q.front() << endl; // In ra 1 q.pop(); // q={2,3,4,5,100} cout << q.back() << endl; // In ra 100 cout << q.empty() << endl; // In ra 0 cout << q.size() << endl; // In ra 5 system("pause"); }

Stack (ngăn xếp) trong C++

Stack là một loại container adaptor, được thiết kế để hoạt động theo kiểu LIFO (Last – in first – out) (vào sau ra trước), tức là một kiểu danh sách mà việc bổ sung và loại bỏ một phần tử được thực hiển ở cuối danh sách. Vị trí cuối cùng của stack gọi là đỉnh (top) của ngăn xếp.

 

Khai báo: #include <stack>

 

Các hàm thành viên:

  • size : trả về kích thước hiện tại của stack. ĐPT O(1).
  • empty : true stack nếu rỗng, và ngược lại. ĐPT O(1).
  • push : đẩy phần tử vào stack. ĐPT O(1).
  • pop : loại bỏ phẩn tử ở đỉnh của stack. ĐPT O(1).
  • top : truy cập tới phần tử ở đỉnh stack. ĐPT O(1).

Chương trình demo:

#include <iostream>

#include <stack>

using namespace std;

stack <int> s;

int i;

main() {

  for (i=1;i<=5;i++) s.push(i); // s={1,2,3,4,5} 
  s.push(100); // s={1,2,3,4,5,100} 
  cout << s.top() << endl; // In ra 100 
  s.pop(); // s={1,2,3,4,5} 
  cout << s.empty() << endl; // In ra 0 
  cout << s.size() << endl; // In ra 5 system("pause");

}

List (danh sách liên kết) trong C++

  • List được thực hiện như danh sách nối kép (doubly-linked list). Mỗi phần tử trong danh sách nối kép có liên kết đến một phần tử trước đó và một phần tử sau nó.
  • Do đó, list có các ưu điểm như sau:
    1. Chèn và loại bỏ phần tử ở bất cứ vị trí nào trong container. O(1).
  • Điểm yếu của list là khả năng truy cập tới phần tử thông qua vị trí. O(n).
  • Khai báo: #include <list>

Các hàm thành viên:

Capacity:

  • size : trả về số lượng phần tử của list. ĐPT O(1).
  • empty : trả về true(1) nếu list rỗng, ngược lại là false(0). ĐPT O(1).

 

Truy cập phần tử:

  • front: trả về giá trị phần tử đầu tiên. ĐPT O(1).
  • back: trả về giá trị phần tử cuối cùng. ĐPT O(1).

 

Chỉnh sửa:

  • push_back : thêm phần tử vào ở cuối list. ĐPT O(1).
  • push_front : thêm phần tử vào đầu list. ĐPT O(1).
  • pop_back : loại bỏ phần tử ở cuối list. ĐPT O(1).
  • pop_front : loại bỏ phần tử ở đầu list. ĐPT O(1).
  • insert (iterator,x): chèn “x” vào trước vị trí “iterator” ( x có thể là phần tử hay iterator của 1 đoạn phần tử…). ĐPT là số phần tử thêm vào.
  • erase : xóa phần tử ở vị trí iterator. ĐPT là số phần tử bị xóa đi.
  • swap : đổi 2 list cho nhau (ví dụ: first.swap(second);). ĐPT O(1).
  • clear: xóa list. ĐPT O(n).

 

Operations:

  • splice : di chuyển phần tử từ list này sang list khác. ĐPT O(n).
  • remove (const) : loại bỏ tất cả phần tử trong list bằng const. ĐPT O(n).
  • remove_if (function) : loại bỏ tất các phần tử trong list nếu hàm function return true . ĐPT O(n).
  • unique : loại bỏ các phần tử bị trùng lặp hoặc thỏa mãn hàm nào đó. ĐPT O(n). Lưu ý: Các phần tử trong list phải được sắp xếp.
  • sort : sắp xếp các phần tử của list. O(NlogN)
  • reverse : đảo ngược lại các phần tử của list. O(n).

Deque trong C++

Deque hay còn được gọi là hàng đợi hai đầu

  • Deque (thuờng được phát âm giống như “deck”) là từ viết tắt của double-ended queue (hàng đợi hai đầu).
  • Deque có các ưu điểm như:
  1. Các phần tử có thể truy cập thông cua chỉ số vị trí của nó. O(1)
  2. Chèn hoặc xóa phần tử ở cuối hoặc đầu của dãy. O(1)

Khai báo: #include <deque>

 

Capacity:

  • size : trả về số lượng phần tử của deque. ĐPT O(1).
  • empty : trả về true(1) nếu deque rỗng, ngược lại là false(0). ĐPT O(1).

Truy cập phần tử:

  • operator [] : trả về giá trị phần tử thứ []. ĐPT O(1).
  • at : tương tự như trên. ĐPT O(1).
  • front: trả về giá trị phần tử đầu tiên. ĐPT O(1).
  • back: trả về giá trị phần tử cuối cùng. ĐPT O(1).

 

Chỉnh sửa:

  • push_back : thêm phần tử vào ở cuối deque. ĐPT O(1).
  • push_front : thêm phần tử vào đầu deque. ĐPT O(1).
  • pop_back : loại bỏ phần tử ở cuối deque. ĐPT O(1).
  • pop_front : loại bỏ phần tử ở đầu deque. ĐPT O(1).
  • insert (iterator,x): chèn “x” vào trước vị trí “iterator” ( x có thể là phần tử hay iterator của 1 đoạn phần tử…). ĐPT O(n).
  • erase : xóa phần tử ở vị trí iterator. ĐPT O(n).
  • swap : đổi 2 deque cho nhau (ví dụ: first.swap(second);). ĐPT O(n). clear: xóa vector. ĐPT O(1).

C11PAIRS – spoj

Đề bài

Thuật toán

-Đầu tiên ta khởi tạo một stack để lưu chiều cao của các bạn theo thứ tự không tăng (s[i]<=s[i-1])

-Đầu tiên ta cho a[n] vào stack, khởi tạo ds=0,sn=1(sn là số phần tử trong ngăn xếp);

-Duyệt i từ n-1 về 1, với mỗi i:

+Tìm vị trí cuối cùng trong stacks mà s[i]>a[i], giả sử ta gọi là vt.

+Nếu vt=0 nghĩa là người đứng ở vị trí i có thể nhìn thấy mọi người trong stack vì vậy ds+=sn;

+Nếu vt!=0 nghĩa là người đứng ở vị trí i có thể nhìn thấy từ người thứ vt đến người thứ sn trong stack vì vậy ds+=(sn-vt+1);

+Tiếp theo ta sẽ bỏ các s[i]<a[i] trong stack sau đó thêm a[i] vào stack.

-Kết quả của bài này chính là ds.

-Từ đó ta thu được thuật toán với đpt O(n*log(n)), mặc dù có thể giảm đpt xuống còn O(n) nhưng mình thấy thuật toán này khá đơn giản và dễ code, có thể là ngắn hơn. Đây là code của mình:

Code

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 1E6+3;
const int oo = 1e9+3;
 
int n, i, j, a[MAXN], c[MAXN], s[MAXN], top, tmp;
ll ans;
 
int main() {
        ios_base::sync_with_stdio(0); cin.tie(0);
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif //yeulaptrinh.pw
    cin >> n;
    FOR(i,1,n) cin >> a[i];
 
    top = 0;
    FOR(i,1,n) {
        tmp = 1;
        while (top&&s[top]<=a[i]) {
            ans += c[top];
            if (s[top]==a[i]) tmp += c[top];
            c[top] = 0; top--;
        }
        if (top) ans++;
        // push
        top++;
        s[top] = a[i];
        c[top] = tmp;
    }
    cout << ans;
	return 0;
}

NKINV – spoj

Đề bài

Thuật toán

  • Interval Tree

Code

uses    math;
const   fi='';
        fo='';
        maxn = 60000+3;
var     t       :array[1..maxn*4] of longint;
        i,j,n   :longint;
        a       :ARRAY[1..maxn] of longint;
        ma      :longint;
        res     :int64;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);for i:=1 to n do read(a[i]);
        close(input);
end;
procedure update(k,l,r,i:longint);
var     m :longint;
begin
        if (i<l) or (i>r) then exit;
        if l=r then
                begin
                        inc(t[k]);
                        exit;
                end;
        m := (l+r) div 2;
        update(k*2,l,m,i);
        update(k*2+1,m+1,r,i);
        t[k] := t[k*2] + t[k*2+1];
end;
function get(k,l,r,i,j:longint):longint;
var     m,tam1,tam2     :longint;
begin
        if i>j then exit(0);
        if (i>r) or (j<l) then exit(0);
        if (i<=l) and (j>=r) then
                begin
                        exit(t[k]);
                end;
        m := (l+r) div 2;
        tam1 := get(k*2,l,m,i,j);
        tam2 := get(k*2+1,m+1,r,i,j);
        get:= tam1+tam2;
end;
procedure process;
var     i :longint;
begin
        for i:=1 to n do ma := max(ma,a[i]);
        res := 0;
        for i:=1 to n do
                begin
                        res := res + get(1,1,ma,a[i]+1,ma);
                        update(1,1,ma,a[i]);
                end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

COMNET – spoj

Đề bài:

Tóm tắt đề:

Cho M đường truyền có các chi phí wi, các truy vấn người ta thay đổi trọng số một số cạnh và hỏi xem cạnh thứ k có thể loại bỏ vì nó không thuộc vào cây khung nhỏ nhất của đồ thị hay không.

Thuật toán:

-Sau khi thay đổi trọng số các cạnh theo đề bài (nếu các cạnh có trọng số bằng nhau thì ưu tiên xét cạnh k đứng đầu), tìm cây khung nhỏ nhất của đồ thị và in ra ‘YES’ hay ‘NO’ tương ứng là cây trả lời. ĐPT O(test*nlogn)
-Thuật toán trên sẽ giúp bạn có được 60->70 điểm, đề ăn full bạn cần thay đổi một chút trước khi tìm cây khung: Vẫn thay đổi trọng số các cạnh theo đề bài, nhưng không sort lại các cạnh mà tìm các cạnh có trọng số nhỏ hơn trọng số của cạnh thứ k, hợp nhất các gốc lại.

Kiểm tra xem hai đỉnh của cạnh thứ k đã thuộc vào cây khung hay chưa rồi in ra ‘YES’ hay ‘NO’ tương ứng. ĐPT O(test*n).

Code:

#include <iostream>
#include <vector>
using namespace std;
 
#define LL long long
 
struct universe {
    vector<int> cha, rank;
    universe(int n): cha(n + 1), rank(n + 1, 0) {
        for (int i=1; i<=n; i++) cha[i] = i;
    }
    int find(int u) {
        if (cha[u] != u) cha[u] = find(cha[u]);
        return cha[u];
    }
    bool join(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return false;
        if (rank[u] == rank[v]) rank[u]++;
        if (rank[u] > rank[v]) cha[v] = u;
        else cha[u] = v;
        return true;
    }
};
 
struct pack { int u, v; };
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n, m, Q; cin >> n >> m >> Q;
        vector<pack> e(m);
        vector<int> w(m);
        for (int i=0; i<m; i++) cin >> e[i].u >> e[i].v >> w[i];
        while (Q--) {
            int id; cin >> id; id--;
            int s; cin >> s;
            vector<int> ww(w);
            while (s--) {
                int t, w; cin >> t >> w;
                ww[t-1] = w;
            }
            universe a(n);
            for (int i=0; i<m; i++) if (ww[i] < ww[id]) {
                a.join(e[i].u, e[i].v);
            }
            if (a.join(e[id].u, e[id].v)) cout << "NO\n";
            else cout << "YES\n";
        }
    }
    return 0;
}