彗星撞擊 題解|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\) 筆。