ZeroJudge 解題筆記：e841. P8. 幽靈寶藏(Treasure)

作者：王一哲
日期：2025年2月14日



ZeroJudge 題目連結：e841. P8. 幽靈寶藏(Treasure)

解題想法

操作有以下 2 種

1. 在連續的數個藏寶箱內放入 $S$ 枚硬幣。
2. 使連續的數個藏寶箱內的硬幣價值變為 $S$ 倍，包括事後放入的硬幣。

所以操作時不需要考慮先加或是先乘，寫起來會簡單很多。

Python 程式碼

測資很大，第18筆測資開始超時。

n, m = map(int, input().split())  # n 個寶箱，編號 1 ~ n；m 次操作
add = [0]*(n+2)  # 各個寶箱硬幣增加的數量
mul = [1]*(n+2)  # 各個寶箱硬幣乘上的倍數
div = [1]*(n+2)  # 各個寶箱硬幣除掉的倍數
for _ in range(m):  # 讀取 m 次操作
    p, q, r, s = map(int, input().split())  # 範圍 [p, q]，操作種類 r，數量 s
    if r == 1:  # 操作是 1
        add[p] += s  # 編號 p 硬幣加 s
        add[q+1] -= s  # 編號 q+1 硬幣減 s
    elif r == 2:  # 操作是 2
        mul[p] *= s  # 編號 p 硬幣乘上的倍數乘以 s
        div[q+1] *= s  # 編號 q+1 硬幣除掉的倍數乘以 s
# end of for loop
idx, imax = 0, 0  # 最大值的寶箱編號，最大值
cur_val, cur_mul = 0, 1  # 目前的硬幣數量，目前乘上的倍數
for i in range(1, n+1):  # 更新各個寶箱的硬幣數量
    cur_mul = cur_mul * mul[i] // div[i]  # 更新 cur_mul
    cur_val += add[i]  # 更新 cur_val
    cur = cur_val * cur_mul  # 計算硬幣數量
    if cur > imax:  # 如果 cur 較大
        imax = cur  # 更新 imax
        idx = i  # 更新 i
print(f"{idx:d} {imax:d}")

C++ 程式碼

使用時間約為 0.3 s，記憶體約為 17 MB，通過測試。

#include <iostream>
#include <vector>
typedef long long LL;
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;  // n 個寶箱，編號 1 ~ n；m 次操作
    vector<LL> add (n+2, 0), mul (n+2, 1), div (n+2, 1);  // 各個寶箱硬幣增加的數量、乘上的倍數、除掉的倍數
    for(int i=0; i<m; i++) {  // 讀取 m 次操作
        LL p, q, r, s; cin >> p >> q >> r >> s;  // 範圍 [p, q]，操作種類 r，數量 s
        if (r == 1) {  // 操作是 1
            add[p] += s;  // 編號 p 硬幣加 s
            add[q+1] -= s;  // 編號 q+1 硬幣減 s
        } else if (r == 2) {  // 操作是 2
            mul[p] *= s;  // 編號 p 硬幣乘上的倍數乘以 s
            div[q+1] *= s;  // 編號 q+1 硬幣除掉的倍數乘以 s
        }
    }
    int idx = 0;  // 最大值的寶箱編號
    LL imax = 0, cur_val = 0, cur_mul = 1;  // 最大值，目前的硬幣數量，目前乘上的倍數
    for(int i=1; i<=n; i++) {  // 更新各個寶箱的硬幣數量
        cur_mul = cur_mul * mul[i] / div[i];  // 更新 cur_mul
        cur_val += add[i];  // 更新 cur_val
        LL cur = cur_val * cur_mul;  // 計算硬幣數量
        if (cur > imax) {  // 如果 cur 較大
            imax = cur;  // 更新 imax
            idx = i;  // 更新 i
        }
    }
    cout << idx << " " << imax << "\n";
    return 0;
}