APCS 2023 10月場題解&心得(未完)
===
## 前言
升高中後第一次APCS，上次6月場在會考隔周，沒太多時間。過了一個暑假，看了兩本APCS解題攻略後果然有所收穫，這次觀念題寫起來比上次更順手，但實作考的分數不是很理想，第二題因為debug太久導致最後只有拿了第一題滿分，還有2,4題的部分子題分，放榜後成績分別是 **(實作:175/觀念76)**。
下面整理了考試當時寫的code和檢討完優化過的。
## 觀念題
網上找不太到這次的觀念題，但考點大致為下面列出的:
- 改錯:給一段程式碼跟輸出讓你改錯或是給你一段程式碼與其目的讓你選出無法通過的側資
- 填空:給一段不完整的程式碼跟輸出給你選出空個該填的程式碼
- 計算:給一段程式碼讓你算輸出(遞迴...)或是計算迴圈執行次數
## 實作題
### [第一題:機械鼠](https://zerojudge.tw/ShowProblem?problemid=m370)
#### 題目
有n個位置上有食物，另外有一隻老鼠一開始位於位置X。
老鼠在開始覓食前要選擇今天要往左邊或往右移動去尋找食物，經過食物時可以停下來吃食物，吃完後可以選擇繼續往相同方向移動，或者是結束今天的覓食。
請問老鼠最多能吃到多少個食物，以及最後停下來吃食物的位置。
#### 考點
- 迴圈應用
### 解題思路
- 先將輸入存到陣列`h`
- 接著用`for`迴圈判斷餅乾在老鼠的左邊或右邊
- 在記錄左右邊數量時順便紀錄該餅乾是否為最左或最右(判斷是否能為最終停留位置
- 全部跑完後再找出餅乾多的那邊，並輸出數量與最終位置
```cpp=
#include<iostream>
using namespace std;
int main(){
int x,n,i,right=0,left=0,l=-101,s=101;
cin>>x>>n;
int h[n];
for(i=0;i<n;i++)
{
cin>>h[i];
}
for(i=0;i<n;i++)
{
if(h[i]>x) //判斷餅乾方向
{
right++;
l=max(l,h[i]); //存最終位置
}
else if(h[i]<x) //判斷餅乾方向
{
left++;
s=min(s,h[i]); //存最終位置
}
}
if(left>right) cout<<left<<' '<<s;
else cout<<right<<' '<<l;
}
```
上面是我考試當下想到的解法之一，回來以後優化程式如下
- 優化後直接判斷輸入，不須存入陣列
```cpp=
#include<iostream>
using namespace std;
int main(){
int x,n,i,right=0,left=0,l=-101,s=101,v;
cin>>x>>n;
for(i=0;i<n;i++)
{
cin>>v;
if(v>x) //判斷餅乾方向
{
right++;
l=max(l,v); //存最終位置
}
else if(v<x) //判斷餅乾方向
{
left++;
s=min(s,v); //存最終位置
}
}
if(left>right) cout<<left<<' '<<s;
else cout<<right<<' '<<l;
}
```
***ZEROJUDGE判定***
優化前
<font color="#76E34D">**AC**</font>(4ms, 328KB)
優化後
<font color="#76E34D">**AC**</font>(3ms, 340KB)
當時還有想到一個解法，但比上面兩個複雜許多
- 先把輸入放到陣列，然後對陣列`sort`，從陣列判斷老鼠位置後計算餅乾多的邊，最後輸出答案跟陣列頭或尾(最終位置)
### [第二題:卡牌遊戲](https://zerojudge.tw/ShowProblem?problemid=m371)
#### 題目
你有一個`N*M`大小的表格，你可以從中消除具有相同數值且之間沒有障礙物的兩個元素，並獲得分數。請問你可以獲得的最大得分。
每一種數字在表格中出現恰好兩次。消除兩個相同的數字`x`時，可以獲得`x`分。
消除規則：你可以垂直或水平地將兩個相同數值的元素消除，但消除的兩個元素之間不能有其他尚未消除的元素。
#### 考點
- 二維陣列
### 解題思路
判斷上下、左右各選一個即可，把整個陣列跑過後上下跟左右會是相對的。找到能匹配的數後把值存入`t`再把兩個位置的值改成-1。
上面要注意的是跑完後可能會有中間被消除的數字像這樣
```
3 3
1 2 3
6 7 7
1 2 3
```
跑完一次後7被消除
```
3 3
1 2 3
6-1-1
1 2 3
```
此時2跟3都是可以消的，所以在外面加一層`for`確保消除後沒有遺漏的
```cpp=
#include<iostream>
using namespace std;
int main(){
int x,n,i,m,j,d,s=0,k,l,t=0;
cin>>n>>m;
int h[n][m];
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
cin>>h[i][j];
}
}
for(x=0;x<n*m;x++) //作至少n*m次確保移除後會在匹配
{
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
d=h[i][j];
if(d==-1) continue; //該格式-1代表已移除，不用檢查
if(i>0)
{
s=i-1;
while(s>=0&h[s][j]==-1) //向上找並跳過-1
{
s--;
}
if(h[s][j]==d)
{
t+=d; //加入配對的數
h[i][j]=h[s][j]=-1; //把配對過的數字改成-1
continue; //找到後跳過本次迴圈
}
}
if(j>0)
{
s=j-1;
while(s>=0&h[i][s]==-1) //向左找並跳過-1
{
s--;
}
if(h[i][s]==d)
{
t+=d; //加入配對的數
h[i][j]=h[i][s]=-1; //把配對過的數字改成-1
continue; //找到後跳過本次迴圈
}
}
}
}
}
cout<<t;
}
```
***ZEROJUDGE判定***
<font color="#76E34D">**AC**</font>(4ms, 332KB)
### [第三題:搬家](https://zerojudge.tw/ShowProblem?problemid=m372)
#### 題目
忍者龜住在下水道中，他們正在準備搬家。下水道由`N*M`的矩陣表示，其中不同的字元代表著水管的開口方向。如果兩個水管可以互相連接，它們屬於同一個連通塊。你需要找出最大的連通塊的大小。
其中，`X`代表十字架，而 `H`、`I`、`F`、`7`、`L` 分別代表其他不同形狀的水管。0 字元代表沒有水管連接的地方。
請注意，在某個連通塊內的水管可以連接，而不同連通塊的水管不會相互連接。
下面是一些可能的水管形狀：
水管的開口方向與字元對應關係
`F`: 右和下
`H`: 左和右
`7`: 左和下
`I`: 上和下
`X`: 上、下、左和右
`L`: 右和上
`J`: 左和上
`0`: 沒有水管
#### 解題思路
### [第四題:投資遊戲](https://zerojudge.tw/ShowProblem?problemid=m373)
#### 題目
你擁有一個長度為`N`的陣列，代表每天的投資收益，以及`K(K≤20)`張金牌。
你可以自行決定投資的開始和結束日期。在你選擇投資的每一天，你可以選擇消耗一張金牌來跳過當天，或者不使用金牌而拿取當天的收益。你的目標是找出如何投資，以實現最大的總收益。
請注意，你只能在投資期間進出一次。
#### 解題思路
## 反思
##### 觀念題
有些題目因為一些細節看錯導致往錯誤方向計算，造成兩節考試都沒時間檢查。
##### 實作題
考試當下想的測資不夠刁鑽導致沒找出問題，最終成績比原本想的差了35分。當時寫的程式都蝦有很大的優化空間，第一題當時沒想到可以邊輸入邊做，不用存成陣列。第二題當時完全是用最慢的寫法在做。
## 成績證明
以下為近三次成績證明
Sign in with Wallet
Connect another wallet