B - Dãy Phép XOR Bitwise
=================================
Mô tả bài toán:
Cho một dãy gồm n số nguyên và m mối quan hệ, mỗi mối quan hệ được biểu diễn dưới dạng a_u ⊕ a_v = w, nghĩa là phép XOR giữa số thứ u và số thứ v bằng w. Hãy xác định xem có thể tìm được dãy n số thỏa mãn tất cả các mối quan hệ này hay không. Nếu không tồn tại, hãy in ra -1; ngược lại, hãy in ra tổng nhỏ nhất của tất cả các số trong các dãy thỏa mãn.
Lời giải:
Đầu tiên, xây dựng đồ thị dựa trên các mối quan hệ, sau đó xử lý từng thành phần liên thông riêng biệt. Chọn một đỉnh làm gốc và gán giá trị 0 cho nó (để đảm bảo tổng nhỏ nhất). Trong quá trình duyệt, nếu phát hiện bất kỳ mâu thuẫn nào thì in ra -1. Ngược lại, đếm số lần xuất hiện của các bit từ thấp đến cao, sau đó tính tổng nhỏ nhất.
Mã nguồn:

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

const int MAXN = 1e6 + 5;

int n, m, id;
int des[MAXN], next[MAXN], head[MAXN], val[MAXN], mark[MAXN], root[MAXN], size[MAXN];

void connect(int u, int v, int w) {
    des[++id] = v;
    val[id] = w;
    next[id] = head[u];
    head[u] = id;
}

void initialize() {
    fill(mark, mark + n, -1);
    fill(size, size + n, 1);
    iota(root, root + n, 0);
}

int locate(int x) {
    return (x == root[x] ? x : root[x] = locate(root[x]));
}

void merge(int u, int v) {
    int ru = locate(u);
    int rv = locate(v);
    if (ru != rv) {
        root[ru] = rv;
        size[rv] += size[ru];
    }
}

void resolve() {
    cin >> n >> m;
    initialize();
    if (!m) {
        cout << 0 << endl;
        return;
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        connect(u, v, w);
        connect(v, u, w);
        merge(u, v);
    }
    ll result = 0;
    for (int i = 0; i < n; i++) {
        if (locate(i) != i)
            continue;
        vector<int> count(30);
        queue<int> q;
        q.push(i);
        mark[i] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int j = head[u]; j; j = next[j]) {
                int v = des[j];
                if (mark[v] == -1) {
                    mark[v] = (mark[u] ^ val[j]);
                    q.push(v);
                    for (int k = 0; k < 30; k++)
                        count[k] += ((mark[v] >> k) & 1);
                } else {
                    if ((mark[u] ^ mark[v]) != val[j]) {
                        cout << -1 << endl;
                        return;
                    }
                }
            }
        }
        for (int j = 0; j < 30; j++)
            result += (1LL << j) * min(count[j], size[i] - count[j]);
    }
    cout << result << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    resolve();
    return 0;
}

E - Edward Gaming, Người Chiến Binh
=================================
Mô tả bài toán:
Cho một chuỗi ký tự, hãy đếm số lần xuất hiện của chuỗi con "edgnb".
Lời giải:
Duyệt qua chuỗi và kiểm tra từng nhóm 5 ký tự liên tiếp có khớp với "edgnb" hay không.
Mã nguồn:

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

void handle() {
    string str;
    cin >> str;
    if (str.size() < 5) {
        cout << 0 << endl;
        return;
    }
    int answer = 0;
    for (int i = 0; i <= str.size() - 5; i++) {
        if (str.substr(i, 5) == "edgnb")
            answer++;
    }
    cout << answer << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    handle();
    return 0;
}

F - Chuỗi Mã Hóa I
=====================
Mô tả bài toán:
Cho một chuỗi s độ dài n (n ≤ 1000), định nghĩa hàm Fs:Fs(c) = chr(G(c, s)), tức là biến đổi mỗi ký tự c trong chuỗi s thành chr(G(c, s)), trong đó G(c, s) là số lượng ký tự khác nhau trong hậu tố của s bắt đầu từ vị trí sau lần cuối cùng xuất hiện của c, và chr(i) là ký tự thứ i (ký tự thứ 0 là a, ký tự thứ 1 là b, ...). Yêu cầu áp dụng hàm Fs lên từng tiền tố không rỗng của s, thu được n chuỗi, sau đó in ra chuỗi lớn nhất theo thứ tự từ điển.
Lời giải:
Thực hiện quy trình biến đổi như mô tả và lưu giữ các chuỗi kết quả, cuối cùng chọn chuỗi lớn nhất.
Mã nguồn:

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

const int MAXN = 1e3 + 5;

map<char, int> countMap[MAXN];

void process() {
    int len;
    string input;
    cin >> len >> input;
    for (int i = len; i >= 1; i--) {
        int distinctCount = 0;
        set<char> seen;
        for (int j = i - 1; j >= 0; j--) {
            if (seen.find(input[j]) == seen.end()) {
                seen.insert(input[j]);
                countMap[i][input[j]] = distinctCount++;
            }
        }
    }
    set<string> results;
    for (int i = len; i >= 1; i--) {
        string transformed = input.substr(0, i);
        for (int j = i - 1; j >= 0; j--)
            transformed[j] = countMap[i][transformed[j]] + 'a';
        results.insert(transformed);
    }
    cout << *results.begin() << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    process();
    return 0;
}

J - Khóa Túi Hành Lý
================
Mô tả bài toán:
Một khóa điện tử gồm 4 chữ số, mỗi lần có thể xoay một hoặc nhiều chữ số liên tiếp lên hoặc xuống một đơn vị. Cho hai khóa A và B, hãy tìm số bước tối thiểu để chuyển từ khóa A thành khóa B.
Lời giải:
Do số lượng trường hợp lớn, thực hiện BFS từ khóa "0000" để xây dựng bảng giá trị. Khi cần tính toán, chỉ cần tra cứu khoảng cách giữa "0000" và hiệu số giữa A và B.
Mã nguồn:

#include<bits/stdc++.h>
using namespace std;
typedef pair<string, int> pstring;

map<string, int> distanceMap;
set<string> visited;

string commands[] = { "1000", "0100", "0010", "0001", "1100", "0110", "0011", "1110", "0111", "1111", "2000", "0200", "0020", "0002", "2200", "0220", "0022", "2220", "0222", "2222" };

string modify(string current, int index) {
    string modified = current;
    for (int i = 0; i < 4; i++) {
        if (commands[index][i] == '1') {
            modified[i]++;
            if (modified[i] > '9')
                modified[i] = '0';
        } else if (commands[index][i] == '2') {
            modified[i]--;
            if (modified[i] < '0')
                modified[i] = '9';
        }
    }
    return modified;
}

void bfs() {
    queue<pstring> q;
    q.push({ "0000", 0 });
    visited.insert("0000");
    while (!q.empty()) {
        string current = q.front().first;
        int step = q.front().second;
        q.pop();
        for (int i = 0; i < 20; i++) {
            string next = modify(current, i);
            if (visited.find(next) == visited.end()) {
                visited.insert(next);
                distanceMap[next] = step + 1;
                q.push({ next, step + 1 });
            }
        }
    }
}

void solve() {
    string start, end;
    cin >> start >> end;
    if (start == end) {
        cout << 0 << endl;
        return;
    }
    string diff = "";
    for (int i = 0; i < 4; i++)
        diff.push_back((end[i] - start[i] + 10) % 10 + '0');
    cout << distanceMap[diff] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    bfs();
    int testCases;
    cin >> testCases;
    while (testCases--)
        solve();
    return 0;
}

H - Phép Phù Hợp Trên Đồ Thị Đường
=======================
Mô tả bài toán:
Cho một đồ thị vô hướng đơn giản và trọng số kết nối G, hãy tính tổng trọng số lớn nhất của một tập cạnh tối ưu trong đồ thị đường L(G) của G. Đồ thị đường L(G) gồm mỗi đỉnh đại diện cho một cạnh của G, và mỗi cạnh trong L(G) liên kết hai đỉnh nếu hai cạnh tương ứng trong G có chung một đỉnh. Trọng số của cạnh trong L(G) là tổng trọng số của hai cạnh tương ứng trong G. Tập cạnh tối ưu là tập cạnh mà không có hai cạnh nào chia sẻ đỉnh và tổng trọng số là lớn nhất.
Lời giải:
Xét từng thành phần liên thông của đồ thị. Nếu số cạnh là số chẵn, tất cả các cạnh đều có thể được ghép; ngược lại, cần loại bỏ một cạnh. Nếu cạnh bị loại bỏ là cạnh cầu, đảm bảo rằng cả hai thành phần liên thông còn lại đều có số cạnh là số chẵn. Có thể sử dụng thuật toán Tarjan để tìm các cạnh cầu hoặc sử dụng phương pháp tham lam, luôn chọn cạnh có trọng số lớn nhất.
Mã nguồn (Phương pháp Tarjan):

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

const int MAXN = 1e6 + 5;

int n, m, id, totalEdges, totalWeight, minEdgeWeight, componentSize;
int dest[MAXN], link[MAXN], start[MAXN], weight[MAXN], discover[MAXN], lowLink[MAXN], edgeCount[MAXN], degree[MAXN];

void addEdge(int u, int v, int w) {
    dest[++id] = v;
    weight[id] = w;
    link[id] = start[u];
    start[u] = id;
}

void tarjan(int u, int prev) {
    discover[u] = lowLink[u] = ++totalEdges;
    edgeCount[u] = degree[u];
    for (int i = start[u]; i; i = link[i]) {
        int v = dest[i];
        if (!discover[v]) {
            tarjan(v, u);
            edgeCount[u] += edgeCount[v];
            lowLink[u] = min(lowLink[u], lowLink[v]);
            if (lowLink[v] > discover[u]) { // cạnh cầu
                if ((edgeCount[v] - 1) / 2 % 2 == 0)
                    minEdgeWeight = min(minEdgeWeight, weight[i]);
            } else
                minEdgeWeight = min(minEdgeWeight, weight[i]);
        } else if (v != prev)
            lowLink[u] = min(lowLink[u], discover[v]), minEdgeWeight = min(minEdgeWeight, weight[i]);
        if (discover[u] < discover[v]) // tổng số cạnh trong thành phần liên thông
            componentSize++;
    }
}

void execute() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
        degree[u]++, degree[v]++;
        totalWeight += w;
    }
    for (int i = 1; i <= n; i++) {
        if (!discover[i]) {
            componentSize = 0;
            minEdgeWeight = LLONG_MAX;
            tarjan(i, -1);
            if (componentSize & 1) // số lẻ cần loại bỏ cạnh nhỏ nhất
                totalWeight -= minEdgeWeight;
        }
    }
    cout << totalWeight << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    execute();
    return 0;
}

Mã nguồn (Phương pháp Tham Lam):

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

const int MAXN = 1e6 + 5;

struct Edge {
    int u, v, w;
    bool operator <(const Edge& other) const {
        return w > other.w;
    }
};

int n, m, result;
vector<Edge> edges;
int parent[MAXN], lastWeight[MAXN];

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

void execute() {
    cin >> n >> m;
    iota(parent + 1, parent + 1 + n, 1);
    edges.resize(m + 1);
    for (int i = 1; i <= m; i++)
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    sort(edges.begin() + 1, edges.end());
    for (int i = 1; i <= m; i++) {
        int pu = findParent(edges[i].u);
        int pv = findParent(edges[i].v);
        if (pu == pv) {
            if (!lastWeight[pu])
                lastWeight[pu] = edges[i].w;
            else {
                result += edges[i].w + lastWeight[pu];
                lastWeight[pu] = 0;
            }
        } else {
            parent[pv] = pu;
            if (!lastWeight[pu] && !lastWeight[pv])
                lastWeight[pu] = edges[i].w;
            else if (!lastWeight[pu] || !lastWeight[pv]) {
                result += edges[i].w + lastWeight[pu] + lastWeight[pv];
                lastWeight[pu] = 0;
            } else {
                result += edges[i].w + max(lastWeight[pu], lastWeight[pv]);
                lastWeight[pu] = min(lastWeight[pu], lastWeight[pv]);
            }
        }
    }
    cout << result << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    execute();
    return 0;
}