Hướng dẫn cho Chuỗi phép thuật

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Tóm tắt đề bài

Có \(N\) viên đá ban đầu có năng lượng bằng \(0\). Có \(Q\) câu thần chú, câu thứ \(i\) tăng năng lượng các viên đá từ \(L_i\) đến \(R_i\) thêm \(1\). Có \(M\) đợt niệm chú, đợt thứ \(j\) thực hiện các câu thần chú từ số hiệu \(x_j\) đến \(y_j\). Tính năng lượng cuối cùng của \(N\) viên đá.

Phân tích

Dữ liệu: \(N, Q, M \le 10^5\).
Thách thức: Nếu làm theo cách thông thường, ta phải thực hiện rất nhiều thao tác cập nhật trên đoạn. Một đợt niệm chú có thể chứa nhiều câu thần chú, và mỗi câu thần chú lại tác động lên nhiều viên đá.
Nhận xét:
- Mỗi câu thần chú thứ \(i\) thực chất sẽ được thực hiện một số lần nhất định, gọi số lần đó là \(count_i\).
- Sau khi biết mỗi câu thần chú \(i\) được thực hiện bao nhiêu lần, ta chỉ cần tăng năng lượng các viên đá từ \(L_i\) đến \(R_i\) thêm \(count_i\) đơn vị.
- Cả hai bước trên đều có dạng: "Cộng một giá trị vào các phần tử trong đoạn \([L, R]\)". Đây là bài toán kinh điển có thể giải quyết hiệu quả bằng Mảng hiệu (Difference Array).

Cách làm đơn giản (Brute Force)

Ý tưởng

Duyệt qua từng đợt niệm chú \(j\) từ \(x_j\) đến \(y_j\). Với mỗi câu thần chú \(i\) trong đó, duyệt từ \(L_i\) đến \(R_i\) để tăng năng lượng viên đá lên \(1\).

Độ phức tạp

Thời gian: \(O(M \times Q \times N)\) trong trường hợp xấu nhất.
Đánh giá: Chỉ phù hợp cho \(N, Q, M \le 1000\) (Subtask 1).

Code Brute Force

C++

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

int main() {
    int n, q, m;
    cin >> n >> q >> m;
    vector<pair<int, int>> spells(q + 1);
    for (int i = 1; i <= q; i++) cin >> spells[i].first >> spells[i].second;

    vector<long long> energy(n + 1, 0);
    for (int j = 0; j < m; j++) {
        int x, y;
        cin >> x >> y;
        for (int i = x; i <= y; i++) {
            for (int k = spells[i].first; k <= spells[i].second; k++) {
                energy[k]++;
            }
        }
    }
    for (int i = 1; i <= n; i++) cout << energy[i] << (i == n ? "" : " ");
    return 0;
}

Python

n, q, m = map(int, input().split())
spells = []
for _ in range(q):
    spells.append(list(map(int, input().split())))

energy = [0] * (n + 1)
for _ in range(m):
    x, y = map(int, input().split())
    for i in range(x - 1, y):
        l, r = spells[i]
        for k in range(l, r + 1):
            energy[k] += 1

print(*(energy[1:]))

Hướng giải quyết (Tối ưu)

Để giải quyết bài toán với \(N, Q, M = 10^5\), ta sử dụng kỹ thuật Mảng hiệu (Difference Array) hai lần:

Bước 1: Tính số lần mỗi câu thần chú được thực hiện

Ta có \(M\) đợt niệm chú, mỗi đợt tác động lên các câu thần chú từ \(x_j\) đến \(y_j\).
Gọi count_diff là mảng hiệu để quản lý số lần thực hiện của \(Q\) câu thần chú.
Với mỗi đợt \((x_j, y_j)\):
- count_diff[x_j] += 1
- count_diff[y_j + 1] -= 1
Sau khi xử lý \(M\) đợt, dùng mảng cộng dồn để tính \(count_i\) (số lần câu thần chú \(i\) được gọi):
- count[i] = count[i-1] + count_diff[i]

Bước 2: Tính năng lượng cuối cùng của các viên đá

Bây giờ ta biết câu thần chú \(i\) (tác động đoạn \([L_i, R_i]\)) được thực hiện \(count_i\) lần. Nghĩa là đoạn \([L_i, R_i]\) của các viên đá được cộng thêm \(count_i\).
Gọi energy_diff là mảng hiệu để quản lý năng lượng của \(N\) viên đá.
Với mỗi câu thần chú \(i\) từ \(1\) đến \(Q\):
- energy_diff[L_i] += count[i]
- energy_diff[R_i + 1] -= count[i]
Cuối cùng, dùng mảng cộng dồn để tính năng lượng thực tế của từng viên đá:
- energy[i] = energy[i-1] + energy_diff[i]

Độ phức tạp

Thời gian: \(O(N + Q + M)\), vì mỗi bước chỉ là duyệt qua các mảng một vài lần.
Bộ nhớ: \(O(N + Q)\) để lưu trữ các mảng hiệu và thông tin câu thần chú.

Code tham khảo

C++

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q, m;
    cin >> n >> q >> m;

    vector<pair<int, int>> spells(q + 1);
    for (int i = 1; i <= q; i++) {
        cin >> spells[i].first >> spells[i].second;
    }

    // Bước 1: Tính số lần mỗi câu thần chú được thực hiện
    vector<long long> count_diff(q + 2, 0);
    for (int j = 0; j < m; j++) {
        int x, y;
        cin >> x >> y;
        count_diff[x]++;
        count_diff[y + 1]--;
    }

    vector<long long> count(q + 1, 0);
    for (int i = 1; i <= q; i++) {
        count[i] = count[i - 1] + count_diff[i];
    }

    // Bước 2: Tính năng lượng các viên đá
    vector<long long> energy_diff(n + 2, 0);
    for (int i = 1; i <= q; i++) {
        int l = spells[i].first;
        int r = spells[i].second;
        energy_diff[l] += count[i];
        energy_diff[r + 1] -= count[i];
    }

    vector<long long> energy(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        energy[i] = energy[i - 1] + energy_diff[i];
        cout << energy[i] << (i == n ? "" : " ");
    }

    return 0;
}

Python

import sys

def solve():
    input = sys.stdin.read().split()
    if not input:
        return

    ptr = 0
    n = int(input[ptr]); ptr += 1
    q = int(input[ptr]); ptr += 1
    m = int(input[ptr]); ptr += 1

    spells = []
    for _ in range(q):
        l = int(input[ptr]); ptr += 1
        r = int(input[ptr]); ptr += 1
        spells.append((l, r))

    # Bước 1: Tính số lần mỗi câu thần chú được thực hiện
    count_diff = [0] * (q + 2)
    for _ in range(m):
        x = int(input[ptr]); ptr += 1
        y = int(input[ptr]); ptr += 1
        count_diff[x] += 1
        count_diff[y + 1] -= 1

    count = [0] * (q + 1)
    for i in range(1, q + 1):
        count[i] = count[i - 1] + count_diff[i]

    # Bước 2: Tính năng lượng các viên đá
    energy_diff = [0] * (n + 2)
    for i in range(1, q + 1):
        l, r = spells[i - 1]
        energy_diff[l] += count[i]
        energy_diff[r + 1] -= count[i]

    energy = [0] * (n + 1)
    ans = []
    for i in range(1, n + 1):
        energy[i] = energy[i - 1] + energy_diff[i]
        ans.append(str(energy[i]))

    sys.stdout.write(" ".join(ans) + "\n")

if __name__ == "__main__":
    solve()

Bình luận

Tải bình luận...

Không có bình luận nào.