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

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

## 第一題 特技表演 (ZeroJudge o076.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=o076)
:::success
有一個城鎮有 $n$ 棟高樓，樓高分別為 $h$~1~, $h$~2~, $h$~3~，市長想要在城鎮中心舉辦高空特技表演，該特技表演會從某棟大樓上朝右側滑翔至地面。為了表演人員的安全，滑翔的路徑樓高必須越來越低，請你找出一個最長的滑翔路徑。
:::

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

### 解題思路
:::warning
這題只需要儲存前一樓高 lh 與 當前樓高 h，並依據以下規則執行：
1. 當前樓高 >= 前一樓高 => 不滿足條件，將路徑長度 t 設為 1
2. 當前樓高 < 前一樓高 => 將路徑長度 t + 1

若當前路徑長度 t > 最大路徑長度 max，則將 max 設為 t。
:::

### 範例程式碼

#include <iostream>
using namespace std;

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i;
	int n, max = 0, t = 1;
	
	cin >> n;
	
	int lh, h;
	
	cin >> lh;
	
	for (i=1;i<n;i++) {
		cin >> h;
		
		if (h >= lh)
			t = 1;
		else
			t++;
			
		if (t > max)
			max = t;
			
		lh = h;
	}
	
	cout << max;

	return 0;
}

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

## 第二題 電子畫布 (ZeroJudge o077.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=o077)
:::success
有一個 $H × M$ 的電子畫布，一開始數值都是 $0$ 代表未填色，接下來請模擬 $N$ 次畫筆操作。

每次畫筆操作為選一個座標 $(r, c)$ 停留 $t$ 秒，他會將曼哈頓距離 $<= t$ 的區塊染上顏色 $x$。若有多個顏色重複填到相同區塊，顏色的數值會累加起來。

請輸出 $N$ 次操作後的畫布狀態。
:::

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

### 解題思路
:::warning
因為曼哈頓距離 <= t 的座標 (j, k) 一定滿足 $| j - r | <= t、| k - c | <= t$，因此我透過巢狀迴圈檢查 $r - t <= j <= r + t$ **、** $c - t <= k <= c + t$ 範圍內的座標是否滿足曼哈頓距離 $|j - r| + |k - c| <= t$，滿足條件則將位置的顏色染上 $x$，即 canva[j][k] = canva[j][k] + x。
:::

### 範例程式碼

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

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, j, k;
	int h, w, n;
	int r, c, t, x;
	
	cin >> h >> w >> n;
	
	int canva[h][w]={};
	
	for (i=0;i<n;i++) {
		cin >> r >> c >> t >> x;
		
		for (j=r-t;j<=r+t;j++)
			for (k=c-t;k<=c+t;k++)
				if (j >= 0 && j < h && k >= 0 && k < w && abs(j-r) + abs(k-c) <= t)
					canva[j][k] = canva[j][k] + x;
				  	
	}
	
	for (i=0;i<h;i++) {
		for (j=0;j<w;j++)
			cout << canva[i][j] << " ";
		cout << endl;
	}

	return 0;
}

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

## 第三題 缺字問題 (ZeroJudge o078.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=o078)
:::success
給定一個大小為 $K$ 個字母的集合和字串 $S$，求出在使用該集合所組出長度為 $L$ 字串中，不為字串 $S$ 子字串的最小字典序字串為何。

例如字母集合 **{a, c, m}**，其能組出長度為 $2$ 的字串字典序由小到大排序為 $aa < ac < am < ca < cc < cm < ma < mc < mm$。字串 $S$ 為 $accaamcm$，因此 $ma$ 為不在 $S$ 內的最小字典序字串。
:::

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

### 解題思路
:::warning
這個解法時間複雜度較高，請斟酌參考。

我這題使用遞迴的方法解。

透過範例測資#1為例，解釋遞迴邏輯：
1. 第一次遞迴選擇 'a' 加入暫存字串 $nc$ = *"a"*，此時 t = 0
2. 第二次遞迴選擇 'a' 加入暫存字串 $nc$ = *"aa"*，此時 t = 1
3. 第三次遞迴的 t = l = 2，返回第二次遞迴
4. 第二次遞迴選擇 'c' 加入暫存字串 $nc$ = *"ac"*，此時 t = 2

以此類推

t >= l 時（例如上述 3.）的字串為 $c$，在字串 $S$ 中尋找與 $c$ 相同的子字串，若無符合的子字串，輸出 $c$ 並結束遞迴，即可得解答（題目說輸入的字串 $K$ 由小到大排序，因此使用上述遞迴規則所得之暫存字串會由小到大）。
:::

### 範例程式碼

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

string k, s;
int l, sk;
int stop = 0;

int cw (int i, string c, int t)
{
	int j;
	string nc;
	
	if (stop == 1)
		return 0;

	if (t >= l) {
		int ok = s.find(c);
		
		if (ok == -1) {
			cout << c;
			stop = 1;
		}
		
		return 0;
	}
	
	for (j=0;j<sk;j++) {
		nc = c + k[j];
		cw(i+1, nc, t+1);
	}
}

int main ()
{
	int i;
	
	cin >> k >> l >> s;
	
	sk = k.size();
	
	cw(i, "", 0);

	return 0;
}

### 運行結果
<font color="#00BB00">**AC**</font> (0.3s, 432KB)

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

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