彗星撞擊 題解|APCS 2025 年 10 月中級 第 1 題


簡潔題意

\(R \times C\) 的地圖(\(R, C \le 100\)),每格的高度一開始都是 \(D\);地圖上有 \(K\) 隻清醒的恐龍,同一格可以有好幾隻。接著依序發生 \(M\) 次撞擊(\(M \le 100\)),每次給中心 \((a, b)\)、奇數邊長 \(S \le 19\)、深度 \(d \le 10\),影響範圍是以 \((a, b)\) 為中心、邊長 \(S\) 的正方形,超出地圖的部分忽略。每次撞擊整個範圍一起判斷:

  • 範圍內有清醒的恐龍:範圍內的清醒恐龍全部暈眩,高度都不變。
  • 範圍內沒有清醒的恐龍:範圍內每一格的高度減 \(d\)。

暈眩的恐龍不會再醒來。輸出最後的最高高度、最低高度、清醒恐龍的隻數。

依正確通過的測試資料筆數給分,其中:

  • 子題組 1(\(60\) 分):\(R = 1\)。
  • 子題組 2(\(40\) 分):無額外限制。

先拿下子題組 1(60 分):只有一列

\(R = 1\) 時地圖就是一排格子,用兩個一維陣列:height[c] 記第 \(c\) 格的高度、awake[c] 記第 \(c\) 格還有幾隻清醒的恐龍。記隻數而不是「有沒有」,最後才數得出幾隻。

令 \(h = \lfloor S / 2 \rfloor\),撞擊範圍是第 \(b - h\) 到第 \(b + h\) 格,超出地圖就切掉:左端取 max(b - h, 0)、右端取 min(b + h, C - 1)(7.6)。

規則是對整個範圍判斷的,所以要掃兩遍:第一遍只看範圍內有沒有清醒的恐龍;第二遍才依結果動手——有的話把範圍內的 awake 全部歸零(牠們暈眩了,之後的撞擊不會再把牠們算成清醒),沒有的話把範圍內的高度全部減 \(d\)。

最後的最高、最低高度用擂台找。高度會變成負的,最低可以到 \(1 - 100 \times 10 = -999\),所以最高高度的擂台初值設 \(0\)、\(-1\) 甚至 \(-100\) 都不夠;直接拿第一格當初值最保險。

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

int height[100];  // 子題組 1 只有一列:height[c]=第 c 行的高度
int awake[100];   // awake[c]=第 c 行還有幾隻清醒的恐龍

int main() {
    int R, C, D;
    cin >> R >> C >> D;  // 子題組 1 保證 R = 1
    for (int c = 0; c < C; c++) {
        height[c] = D;
    }
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int r, c;
        cin >> r >> c;
        awake[c]++;
    }
    int m;
    cin >> m;
    for (int j = 0; j < m; j++) {
        int a, b, s, d;
        cin >> a >> b >> s >> d;
        int h = s / 2;
        int left = max(b - h, 0);  // 超出地圖的部分直接切掉
        int right = min(b + h, C - 1);
        bool hasAwake = false;
        for (int c = left; c <= right; c++) {
            if (awake[c] > 0) hasAwake = true;
        }
        for (int c = left; c <= right; c++) {
            if (hasAwake) awake[c] = 0;  // 範圍內的清醒恐龍全部暈眩
            else height[c] -= d;
        }
    }
    int highest = height[0], lowest = height[0], awakeCount = 0;
    for (int c = 0; c < C; c++) {
        highest = max(highest, height[c]);
        lowest = min(lowest, height[c]);
        awakeCount += awake[c];
    }
    cout << highest << " " << lowest << " " << awakeCount << endl;
}

這個版本對子題組 1 的 \(12\) 筆全對,穩拿 \(60\) 分。

從 60 分到 100 分:多一個維度,其他照舊

一般的 \(R\) 就把兩個陣列換成二維,範圍多一組上下界:上端 max(a - h, 0)、下端 min(a + h, R - 1)。掃兩遍、擂台、數清醒的恐龍都和上面一樣,每個迴圈多包一層而已。

每次撞擊最多看 \(19 \times 19\) 格、共 \(100\) 次,再加上最後掃一次地圖,運算量很小。

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

int height[100][100];  // height[r][c]=第 r 列第 c 行的高度
int awake[100][100];   // awake[r][c]=這一格還有幾隻清醒的恐龍

int main() {
    int R, C, D;
    cin >> R >> C >> D;
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            height[r][c] = D;
        }
    }
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int r, c;
        cin >> r >> c;
        awake[r][c]++;
    }
    int m;
    cin >> m;
    for (int j = 0; j < m; j++) {
        int a, b, s, d;
        cin >> a >> b >> s >> d;
        int h = s / 2;
        int top = max(a - h, 0), bottom = min(a + h, R - 1);  // 正方形和地圖取交集
        int left = max(b - h, 0), right = min(b + h, C - 1);
        bool hasAwake = false;  // 先把整塊看完:有沒有清醒的恐龍
        for (int r = top; r <= bottom; r++) {
            for (int c = left; c <= right; c++) {
                if (awake[r][c] > 0) hasAwake = true;
            }
        }
        for (int r = top; r <= bottom; r++) {  // 再決定整塊套用哪一條規則
            for (int c = left; c <= right; c++) {
                if (hasAwake) awake[r][c] = 0;
                else height[r][c] -= d;
            }
        }
    }
    int highest = height[0][0], lowest = height[0][0], awakeCount = 0;  // 拿第一格當擂台初值
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            highest = max(highest, height[r][c]);
            lowest = min(lowest, height[r][c]);
            awakeCount += awake[r][c];
        }
    }
    cout << highest << " " << lowest << " " << awakeCount << endl;
}

測過再交:範例只有一列

範例是 \(R = 1\),最後的高度也都是正的。下面四種錯法範例都會過(見常犯錯誤),這幾筆專門抓它們:

輸入 正確輸出 這一筆在測什麼
1 3 5/1/0 0/1/0 1 3 2 5 5 0 範圍內有清醒的恐龍:整個範圍的高度都不動,沒有恐龍的格子也一樣
1 3 5/1/0 0/2/0 0 1 1/0 0 1 1 5 4 0 暈眩的恐龍擋不住下一次撞擊
1 1 1/0/1/0 0 1 10 -9 -9 0 最高高度也是負的
3 3 10/1/2 2/2/0 0 3 4/2 2 1 1 10 6 0 二維、中心在角落,正方形超出地圖

四筆都親眼看過正確,這題就穩了。

常犯錯誤
  • 每一格各自判斷:有恐龍的格子讓恐龍暈眩、沒恐龍的格子照樣減高度。範例全過,自測表第 1 列印 5 3 0;本站 \(20\) 筆掛 \(10\) 筆。
  • 暈眩之後還留著「這格有恐龍」的紀錄,下一次撞擊照樣被擋住:範例全過,自測表第 2 列印 5 5 0;本站 \(20\) 筆掛 \(12\) 筆。
  • 最高高度的擂台初值設成 \(0\)、\(-1\) 或 \(-100\):範例全過,自測表第 3 列在初值 \(0\) 時印 0 -9 0;本站 \(20\) 筆掛 \(1\) 筆。
  • 最高高度的擂台初值設成 \(D\):高度只會往下掉,每一格都不超過 \(D\),擂台上的 \(D\) 永遠不會被換掉。範例全過,自測表第 3 列印 1 -9 0;本站 \(20\) 筆掛 \(9\) 筆。