Nhớ

Chỉ có một người nuôi nấng, chăm lo cho ta suốt cuộc đời
Chỉ có một người thương yêu, lo lắng cho ta suốt cuộc đời
Chỉ có một một tình yêu vô điều kiện, mà ta ít khi nhận ra
... Và chỉ có một nỗi buồn, nỗi nhớ luôn theo ta suốt cuộc đời này.

Video 1. Mẹ

Video 2. Nhật ký của Mẹ

Mở file trong Code::Blocks

Thay đổi chương trình dùng để mở file trong Code::Blocks

Khi bạn dùng Code::Blocks mở một file có đuôi không phải là *.c, *.cpp thì Code::Block yêu cầu chọn:
- Select an external program to open it
- Open it with the associated application
- Open it inside the Code::Blocks editor

Nếu chúng ta chọn "Select an external program to open it" thì lần sau dùng Code::Blocks để mở file có đuôi đó thì Code::Blocks sẽ dùng chương trình "external" trước đó để mở file.

Nếu muốn mở file đó trong Code::Blocks ta dùng cách sau:
- Chọn Settings menu, Enviroment

- Chọn Files extension handling, Chọn đuôi trong Registered wildcards, Chọn "Open it in a Code::Blocks"

Đường đi ngắn nhất. Thuật toán Dijkstra's với priority_queue hay set trong

Thuật toán Dijkstra 

Độ phức tạp: O(E.logV)

#include <bits/stdc++.h>
using namespace std;

const int INT_MAX = 1e9;
typedef pair<int, int> pii;

// input
vector<vector<pii> > adj;

// output
vector<int> dist, pre;
Thuật toán Dijkstra với priority_queue

void Dijkstra(int s) {
  // Khoi tao
  int n = adj.size();
  dist.assign(n, INT_MAX);
  dist[s] = 0;
  pre.assign(n, -1);

  priority_queue<pii, vector<pii> , greater<pii> > q;
  q.push(make_pair(0, s));

  // Lap
  while (!q.empty()) {
    int d = q.top().first;
    int u = q.top().second;
    q.pop();

    if (d != dist[u]) continue;

    for (int i=0; i<(int) adj[u].size(); i++) {
      int v = adj[u][i].first;
      int uv = adj[u][i].second;
      

      if (dist[v] > d+uv) {
        dist[v] = d+uv;
        pre[v] = u;
        q.push(make_pair(dist[v], v));      
      }
    }
  }
}



Thuật toán Dijkstra với set

void Dijkstra2(int s) {
  // Khoi tao  
  int n = adj.size();  
  dist.assign(n, INT_MAX);  
  dist[s] = 0;  
  pre.assign(n, -1);  

  set<pii> q;  
  q.insert(make_pair(0, s));  

  // Lap  
  while (!q.empty()) {    
    int u = q.begin()->second;

    q.erase(q.begin()); 
   
    for (int i=0; i<(int) adj[u].size(); i++) {      
      int v = adj[u][i].first;      
      int uv = adj[u][i].second;     

      if (dist[v] > dist[u]+uv) {        
        q.erase(make_pair(dist[v], v));        
        dist[v] = ndist[u]+uv;        
        pre[v] = u;        
        q.insert(make_pair(dist[v], v));      
      }    
    }
  }
}


int main() {
  adj.resize(2);
  adj[0].push_back(make_pair(1, 10));
  adj[1].push_back(make_pair(2, -5));
  adj[0].push_back(make_pair(2, 8));

  Dijkstra(0);

  for (int i = 0; i < dist.size(); i++)  cout << dist[i] << endl;
}

CTDL Disjoint-set với rank heuristic

CẤU TRÚC DỮ LIỆU DISJOIN - SET

Ý nghĩa: cấu trúc dữ liệu Disjoin - set dùng để biểu diễn các tập hợp, mỗi tập hợp có thể có giá trị từ 0 đến n. Disjoin - set cho phép thực hiện nhanh các thao tác như: 
(1) Hợp 2 tập hợp thành một tập hợp
(2) Kiểm tra 2 phần tử có thuộc tập hợp không

Cấu trúc dữ liệu:

• Các phần tử: có giá trị từ 0, 1, 2, ..., n
• Các phần tử này thuộc tập hợp nào đó, nên ta quản lý tập hợp phần tử i thuộc là parent[i]. Như vậy một tập hợp là một cái cây, và gốc của cây là giá trị đại diện cho tập hợp

Như vậy, cấu disjoin set chỉ đơn giảng là một mảng parent[] của các phần tử i cho biết cha của phần tử i là ai.


Chương trình:
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200000;

// Cấu trúc dữ liệu
int parent[maxn];
int n;

int rank[maxn];


void Init(int num) {
  n = num;
  fill(rank, rank + n, 0);
  for (int i = 0; i < n; i++) parent[i] = i;
}


int Root(int x) {
  return (x == parent[x]) ? x : (parent[x] = Root(parent[x]));
}


void UnionSet(int a, int b) {
  a = Root(a);
  b = Root(b);
  if (a == b) return;
  if (rank[a] < rank[b]) swap(a, b);
  if (rank[a] == rank[b]) ++rank[a];
  parent[b] = a;
}

bool IsSameSet(int a, int b) {
  a = Root(a);
  b = Root(b);

  return a==b;
}

int main() {
  Init(3);
  UnionSet(0, 2);
  cout << (0 == Root(0)) << '\n';
  cout << (1 == Root(1)) << '\n';
  cout << (0 == Root(2)) << '\n';
}

Fenwick tree

Fenwick tree

Bài toán
Cho dãy số a=(a(1), a(2), ..., a(n)) và nhiều phép truy vấn Sum(l, r) dùng tính tổng dãy con a(l) + a(l+1) + ... + a(r) và truy vấn Update(i, x) để tăng giá trị a(i) lên x giá trị.

Giải pháp Fenwick tree
Giới thiệu:

1. Fenwick tree hay Binary Indexed Tree (BIT) là phương pháp tiền xử lý giúp tính tổng Sum(l, r) và cập nhật Update(i, x) trên dãy số a trong thời gian O(log n). 
2. Lịch sử: Phương pháp Fenwick tree do Pete Fenwickin đề xuất vào năm 1994.
3. Độ phức tạp: Độ phức tạp của phép toán tính tổng dãy con và cập nhật các phần tử của mảng là O(log n)

Ý tưởng Fenwick tree:
Fenwick tree là mảng T[1...n], trong T[i] = tổng các phần tử dãy a thuộc đoạn [(i-2^k)+1, i], trong đó k là vị trí bit 1 nằm bên phải nhất của số nhị phân của biến i.

Bây giờ, chúng ta sẽ trình bày toàn bộ code của Fenwick tree:

void Update(int i, int x) {
    while (i<n) {
        T[i] += x;
        i |= (i + 1);
    }
}

int Sum(int n) {
    int res = 0;
    while (n>= 0) {
        res += data[n];
        n= (n& (n+1)) - 1;
    }
    return res;
}

Ở đây, Sum(i) trả về tổng của các phần tự từ phần tử đầu tiên đến phần tử thứ i. Việc tìm tổng của một đoạn bất kỳ có thể thực hiện bằng truy vấn Sum(right)-Sum(left-1). 

Fenwick tree chuẩn chỉ hỗ trợ cập nhật 1 phần tử tại một thời điểm. Tuy nhiên, chúng ta có thể mở rộng cho việc cập nhật cả một đoạn - câu lệnh cập nhật sẽ phát biểu thành "tăng mỗi giá trị giữa left và right một lượng giá trị". Chúng ta có thể chỉnh sửa cây cho cập nhật như thế trong thời gian O(log n):

void Update(int left, int right, int by) {
    internalUpdate(left, by, -by * (left - 1));
    internalUpdate(right, -by, by * right);
}

void InternalUpdate(int i, int mul, int add) {
    while (i<n) {
        dataMul[i] += mul;
        dataAdd[i] += add;
        i|=(i+ 1);
    }
}

int Query(int i) {
    int mul = 0;
    int add = 0;
    int start = i;
    while (i>= 0) {
        mul += dataMul[i];
        add += dataAdd[i];
        i= (i& (i+ 1)) - 1;
    }
    return mul * start + add;
}