Bài A: Đếm số phần tử có thể chèn giữa hai số

Nếu hai số A và B khác nhau, kiểm tra xem hiệu của chúng có chẵn hay không. Nếu chẵn, có thể chèn một số ở giữa → tổng cộng 3 số. Nếu lẻ, chỉ có thể giữ nguyên hai đầu mút → 2 số. Trường hợp A == B, chỉ có duy nhất một giá trị.

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

int main() {
    int x, y;
    cin >> x >> y;
    int diff = abs(y - x);
    if (diff == 0) {
        cout << 1;
    } else if (diff % 2 == 0) {
        cout << 3;
    } else {
        cout << 2;
    }
    return 0;
}

Bài B: Mô phỏng di chuyển tay trái/phải

Theo dõi vị trí hiện tại của tay trái và tay phải. Với mỗi thao tác, cộng dồn khoảng cách di chuyển từ vị trí trước đó đến vị trí mới, sau đó cập nhật lại vị trí tay tương ứng.

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

int main() {
    int cnt;
    cin >> cnt;
    vector<pair<int, char>> moves(cnt);
    for (auto& [pos, hand] : moves) {
        cin >> pos >> hand;
    }

    long long total = 0;
    int leftPos = -1, rightPos = -1;

    for (auto [target, whichHand] : moves) {
        if (whichHand == 'L') {
            if (leftPos != -1) total += abs(target - leftPos);
            leftPos = target;
        } else {
            if (rightPos != -1) total += abs(target - rightPos);
            rightPos = target;
        }
    }

    cout << total;
    return 0;
}

Bài C: Đếm số dãy con cấp số cộng

Tính mảng hiệu số, sau đó tìm các đoạn liên tiếp có cùng giá trị hiệu. Mỗi đoạn dài k sẽ tạo ra C(k+1, 2) dãy con cấp số cộng (chọn hai điểm đầu-cuối). Cộng thêm n vì mỗi phần tử đơn lẻ cũng là một dãy.

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

ll comb(ll x) { return x * (x - 1) / 2; }

int main() {
    int len;
    cin >> len;
    vector<ll> arr(len + 1), diff(len + 2);
    for (int i = 1; i <= len; ++i) {
        cin >> arr[i];
        diff[i] = arr[i] - arr[i - 1];
    }
    diff[len + 1] = diff[len] + 1; // sentinel

    ll result = len;
    ll runLen = 1;
    ll currentDiff = diff[1];

    for (int i = 2; i <= len + 1; ++i) {
        if (diff[i] != currentDiff) {
            result += comb(runLen);
            runLen = 1;
            currentDiff = diff[i];
        } else {
            runLen++;
        }
    }

    cout << result;
    return 0;
}

Bài D: Quy hoạch động theo tính chẵn lẻ

Định nghĩa dp[i][take][parity]: giá trị kinh nghiệm lớn nhất khi xét đến quái thứ i, chọn hoặc không chọn (take=1/0), và hiện tại đang ở vị trí chẵn/lẻ (parity=0/1). Chuyển trạng thái dựa trên việc giữ nguyên hay đổi parity.

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

int main() {
    int monsters;
    cin >> monsters;
    vector<ll> exp(monsters + 1);
    for (int i = 1; i <= monsters; ++i) cin >> exp[i];

    vector dp(monsters + 1, vector(2, vector<ll>(2, LLONG_MIN)));
    dp[0][0][1] = dp[0][1][1] = LLONG_MIN;

    auto getMax = [&](int idx, int par) {
        return max(dp[idx][0][par], dp[idx][1][par]);
    };

    for (int i = 1; i <= monsters; ++i) {
        // Không đánh
        dp[i][0][0] = getMax(i - 1, 0);
        dp[i][0][1] = getMax(i - 1, 1);
        // Đánh
        dp[i][1][0] = getMax(i - 1, 1) + 2 * exp[i];
        dp[i][1][1] = getMax(i - 1, 0) + exp[i];
    }

    cout << max(getMax(monsters, 0), getMax(monsters, 1));
    return 0;
}

Bài E: Tìm đường đi tối ưu qua các cạnh bắt buộc

Dùng Floyd-Warshall để tính toán khoảng cách ngắn nhất giữa mọi cặp đỉnh. Sau đó, duyệt hoán vị các cạnh cần đi qua (theo cả hai hướng), cộng dồn chi phí di chuyển giữa các đoạn. Kết quả là tổng nhỏ nhất từ đỉnh 1 đến n qua tất cả các cạnh yêu cầu.

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

const ll INF = 1e18;

void solveQuery(int edgeCount, vector<int>& edges, vector<vector<ll>>& dist, int n) {
    ll minCost = INF;
    vector<bool> used(edgeCount, false);
    ll currentSum = 0;

    function<void(int, int)> backtrack = [&](int depth, int lastNode) {
        if (depth > edgeCount) {
            minCost = min(minCost, currentSum + dist[lastNode][n]);
            return;
        }
        for (int i = 0; i < edgeCount; ++i) {
            if (used[i]) continue;
            int u = edges[i] * 2 - 1, v = edges[i] * 2, w = /* weight */;
            // Giả sử đã lưu trữ trọng số trong cấu trúc riêng
            used[i] = true;
            currentSum += dist[lastNode][u] + w;
            backtrack(depth + 1, v);
            currentSum -= dist[lastNode][u] + w;
            currentSum += dist[lastNode][v] + w;
            backtrack(depth + 1, u);
            currentSum -= dist[lastNode][v] + w;
            used[i] = false;
        }
    };

    backtrack(1, 1);
    cout << minCost << '\n';
}

int main() {
    int nodes, edges;
    cin >> nodes >> edges;
    vector<vector<ll>> graph(nodes + 1, vector<ll>(nodes + 1, INF));
    for (int i = 1; i <= nodes; ++i) graph[i][i] = 0;

    for (int i = 0; i < edges; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u][v] = min(graph[u][v], (ll)w);
        graph[v][u] = graph[u][v];
    }

    // Floyd-Warshall
    for (int k = 1; k <= nodes; ++k)
        for (int i = 1; i <= nodes; ++i)
            for (int j = 1; j <= nodes; ++j)
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);

    int queries;
    cin >> queries;
    while (queries--) {
        int k;
        cin >> k;
        vector<int> requiredEdges(k);
        for (int& e : requiredEdges) cin >> e;
        solveQuery(k, requiredEdges, graph, nodes);
    }

    return 0;
}