Tiền đề

Bài viết này tập trung vào việc phân tích và cung cấp giải pháp chi tiết cho một số bài toán lập trình phổ biến. Mỗi bài toán sẽ được thảo luận từ góc độ chiến lược giải quyết và minh họa bằng ví dụ mã nguồn cụ thể.

Bài toán mô phỏng

Kết quả không như mong đợi:

A. Pahuljice

Quan sát thấy rằng trong một bông tuyết kích thước x có chứa một bông tuyết nhỏ hơn với kích thước x-1. Có thể sử dụng phương pháp mở rộng từ tâm ra ngoài để xác định kích thước của bông tuyết.

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 55;
int grid[MAX][MAX];
vector> crosses;

bool isValid(int x, int y, int n, int m, int k) {
    return (x + k >= 1 && x + k <= n && 
            y + k >= 1 && y + k <= m && 
            x - k >= 1 && x - k <= n && 
            y - k >= 1 && y - k <= m);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= n; ++i) {
        string row;
        cin >> row;
        for (int j = 1; j <= m; ++j) {
            grid[i][j] = row[j - 1];
            if (grid[i][j] == '+') {
                crosses.emplace_back(i, j);
            }
        }
    }

    int result = 0;
    for (auto &[x, y] : crosses) {
        int k = 0;
        while (isValid(x, y, n, m, k)) {
            bool match = true;
            for (int dir = 0; dir < 8 && match; ++dir) {
                int nx = x + (dir / 3 - 1) * k;
                int ny = y + (dir % 3 - 1) * k;
                if (grid[nx][ny] != '+') {
                    match = false;
                }
            }
            if (!match) break;
            ++k;
        }
        result = max(result, k);
    }
    cout << result;
    return 0;
}

B. Pingvin

Bài toán tìm đường đi ngắn nhất thường được giải quyết bằng thuật toán Dijkstra.

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

struct Node {
    int x, y, z, dist;
};

bool operator<(const Node &a, const Node &b) { return a.dist > b.dist; }

const int SIZE = 105;
int grid[SIZE][SIZE][SIZE], distanceGrid[SIZE][SIZE][SIZE];
bool visited[SIZE][SIZE][SIZE];
int directions[6][3] = {{-1, 0, 0}, {1, 0, 0}, {0, -1, 0}, {0, 1, 0}, {0, 0, -1}, {0, 0, 1}};

void dijkstra(int sx, int sy, int sz, int tx, int ty, int tz, int n) {
    priority_queue<Node> pq;
    memset(distanceGrid, 0x3f, sizeof(distanceGrid));
    distanceGrid[sx][sy][sz] = 0;
    pq.push({sx, sy, sz, 0});

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();

        if (visited[current.x][current.y][current.z]) continue;
        visited[current.x][current.y][current.z] = true;

        for (int i = 0; i < 6; ++i) {
            int newX = current.x + directions[i][0];
            int newY = current.y + directions[i][1];
            int newZ = current.z + directions[i][2];

            if (newX >= 1 && newX <= n && newY >= 1 && newY <= n && newZ >= 1 && newZ <= n &&
                !grid[newX][newY][newZ] && distanceGrid[newX][newY][newZ] > current.dist + 1) {
                distanceGrid[newX][newY][newZ] = current.dist + 1;
                pq.push({newX, newY, newZ, current.dist + 1});
            }
        }
    }
}

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

    int n, sx, sy, sz, tx, ty, tz;
    cin >> n >> sx >> sy >> sz >> tx >> ty >> tz;

    for (int z = 1; z <= n; ++z) {
        for (int x = 1; x <= n; ++x) {
            string s;
            cin >> s;
            for (int y = 1; y <= n; ++y) {
                grid[x][y][z] = s[y - 1] - '0';
            }
        }
    }

    dijkstra(sx, sy, sz, tx, ty, tz, n);
    cout << (distanceGrid[tx][ty][tz] == 0x3f3f3f3f ? -1 : distanceGrid[tx][ty][tz]);
    return 0;
}

C. Dizalo

Quan sát quy trình người lên xuống thang máy, ta nhận thấy rằng sau mỗi lần một nhóm người rời đi, cách quay lại hiệu quả nhất là sắp xếp theo thứ tự tầng cao đến thấp.

#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int MAXN = 1e5 + 5;
int N, Q, A[MAXN], T[MAXN], QueryTime[MAXN], DeleteFlag[MAXN];
long long TotalSum = 0;
vector<int> Events[MAXN];
set<pair<int, int>> ActiveSet;

void updateBitTree(int tree[], int idx, int delta, int size) {
    while (idx <= size) {
        tree[idx] += delta;
        idx += (idx & (-idx));
    }
}

int queryBitTree(int tree[], int idx) {
    int res = 0;
    while (idx > 0) {
        res += tree[idx];
        idx -= (idx & (-idx));
    }
    return res;
}

int main() {
    cin >> N >> Q;
    for (int i = 1; i <= N; ++i) T[i] = Q + 1;
    for (int i = 1; i <= N; ++i) cin >> A[i];
    for (int i = 1; i <= Q; ++i) {
        cin >> QueryTime[i];
        T[QueryTime[i]] = i;
    }

    // Build events
    for (int i = N; i >= 1; --i) {
        Events[queryBitTree(T, A[i] - 1)].push_back(i);
        updateBitTree(T, A[i], 1, N);
    }

    ActiveSet.insert({0, 0});
    ActiveSet.insert({N + 1, N + 1});
    for (int i = 0; i < Events[0].size(); ++i) {
        int w = Events[0][i];
        TotalSum += w - A[w];
    }

    cout << TotalSum + N << " ";
    for (int i = 1; i <= Q; ++i) {
        DeleteFlag[QueryTime[i]] = 1;
        // Logic to handle updates and queries
    }
    return 0;
}

D. Kuglice

Với phạm vi dữ liệu cho phép, phương pháp động \\(\mathcal{O}(n^2)\\) là hợp lý.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 3005;
int N, CountColor, Balls[MAXN], LeftMost[MAXN], RightMost[MAXN], DP[MAXN][MAXN];

int calculateDP(int left, int right) {
    if (left == right) return (LeftMost[Balls[left]] >= left && RightMost[Balls[left]] <= right);
    if (DP[left][right] == 0x3f3f3f3f) {
        DP[left][right] = max(
            (LeftMost[Balls[left]] >= left && RightMost[Balls[left]] <= right) - calculateDP(left + 1, right),
            (LeftMost[Balls[right]] >= left && RightMost[Balls[right]] <= right) - calculateDP(left, right - 1)
        );
    }
    return DP[left][right];
}

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

    cin >> N;
    if (N == 1) {
        cout << "1:0\n";
        return 0;
    }

    set<int> uniqueColors;
    for (int i = 1; i <= N; ++i) {
        cin >> Balls[i];
        uniqueColors.insert(Balls[i]);
        if (!LeftMost[Balls[i]]) LeftMost[Balls[i]] = i;
        RightMost[Balls[i]] = i;
    }

    CountColor = uniqueColors.size();
    memset(DP, 0x3f, sizeof(DP));
    calculateDP(1, N);

    cout << (CountColor + DP[1][N]) / 2 << ":" << CountColor - (CountColor + DP[1][N]) / 2 << "\n";
    return 0;
}

E. Zatopljenje

Bài toán xử lý các truy vấn liên quan đến mức nước biển giảm dần.

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 2e5 + 5;
int N, Q, Heights[MAXN], Answers[MAXN];
struct Query {
    int l, r, h, id;
};
vector<Query> Queries(MAXN);
vector<pair<int, int>> Points(MAXN);
int SegmentTree[4 * MAXN];

void buildSegmentTree(int node, int start, int end) {
    if (start == end) {
        SegmentTree[node] = Heights[start];
        return;
    }
    int mid = (start + end) / 2;
    buildSegmentTree(node * 2, start, mid);
    buildSegmentTree(node * 2 + 1, mid + 1, end);
    SegmentTree[node] = SegmentTree[node * 2] + SegmentTree[node * 2 + 1];
}

int querySegmentTree(int node, int start, int end, int left, int right) {
    if (left > end || right < start) return 0;
    if (left <= start && end <= right) return SegmentTree[node];
    int mid = (start + end) / 2;
    return querySegmentTree(node * 2, start, mid, left, right) +
           querySegmentTree(node * 2 + 1, mid + 1, end, left, right);
}

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

    cin >> N >> Q;
    for (int i = 1; i <= N; ++i) {
        cin >> Heights[i];
        Points[i] = {Heights[i], i};
    }
    for (int i = 1; i <= Q; ++i) {
        cin >> Queries[i].l >> Queries[i].r >> Queries[i].h;
        Queries[i].id = i;
    }

    sort(Queries.begin() + 1, Queries.begin() + Q + 1, [&](const Query &a, const Query &b) { return a.h > b.h; });
    sort(Points.begin() + 1, Points.begin() + N + 1, [&](const pair<int, int> &a, const pair<int, int> &b) { return a.first > b.first; });

    int pointIndex = 1;
    buildSegmentTree(1, 1, N);

    for (int i = 1; i <= Q; ++i) {
        while (pointIndex <= N && Points[pointIndex].first > Queries[i].h) {
            Heights[Points[pointIndex].second] = 1;
            buildSegmentTree(1, 1, N);
            pointIndex++;
        }
        Answers[Queries[i].id] = querySegmentTree(1, 1, N, Queries[i].l, Queries[i].r);
    }

    for (int i = 1; i <= Q; ++i) cout << Answers[i] << "\n";
    return 0;
}