APCS 2023/10 實作題題解 — C++

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

第一題 機械鼠 (ZeroJudge m370.)

題目

有

$n$ 個位置上有食物，另外有一隻老鼠一開始位於位置

$x$。

老鼠在開始覓食前要選擇今天要往左邊或往右移動去尋找食物，經過食物時可以停下來吃食物，吃完後可以選擇繼續往相同方向移動，或者是結束今天的覓食。

請問老鼠最多能吃到多少個食物，以及最後停下來吃食物的位置。

輸入 / 輸出說明

輸入說明	輸出說明

解題思路

我利用 ti 儲存左邊的食物量、tx 儲存右邊的食物量，而 min 儲存最左邊的食物所在位置、max 儲存最右邊的食物所在位置。

當輸入值

$a<x$ 時，將 ti 加 1 並判斷 a 是否小於 min，若小於 min，則將 min 更改為 a。當輸入值

$a>x$ 時，將 tx 加 1 並判斷 a 是否大於 max，若大於 max，則將 max 更改為 a。

最後判斷 ti 與 tx 的大小，取大的輸出，並同時輸出 min 或 max 為最後停下的位置。

範例程式碼

#include <iostream>
using namespace std;

int main()
{
	
	int i;
	int x, n, a, min, max = 0, ti = 0, tx = 0;
	
	cin >> x >> n;
	
	min = x;
	
	for (i=0;i<n;i++) {
		cin >> a;
		
		if (a < x) {
			if (a < min)
				min = a;
			ti++;
		}
		else {
			if (a > max)
				max = a;
			tx++;
		}
	}
	
	if (tx > ti)
		cout << tx << " " << max;
	else
		cout << ti << " " << min;
	
    return 0;
}

運行結果

AC (2ms, 320KB)

第二題 卡牌遊戲 (ZeroJudge m371.)

題目

你有一個

$n\times m$ 大小的表格，你可以從中消除具有相同數值且之間沒有障礙物的兩個元素，並獲得分數。請問你可以獲得的最大得分。

每一種數字在表格中出現恰好兩次。消除兩個相同的數字

$x$ 時，可以獲得

$x$ 分。

消除規則：你可以垂直或水平地將兩個相同數值的元素消除，但消除的兩個元素之間不能有其他尚未消除的元素。

輸入 / 輸出說明

輸入說明	輸出說明

解題思路

這題可以直接暴力解出來，不斷移除相同的數字並增加得分即可。當遍歷一遍表格後得分並未增加，則視為終止。

題目宣稱每一種數字出現恰好 2 次，所以上下、左右各只需要選擇一個方向即可（我選擇下、右）。

範例程式碼

#include <iostream>
using namespace std;

int main ()
{
	int i, j, k;
	int n, m, point = 0;
	int ok = 1;
	
	cin >> n >> m;
	
	int x[n][m];
	
	for (i=0;i<n;i++)
		for (j=0;j<m;j++)
			cin >> x[i][j];
			
	while (ok == 1) {
		ok = 0;
		
		for (i=0;i<n;i++) {
			for (j=0;j<m;j++) {
				if (x[i][j] != -1) {
					for (k=i+1;k<n;k++) {
						if (x[k][j] == x[i][j] && x[i][j] != -1) {
							ok = 1;
							point = point + x[i][j];
							x[k][j] = -1;
							x[i][j] = -1;
							break;
						}
						
						if (x[k][j] != -1)
							break;
					}
					
					for (k=j+1;k<m;k++) {
						if (x[i][k] == x[i][j] && x[i][j] != -1) {
							ok = 1;
							point = point + x[i][j];
							x[i][k] = -1;
							x[i][j] = -1;
							break;
						}
						
						if (x[i][k] != -1)
							break;
					}
				}
			}
		}
	}
	
	cout << point;

	return 0;
}

運行結果

AC (3ms, 332KB)

第三題 搬家 (ZeroJudge m372.)

題目

忍者龜住在下水道中，他們正在準備搬家。下水道由

$n\times m$ 的矩陣表示，其中不同的字元代表著水管的開口方向。如果兩個水管可以互相連接，它們屬於同一個連通塊。你需要找出最大的連通塊的大小。

其中，X 代表十字架，而 H、I、F、7、L 分別代表其他不同形狀的水管。0 字元代表沒有水管連接的地方。

請注意，在某個連通塊內的水管可以連接，而不同連通塊的水管不會相互連接。

下面是一些可能的水管形狀：

水管的開口方向與字元對應關係
F: 右和下
H: 左和右
7: 左和下
I: 上和下
X: 上、下、左和右
L: 右和上
J: 左和上
0: 沒有水管

輸入 / 輸出說明

輸入說明	輸出說明

解題思路

這題我使用 dfs 解的時候，由於記憶體不夠，因此會卡在 95%，最終利用 bfs 即得到 AC 解。

由於我習慣用 queue 處理 bfs 排序，因此我透過一個簡單的換算方式，將二維陣列轉為一維陣列的形式。將 tunnel[i][j] 換算為 tunnel[

$(i-1)\times m+j$]。

我會先讀入資料，當讀到沒走過的水管後，開始一個新的 bfs。我利用 pipe 陣列儲存已走過的資料，以確保 bfs 的都是新的水管（不必重複讀取已走過的水管），並透過 now 儲存該連通塊的水管數量，並與 Max 比較大小，最終 Max 即為本題解答。

範例程式碼

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

bool up (char ch)
{
    return ch == 'I' || ch == 'L' || ch == 'J' || ch == 'X';
}

bool down (char ch)
{
    return ch == 'I' || ch == '7' || ch == 'F' || ch == 'X';
}

bool left (char ch)
{
    return ch == 'H' || ch == 'J' || ch == '7' || ch == 'X';
}

bool right (char ch)
{
    return ch == 'H' || ch == 'L' || ch == 'F' || ch == 'X';
}

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, j, k;
	int n, m, a, x;
	int Max = 0, now;
	
	cin >> n >> m;
	
	char tunnel[(n+2)*(m+2)];
	int pipe[(n+2)*(m+2)]={};
	
	memset(tunnel, '0', sizeof(tunnel));
	
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			cin >> tunnel[(i-1)*m+j];
			
	for (i=1;i<=n;i++) {
		for (j=1;j<=m;j++) {
			a = (i - 1) * m + j;
			if (pipe[a] == 0 && tunnel[a] != '0') {
				pipe[a] = 1;
				now = 0;
				
				queue <int> run;
				run.push(a);
				
				while (run.size() != 0) {
					x = run.front();
					now++;
					
					if (up(tunnel[x]) && down(tunnel[x-m]) && pipe[x-m] == 0) {
						pipe[x-m] = 1;
						run.push(x-m);
					}
					if (down(tunnel[x]) && up(tunnel[x+m]) && pipe[x+m] == 0) {
						pipe[x+m] = 1;
						run.push(x+m);
					}
					if (left(tunnel[x]) && right(tunnel[x-1]) && pipe[x-1] == 0) {
						pipe[x-1] = 1;
						run.push(x-1);
					}
					if (right(tunnel[x]) && left(tunnel[x+1]) && pipe[x+1] == 0) {
						pipe[x+1] = 1;
						run.push(x+1);
					}
					
					run.pop();
				}
				
				if (now > Max)
					Max = now;
			}
		}
	} 
	
	cout << Max;

	return 0;
}

運行結果

AC (27ms, 1.5MB)

第四題 投資遊戲 (ZeroJudge m373.)

題目

你擁有一個長度為

$n$ 的陣列，代表每天的投資收益，以及

$k（k\le 20）$ 張金牌。

你可以自行決定投資的開始和結束日期。在你選擇投資的每一天，你可以選擇消耗一張金牌來跳過當天，或者不使用金牌而拿取當天的收益。你的目標是找出如何投資，以實現最大的總收益。

請注意，你只能在投資期間進出一次。

輸入 / 輸出說明

輸入說明	輸出說明

解題思路

這題是 dp 題，與背包問題類似。

我利用 dp[i][j] 儲存 i 個金牌、第 j 天的收益。需要注意的是，dp 時我利用 j 代表金牌數，因此在第 21 行使用 dp[j][i]。

根據題目可歸納出，dp[i][j] 就是不斷比較 i 個金牌、第 j 天的收益（該日不使用金牌的收益）與 i - 1 個金牌、第 j - 1 天的收益（該日使用金牌後的收益），而最終答案就是 dp[k+1][i]（1 ≤ i ≤ n）時的最大值（我另 k + 1 作為 k 個獎牌的情形）。

範例程式碼

#include <iostream>
using namespace std;

int a[1000000];
int dp[50][1000000]={};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, j;
	int n, k, b, max;
	
	cin >> n >> k;
	
	for (i=1;i<=n;i++) {
		cin >> a[i];
		
		for (j=1;j<=k+1;j++) {
			dp[j][i] = dp[j-1][i-1];
			b = dp[j][i-1] + a[i];
			
			if (dp[j][i] < b)
				dp[j][i] = b;
			
		}
	}
	
	max = dp[k+1][0];
	
	for (i=1;i<=n;i++) {
		if (dp[k+1][i] > max)
			max = dp[k+1][i];
	}
	
	cout << max;
}

運行結果

AC (25ms, 9.3MB)

tags: APCS實作題

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