Bài A

Đề bài: sau y tháng tính từ tháng x thì đang ở tháng mấy. Đây chỉ là một phép toán chia lấy dư đơn giản.

void solve() {
    int currentMonth, delta;
    cin >> currentMonth >> delta;
    cout << (currentMonth - 1 + delta) % 12 + 1 << "\n";
}

Bài B

Yêu cầu tìm số hiệu của người chơi có tổng điểm cao nhất. Ta mô phỏng trực tiếp điểm thưởng của từng vòng theo đúng quy tắc.

void solve() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i) {
        string line;
        cin >> line;
        for (int j = 1; j <= m; ++j) {
            grid[i][j] = line[j - 1] - '0';
        }
    }

    vector<int> points(n + 1, 0);

    for (int col = 1; col <= m; ++col) {
        int zeroCnt = 0, oneCnt = 0;
        vector<int> choice(n + 1, 0);

        for (int row = 1; row <= n; ++row) {
            if (grid[row][col] == 1) {
                ++oneCnt;
                choice[row] = 1;
            } else {
                ++zeroCnt;
                choice[row] = 2;
            }
        }

        if (oneCnt == 0 || zeroCnt == 0) {
            for (int i = 1; i <= n; ++i) ++points[i];
        } else if (oneCnt < zeroCnt) {
            for (int i = 1; i <= n; ++i)
                if (choice[i] == 1) ++points[i];
        } else {
            for (int i = 1; i <= n; ++i)
                if (choice[i] == 2) ++points[i];
        }
    }

    int best = 0;
    for (int i = 1; i <= n; ++i) best = max(best, points[i]);
    for (int i = 1; i <= n; ++i)
        if (points[i] == best) cout << i << " ";
}

Bài C

Đầu tiên, dùng mảng state để lưu quan hệ lớn – nhỏ hiện tại giữa hai giá trị tại mỗi vị trí, đồng thời duy trì biến sum là tổng các giá trị nhỏ hơn trong từng cặp.

Xét thao tác sửa mảng A: nếu trước khi sửa, A[p] ≤ B[p], tức A[p] đang là giá trị được tính vào sum; khi đó phải trừ A[p] cũ ra khỏi sum, gán A[p] bằng giá trị mới rồi cộng min(A[p], B[p]) vào lại. Ngược lại, nếu B[p] đang nhỏ hơn A[p], thì chỉ cần cập nhật sum khi giá trị mới nhỏ hơn B[p]. Thao tác trên mảng B làm hoàn toàn tương tự.

void solve() {
    int n, q;
    cin >> n >> q;

    vector<int> arrA(n + 1), arrB(n + 1);
    vector<int> state(n + 1); // 1: arrA < arrB, 2: arrA > arrB, 3: arrA == arrB
    long long sum = 0;

    auto refresh = [&](int idx) {
        if (arrA[idx] < arrB[idx]) state[idx] = 1;
        else if (arrA[idx] > arrB[idx]) state[idx] = 2;
        else state[idx] = 3;
    };

    for (int i = 1; i <= n; ++i) cin >> arrA[i];
    for (int i = 1; i <= n; ++i) {
        cin >> arrB[i];
        sum += min(arrA[i], arrB[i]);
        refresh(i);
    }

    while (q--) {
        char op;
        int pos, val;
        cin >> op >> pos >> val;

        if (op == 'A') {
            if (state[pos] != 2) { // arrA đang là giá trị nhỏ hơn hoặc bằng
                sum -= arrA[pos];
                arrA[pos] = val;
                sum += min(arrA[pos], arrB[pos]);
            } else {
                if (val < arrB[pos]) {
                    sum -= arrB[pos];
                    sum += val;
                }
                arrA[pos] = val;
            }
        } else {
            if (state[pos] != 1) { // arrB đang là giá trị nhỏ hơn hoặc bằng
                sum -= arrB[pos];
                arrB[pos] = val;
                sum += min(arrA[pos], arrB[pos]);
            } else {
                if (val < arrA[pos]) {
                    sum -= arrA[pos];
                    sum += val;
                }
                arrB[pos] = val;
            }
        }

        refresh(pos);
        cout << sum << "\n";
    }
}

Bài D

Đây là kĩ thuật đồ thị phân lớp (layered graph). Lí do là khi đứng ở một ô nào đó, trạng thái của cả lưới có thể thay đổi.

Theo đề bài, cần xây dựng hai tầng đồ thị: một tầng là lưới gốc, tầng còn lại là lưới đảo ngược trạng thái (ô o thành x và ngược lại). Khi đi vào ô ?, ta phải chuyển sang tầng còn lại.

Trên thực tế không cần dựng hẳn đồ thị mới; chỉ cần thêm một chiều vào mảng đánh dấu visited để ghi nhận tầng nào đã được duyệt. Trong quá trình BFS cũng cần lưu tầng hiện tại của từng trạng thái.

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

const int MAXN = 505;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, 1, -1};

int h, w;
int sx, sy, gx, gy;
char grid[MAXN][MAXN];
bool visited[MAXN][MAXN][2];

struct State {
    int x, y, step, layer;
};

bool canMove(int x, int y, int layer) {
    if (x < 1 || x > h || y < 1 || y > w) return false;
    char c = grid[x][y];
    if (c == '#') return false;
    if (c == 'x' && layer == 0) return false;
    if (c == 'o' && layer == 1) return false;
    return !visited[x][y][layer];
}

int bfs() {
    queue<State> q;
    q.push({sx, sy, 0, 0});

    while (!q.empty()) {
        State cur = q.front();
        q.pop();

        int x = cur.x, y = cur.y;
        int step = cur.step, layer = cur.layer;

        if (visited[x][y][layer]) continue;
        visited[x][y][layer] = true;

        if (x == gx && y == gy) return step;

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (grid[x][y] == '?') {
                int nxtLayer = layer ^ 1;
                if (canMove(nx, ny, nxtLayer)) {
                    q.push({nx, ny, step + 1, nxtLayer});
                }
            } else {
                if (canMove(nx, ny, layer)) {
                    q.push({nx, ny, step + 1, layer});
                }
            }
        }
    }
    return -1;
}

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

    cin >> h >> w;
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            cin >> grid[i][j];
            if (grid[i][j] == 'S') {
                sx = i;
                sy = j;
            } else if (grid[i][j] == 'G') {
                gx = i;
                gy = j;
            }
        }
    }

    cout << bfs() << '\n';
    return 0;
}

Bài E

Đơn giản hóa yêu cầu: chỉ cần biết trong thành phần liên thông chứa điểm đang hỏi có tồn tại điểm đen hay không. Dùng cấu trúc DSU (Union-Find) để duy trì.

DSU quản lý quan hệ các phần tử thuộc cùng một tập hợp; ngoài ra cần mảng color lưu màu hiện tại của từng điểm và mảng blackCnt đếm số điểm đen trong từng tập hợp.

const int MAXN = 200005;

int parent[MAXN];
int blackCnt[MAXN];
int color[MAXN];

int findRoot(int v) {
    if (parent[v] == v) return v;
    return parent[v] = findRoot(parent[v]);
}

void unite(int u, int v) {
    int ru = findRoot(u);
    int rv = findRoot(v);
    if (ru == rv) return;

    int small = min(ru, rv);
    int big = max(ru, rv);

    parent[big] = small;
    blackCnt[small] += blackCnt[big];
    blackCnt[big] = 0;
}

void toggleColor(int v) {
    int root = findRoot(v);
    if (color[v] == 0) {
        color[v] = 1;
        ++blackCnt[root];
    } else {
        color[v] = 0;
        --blackCnt[root];
    }
}

void solve() {
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; ++i) parent[i] = i;

    while (q--) {
        int type;
        cin >> type;

        if (type == 1) {
            int u, v;
            cin >> u >> v;
            unite(u, v);
        } else if (type == 2) {
            int v;
            cin >> v;
            toggleColor(v);
        } else {
            int v;
            cin >> v;
            int root = findRoot(v);
            cout << (blackCnt[root] ? "Yes" : "No") << '\n';
        }
    }
}