Hướng giải của Lật Bóng Đèn Ma Trận

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Trò chơi yêu cầu bật/tắt (lật trạng thái) một bóng đèn đơn lẻ và đếm số lượng bóng đèn đang bật trong một khu vực hình chữ nhật.

  1. Ta sử dụng mảng phụ current_state kích thước \(N \times M\) để ghi nhớ trạng thái tắt/bật (0/1) của mỗi bóng đèn.
  2. Khi lật bóng đèn tại \((x, y)\):
    • Nếu bóng đang tắt (0), ta đổi trạng thái thành bật (1) và thực hiện cập nhật cộng thêm 1 vào BIT 2D.
    • Nếu bóng đang bật (1), ta đổi trạng thái thành tắt (0) và cập nhật trừ đi 1 (cộng -1) vào BIT 2D.
  3. Để đếm số bóng đèn bật sáng trong khu vực hình chữ nhật từ \((x_1, y_1)\) đến \((x_2, y_2)\), ta thực hiện truy vấn Range Query bằng nguyên lý Bao hàm - Loại trừ trên BIT 2D.

Mã nguồn C++ mẫu

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

int n, m, q;
vector<vector<int>> bit;
vector<vector<int>> current_state;

void update(int x, int y, int val) {
    for (int i = x; i <= n; i += i & -i) {
        for (int j = y; j <= m; j += j & -j) {
            bit[i][j] += val;
        }
    }
}

int query(int x, int y) {
    int s = 0;
    for (int i = x; i > 0; i -= i & -i) {
        for (int j = y; j > 0; j -= j & -j) {
            s += bit[i][j];
        }
    }
    return s;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    if (!(cin >> n >> m >> q)) return 0;
    bit.assign(n + 1, vector<int>(m + 1, 0));
    current_state.assign(n + 1, vector<int>(m + 1, 0));
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x, y; cin >> x >> y;
            if (current_state[x][y] == 0) {
                current_state[x][y] = 1;
                update(x, y, 1);
            } else {
                current_state[x][y] = 0;
                update(x, y, -1);
            }
        } else {
            int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
            cout << query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1) << "\n";
        }
    }
}

Nhận xét

Không có ý kiến tại thời điểm này.