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

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

第一題 遊戲選角 (ZeroJudge m931.)

題目

有

$n$ 個角色，每個角色有攻擊力和防禦力。

角色的能力值是攻擊力和防禦力的平方和，輸出能力值第二大的攻擊力和防禦力數值。

保證每個角色的能力值相異。

輸入 / 輸出說明

輸入說明	輸出說明

解題思路

我利用first、second紀錄能力值前兩大的數值，並透過a1 d1、a2 d2紀錄攻擊力與防禦力。

當新的數值a d輸入時，比較其能力值t相較first、second的大小，並遵循以下規則：

1. $t>first$ => t 取代 first、first 取代 second
2. $second<t<first$ => t 取代 second
3. $t<second<first$ => 不變

最終輸出second的a、d（實際上是a2、d2），即為本題答案

範例程式碼

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

int main () 
{
    int i, n, 
    int a, d, t, first = -1, second = -1, a1, d1, a2, d2;
    
    cin >> n;
    
    for (i=0;i<n;i++) {
        cin >> a >> d;
        t = a * a + d * d;
        
        if (t > first) {
            second = first;
            first = t;
            
            a2 = a1;
            y2 = d1;
            
            a1 = a;
            y1 = d;
        } 
        else if (t > second) {
            second = t;
            
            a2 = a;
            d2 = d;
        }
    }
    cout << a2 << " " << d2 << endl;
    return 0;
}

運行結果

AC (2ms, 332KB)

第二題 蜜蜂觀察 (ZeroJudge m932.)

題目

蜜蜂 Bob 在一個大小是

$m\times n$ 的蜂巢 (見範例說明圖示），並且每個蜂巢格上會有一個代表字母（大小或小寫英文字母）。

Bob 一開始在蜂巢左下角，行走方向定義如圖：0 是往右上; 1 是往右邊; 2 是往右下; 3 是往左下; 4 是往左邊; 5 是往左上。

輸入每步移動的方向，請輸出經過的路徑每格的代表字母，以及經過字元的種類數（大小寫相異），若經過時碰到牆壁該行動會停在原地。

輸入 / 輸出說明

輸入說明	輸出說明

解題思路

這題的挑戰點在 移動方向 上，但只要仔細觀察，其實並不困難，以範例測資#2為例：

rMmnis
LRveEX
ZexDoc
HAdbHA

假設目前在 v 的位置，我們可以很簡單的歸納出六角形編號 0~5 的移動方向在陣列的表達形式。

接著只需要注意加上if條件，判斷移動後是否超出陣列即可。
〔設為

$(m+2)\times (n+2)$ 陣列，外面一圈留空〕

範例程式碼

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

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, j;
	int m, n, k, move, t = 0;
	int path[6][2] = {{-1,0},{0,1},{1,1},{1,0},{0,-1},{-1,-1}};
	int word[52]={};
	
	cin >> m >> n >> k;
	
	char comb[m+2][n+2];
	int y = m, x = 1;
	int a, b;
	
	memset(comb, ' ', sizeof(comb));
	
	for (i=1;i<=m;i++)
		for (j=1;j<=n;j++)
			cin >> comb[i][j];
			
	for (i=0;i<k;i++) {
		cin >> move;
		
		a = y + path[move][0];
		b = x + path[move][1];
		
		if (a >= 1 && a <= m && b >= 1 && b <= n) {
			y = a;
			x = b;
		}
		
		if (comb[y][x] > 'Z') {
			if (word[comb[y][x]-'a'+26] == 0)
				t++;
			word[comb[y][x]-'a'+26] = 1;
		}
		else {
			if (word[comb[y][x]-'A'] == 0)
				t++;
			word[comb[y][x]-'A'] = 1;
		}
		
		cout << comb[y][x];
	}
	
	cout << endl << t;

	return 0;
}

運行結果

AC (2ms, 348KB)

第三題 邏輯電路 (ZeroJudge m933.)

題目

請設計一個程式，模擬一個基本的邏輯電路系統。這個電路系統由數個輸入端口、邏輯閘和輸出端口組成，您需要模擬電路中的訊號傳遞與閘的運算求出所有輸出端口的數值，並計算整個電路的最大延遲時間。

電路包含以下元件：

• 輸入端口（Input Ports）： 您將接收幾個二進制訊號，每個訊號的值為 0 或 1。這些訊號將用作電路的輸入。電路內共有
  $p$ 個輸入端口，編號為
  $p$ 到
  $q$。
• 邏輯閘（Logic Gates）： 有四種類型的邏輯閘，分別為 AND、OR、XOR 和 NOT 閘。這些閘接收輸入訊號，並根據其功能進行運算。電路內共有
  $q$ 個邏輯閘，編號為
  $p+1$ 到
  $p+q$。各種邏輯閘的運算規則如下：
  • AND 閘（AND gate）： 接收兩個輸入，如果兩個輸入皆為 1，則輸出為 1；否則輸出為 0。
  • OR 閘（OR gate）： 接收兩個輸入，如果至少有一個輸入為 1，則輸出為 1；如果兩個輸入皆為 0，則輸出為 0。
  • XOR 閘（XOR gate）： 接收兩個輸入，如果兩個輸入不相同，則輸出為 1；如果兩個輸入相同，則輸出為 0。
  • NOT 閘（NOT gate）： 僅接收一個輸入，並將其反轉。如果輸入為 1，則輸出為 0；如果輸入為 0，則輸出為 1。
• 輸出端口（Output Ports）： 最終結果將會從這些端口輸出，每個端口對應著某些閘的輸出值。電路內共有
  $r$ 個輸出端口，編號為
  $p+q+1$ 到
  $p+q+r$。

請模擬這個電路系統，確定每個閘的輸出值，以及計算整個電路的最大延遲時間，最大延遲時間即訊號從輸入端口傳遞到輸出端口可能經過最多邏輯閘的數量。

輸入 / 輸出說明

輸入說明	輸出說明

解題思路

這題的挑戰點在 複雜的題幹 上，我自己是試了 5 次才得到 AC 解。

我透過 output 陣列儲存每個端點的輸出值、t 陣列儲存邏輯閘的類型、node 陣列儲存端點之間的連接關係、logic 陣列儲存輸入該端點的值的總和、used 陣列表示第幾次讀取該端點（例如AND邏輯閘需要兩個來自不同端點值輸入，而 used 陣列在第二次表示為 1，則可透過 gate 陣列判斷 AND 邏輯閘的輸出值）、delay 陣列儲存延遲時間、num 陣列儲存端點編號在 node 陣列的起始位置、gate 陣列儲存不同類型邏輯閘的輸出邏輯。

這題的解法可以看成 BFS，我透過 queue 存入已知輸出數值的端點，讀入一個端點的輸出值後，在 queue 末尾加入該端點所接到的每一個端點（邏輯閘或輸出端口），並刪除該端點在 queue 中的排序，以此傳遞訊號。

以範例測資#2為例：

假設我們在 g6 邏輯閘位置，則需要獲取 g1 的輸出值、g7 的輸出值，由於 g6 為 OR 類型，因此得到 logic 陣列的數值為 1（g1 輸出 0 + g7 輸出 1）的時候，g6 輸出 1。

需要特別注意的是，OR 邏輯閘的 logic 陣列數值可以是 1 或 2，因此在判斷輸出值的 gate 陣列中，為了配合 OR 邏輯閘，以 2 維陣列的形式表示。

範例程式碼

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

struct port
{
	int a, b;
};

port node[1000000];
int t[100000], logic[100000]={}, used[100000]={};
int output[100000], delay[100000]={}, num[100000];

bool rule (const port &first, const port &second)
{
	if (first.a == second.a)
		return first.b < second.b;
		
	return first.a < second.a;
}

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, j;
	int p, q, r, m;
	int n, x;
	int gate[4][2]={{2,2},{1,2},{1,1},{0,0}};
	
	cin >> p >> q >> r >> m;
	
	queue <int> run;
	
	for (i=0;i<p;i++) {
		cin >> output[i];
		run.push(i);
	}
		
	for (i=0;i<q;i++)
		cin >> t[i];
		
	for (i=0;i<m;i++)
		cin >> node[i].a >> node[i].b;
		
	sort(node, node + m, rule);
	
	num[0] = 0;
	
	for (i=1;i<m;i++)
		if (node[i].a > node[i-1].a)
			num[node[i].a-1] = i;
			
	num[p+q] = m;
	
	while (run.size() != 0) {
		x = run.front();
		
		if (x >= p && x < p + q) {
			if (t[x-p] == 4 || used[x] == 1) {
				if (logic[x] == gate[t[x-p]-1][0] || logic[x] == gate[t[x-p]-1][1])
					output[x] = 1;
				else 
					output[x] = 0;
			} 
			else {
				used[x]++;
				x = -1;
			}
		}
		
		if (x < p + q && x != -1) {
			for (i=num[x];i<num[x+1];i++) {
				n = node[i].b - 1;
				
				run.push(n);
				
				if (delay[x] >= delay[n] && x >= p)
					delay[n] = delay[x] + 1;
				
				logic[n] = logic[n] + output[x];
				
				if (n >= p + q)
					output[n] = output[x];
			}
		}
		
		run.pop();
	}
	
	sort(delay, delay + p + q + r);
	
	cout << delay[p+q+r-1] << endl;
	
	for (i=p+q;i<p+q+r;i++)
		cout << output[i] << " ";

	return 0;
}

運行結果

AC (63ms, 2.7MB)

第四題 合併成本 (ZeroJudge m934.)

題目

有

$n$ 個數字排成一列，依序是

$a[1],a[2],a[3],...,a[n]$。

每次可以挑選兩個相鄰的數字

$(u,v)$ 合併，合併會花費

$|u-v|$ 元，合併起來的數字會變為

$u+v$。

問把

$n$ 個東西合成一個數字的最小花費是多少？

輸入 / 輸出說明

輸入說明	輸出說明

解題思路

這題為 dp 題，挑戰點在 找到方法 上，而程式本身並不困難。

我令 cost[i][j] 儲存 i ~ j 合併的花費，value[i][j] 儲存 i ~ j 合併後的數值。

根據題目可歸納出，cost[i][j] 就是不斷比較已紀錄的花費

$cost[i][j]$ 與 i ~ k、k+1 ~ j 分別合併後，再合併的花費

$cost[i][k]+cost[k+1][j]+|v[i][k]-v[k+1][j]|$ 之間的大小，並取較小者以取得子問題答案，而最終答案就是 dp 到最後的右上角 (1, n) 的數值（a[1] ~ a[n] 合併後的最小花費）。

以範例測資#2為例：
l = 1 時，cost陣列會以斜向的方式填入相鄰的所有數字合併後的花費
0 8 0 0 0 0
0 0 3 0 0 0
0 0 0 4 0 0
0 0 0 0 7 0
0 0 0 0 0 5
0 0 0 0 0 0

l = 2 ~ l = n - 1時則需要不斷比較合併後的花費，以取得子問題的答案。
假設目前要合併 -5 ~ 0（a[1] ~ a[3]），則有以下兩種合併方式：

1. -5、3 合併 => -2（cost = 8） ， -2、0 合併 => -2（cost = 2）
   Total = 10
   

2. 3、0 合併 => 3（cost = 3） ， -5、3 合併 => -2（cost = 8）
   Total = 11
   

在此情況下，取 1. 的 Total 為 cost[1][3] 的數值。

範例程式碼

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

int cost[102][102];
int value[102][102];

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, j, k, l;
	int n, s;
	
	cin >> n;
	
	for (i=1;i<=n;i++)
		cin >> value[i][i];
		
	for (i=1;i<=n;i++)
		cost[i][i] = 0;
		
	for (l=1;l<n;l++) {
		for (i=1;i<=n-l;i++) {
			j = i + l;
			
			cost[i][j] = 1e9;
			
			for (k=i;k<=j;k++) {
				s = cost[i][k] + cost[k+1][j] + abs(value[i][k]-value[k+1][j]);
				
				if (s < cost[i][j])
					cost[i][j] = s;
					
				value[i][j] = value[i][k] + value[k+1][j];
			}
		}
	}
	
	cout << cost[1][n];
	
	return 0;
}

運行結果

AC (3ms, 428KB)

tags: APCS實作題

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