APCS 2024/06 實作題題解 — C++

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

第一題 特技表演 (ZeroJudge o076.)

題目

有一個城鎮有

$n$ 棟高樓，樓高分別為

$h$₁,

$h$₂,

$h$₃，市長想要在城鎮中心舉辦高空特技表演，該特技表演會從某棟大樓上朝右側滑翔至地面。為了表演人員的安全，滑翔的路徑樓高必須越來越低，請你找出一個最長的滑翔路徑。

輸入 / 輸出說明

輸入說明	輸出說明

解題思路

這題只需要儲存前一樓高 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;
}

運行結果

AC (2ms, 344KB)

第二題 電子畫布 (ZeroJudge o077.)

題目

有一個

$H\times M$ 的電子畫布，一開始數值都是

$0$ 代表未填色，接下來請模擬

$N$ 次畫筆操作。

每次畫筆操作為選一個座標

$(r,c)$ 停留

$t$ 秒，他會將曼哈頓距離

$<=t$ 的區塊染上顏色

$x$。若有多個顏色重複填到相同區塊，顏色的數值會累加起來。

請輸出

$N$ 次操作後的畫布狀態。

輸入 / 輸出說明

輸入說明	輸出說明

解題思路

因為曼哈頓距離 <= 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;
}

運行結果

AC (3ms, 344KB)

第三題 缺字問題 (ZeroJudge o078.)

題目

給定一個大小為

$K$ 個字母的集合和字串

$S$，求出在使用該集合所組出長度為

$L$ 字串中，不為字串

$S$ 子字串的最小字典序字串為何。

例如字母集合 {a, c, m}，其能組出長度為

$2$ 的字串字典序由小到大排序為

$aa<ac<am<ca<cc<cm<ma<mc<mm$。字串

$S$ 為

$accaamcm$，因此

$ma$ 為不在

$S$ 內的最小字典序字串。

輸入 / 輸出說明

輸入說明	輸出說明

解題思路

這個解法時間複雜度較高，請斟酌參考。

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

透過範例測資#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;
}

運行結果

AC (0.3s, 432KB)

tags: APCS實作題

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