# APCS 2023/10月題解
## ==機械鼠==
### <font color="0E81A6">敘述</font>
有n個位置上有食物，另外有一隻老鼠一開始位於位置x。
老鼠在開始覓食前要選擇今天要往左邊或往右移動去尋找食物，經過食物時可以停下來吃食物，吃完後可以選擇繼續往相同方向移動，或者是結束今天的覓食。
請問老鼠最多能吃到多少個食物，以及最後停下來吃食物的位置。
### <font color="0E81A6">輸入說明</font>
第一行包含兩個整數：x和n，以空格分隔。x代表老鼠的初始位置，n代表食物的數量。
第二行包含n個整數，以空格分隔，表示每個食物的位置，且不會與老鼠位置重疊。
所有測試資料皆保證(3<=n<=20)且n是奇數，老鼠與食物位置範圍均為-100到100。
### <font color="0E81A6">輸出說明</font>
請輸出兩個整數，分別代表最多能吃到的食物數目和最後一個吃的食物停下的位置。
### <font color="E3A506">核心</font>
陣列、條件判斷、排序
### <font color="E3A506">思路</font>
走訪一次排序後的陣列，當目前食物位置大於x時，進行老鼠左右邊食物量的比較。
```c++
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,x,n;
int food[20];
scanf("%d%d",&x,&n);
for(i=0;i<n;i++) scanf("%d",food+i);
sort(food,food+n);
int num=0,location=food[0];
for(i=0;i<n;i++)
{
if(food[i]>x)
{
if(n-i>i) num=n-i,location=food[n-1];
break;
}
num++;
}
printf("%d %d\n",num,location);
}
```
## ==卡牌遊戲==
### <font color="0E81A6">敘述</font>
你有一個n*m大小的表格，你可以從中消除具有相同數值且之間沒有障礙物的兩個元素，並獲得分數。請問你可以獲得的最大得分。
每一種數字在表格中出現恰好兩次。消除兩個相同的數字x時，可以獲得x分。
消除規則：你可以垂直或水平地將兩個相同數值的元素消除，但消除的兩個元素之間不能有其他尚未消除的元素。
### <font color="0E81A6">輸入說明</font>
第一行包含兩個整數:n和m，以空格分隔。它們分別代表表格的行數和列數。
接下來有n行，每行包含m個整數，以空格分隔，表示表格中的元素。每個元素的數值範圍介於[0,1000]之內，且每種數字在表格中出現恰好兩次。
輸入保證表格上的每種數字恰好出現兩次，且表格的格數為偶數。
### <font color="0E81A6">輸出說明</font>
請輸出一個整數，代表你可以獲得的最大得分。
### <font color="E3A506">核心</font>
二維陣列、模擬
### <font color="E3A506">思路</font>
走訪一次陣列就夠了!，因為卡牌是上下、左右對消。當前位置消除後若它的上方能和它的下方進行對消，則在檢查到下方時就能發現上方未消除卡牌。
將已消除的位置改為-1，略過檢查。
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
int card[20][40];
scanf("%d %d", &n, &m);
for(int i=0; i<n; i++) for(int j=0; j<m; j++) scanf("%d", &card[i][j]);
int sum=0;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(card[i][j]==-1) continue;
//up
int up=i-1;
while(up>=0 && card[up][j]==-1) up--;
if(up>=0 && card[up][j]==card[i][j])
{
sum+=card[i][j];
card[up][j]=-1;
card[i][j]=-1;
continue;
}
//down
int down=i+1;
while(down<n && card[down][j]==-1) down++;
if(down<n && card[down][j]==card[i][j])
{
sum+=card[i][j];
card[down][j]=-1;
card[i][j]=-1;
continue;
}
//left
int left=j-1;
while(left>=0 && card[i][left]==-1) left--;
if(left>=0 && card[i][left]==card[i][j])
{
sum+=card[i][j];
card[i][left]=-1;
card[i][j]=-1;
continue;
}
//right
int right=j+1;
while(right<m && card[i][right]==-1) right++;
if(right<m && card[i][right]==card[i][j])
{
sum+=card[i][j];
card[i][right]=-1;
card[i][j]=-1;
continue;
}
}
}
printf("%d\n", sum);
}
```
## ==搬家==
### 敘述
忍者龜住在下水道中，他們正在準備搬家。下水道由n*m的矩陣表示，其中不同的字元代表著水管的開口方向。如果兩個水管可以互相連接，它們屬於同一個連通塊。你需要找出最大的連通塊的大小。
其中，X 代表十字架，而 H、I、F、7、L 分別代表其他不同形狀的水管。0字元代表沒有水管連接的地方。
請注意，在某個連通塊內的水管可以連接，而不同連通塊的水管不會相互連接。
下面是一些可能的水管形狀：
水管的開口方向與字元對應關係
F: 右和下
H: 左和右
7: 左和下
I: 上和下
X: 上、下、左和右
L: 右和上
J: 左和上
0: 沒有水管
### 輸入說明
第一行包含兩個整數：n和m，以空格分隔。它們分別代表下水道矩陣的行數和列數。
接下來的n行，每行包含m個字元，用於表示下水道的樣子。這些字元描述了各種水管的不同形狀，以及沒有水管的地方。不同的字元代表不同的水管形狀，如H、I、F、7、L和0。水管形狀的解釋在題目敘述中有詳細說明。
請注意，連接在一起的相同形狀的水管屬於同一個連通塊，但不同連通塊之間的水管是不會相互連接的。
所有測試資料皆滿足1<=n,m<=500
### 輸出說明
輸出出最大連通塊的大小。
### <font color="E3A506">核心</font>
DFS、BFS、併查集
### <font color="E3A506">思路</font>
這題很陰險，用DFS做的話會卡在95%，最後5%因記憶體區段錯誤而拿不到分數。
DFS可能會因為記憶體不足而出錯，特別是在處理深度非常大的遞迴樹或圖時。這主要是因為每次遞迴調用都會在呼叫堆疊（call stack）上分配記憶體，當樹或圖的深度過大時，遞迴深度也會變得很深，最終可能導致堆疊溢出（stack overflow）。
可以改用BFS做，或是優化DFS寫法，這裡我介紹DFS的優化寫法。
欲解決遞迴深度問題，可以改用迭代的方式去實現。說白了就是利用stack去寫DFS，改寫很輕鬆。
此題我用struct去模擬水管的方向、map記錄不同水管。
切記要維護陣列範圍!以及走過的水管就不能再走了。
此提亦可用併查集去做，有興趣者可試試看。
```c++=
#include <bits/stdc++.h>
using namespace std;
#define N 505
int n, m;
char pipe[N][N];
bool visit[N][N] = {false};
struct direction
{
bool up = false, down = false, left = false, right = false;
};
map<char, direction> M;
void initializeMap()
{
M['0'];
M['X'].up = true, M['X'].down = true, M['X'].left = true, M['X'].right = true;
M['I'].up = true, M['I'].down = true;
M['H'].left = true, M['H'].right = true;
M['L'].up = true, M['L'].right = true;
M['7'].left = true, M['7'].down = true;
M['F'].right = true, M['F'].down = true;
M['J'].up = true, M['J'].left = true;
}
int iterativeDFS(int startX, int startY)
{
stack<pair<int, int>> s;
s.push({startX, startY});
visit[startX][startY] = true;
int cnt = 0;
while (!s.empty())
{
auto [i, j] = s.top();
s.pop();
cnt++;
direction dir = M[pipe[i][j]];
if (i-1>=1 && dir.up && !visit[i-1][j] && M[pipe[i-1][j]].down)
{
s.push({i-1, j});
visit[i-1][j] = true;
}
if (i+1<=n && dir.down && !visit[i+1][j] && M[pipe[i+1][j]].up)
{
s.push({i+1, j});
visit[i+1][j] = true;
}
if (j-1>=1 && dir.left && !visit[i][j-1] && M[pipe[i][j-1]].right)
{
s.push({i, j-1});
visit[i][j-1] = true;
}
if (j+1<=m && dir.right && !visit[i][j+1] && M[pipe[i][j+1]].left)
{
s.push({i, j+1});
visit[i][j+1] = true;
}
}
return cnt;
}
int main() {
scanf("%d %d", &n, &m);
for (int i=1;i<=n;i++) scanf("%s", pipe[i]+1);
initializeMap();
int maxPipe=0;
for (int i=1; i<=n;i++)
{
for (int j=1;j<=m;j++)
{
if(!visit[i][j] && pipe[i][j]!='0') maxPipe = max(maxPipe, iterativeDFS(i, j));
}
}
printf("%d\n", maxPipe);
}
```
## ==投資遊戲==
### <font color="0E81A6">敘述</font>
你擁有一個長度為n的陣列，代表每天的投資收益，以及k(k<=20)張金牌。
你可以自行決定投資的開始和結束日期。在你選擇投資的每一天，你可以選擇消耗一張金牌來跳過當天，或者不使用金牌而拿取當天的收益。你的目標是找出如何投資，以實現最大的總收益。
請注意，你只能在投資期間進出一次。
### <font color="0E81A6">輸入說明</font>
第一行包含兩個整數:n和k，以空格分隔。n(1<=n<=150000)表示天數，k(1<=k<=20)表示金牌數。
第二行包含n個整數，以空格分隔，代表每天的投資收益。這些整數按照天數的順序給出，數值範圍為-10000到10000。
### <font color="0E81A6">輸出說明</font>
請輸出一個整數，代表達到的最大收益。
### <font color="E3A506">核心</font>
DP
### <font color="E3A506">思路</font>
n<=150000，必然是O(n)解。
試想一下，金牌可用可不用，投資開始和結束的時間也未知，這種題必然歸屬於動態規劃了。
既然知道是動態規劃，首先第一步就是建構關係式:
每日收益存於v陣列。
以dp[i][j]表第i天使用金牌j個所獲得的最大利益。
使用金牌: dp[i][j]=dp[i-1][j-1]
不使用金牌: dp[i][j]=max(dp[i][j],dp[i-1]+v[i])
解法呼之欲出了。
最後在檢查所有的有效解。
```c++=
#include <bits/stdc++.h>
using namespace std;
#define N 150005
int v[N];
int dp[N][30]={0};
int main()
{
int n, k;
scanf("%d%d",&n,&k);
for (int i = 1; i <= n; i++)
{
scanf("%d",v+i);
for (int j = 0; j <= k; j++)
{
if (j > 0) dp[i][j] = dp[i-1][j-1];
dp[i][j] = max(dp[i][j], dp[i-1][j] + v[i]);
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= k; j++) ans = max({ans, dp[i][j], 0});
}
printf("%d\n",ans);
}
```
Sign in with Wallet
Connect another wallet