Bội tăng và LCA

Bội tăng

Bội tăng là một kỹ thuật trong lập trình giúp tối ưu hóa các bài toán có không gian trạng thái lớn. Thay vì thực hiện phép lặp tuyến tính, ta sử dụng cách tiếp cận theo cấp số nhân để giảm độ phức tạp của thuật toán.

Với bội tăng, chúng ta chỉ cần lưu trữ giá trị đại diện cho các vị trí ở lũy thừa của 2 trong không gian trạng thái. Khi cần tìm giá trị tại một vị trí bất kỳ, ta có thể sử dụng đặc tính phân rã của các số nguyên thành tổng các lũy thừa của 2 để ghép các giá trị đã tính trước đó.

Ví dụ: Tìm đoạn dài nhất thỏa mãn điều kiện

Để minh họa, ta xét bài toán sau:

Yêu cầu: Cho dãy số và một ngưỡng T. Phân chia dãy thành nhiều đoạn sao cho hiệu giữa phần tử lớn nhất và nhỏ nhất trong mỗi đoạn không vượt quá T. Hãy tìm số đoạn ít nhất.

Phương pháp bội tăng:

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

const int N = 1e5 + 5;
int n, t;
int a[N], b[N], c[N];

bool check(int l, int r) {
    if (r > n) return false;
    vector<int> temp(a + l, a + r + 1);
    sort(temp.begin(), temp.end());
    int mx = temp.back(), mn = temp.front();
    return (mx - mn) <= t;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> t;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    int cnt = 0, l = 1, r = 1, p = 1;
    while (l <= n) {
        if (!p) {
            cnt++;
            l = r + 1;
            r = l;
            p = 1;
        }
        if (check(l, r + (1 << p) - 1)) {
            r += (1 << p) - 1;
            p++;
        } else {
            p--;
        }
    }
    cout << cnt;
    return 0;
}

LCA (Least Common Ancestor)

LCA là thuật toán dùng để tìm tổ tiên chung gần nhất của hai nút trong cây. Dưới đây là một số bài tập liên quan đến LCA.

Bài 1: P4281 [AHOI2008] Khẩn cấp

Mô tả: Cho ba nút A, B, C trên cây. Tìm một nút U sao cho tổng khoảng cách từ A, B, C đến U là nhỏ nhất.

Giải pháp: Sử dụng phương pháp LCA để tìm tổ tiên chung gần nhất giữa các cặp nút. Sau đó, chọn tổ tiên nào có tổng khoảng cách nhỏ nhất.

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

const int N = 1e5 + 5;
int depth[N], ancestor[N][20];
vector<int> adj[N];

void dfs(int u, int par) {
    ancestor[u][0] = par;
    for (int j = 1; j < 20; j++) {
        if (ancestor[u][j - 1] != -1)
            ancestor[u][j] = ancestor[ancestor[u][j - 1]][j - 1];
        else
            ancestor[u][j] = -1;
    }
    for (auto v : adj[u]) {
        if (v != par) {
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int j = 19; j >= 0; j--) {
        if (ancestor[u][j] != -1 && depth[ancestor[u][j]] >= depth[v])
            u = ancestor[u][j];
    }
    if (u == v) return u;
    for (int j = 19; j >= 0; j--) {
        if (ancestor[u][j] != -1 && ancestor[u][j] != ancestor[v][j]) {
            u = ancestor[u][j];
            v = ancestor[v][j];
        }
    }
    return ancestor[u][0];
}

int get_distance(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    memset(ancestor, -1, sizeof(ancestor));
    dfs(1, -1);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        int p1 = lca(a, b), p2 = lca(b, c), p3 = lca(c, a);
        int d1 = get_distance(a, p1) + get_distance(b, p1) + get_distance(c, p1);
        int d2 = get_distance(a, p2) + get_distance(b, p2) + get_distance(c, p2);
        int d3 = get_distance(a, p3) + get_distance(b, p3) + get_distance(c, p3);
        if (d1 <= d2 && d1 <= d3) cout << p1 << " " << d1 << "\n";
        else if (d2 <= d1 && d2 <= d3) cout << p2 << " " << d2 << "\n";
        else cout << p3 << " " << d3 << "\n";
    }
    return 0;
}

Bài 2: P3533 [POI2012] RAN

Mô tả: Cho đồ thị có hướng với các ràng buộc về khoảng cách giữa các đỉnh. Hãy xác định cặp số thỏa mãn mọi ràng buộc.

Giải pháp: Sử dụng LCA kết hợp với kiểm tra chu trình và tính toán khoảng cách.

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

struct Pair {
    int x, y;
    bool operator<(const Pair &other) const {
        if (max(x, y) != max(other.x, other.y)) return max(x, y) < max(other.x, other.y);
        return min(x, y) < min(other.x, other.y);
    }
};

Pair cmp(Pair a, Pair b) {
    if (a < b) return a;
    return b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // Code implementation...
    return 0;
}