# APCS 2024 年 10 月 AA 競程 dreamoon 老師的參考作法
:::success
以下題目的講解都已假設大家已擁有 AA 競程 Level 0 所介紹過的所有語法知識，而 Level 0 的教學內容可參考以下兩個網頁提到的課程大綱：
1. [AA 競程 Level 0 語法班](https://aacpschool.com/2024-3-base2/)
2. [AA 競程 Level 0 競程入門班](https://aacpschool.com/2024-4-start/)
:::
## P1. [裝飲料](https://zerojudge.tw/ShowProblem?problemid=o711)
此題網路上已有非常多參考程式碼，這裡介紹一個比較特別一點的實作方法。
在以下範例程式碼中，對於每次裝飲料實際算飲料身高多少高度的方法比較特別，可看到它並不是直接用 $O(1)$ 的方法 計算，而是直接用迴圈，想像成一次只裝一公分高度的飲料，要裝幾次才能把此次要裝的飲料份量用完。
此種寫法雖然時間複雜度比較高(時間複雜度是 $O(n + h1 + h2)$)，但能讓我們不要列出太複雜的數學式就能解出此題，是使用更高的時間複雜度來取代思考程式碼細節的時間。這是程式競賽解題的一個很重要的技巧，可大量減少寫程式碼的時間。
```cpp=
#include<iostream>
using namespace std;
int main() {
int n;
cin >> n;
int w1, w2, h1, h2;
cin >> w1 >> w2 >> h1 >> h2;
int ans = 0;
// h1, h2 在迴圈裡模擬的過程中代表還剩下多少高度可以裝水
while(n--) {
int x;
cin >> x;
int added = 0; // 此次到飲料總共增加多少公分
// 只要第一個長方體還沒裝滿，且還有還沒到進去的飲料，就先倒進去一公分
while(h1 > 0 && x > 0) {
added++;
h1--;
x -= w1 * w1;
}
// 只要第二個長方體還沒裝滿，且還有還沒到進去的飲料，就先倒進去一公分
while(h2 > 0 && x > 0) {
added++;
h2--;
x -= w2 * w2;
}
if(ans < added) ans = added;
}
cout << ans << '\n';
}
```
## P2. [蒐集寶石](https://zerojudge.tw/ShowProblem?problemid=o712)
此題在歷屆的第二題來說，老師感覺起來算是比較簡單的，因位幾乎敘述裡的每一句話都直接對應到一小段程式碼，所以只要對二維的陣列(或 vector 套 vector) 以及模擬一個機器人在二維地圖走動的題目熟悉的人(也就是考古題做得多的人啦)，都能按照以前的做題經驗把此題做出來。
這裡就強調幾個兩個實作重點：
1. 把右下左上這 $4$ 個移動方向垂直座標和水平座標各會移動多少距離儲存在陣列裡，這樣子就只要維護一個變數 ---- 代表現在機器人面向哪個方向，這樣子程式碼實作起來就比較乾淨。
2. 雖然用二維陣列儲存地圖資訊也可以實作出此題，但考量到在有些比賽出題者可能不小心出測試資料時，會超出題目敘述寫的地圖大小範圍，所以用 vector 套 vector 的方式來裝地圖資訊，可根據輸入來決定容器大小，就不用擔心出題者犯的錯造成自己的不便，另外，這樣寫也可以根據 vector 物件直接取得地圖大小資訊。
:::danger
請注意，老師是反對使用變數當陣列大小那一派的(也就是 [VLA](https://zh.wikipedia.org/zh-tw/%E5%8F%AF%E8%AE%8A%E9%95%B7%E9%99%A3%E5%88%97))。
所以老師不會使用 ``int grid[N][M]`` 這種寫法，因為這不符合 C++ 的標準。
:::
```cpp=
#include<iostream>
#include<vector>
#define SZ(X) ((int)(X).size())
using namespace std;
const int MAX_SIZE = 101;
const int dx[] = {0, 1, 0, -1}; // dx[i] 紀錄第 i 個方向會往垂直方向移動多少個格子
const int dy[] = {1, 0, -1, 0}; // dy[i] 紀錄第 i 個方向會往水平方向移動多少個格子
// valid(grid, r, c, dir) 用來判斷第 r 個 row 和第 c 個 column 這個位置往第 dir 個方向移動一部後，是否是個機器人可以站上去的座標
bool valid(const vector<vector<int>> &grid, int r, int c, int dir) {
r += dx[dir];
c += dy[dir];
return r >= 0 && c >= 0 && r < SZ(grid) && c < SZ(grid[0]) && grid[r][c] != -1;
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int M, N, k, r, c;
cin >> M >> N >> k >> r >> c;
vector<vector<int>> grid(M, vector<int>(N));
for(int row_id = 0; row_id < M; row_id++) {
for(int col_id = 0; col_id < N; col_id++) {
cin >> grid[row_id][col_id];
}
}
int score = 0; // 紀錄當前分數
int dir = 0; // 紀錄當前機器人方向
int gem_num = 0; // 紀錄當前已經減了多少個寶石
while(grid[r][c]) { // 當目前所在的位置有至少一顆寶石時，繼續模擬
score += grid[r][c]; // 分數加上目前的位置上的寶石數量
grid[r][c]--; // 撿起一個寶石，所以該位置寶石數量減 1
gem_num++; // 撿起的寶石多一個
if(score % k == 0) { // 如果目前的分數是 k 的倍數，往右轉。而往右轉就是方向的編號加 1，但加到 4 時要變回 0
dir = (dir + 1) % 4;
}
// 當發現往第 dir 個方向移動會移動到不合法的位置，就要再向右轉一次
while(!valid(grid, r, c, dir)) dir = (dir + 1) % 4;
r += dx[dir];
c += dy[dir];
}
cout << gem_num << '\n';
}
```
## P3. [連鎖反應](https://zerojudge.tw/ShowProblem?problemid=o713)
:::success
閱讀此題題解除了需要基礎語法知識外，還需要的前置知識有：
1. BFS(廣度優先搜尋)
2. 遞迴函式
:::
要能解出此題的關鍵就是了解 [BFS(廣度優先搜尋)](https://zh.wikipedia.org/zh-tw/%E5%BB%A3%E5%BA%A6%E5%84%AA%E5%85%88%E6%90%9C%E5%B0%8B) 的概念，若沒此知識，要在考試中做出此題相當困難。
且此題實作較為複雜，細節較多，老師會猜測若這次拿到滿級分人數很少，多半是因為這題實作寫壞，或是這題花太多時間導致其他題寫不完。此題會是個練習實作能力的相當不錯的題目。
---
題目既然是要問初始炸彈的引爆半徑至少要多少，那我們就依序枚舉所有距離初試炸彈 $0$ 的所有位置，試試看這些位置的炸彈都引爆數量是否已達到 $q$；否則繼續檢查距離初始炸彈為 $1$ 的所有位置引爆後又會是怎樣、距離初始炸彈為 $2$ 的所有位置引爆後又會怎樣...看什麼時後被炸到的格子數量達到 $q$，此時枚舉到的引爆半徑就是答案。
所以此題的第一步是把初始炸彈位置當作起點做一次 bfs，對於每個非負整數 $i$，都算出距離初始炸彈距離為 $i$ 的所有位置並儲存下來。
之後就要按梨初始炸彈距離小至大枚舉所有炸彈。當枚舉到一個炸彈時，也要再用一次 bfs 去看能炸到哪些位置，並使用遞迴的概念繼續引爆新的炸彈，要確保時間複雜度正確的關鍵是**同一個炸彈只需引爆一次**，也就是說，若一個炸彈已被枚舉並執行過 bfs 了，下次若在枚舉到同個炸彈，就不要再做 bfs 了。
這地餓做法時間複雜度可這樣計算：除了初始炸彈外，其他炸彈的引爆距離都不超過 30，所以每個炸彈會炸到的位置絕不會超過 2000 個，而至多只有 1500 個炸彈，所以除了起始位置的炸彈外，其他所有炸彈做 bfs 時能拜訪到的格子數絕不會超過 1500 * 2000，對於時限 1 秒來說，並不是個太大的數字，所以此做法就能通過。
若另格子上數字的上限為 $d$，大於 0 的數字數量為 $k$，此題時間複雜度可做到 $O(NM + d \cdot k^2)$，不過老師下面示範的程式碼實際上實作的程式碼時間複雜度是 $O(NM + d \cdot k^2 \cdot \log(k))$。因為引爆非初始炸彈的其他炸彈時，bfs 是使用 map 來記錄每個格子的距離。
```cpp=
#include<iostream>
#include<queue>
#include<map>
#include<algorithm>
#define SZ(X) ((int)(X).size())
using namespace std;
// (dx[i], dy[i]) 代表上下左右 4 個方向的垂直和水平位移
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
// Location 是用來記錄地圖位置的結構體，同時有一些方便解題的成員函示
struct Location {
int r, c;
// invalid 用來判斷此位置對於 a 這個地圖是否合法
bool invalid(const vector<vector<int>> &a) {
return r < 0 || c < 0 || r >= SZ(a) || c >= SZ(a[0]) || a[r][c] == -1;
}
// go_ahead 會回傳此位置往第 dir 個方向後會移動到哪個位置
Location go_ahead(int dir) {
return {r + dx[dir], c + dy[dir]};
}
// 定義 Location 的小於運算子，這樣才能讓 set 裝 Location
bool operator < (const Location & b) const {
return r < b.r || (r == b.r && c < b.c);
}
};
// 因為 detonate 和 chain_exlosion 會互相引用，所以要先宣告比較晚出現的 detonate 這個函式
int detonate(const vector<vector<int>> &a, vector<vector<int>> &exploded, Location x);
// 在爆炸過程中，引爆了 bomb_pos 這個位置的炸彈，產生了新的連鎖引爆, a 和 exploded 分別是地圖及哪些位置已爆炸的資訊
int chain_explosion(const vector<vector<int>> &a, vector<vector<int>> &exploded, Location bomb_pos) {
int explosion_num = 0; // 用來儲存此次爆炸及其所影起的連鎖反應會多讓幾個位置被炸到
/* 以下是使用 bfs 來判斷此次炸彈引爆會炸到哪些位置。
* 其中一個位置是否曾經拜訪過，以及離爆炸起點距離的資訊直接使用 map<Location, int> dis 儲存，
* 這麽做是因為題目有說爆炸距離不超過 30，所以每個炸彈會炸到的位置一定不太多，
* 所以就算 map 的常數太大，也不會拖慢時間太多，並且不需重新宣告太大的陣列或 vector來記錄這些資訊
*/
queue<Location> bfs;
bfs.push(bomb_pos);
map<Location, int> dis;
dis[bomb_pos] = 0;
while(!bfs.empty()) {
auto me = bfs.front();
bfs.pop();
explosion_num += detonate(a, exploded, me); // 爆炸數量加上引爆 bfs 走到的這個位置會被連鎖引爆的位置數量
int my_dis = dis[me];
if(my_dis == a[bomb_pos.r][bomb_pos.c]) continue; // 如果此位置離炸彈距離已達到極限，就不會再繼續炸到隔壁位置
for(int dir = 0; dir < 4; dir++) {
Location nxt = me.go_ahead(dir);
if(nxt.invalid(a) || dis.count(nxt)) continue;
dis[nxt] = my_dis + 1;
bfs.push(nxt);
}
}
return explosion_num;
}
/* 引爆位置 x，如果不是第依次被炸就直接 return 0；否則若此位置有距離超過 0 的炸彈，
* 就遞迴計算算此炸彈引爆後能多炸幾個位置。
*/
int detonate(const vector<vector<int>> &a, vector<vector<int>> &exploded, Location x) {
if(exploded[x.r][x.c]) return 0;
exploded[x.r][x.c] = 1;
int explosion_num = 1;
if(a[x.r][x.c] > 0) explosion_num += chain_explosion(a, exploded, x);
return explosion_num;
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int M, N, q;
cin >> M >> N >> q;
vector<vector<int>> a(M, vector<int>(N));
Location initial_bomb; // 儲存要我們決定能炸的距離的炸彈位置
for(int i = 0; i < SZ(a); i++) {
for(int j = 0; j < SZ(a[0]); j++) {
cin >> a[i][j];
if(a[i][j] == -2) initial_bomb = {i, j};
}
}
/* 以下就是很普通的 bfs
* 只是多了一個 dis 的 vector，用 dis[L] 儲存所有距離初始炸彈 L 的所有位置
*/
queue<Location> bfs;
vector<vector<int>> visited(M, vector<int>(N));
vector<vector<int>> dis(M, vector<int>(N));
bfs.push(initial_bomb);
visited[initial_bomb.r][initial_bomb.c] = 1;
vector<vector<Location>> pos(N * M);
while(!bfs.empty()) {
auto me = bfs.front();
bfs.pop();
pos[dis[me.r][me.c]].push_back(me);
for(int dir = 0; dir < 4; dir++) {
Location nxt = me.go_ahead(dir);
if(nxt.invalid(a) || visited[nxt.r][nxt.c]) continue;
bfs.push(nxt);
visited[nxt.r][nxt.c] = 1;
dis[nxt.r][nxt.c] = dis[me.r][me.c] + 1;
}
}
vector<vector<int>> exploded(M, vector<int>(N)); // 用來記錄哪個些位置已被炸
int detonated_num = 0;
/* 依序引爆所有距離初始炸彈 0, 1, 2, ... 的所有炸彈，
* 過程中 q 的意思代表還要再多炸幾個位置，
* 當某個距離所有炸彈都炸完後，發現 q <= 0 代表此時枚舉到的距離就是答案。
*/
for(int ans = 0; ;ans++) {
for(auto x: pos[ans]) detonated_num += detonate(a, exploded, x);
if(detonated_num >= q) {
cout << ans << '\n';
return 0;
}
}
}
```
## P4. [搭到終點](https://zerojudge.tw/ShowProblem?problemid=o714)
:::success
閱讀此題題解除了需要基礎語法知識外，還需要的前置知識有：
1. 動態規劃的基本概念
2. 快速區間求和
3. [求和符號](https://zh.wikipedia.org/zh-tw/%E6%B1%82%E5%92%8C%E7%AC%A6%E8%99%9F)的知識
:::
此題會依序講解不同測試資料範圍內的作法，並在講解之前，先補充相關的數學知識
### 零、關於「答案除以 $p$」的相關知識
此題是個在「競程」中常見動態規計數劃題，但老師覺得這樣的類型的題目出現在 APCS 這樣的檢定是很奇怪的，因為此題要求輸出的答案必須是除以 $p$ 的餘數，這樣的問題就必需擁有[同餘運算](https://zh.wikipedia.org/zh-tw/%E5%90%8C%E9%A4%98)相關的知識，這樣的知識甚至在台灣的高中義務教育並沒有特別強調。雖然這在「競程比賽」上是相當基礎的知識，有放在 AA 競程課程的 Level 1 裡介紹，但這在一般程式相關領域算是比較偏門的知識。所以會有部份參加檢定的同學光是看到題目要求輸出答案除以 $p$ 的餘數這件事就卡住而放棄了吧 🥲
所以在介紹這題的作法前，先強調一下一個基礎的關於題目有「請輸出答案除以 $p$ 的餘數」的基本知識：
:::info
首先，定義 $x\ mod\ p$ 的意思是 $x$ 除以 $p$ 的餘數，且此於數的範圍一定要落在 $0$ 至 $p-1$ 之間，且 $mod$ 運算的優先級和乘法及除法以一樣。
我們若要計算一個運算式運算完後除以 $mod\ p$ 的結果，且此運算式出現的運算子只有「加」、「減」、「乘」，那麼我們可以在運算式子裡任意地方插入$\mod p$ 這樣的運算，例如 $(3 \times 5 \times 7-2*10)\ mod\ p = ((3 \times 5)\ mod\ p \times 7\ mod\ p - 2 \times 10\ mod\ p)\ mod\ p$
於是若遇到需要輸出答案除以 $p$ 題目，就可以在過程中隨意地穿插除以 $p$ 的運算來防止計算過程中發生整數溢位(在 C++ 及 java 會有此情況)，或是防止運算過程出現的數字太大而造成計算太慢(在 python 或用 java 的 BigInteger 或有此情況)
:::
在此題，運算過程可以只出現加法，所以每當要做加法時，我們會使用以下函式 $add\_with\_mod(x, y, p)$ 來計算 $(x+y)\ mod\ p$ 的結果，來確保計算答案的過程中，所有的數字都落在 $0$ 至 $p-1$ 的範圍內，以防止整數溢位，並且最終能直接輸出儲存的數字。
```cpp=
int add_with_mod(long long x, long long y, int p) {
int res = (x + y) % p;
/* 要小心若 x+y 是負數，對 $p$ 取餘後仍會是負數，
* 所以計算完後還要檢查計算結果是否為負，
* 是負的話就要加上 p，使得運算結果總式落在 [0, p-1] 的範圍內
*/
if(res < 0) res += p;
return res;
}
```
### 一、$1 \le n, m \le 100$
首先定義 $st[i]$ 代表第 $i$ 個公車的出發位置，$ed[i]$ 代表第 $i$ 個公車的到達位置。
此子題能設計如下 dp 狀態及轉移式：
定義 $dp[x]$ 代表在同樣的公車配置下，終點是 $x$ 的答案，那麼可列出以下轉移式：
$$
\begin{cases}
dp[x] = 1，當\ x = 0 \\
dp[x] =\sum\limits_{i \in \{t | ed[t] = x\}}\sum_{j=1}^{ed[i] - 1} dp[i]，當\ x > 0
\end{cases}
$$
直覺的理解就是：最終若要在位置 $x$ 下車，那麼就枚舉最後一班搭的公車是哪一班，若是第 $i$ 班，那麼倒數第二班下車的位置可以是 $st[i] \sim ed[i] - 1$ 中的任何一個整數座標，所以只要把 $\sum_{j=1}^{ed[i] - 1}$ 加到 $dp[x]$ 裡即可。
此做法的時間複雜度為 $O(nm)$，參考程式碼如下：
```cpp=
#include<iostream>
#include<vector>
using namespace std;
int add_with_mod(long long x, long long y, int p) {
int res = (x + y) % p;
if(res < 0) res += p;
return res;
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int n, m, p;
cin >> n >> m >> p;
vector<int> st(n), ed(n);
for(int &x: st) cin >> x;
for(int &x: ed) cin >> x;
vector<vector<int>> bus_from(m + 1); // bus_from[x] 紀錄所有終點是位置 x 的巴士的起點位置資訊
for(int i = 0; i < n; i++) {
// 終點位置超出 m 的根本不需要考慮。
if(ed[i] <= m) bus_from[ed[i]].push_back(st[i]);
}
// 以下就是根據題解裡所列的 dp 轉移式計算出每個 dp 狀態的答案
vector<int> dp(m + 1);
dp[0] = 1 % p;
for(int x = 1; x <= m; x++) {
for(int s: bus_from[x]) {
for(int i = s; i < x; i++) {
dp[x] = add_with_mod(dp[s], dp[i], p);
}
}
}
cout << dp[m] << '\n';
}
```
### 二、$1 \le m \le 10^5$
此範圍若使用方才的 $O(nm)$ 演算法就會超時，要想辦法優化。
能優化的方法其實很單純，只要觀察到對時間複雜度裡的 $m$ 有貢獻的是這個式子 $\sum_{j=1}^{ed[i] - 1} dp[j]$ 的計算，並發現它就是在計算前綴和，所以只需要使快速區間求和的 $O(1)$ 演算法取代慢慢的用 $for$ 迴圈計算此式子，即可做到時間複雜度 $O(n + m)$。
參考程式碼如下：
```cpp=
#include<iostream>
#include<vector>
using namespace std;
int add_with_mod(long long x, long long y, int p) {
int res = (x + y) % p;
if(res < 0) res += p;
return res;
}
int get_sum(const vector<int> &prefix_sum, int st, int ed, int p) {
if(!st) return prefix_sum[ed];
return add_with_mod(prefix_sum[ed], -prefix_sum[st - 1], p);
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int n, m, p;
cin >> n >> m >> p;
vector<int> st(n), ed(n);
for(int &x: st) cin >> x;
for(int &x: ed) cin >> x;
vector<vector<int>> bus_from(m + 1); // bus_from[x] 紀錄所有終點是位置 x 的巴士的起點位置資訊
for(int i = 0; i < n; i++) {
// 終點位置超出 m 的根本不需要考慮。
if(ed[i] <= m) bus_from[ed[i]].push_back(st[i]);
}
vector<int> dp(m + 1);
vector<int> prefix_sum(m + 1); // prefix_sum[i] = dp[0] + dp[1] + ... + dp[i]
prefix_sum[0] = dp[0] = 1 % p;
for(int x = 1; x <= m; x++) {
for(int s: bus_from[x]) {
dp[x] = add_with_mod(dp[x], get_sum(prefix_sum, s, x - 1, p), p);
}
prefix_sum[x] = add_with_mod(prefix_sum[x - 1], dp[x], p);
}
cout << dp[m] << '\n';
}
```
### 三、$1 \le m \le 10^9$
要在此題得到滿分的話，用上一個程式碼也行不通，困難點在於我們計算 dp 狀態時要從 $1$ 枚舉到 $m$，但可發現大部分的 $x$ 值 $dp[x]$ 都是 $0$，所以我們只需要考慮那些是某些至少是某個公車終點的那些位置即可，一個相對簡單且直覺的優化方法就是把所有陣列都改成 STL 中的 map 就好啦！
除此之外也有利用「離散化」的概念的方法，有興趣者可參考[USACO GUIDE: Coordinate Compression](https://usaco.guide/silver/sorting-custom?lang=cpp#coordinate-compression) 自行學習
以下是使用 map 的參考程式碼：
```cpp=
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int add_with_mod(long long x, long long y, int p) {
int res = (x + y) % p;
if(res < 0) res += p;
return res;
}
int get_sum(const map<int, int> &prefix_sum, int st, int ed, int p) {
auto ed_iter = prefix_sum.upper_bound(ed);
ed_iter--;
if(!st) return ed_iter->second;
auto st_iter = prefix_sum.lower_bound(st);
st_iter--;
return add_with_mod(ed_iter->second, -st_iter->second, p);
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int n, m, p;
cin >> n >> m >> p;
vector<int> st(n);
map<int, vector<int>> bus_from; // bus_from[x] 紀錄所有終點是位置 x 的巴士的起點位置資訊
map<int, int> dp;
map<int, int> prefix_sum;
for(int &x: st) cin >> x;
for(int i = 0; i < n; i++) {
int ed;
cin >> ed;
if(ed <= m) {
bus_from[ed].push_back(st[i]);
prefix_sum[ed] = dp[ed] = 0;
}
}
prefix_sum[0] = dp[0] = 1 % p;
for(auto dp_iter = dp.begin(), pre_iter = prefix_sum.begin(); dp_iter != dp.end(); dp_iter++, pre_iter++) {
int x = dp_iter->first;
for(int s: bus_from[x]) {
dp_iter->second = add_with_mod(dp_iter->second, get_sum(prefix_sum, s, x - 1, p), p);
}
/* 由於我們要避免計算所有位置的前綴和，所以在計算前綴和時，
* 直接使用當前位置的 dp 值加上前一個存在公車終點的位置的前綴和值來得到
* 當前前綴和的值
*/
if(pre_iter != prefix_sum.begin()) {
pre_iter->second = add_with_mod(prev(pre_iter)->second, dp_iter->second, p);
}
}
cout << dp[m] << '\n';
}
```
:::info
**對競程選手的小提醒**
使用 map 的執行時間的常數比較大，所以若 $m$ 更大(如 $m \le 10^6$)時，上面附的參考程式碼仍會超時，雖然 APCS 不太可能這樣考，但若是競程比賽就難說了，遇到這種情況時，就得使用 AA 競程課程中強調過的離散化寫法唷！(也可自行在網上搜索「lower_bound 離散化」 來取得相關資訊)
:::
Sign in with Wallet
Connect another wallet