B. Dãy số XOR từng bit

Đề bài yêu cầu tìm một dãy số nguyên sao cho mỗi cặp chỉ số (u, v) thỏa mãn điều kiện a[u] ⊕ a[v] = w. Ta có thể mô hình hóa bài toán dưới dạng đồ thị: mỗi số là một đỉnh, mỗi ràng buộc là một cạnh với trọng số tương ứng.

Khi xây dựng đồ thị, cần kiểm tra hai trường hợp đặc biệt: tồn tại cạnh trùng lặp hoặc chu trình. Với cạnh trùng lặp, hai trọng số phải bằng nhau; với chu trình, tổng XOR theo đường đi phải bằng 0.

Sử dụng DFS để duyệt từng thành phần liên thông, duy trì giá trị XOR tiền tố tại mỗi đỉnh. Sau đó, với mỗi thành phần, xét từng bit từ 0 đến 29, chọn đặt bit 0 hay 1 sao cho số lượng bit 1 là ít nhất.

const int N = 1e5 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, m;
vector<pair<int, int>> edges[N];
bool visited[N];
ll prefix_xor[N];
vector<int> component[N];

void dfs(int u, int root) {
    visited[root] = true;
    for (auto &[v, w] : edges[root]) {
        if (visited[v]) {
            if ((prefix_xor[root] ^ w) != prefix_xor[v]) {
                cout << -1 << '\n';
                exit(0);
            }
        } else {
            prefix_xor[v] = prefix_xor[root] ^ w;
            component[u].push_back(v);
            dfs(u, v);
        }
    }
}

ll calculate_min_cost(int root) {
    int total = component[root].size();
    ll result = 0;
    for (int bit = 0; bit < 30; ++bit) {
        int ones = 0;
        for (int node : component[root]) {
            if (prefix_xor[node] >> bit & 1) ++ones;
        }
        if (ones > total - ones) {
            result |= (1LL << bit);
        }
    }
    for (int node : component[root]) {
        result += prefix_xor[node] ^ result;
    }
    return result;
}

void solve() {
    cin >> n >> m;
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[u].emplace_back(v, w);
        edges[v].emplace_back(u, w);
    }

    ll total_cost = 0;
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            dfs(i, i);
            total_cost += calculate_min_cost(i);
        }
    }
    cout << total_cost << '\n';
}

E. Edward Gaming, nhà vô địch

Yêu cầu đếm số lần xuất hiện của xâu con "edgnb" trong xâu đầu vào.

Thực hiện duyệt qua từng vị trí và so sánh xâu con độ dài 5.

void solve() {
    string text;
    cin >> text;
    int count = 0;
    for (int i = 0; i + 5 <= text.size(); ++i) {
        if (text.substr(i, 5) == "edgnb") {
            ++count;
        }
    }
    cout << count << '\n';
}

F. Chuỗi đã mã hóa I

Xét từ cuối về đầu. Khi gặp một ký tự chưa xuất hiện trước đó, ta gán nó một nhãn mới theo thứ tự tăng dần. Nếu đã xuất hiện, dùng nhãn đã gán trước đó.

Tại mỗi vị trí bắt đầu, xây dựng chuỗi thay thế và chọn ra chuỗi có thứ tự từ điển lớn nhất.

void solve() {
    int n;
    string s;
    cin >> n >> s;
    string best = "";

    for (int i = 0; i < n; ++i) {
        vector<int> last_occurrence(26, -1);
        string current = "";
        int next_label = 0;

        for (int j = i; j >= 0; --j) {
            int c = s[j] - 'a';
            if (last_occurrence[c] == -1) {
                last_occurrence[c] = next_label++;
                current = char('a' + last_occurrence[c]) + current;
            } else {
                current = char('a' + last_occurrence[c]) + current;
            }
        }

        if (current > best) {
            best = current;
        }
    }

    cout << best << '\n';
}

J. Khóa hành lý

Một khóa gồm 4 chữ số, mỗi thao tác có thể tăng hoặc giảm một đoạn liên tiếp các chữ số từ 0 đến 9 (mod 10). Mục tiêu là chuyển từ trạng thái ban đầu a sang trạng thái cuối b.

Do thao tác độc lập với giá trị ban đầu, ta có thể quy về việc chuyển từ "0000" sang hiệu số t = b - a (theo từng chữ số).

Dùng BFS tiền xử lý tất cả các trạng thái khả thi từ "0000", lưu lại khoảng cách ngắn nhất tới mỗi trạng thái. Sau đó trả lời truy vấn trong O(1).

map<string, int> dist;

void precompute() {
    queue<string> q;
    q.push("0000");
    dist["0000"] = 0;

    while (!q.empty()) {
        string curr = q.front(); q.pop();
        int d = dist[curr];

        for (int i = 0; i < 4; ++i) {
            for (int j = i; j < 4; ++j) {
                string up = curr, down = curr;
                for (int k = i; k <= j; ++k) {
                    up[k] = (up[k] - '0' + 1) % 10 + '0';
                    down[k] = (down[k] - '0' + 9) % 10 + '0';
                }
                if (!dist.count(up)) {
                    dist[up] = d + 1;
                    q.push(up);
                }
                if (!dist.count(down)) {
                    dist[down] = d + 1;
                    q.push(down);
                }
            }
        }
    }
}

void solve() {
    string start, end;
    cin >> start >> end;
    string target = "";
    for (int i = 0; i < 4; ++i) {
        target += char((10 + (end[i] - start[i])) % 10 + '0');
    }
    cout << dist[target] << '\n';
}