1 条题解

  • 0
    @ 2026-8-11 23:17:05
    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    
    const int N = 205, M = 505;
    // 模拟僵尸移动与炸弹引爆
    // alive[i] 记录第 i 个僵尸是否还在路上
    // bombs[t] 记录在时刻 t 引爆的炸弹的 (位置 x, 半径 r)
    int n, m, k;
    vector<pair<int, int>> bombs[M];
    bool alive[N];
    
    signed main() {
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        cin >> n >> m >> k;
        for (int i = 0; i < k; i++) {
            int x, r, t;
            cin >> x >> r >> t;
            if (t < M) {
                bombs[t].push_back({x, r});
            }
        }
        
        int arrived_count = 0;
        memset(alive, 0, sizeof(alive));
        
        // 最晚的僵尸在第 m 秒初出发,走到 n+1 需要 n+1 秒,所以在 m+n 秒末到达
        // 炸弹最晚在 500 秒末引爆,因此模拟到 max(m+n+1, 500) 即可
        int max_T = max(m + n + 1, 500LL);
        for (int T = 1; T <= max_T; T++) {
            // 1. 僵尸出发
            if (T <= m) {
                alive[T] = true;
            }
            
            // 2. 检查是否到达城市
            for (int j = 1; j <= min(T, m); j++) {
                if (alive[j]) {
                    int current_pos = T - j + 1;
                    if (current_pos == n + 1) {
                        alive[j] = false;
                        arrived_count++;
                    }
                }
            }
            
            // 3. 炸弹引爆
            if (T < M) {
                for (auto& bomb : bombs[T]) {
                    int x = bomb.first;
                    int r = bomb.second;
                    for (int j = 1; j <= min(T, m); j++) {
                        if (alive[j]) {
                            int current_pos = T - j + 1;
                            if (abs(current_pos - x) <= r) {
                                alive[j] = false;
                            }
                        }
                    }
                }
            }
        }
        
        cout << arrived_count << '\n';
        return 0;
    }
    
    • 1

    [COCI 2025/2026 #4] 僵尸启示录 / Zombie Apocalypse

    信息

    ID
    12629
    时间
    3000ms
    内存
    512MiB
    难度
    6
    标签
    递交数
    40
    已通过
    14
    上传者