---
title: 'APCS 2024/10 實作題題解 — C++'
disqus: hackmd
---

# APCS 2024/10 實作題題解 — C++
:::info
:bulb: 此筆記為APCS 2024年10月實作題考試的題目詳解。每一題的題解都包含解題思路、C++範例程式碼。
:::

## 第一題 裝飲料 (ZeroJudge o711.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=o711)
:::success
有一個杯子，可將其體積視為由兩個長方體組成（如下圖），下方的長方體底面積為 $w1 × w1$ $cm^2$，高為 $h$~1~ $cm$，上方的長方體底面積為 $w2 × w2$ $cm^2$，高為 $h$~2~ $cm$。


一開始杯子為空。要裝 $n$ 次飲料，每一次裝 $v$ $cm^3$ 容量的飲料，當水杯滿時水位不再上升。問這 $n$ 次倒飲料中水位上升變化量最高是幾 $cm$。
:::

### 輸入 / 輸出說明
| **輸入說明** | **輸出說明** |
|:-:|:-:|
|  |  |

### 解題思路
:::warning
依題目列變數，並透過 a1, a2 存下方與上方的長方體**底面積**，每次裝 drink 容量的飲料， v1 = v1 - drink 代表倒入後 v1 剩餘的體積，v2 = v2 - drink 代表倒入後 v2 剩餘的體積，並將之透過自訂 height 函式處理後回傳倒入後增加的高度，將兩個長方體增加的水位加起來後與 max 比較，若此杯飲料水位增加量 h > max，則將 max 設為 h，最後輸出 max 即為答案。

height 函式：
1. 當 v < 0 時
將 drink + v，因為 v 是剛剛減去 drink 的值，因此若要求得倒入的量時就將 drink 加上 v，而高度就是 (drink + v) / a。
2. 當 v >= 0 時
代表這一杯飲料的體積 drink 可以完全倒入該長方體內，因此高度就是 drink / a。
:::

### 範例程式碼

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

int drink;

int height(int v, int a) 
{
	int h = 0;
	
	if (drink == 0)
		return 0;
	
	if (v < 0) {
		h = (drink + v) / a;
		drink = abs(v);
	}
	else {
		h = drink / a;
		drink = 0;
	}
	
	return h;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, n, max = 0;
	int w1, w2, h1, h2;
	int a1, a2, v1, v2;
	
	cin >> n >> w1 >> w2 >> h1 >> h2;
	
	a1 = w1 * w1;
	a2 = w2 * w2;
	v1 = a1 * h1;
	v2 = a2 * h2;
	
	for (i=0;i<n;i++) {
		cin >> drink;
		
		int h = 0;
		
		if (v1 > 0) {
			v1 = v1 - drink;
			h = height(v1, a1);
		}
		
		if (v2 > 0) {
			v2 = v2 - drink;
			h += height(v2, a2);
		}
		
		if (h > max)
			max = h;
	}
	
	cout << max;

	return 0;
}

### 運行結果
<font color="#00BB00">**AC**</font> (3ms, 348KB)

## 第二題 蒐集寶石 (ZeroJudge o712.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=o712)
:::success
有一個 $M × N$ 的地圖，每一格的數字紀錄著寶石的數量，如果數字是 -1 代表牆壁。
有一位機器人一開始位於 $(r, c)$ 的位置上且方向朝右邊，他遵循著以下規則行走。
1. 若機器人位於的格字內寶石數量為 $0$，則機器人程式終止。
2. 機器人維護著一個分數 score，將 score 加上當前格的寶石數量，並且撿起一顆寶石。
3. 若 score 是 $k$ 的倍數，則向右轉 90 度。
4. 若機器人面向的格子是牆壁或是超出邊界，則繼續向右轉 90 度直到面向的格子非牆壁或非超出邊界，並回到第 1 步。


例如機器人一開始在座標 $(2, 1)$ 且 $k = 2$，向右走兩步之後分數為 $3+2+3=8$，由於 $8$ 是 $2(k=2)$ 的倍數所以向右轉 $90$ 度。接下來往下走一步分數變為 $11$，需要向右轉 $2$ 次 $90$ 度才不會面向牆壁或是邊界外的格子。

接下來向前走一步走到座標 $(2, 3)$，由於先前已經拿走一顆寶石，該位置的寶石數量變為 $2$
，因此分數變為 $13$，再繼續往上走兩步到 $(0, 3)$ 處分數為 $16$，由於 $16$ 為 $2(k=2)$ 的倍數所以向右轉 $90$ 度。

向前走一格到 $(0, 4)$ 後需要向右轉兩次 $90$ 度，回到 $(0, 3)$ 後由於寶石數量為 $0$，機器人停止。過程中機器人總共撿了 $8$ 顆寶石。
:::

### 輸入 / 輸出說明
| **輸入說明** | **輸出說明** |
|:-:|:-:|
|  |  |

### 解題思路
:::warning
moves = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

我將 moves 陣列作為每次移動的依據，由於題目一開始設定為向右，因此向 dir 設定為 0，對應的 moves[0] = {0, 1}，即列不變（縱向，即 Row）、行加1（橫向，即 Column），後面向右轉時使用 dir = (dir + 1) % 4（確保 dir + 1 = 4 的時候會歸零）。

我將 jewel 作為儲存地圖上寶石數量的陣列，一開始先將地圖全部設為牆壁（可將規則 4. 中提及的遇到牆壁或邊界當作同一件事）。

第一個 while 迴圈不斷讓機器人前進，並利用 end 函式判斷是否達停止條件，若達成則將 while 迴圈 break 掉，如果沒有達成的話就是該位置可繼續移動，將 score 加上該位置的寶石數量，並將 t + 1（最後輸出的是 t，因為題目要求的是機器人蒐集的寶石數量），最後才將該位置寶石數量 - 1。

第 52 行是題目中的規則 3. 要求的強制右轉 90 度，而第二個 while 迴圈則是讓機器人選擇正確的下一個位置的方向，並將之設為下一個 r、c。
:::

### 範例程式碼

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

int jewel[102][102];
int moves[4][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int end(int r, int c)
{
	int i, ok = 4;
		
	if (jewel[r][c] == 0)  //當前位置無寶石 
		return 1;
			
	for (i=0;i<4;i++)  //判斷四面是否都是牆壁
		if (jewel[r+moves[i][0]][c+moves[i][1]] == -1)
			ok--;
				
	if (ok == 0)  //四面都是牆壁 
		return 1;
		
	return 0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, j;
	int m, n, k, r, c;
	int dir = 0, score = 0, t = 0;
	
	cin >> m >> n >> k >> r >> c;
	
	r++;
	c++;
	
	memset(jewel, -1, sizeof(jewel));  //預設為全部都是牆壁 
	
	for (i=1;i<=m;i++)
		for (j=1;j<=n;j++)
			cin >> jewel[i][j];
			
	while (true) {
		if (end(r, c))  //符合結束條件
			break;
		
		score += jewel[r][c];
		t++;
		jewel[r][c]--;
		
		if (score % k == 0)  //score是k的倍數 
			dir = (dir + 1) % 4; 
		
		int temp_r, temp_c;
		
		while (true) {
			temp_r = r + moves[dir][0];
			temp_c = c + moves[dir][1];
			
			if (jewel[temp_r][temp_c] == -1)  //面向牆壁或邊界外
				dir = (dir + 1) % 4; 
			else
				break;
		}
		
		r = temp_r;
		c = temp_c;
	}
	
	cout << t;

	return 0;
}

### 運行結果
<font color="#00BB00">**AC**</font> (4ms, 384KB)

## 第三題 連鎖反應 (ZeroJudge o713.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=o713)
:::success
在一個 $M × N$ 的網格中，每一格可能是石頭或是炸彈，具體包含以下數字：

`-1` 表示石頭，無法被炸彈引爆，炸彈震波無法通過該格傳遞。
`-2` 表示初始炸彈的起始點，可以設定爆炸半徑。
其他整數表示該位置存在爆炸半徑為該數值的炸彈。
炸彈爆炸時，會影響周圍一定範圍內的格子。炸彈會以該格為中心擴散，若一個炸彈的爆炸半徑為 $v$，則會將從該格開始沿著上、下、左或右走 $v$ 步內可以走到的格子都引爆。若某一顆炸彈引爆的範圍中涵蓋到尚未引爆的炸彈，則會引發鏈鎖反應將尚未引爆的炸彈引爆，並依循著相同的規則發生鏈鎖反應。

目標是找出初始炸彈所需設置的最小爆炸半徑，使得至少有 $q$ 個格子被引爆。
:::

### 輸入 / 輸出說明
| **輸入說明** | **輸出說明** |
|:-:|:-:|
|  |  |

### 解題思路
:::warning
這題我自己花的時間會比第四題長很多，建議先規劃好解題方向後再做。我 NA 了 20 幾次後，選擇先把流程圖寫在紙上再做，結果就 AC 了。

這題我使用 **BFS 廣度優先搜尋演算法** (DFS 應該也可以，我沒有嘗試)、**Binary Search 二分搜尋**、**剪枝**。

1. 二分搜尋
因為題目要求半徑多大的**初始**炸彈，才能使 $q$ 個格子被引爆，所以為了降低時間複雜度，使用二分搜尋從 $0$ ~ $n × m$ (因為有 `-1` 石頭的存在，因此最大的可能會是 $n × m$，若題目將石頭這個障礙物刪除，則範圍會變成 $0$ ~ $2 × (n - 1)$ ) 中找到能引爆 $q$ 個格子以上的半徑中最小的一個。
2. BFS & 剪枝
* 這裡的 BFS 限制條件並非已走過的格子就不允許再走一遍，理論上是可以走第二遍以上的，但要小心避免無窮迴圈(沒錯，我卡 20 幾次就是這個原因)。我用 visited 儲存其中某一個炸彈波及到該格時所剩下的爆炸半徑(我叫他 A)，如果又有一個新的炸彈波及到此，將新的炸彈剩下的爆炸半徑(我叫他 B)與原爆炸半徑(A)比較，如果 B > A 就允許走到這個位置，反之若 B <= A 則不允許再走一遍(**這邊說的就是剪枝**)。這邊要注意第 18 行，我會先把 visited 全部設為 -1，避免儲存時剩餘爆炸半徑剛好就是 0 的例外狀況。

* 另外就是判斷完上面所說的部份後，如果下一格是**尚未觸發** (visited[y][x] == -1)的炸彈的話，就將他的爆炸半徑設為他爆炸的半徑(題目輸入的數字)。
:::

### 範例程式碼

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

int start_x, start_y;
int m, n, q;
int a[600][600], visited[600][600];
int moves[4][2]={{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  //上下左右 

struct boom_range {
	int y, x, t;  //y, x儲存該位置的座標  | t儲存剩餘能量 
};

int bfs(int start_range)
{
	int i, affected = 1, total = 0;  //affected 紀錄受波及格子數
	queue<boom_range> spread;  //儲存會波及的地方 
	
	memset(visited, -1, sizeof(visited));
	//將 visited 儲存的受波及後該格剩餘的能量，避免後面 power 跟 visited 都是 0會出現例外 
	
	spread.push({start_y, start_x, start_range});
	
	while (spread.size() > 0) {
		total++;
		boom_range point = spread.front();
		spread.pop();
		
		int power = point.t;
		
		if (power > 0) {
	          for (i=0;i<4;i++) {
		    int next_y, next_x, next_power;
		    next_y = point.y + moves[i][0];
		    next_x = point.x + moves[i][1];
				
		    next_power = power - 1;
				
		    if (next_power > visited[next_y][next_x] && a[next_y][next_x] >= 0) {  
			//若新給予的能量比其他炸彈給予的能量大且不是石頭、邊界或初始炸彈 
		      if (visited[next_y][next_x] == -1) {  //若是先前尚未受波及
		        affected++;
						
		        if (a[next_y][next_x] > next_power)
		        //若是尚未引發的炸彈且爆炸能量 > 剩餘能量 
			  next_power = a[next_y][next_x];
		      }
						
		      spread.push({next_y, next_x, next_power});
              
		      visited[next_y][next_x] = next_power;
		      //儲存該位置剩餘能量
		    }
		  }
		} 
	}
	
	if (affected >= q)
		return 1;
	
	return 0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int i, j;
	
	cin >> m >> n >> q;
	
	memset(a, -1, sizeof(a));  //預設全部都是石頭 (避免之後須考慮邊界問題) 
	
	for (i=1;i<=m;i++) {
		for (j=1;j<=n;j++) {
			cin >> a[i][j];
			
			if (a[i][j] == -2) {
				start_y = i;
				start_x = j;
			}
		}
	}
	
	int l = 0, r = n * m;
	
	while (l <= r) {
		int mid = (l + r) / 2;
		
		if (bfs(mid))
			r = mid - 1;
		else
			l = mid + 1;
	}
	
	cout << l;

	return 0;
}

### 運行結果
<font color="#00BB00">**AC**</font> (69ms, 3.1MB)

## 第四題 搭到終點 (ZeroJudge o714.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=o714)
:::success
有一個數線從 $0$ 到 $m$，你一開始在位置 $0$ 上，想要搭公車到位置 $m$ 處。
有 $n$ 台公車路線可以選擇，每一公車路線都有其行駛的起點和終點。

例如你想要到位置 $m=9$，且有 $n=5$ 條公車路線如下

| 公車路線編號 | 1 | 2 | 3 | 4 | 5 |
| -------- | -------- | -------- | -------- | -------- | -------- |
| 路線起終點 | [0, 4] | [4, 6] | [0, 6] | [3, 7] | [5, 9] |

你可以任意地決定公車何時出發，並且在公車的路線範圍內都可以上車，但一定會搭到該路線的終點才下車，且不可在同一位置同時上下車。

你想知道總共有幾種搭車方式可以到位置 $m$。如上述例子總共有 $7$ 種搭車方式，分別如下列：
(1) 1 -> 2 -> 4 -> 5 (先搭乘路線1 到 位置 $4$，再搭乘路線2 到位置 $6$，接著搭乘路線4 到位置 $7$，最後搭乘路線5 到位置 $9$ )
(2) 1 -> 2 -> 5
(3) 1 -> 3 -> 4 -> 5
(4) 1 -> 3 -> 5
(5) 1 -> 4 -> 5
(6) 3 -> 4 -> 5
(7) 3 -> 5

由於搭乘方式數量可能很大，請輸出搭乘方式數量 mod $p$ 的結果。
:::

### 輸入 / 輸出說明
| **輸入說明** | **輸出說明** |
|:-:|:-:|
|  |  |

### 解題思路
:::warning
這題我一開始是用**前綴和**、**二分搜尋法**去做，最終得到 60 %，我檢討了之後發現是空間用太多了，最後把 station 從陣列改成 Map 就成功 AC。

首先我建立一個名為 bus 的 struct，struct 包含兩個 long long int，分別是每一個路線的起點(start)以及終點(end)並將它應用在 route 陣列上，這樣我們就可以透過自定義的規則(rule 函式)排序路線，這邊我是透過 **終點** 去排序，因為題目說公車只能坐到終點但能中途上車，因此這可以確保我們擺在索引值比較後面的路線只需要找索引值前面的終點是否在路線起終點之間(是否可以上車)，而且是連續的，不會中途某條線是不再範圍內的。

而尋找前面的路線的終點是否在此路線的起終點之間(是否可以上車)則是透過 **二分搜尋法** 搜尋，依照我在程式碼標示的部分，binary_search 函式符合條件中編號最小到編號最大的(最小的 begin - 1、最大的 ends)的回傳方式不同，因為我們找的範圍是此路線的 **[start, end)**，如果前面的路線的終點剛好是此路線的終點就不能算進這條線(如果算進去的話就像你搭 A 車到站了然後又上另一台 B 車刷兩次卡上下車)。

由於題目要求的是搭乘方式數量除以 $p$ 的餘數，因此我們找出的該路線搭乘方式數量就直接算 $p$ 的餘數，不然數字會過大，而計算的方式就是 binary_search 得到的最大編號的前綴和 - 最小編號的前綴和再除以 $p$ 的餘數，即 total = (prefix[ends] - prefix[begin-1] + p) % p; (這裡先 +p 的原因是防止兩個相減是負數)，則此路線累積的前綴和 prefix[i] 就是 total + 上一條路線的前綴和 prefix[i-1] 再除以 $p$ 的餘數。

最後我們透過 map (取名 station)來儲存每一個終點的數量和除以 $p$ 的餘數，最後輸出 station[所求終點 m] 即可得到答案，這邊原本我是用陣列去存，但終點數量並沒有那麼多，因此會有很多 0 浪費許多空間，而 map 即可解決此問題。
:::

### 範例程式碼

#include <bits/stdc++.h>
using namespace std;
typedef int long long ull;

struct bus {
	ull start, end;
};

int rule(bus a, bus b)  //排序規則
{
	if (a.end != b.end)  //路線終點小的往前 
		return a.end < b.end;
	else  //路線終點一樣，則路線起點小的往前 
		return a.start < b.start;
}

int binary_search(bus route[], ull l, ull r, ull key, int mode)  //二分搜尋法
{
	ull mid = (l + r) / 2;
	
	while (l <= r) {
		mid = (l + r) / 2;		

		if (route[mid].end >= key)
			r = mid - 1;
		else
			l = mid + 1;
	}
	
	if (mode == 0)  //找 >= key 的
		return l;
	else if (mode == 1)  //找 < key 的
		return r;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i;
	ull n, m, p;
	
	cin >> n >> m >> p;
	
	bus route[n+1];  //公車路線
	ull prefix[n+1]={}; 
	map<ull, ull> station;  //儲存到該站牌的方法數 
	
	route[0].start = -1;
	route[0].end = -1;
	
	for (i=1;i<=n;i++)  //輸入路線起點 
		cin >> route[i].start;
		
	for (i=1;i<=n;i++)  //輸入路線終點 
		cin >> route[i].end;
		
	sort(route, route + n + 1, rule);  //將路線依據 rule 排序 
	
	for (i=1;i<=n;i++) {
		ull begin, ends, total = 0;
		
		begin = binary_search(route, 0, n, route[i].start, 0);  //搜尋第一個 >= 此路線起點為 begin 
		ends = binary_search(route, 0, n, route[i].end, 1);  //搜尋最後一個 < 此路線終點的為 ends 
		
		total = (prefix[ends] - prefix[begin-1] + p) % p;  //找到這條路線有幾種搭車方式 % p 的結果 
			
		if (route[i].start == 0)  //起點在 0 固定有 1 條路線 
			total++;
		
		prefix[i] = (total % p + prefix[i-1] % p) % p;  //搭車方式的前綴和
		
		if (station.find(route[i].end) != station.end())  //紀錄到某一個點 (route[i].end) 的搭車方式 % p 的結果 
			station[route[i].end] += total % p;
		else
			station[route[i].end] = total % p;
	}
		
	cout << station[m] % p;

	return 0;
}

### 運行結果
<font color="#00BB00">**AC**</font> (0.2s, 13.2MB)

###### tags: `APCS實作題`

:::danger
查看更多資訊請至：https://www.tseng-school.com/
:::