Editorial for 運貨站 (APCS 2022-10 中級)
簡潔題意
\(R\) 列 \(C\) 行的倉庫(\(1 \le R \le 30\)、\(1 \le C \le 50\)),依序收到 \(n\) 件貨物(\(1 \le n \le 200\))。每件貨物是 A~E 五種固定形狀之一、不能旋轉翻面,最上方那一列固定在第 \(y_i\) 列(保證不會超出倉庫底部)。貨物從倉庫右側進來:先試「剛好完全進入倉庫」的最右位置,放不下(出界或跟已放的貨物重疊)就整件丟棄、倉庫不變;放得下就一格一格往左推,直到再往左會出界或碰到別的貨物為止。輸出最後倉庫的空格數與被丟棄的貨物數。
依正確通過的測試資料筆數給分,其中:
- 子題組 1(\(20\) 分):只會出現 B。
- 子題組 2(\(40\) 分):只會出現 A、B、C。
- 子題組 3(\(40\) 分):無額外限制。
先拿下子題組 1(20 分):只有 B,每一列記一個數就夠
B 是「一列三格」。只有 B 的時候每一列各自獨立、互不影響:一件 B 進了第 \(y\) 列就一路往左推到底——不是貼左牆,就是貼在這一列前一件 B 的右邊。所以每一列只要記一個數 w[r]:這一列從左邊數起,前 w[r] 行已經被堵住(一開始全部是 \(0\))。新的 B 要放進第 \(y\) 列時:
w[y] + 3 > C:這一列剩下的空間連三格都不夠,連最右邊都放不下——丟棄。- 否則放得下,而且會一路推到
w[y]旁邊:w[y]加 \(3\),放進去的格數也加 \(3\)。
最後的空格數=\(R \times C\) 減掉放進去的格數。
#include <iostream>
using namespace std;
const int MAX_R = 30;
int main() {
int R, C, n;
cin >> R >> C >> n;
int w[MAX_R] = {}; // w[r]=第 r 列從左數起,前 w[r] 行已經被堵住(一開始全 0)
int placed = 0, discarded = 0;
for (int i = 0; i < n; i++) {
char t;
int y;
cin >> t >> y; // 子題組 1 保證 t 一定是 B:一列三格
if (w[y] + 3 > C) { // 這一列剩下的空間連三格都塞不下
discarded++;
} else {
w[y] += 3;
placed += 3;
}
}
cout << R * C - placed << ' ' << discarded << '\n';
return 0;
}
int w[MAX_R] = {}; 是上冊 6.5 的全部歸零。這份程式交上去,範例 2 和子題組 2、3 大多數的測資會 WA——這是正常的,逐筆給分之下子題組 1 的 \(20\) 分穩穩到手。
從 20 分到 100 分:把倉庫真的畫出來,一格一格往左推
五種形狀一來,「每一列各自獨立」就不成立了:A 一次跨四列、E 跨三列,同一件貨物是一體的——任何一列被擋住,整件就得停。最直接的做法是照題目說的做:開一張 \(R \times C\) 的地圖 occupied 記每一格有沒有貨物(13.1),每一件貨物真的從最右邊開始、一格一格往左試。
要試「放在這裡行不行」,得先講清楚形狀的每一格在哪。13.8 的做法:把形狀打成表——挑「最上列、最右行」那一格當基準點 \((0, 0)\),其他每格記相對於它的位移 (dr, dc),直接照題目附圖抄。A、B、C 左右對稱、不容易抄錯;D 是上面一格靠右、下面一整排三格,E 是上面一格靠右、下面兩列各兩格——這兩個抄的時候對著圖再看一次。基準點放在第 top 列、第 right 行,形狀的每一格就在 (top + dr, right + dc);canPlace 把表跑一遍,任何一格出界(13.2)或已經有貨物就回傳 false(上冊 7.4 的判斷函式)。
主程式對每一件貨物做四步:
right = C - 1:先試「剛好完全進入倉庫」的最右位置——基準點就在最右一行。- 這裡放不下就
discarded++、直接處理下一件(continue)。不能再往左找:貨物穿不過障礙,障礙左邊的洞是到不了的。 while (canPlace(top, right - 1, cells)) right--;:往左一格還放得下就推——就是 13.4 的一步一步走,只是方向固定往左、停下來的條件是「下一格放不下」。- 停下來之後把這幾格標成已佔用、累加放進去的格數。
#include <bits/stdc++.h>
using namespace std;
// 五種形狀打成表:每個方格相對於「最上列、最右行」的位移 (dr, dc)
vector<pair<int, int>> shape(char type) {
if (type == 'A') return {{0, 0}, {1, 0}, {2, 0}, {3, 0}};
if (type == 'B') return {{0, -2}, {0, -1}, {0, 0}};
if (type == 'C') return {{0, -1}, {0, 0}, {1, -1}, {1, 0}};
if (type == 'D') return {{0, 0}, {1, -2}, {1, -1}, {1, 0}};
return {{0, 0}, {1, -1}, {1, 0}, {2, -1}, {2, 0}}; // E
}
int R, C;
vector<vector<bool>> occupied;
// 把形狀的最右行放在第 right 行、最上列放在第 top 列,放得下嗎?
bool canPlace(int top, int right, const vector<pair<int, int>>& cells) {
for (auto [dr, dc] : cells) {
int r = top + dr, c = right + dc;
if (r < 0 || r >= R || c < 0 || c >= C) return false; // 出界
if (occupied[r][c]) return false; // 撞到別的貨物
}
return true;
}
int main() {
int n;
cin >> R >> C >> n;
occupied.assign(R, vector<bool>(C, false));
int used = 0, discarded = 0;
while (n--) {
char type;
int top;
cin >> type >> top;
vector<pair<int, int>> cells = shape(type);
int right = C - 1; // 先試「剛好完全進入倉庫」的最右位置
if (!canPlace(top, right, cells)) { discarded++; continue; }
while (canPlace(top, right - 1, cells)) right--; // 還能往左就繼續推
for (auto [dr, dc] : cells) occupied[top + dr][right + dc] = true;
used += cells.size();
}
cout << R * C - used << ' ' << discarded << '\n';
return 0;
}
auto [dr, dc] 是 12.5 的結構化綁定,把一個 pair 一次拆成兩個變數。速度不用擔心:最多 \(200\) 件貨物、每件最多往左推 \(50\) 格、每格查 \(5\) 個方格,總共 \(200 \times 50 \times 5 = 50000\) 次上下。
更簡潔的寫法:每一列還是只記一個數
回頭看子題組 1:那時每一列只記「被堵到第幾行」就夠了。這個想法其實五種形狀都適用,靠的是兩個觀察:
- 五種形狀的每一列都是連續的、而且靠右對齊——每一列最右邊那格全在同一行(D 是
..#/###,E 是.#/##/##)。所以一個形狀只要記「由上到下每一列有幾格」:A{1,1,1,1}、B{3}、C{2,2}、D{1,3}、E{1,2,2}。 - 貨物只會水平移動、而且只從右邊進來——第 \(r\) 列一旦有格子被佔到第 \(c\) 行,第 \(c\) 行左邊的空格(不管是不是洞)之後任何貨物都到不了。所以每一列只要一個數
w[r]=這一列從左數起前w[r]行已經到不了;那一列裡真正有幾格是貨物、有幾格是洞,都不用管。
於是一件貨物放進第 \(y\) 列的過程變成:形狀的第 \(i\) 列(倉庫的第 \(y + i\) 列)有 tile[i] 格,它的右邊界至少要到 w[y + i] + tile[i] 才不會撞到東西;整件貨物是一體的,所以最後停下來的右邊界是各列的最大值 ma。任何一列 w[y + i] + tile[i] > C(連最右邊都塞不下)就丟棄;否則這幾列的 w 全部改成 ma——包括格數少的那幾列(D 上面那列只有一格,這一列的牆同樣要推到 ma:它左邊的格子從此到不了)。
空格數仍然是 \(R \times C\) 減掉放進去的格數(每種形狀幾格=grid_num),不能拿 w 加總——被堵在後面的洞到不了、卻仍然是空格。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 五種形狀「由上到下每一列有幾格」:每一列都靠右對齊,所以只記寬度就夠
vector<vector<int>> tiles{
{1, 1, 1, 1}, // A
{3}, // B
{2, 2}, // C
{1, 3}, // D
{1, 2, 2} // E
};
int grid_num[5] = {4, 3, 4, 4, 5}; // 每種形狀共幾格
int R, C;
// 把形狀 tile 的最上列放在第 y 列往左推:放得下就更新 w 並回傳 true,放不下回傳 false
bool push(vector<int> &tile, int y, vector<int> &w) {
int ma = 0; // 推完之後整件貨物共同的右邊界(佔到第 ma - 1 行)
for (int i = 0; i < (int)tile.size(); i++) {
if (tile[i] + w[y + i] > C) return false; // 這一列連最右邊都塞不下
ma = max(ma, tile[i] + w[y + i]);
}
for (int i = 0; i < (int)tile.size(); i++) {
w[y + i] = ma; // 整件貨物一起停:這幾列的牆都推到 ma
}
return true;
}
int main() {
int n;
cin >> R >> C >> n;
vector<int> w(R); // w[r]=第 r 列從左數起前 w[r] 行已經到不了(一開始全 0)
int ans = R * C;
int drop_cnt = 0;
for (int i = 0; i < n; i++) {
char t;
int y;
cin >> t >> y;
if (push(tiles[t - 'A'], y, w)) {
ans -= grid_num[t - 'A'];
} else {
drop_cnt++;
}
}
cout << ans << ' ' << drop_cnt << '\n';
}
push 的參數 w 用參考傳進去(上冊 7.5),改的是 main 裡那一份;tiles[t - 'A'] 用字元相減把 A~E 變成 \(0 \sim 4\)(8.3);vector<vector<int>> 是 10.3 的巢狀 vector,每一列長度可以不一樣,剛好裝五種高度不同的形狀。
兩種寫法答案完全一樣、都是滿分。模擬版照題意做、不需要任何觀察;簡潔版少開一張地圖、程式短了一半,但它成立的前提是「每一列靠右對齊、只水平移動」——形狀或規則一變(例如某個形狀有一列不靠右),還是得回到模擬版。
測過再交:範例沒有 D,也抓不到 E 抄反
範例 1 只有 B——它只是子題組 1 的驗收。範例 2 有 C、A、E、B,卻沒有 D;更麻煩的是它連 E 抄反都抓不到:把 E 左右鏡射成 #./##/## 跑範例 2,E 上面那一格會落在不同的行,最後的空格數和丟棄數卻一模一樣。「形狀有沒有抄對」是這題最容易錯、範例又幾乎不幫你檢查的地方,用手算得動的小倉庫自己補:
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
2 3 1 / D 0 |
2 0 |
D 剛好貼右牆放進 \(2 \times 3\),上面那列左邊兩格是永遠到不了的洞——但洞仍然是空格。把 w 加總當佔用格數的程式印 0 0 |
2 4 2 / B 0 / D 0 |
1 0 |
範例沒有 D:D 上面那一格卡在 B 右邊、下面三格在 B 底下,剛好放得下、一格都推不動。D 左右抄反或上下抄反的程式都會把 D 丟掉,印 5 1 |
3 4 2 / B 0 / E 0 |
4 0 |
同一件事換成 E:E 抄反、或是把貨物從左邊往右推的程式印 9 1——這幾種錯兩個範例都抓不到 |
1 3 2 / B 0 / B 0 |
0 1 |
剛好貼牆算放得下、第二件才丟棄:寫成 >= C 就丟棄的程式印 3 2。子題組 1 版就能驗 |
四筆都親眼看過正確,這題就穩了。
常犯錯誤
- 最右邊放不下就往左繼續找位置:貨物穿不過障礙、到不了障礙左邊的洞。範例 2 的
B 0會被塞進第 0 列左邊,印10 1(該印13 2)。 - D、E 抄反(左右鏡射或上下顛倒),或把貨物從左邊往右推:A、B、C 左右對稱、看不出差別,兩個範例全過(範例 2 有 E 也一樣);自測表第 2、3 列印
5 1/9 1。 - 每一列各自往左推(
w[y + i] += tile[i],忘了整件貨物要一起停):範例 2 印10 1。 - 用
w加總當佔用格數:被堵住的洞也是空格。範例 1 過、範例 2 印3 2。 w[y + i] + tile[i] >= C就丟棄:剛好貼右牆是放得下的。範例 1 過、範例 2 印17 3。- 判定放不下之後忘了
continue:丟棄的貨物照樣被往左推、被標記。範例 1 印2 2。