Trong bài viết này, chúng ta sẽ khám phá cách xử lý và tối ưu mã nguồn cho một số bài toán lập trình phổ biến. Mỗi phần của bài viết sẽ tập trung vào một bài toán cụ thể, giải thích chi tiết cách tiếp cận và cung cấp mã nguồn đã được tái cấu trúc để dễ hiểu hơn.

Cấu trúc dữ liệu và thuật toán cho bài toán A

Để giải quyết vấn đề truyền thông tin qua chuỗi nhị phân, chúng ta cần xây dựng một phương pháp hiệu quả sử dụng tổ hợp để biểu diễn thông tin:

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

int main() {
    int n = 10, p = 4;
    vector<vector<long long>> C(n + 1, vector<long long>(n + 1, 0));
    for (int i = 0; i <= n; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j)
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }

    // Xây dựng đoạn mã
    int k = 10;
    vector<int> data(k);
    for (int i = 0; i < k; ++i) cin >> data[i];

    // Tính toán vị trí của các giá trị trong đoạn mã
    vector<int> positions;
    for (int i = 0; i < k; ++i) {
        if (data[i] == 1) positions.push_back(i);
    }

    // Truyền thông tin dựa trên vị trí
    vector<int> encoded;
    for (int i = 0; i < positions.size(); ++i) {
        encoded.push_back(positions[i]);
    }

    // Kết quả
    for (auto val : encoded) cout << val << " ";
    return 0;
}

Bài toán B: Sắp xếp và tối ưu hóa chuỗi ký tự

Với bài toán sắp xếp chuỗi ký tự theo thứ tự tăng dần hoặc giảm dần, chúng ta có thể áp dụng thuật toán sau:

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

struct BIT {
    int tree[500005];
    void update(int idx, int delta) {
        while (idx <= 500000) {
            tree[idx] += delta;
            idx += idx & (-idx);
        }
    }
    int query(int idx) {
        int res = 0;
        while (idx > 0) {
            res += tree[idx];
            idx -= idx & (-idx);
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        b[i] = (a[i] < 0) ^ (i % 2);
    }

    BIT bit;
    long long dp[2][2] = {0};
    for (int i = 0; i < n; ++i) {
        bit.update(a[i] + 250000, 1);
    }

    memset(dp, 63, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 0; i < n; ++i) {
        // Chuyển trạng thái
    }

    cout << *min_element(dp[0], dp[0] + 2) << "\n";
    return 0;
}

Bài toán C: Tìm kiếm đường đi trong đồ thị

Để tìm kiếm đường đi hiệu quả trong một đồ thị, chúng ta có thể sử dụng thuật toán DFS kết hợp với quản lý độ sâu:

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

vector<vector<int>> adj(105);
int depth[105], color[105], root, par;

void dfs(int u) {
    bool ok = (depth[u] == 2);
    for (auto v : adj[u]) {
        if (!depth[v]) {
            depth[v] = depth[u] + 1;
            color[v] = (depth[u] > 1) ? color[u] : v;
            dfs(v);
            if (ok) {
                for (auto w : adj[v]) ok &= (depth[w] > 1);
            }
        }
    }
    if (ok) par = u;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Tìm gốc và thực hiện DFS
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    for (int _ = 0; _ < 1000; ++_) {
        for (int i = 1; i <= n; ++i) {
            shuffle(adj[i].begin(), adj[i].end(), rng);
            depth[i] = color[i] = 0;
        }
        root = uniform_int_distribution<int>(1, n)(rng);
        depth[root] = 1;
        dfs(root);
        if (par) break;
    }

    cout << "600\n";
    for (int t = 0; t < 600; ++t) {
        for (int i = 1; i <= n; ++i) {
            cout << ((t % 2) ? (depth[i] + 1) / 2 : depth[i] / 2 + (color[i] == par ? 0 : 1)) << "\n"[i == n];
        }
    }
    return 0;
}