Editorial for 特殊位置 (APCS 2023-06 中級)
簡潔題意
\(n \times m\) 的正整數陣列(\(1 \le n, m \le 50\),每格 \(1 \sim 9\))。兩格的距離=列差的絕對值加行差的絕對值。對每個元素 \(A[i][j] = x\),把「距離不超過 \(x\)」的所有元素加起來(含自己,超出陣列的不算);總和除以 \(10\) 的餘數等於 \(x\) 除以 \(10\) 的餘數,\((i, j)\) 就是特殊位置。輸出特殊位置的個數,再一行一個、依列優先(列小的先、同列行小的先)列出。
依正確通過的測試資料筆數給分,其中:
- 子題組 1(\(60\) 分):\(n = 1\)。
- 子題組 2(\(40\) 分):無額外限制。
先拿下子題組 1(60 分):只有一列,範圍就是左右各 x 格
\(n = 1\) 時陣列是一排 \(m\) 個數,用一維陣列裝(上冊 6.1)。兩格的距離只剩「行差的絕對值」,所以 a[j] = x 的範圍就是第 \(j - x\) 個到第 \(j + x\) 個——一個 for 從 j - x 跑到 j + x,出界的索引跳過(c < 0 || c >= m 就 continue,上冊 4.5),剩下的加起來。這題的 \(x\) 最大 \(9\)、陣列可能只有幾格,範圍常常兩邊都伸出陣列外,出界判斷不是可有可無。
「特殊位置」的判斷照題目寫:total % 10 == x % 10(\(x\) 本來就小於 \(10\),x % 10 就是 x,照寫比較安心)。輸出格式是「先印個數、再一行一個位置」——所以要先全部判完、數好個數,再印位置:用一個 bool 陣列記每個位置是不是特殊位置(上冊 6.7),印的時候列註標永遠是 \(0\)。
#include <iostream>
using namespace std;
const int MAX_M = 50;
int main() {
int n, m;
cin >> n >> m; // 子題組 1 保證 n = 1:陣列只有一列
int a[MAX_M];
for (int j = 0; j < m; j++) cin >> a[j];
int count = 0;
bool special[MAX_M]; // 先記下每個位置是不是特殊位置,數完個數再印
for (int j = 0; j < m; j++) {
int x = a[j];
int total = 0;
for (int c = j - x; c <= j + x; c++) { // 距離不超過 x:第 j - x 到第 j + x 個
if (c < 0 || c >= m) continue; // 超出陣列的不計算
total += a[c];
}
special[j] = (total % 10 == x % 10);
if (special[j]) count++;
}
cout << count << '\n';
for (int j = 0; j < m; j++) {
if (special[j]) cout << 0 << ' ' << j << '\n';
}
return 0;
}
這份程式交上去,範例 2 和子題組 2 會 WA——這是正常的,逐筆給分之下子題組 1 的 \(60\) 分穩穩到手。
從 60 分到 100 分:枚舉菱形範圍
二維的「距離不超過 \(x\)」是一個菱形(曼哈頓距離,13.6 的範圍枚舉):不是 \((2x + 1) \times (2x + 1)\) 的正方形——正方形的四個角落距離是 \(2x\),不在範圍裡。最直接的寫法是把包住菱形的正方形跑一遍(di、dj 各從 \(-x\) 到 \(x\)),每一格先看 abs(di) + abs(dj) > x 就跳過(不在菱形裡),再用 inside 擋掉出界的(13.2)。一維版那個「j - x 到 j + x」的迴圈,就是這段在 \(n = 1\) 時的樣子。
輸出要「列小的先、同列行小的先」——這正好就是雙層迴圈的順序(外層 i、內層 j),判到一個就 push_back 進一個 vector<pair<int, int>>(10.11),自然已經排好,不用另外排序;個數就是 answer.size()。陣列用巢狀 vector 裝(13.1),n、m、a 放全域讓 inside 看得到。
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> a;
bool inside(int r, int c) {
return 0 <= r && r < n && 0 <= c && c < m;
}
int main() {
cin >> n >> m;
a.assign(n, vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
vector<pair<int, int>> answer;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int x = a[i][j];
int total = 0;
for (int di = -x; di <= x; di++) { // 枚舉「範圍」裡的每一格
for (int dj = -x; dj <= x; dj++) {
if (abs(di) + abs(dj) > x) continue; // 曼哈頓距離超過 x:不在範圍內
int r = i + di, c = j + dj;
if (!inside(r, c)) continue; // 出界的格子不計算
total += a[r][c];
}
}
if (total % 10 == x % 10) answer.push_back({i, j});
}
}
cout << answer.size() << '\n';
for (auto [r, c] : answer) cout << r << ' ' << c << '\n';
return 0;
}
最後那行 for (auto [r, c] : answer) 是範圍 for(12.4)加結構化綁定(12.5),把每個 pair 一次拆成 r、c。運算量:\(2500\) 個位置、每個最多掃 \(19 \times 19 = 361\) 格,總共不到 \(10^6\) 次。
測過再交:範例 2 的四個特殊位置怎麼排都一樣
範例 2 的答案是 \((0, 2)\)、\((1, 3)\)、\((2, 3)\)、\((3, 3)\)——列優先和行優先排出來剛好相同,輸出順序寫錯的程式兩個範例照樣全過。範例也沒有「一個特殊位置都沒有」和「範圍比整張陣列還大」的情況:
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
1 1 / 5 |
1 / 0 0 |
只有一格:範圍裡只有自己,總和 \(5\)、餘數 \(5\) |
1 2 / 9 1 |
0 |
沒有特殊位置時只印一個 0;\(x = 9\) 的範圍兩邊都伸出陣列外,只算裡面的兩格 |
2 2 / 1 8 / 8 1 |
2 / 0 1 / 1 0 |
兩個特殊位置不同列也不同行:列小的 \((0, 1)\) 要先印。外層跑行、內層跑列的程式印成 1 0 在前——範例抓不到 |
2 3 / 7 3 3 / 9 4 1 |
1 / 0 0 |
菱形對正方形:\((1, 2)\) 的 \(1\) 只管上面的 \(3\) 和左邊的 \(4\)(\(1 + 3 + 4 = 8\),不特殊);把斜角 \((0, 1)\) 也算進去的程式得到 \(11\)、誤判它特殊,印 2/0 0/1 2 |
3 1 / 5 / 5 / 5 |
3 / 0 0 / 1 0 / 2 0 |
直的陣列、每一格都是特殊位置(範例都是橫的) |
五筆都親眼看過正確,這題就穩了。
常犯錯誤
- 範圍用正方形(只看 \(|di| \le x\) 且 \(|dj| \le x\),沒檢查兩者相加):範例 1 是一列、沒有斜角,照樣過;範例 2 印
5個。自測表第 4 列是手算得動的最小反例。 - 只看同列同行的十字:範例 1 照樣過;範例 2 第三個位置印成
1 4(該印2 3)。 - 輸出順序用行優先(外層
j、內層i):兩個範例全過;自測表第 3 列印1 0在前。 - 距離寫成
< x:範例 1 印3個。 - 自己沒算進總和:範例 1 印
0。 - 註標從 \(1\) 開始印,或列、行印反:範例 1 分別印
1 1/1 3和0 0/2 0。 - 沒判出界:範圍伸出陣列就讀到外面去——範例 1 第一格 \(x = 3\) 往左就出界,程式直接當掉。