---
# System prepended metadata

title: APCS23/10/22實作學習歷程

---

APCS 2023 10月場題解&心得
===
## 前言
升高中後第一次APCS，上次6月場在會考隔周，沒太多時間。過了一個暑假，看了兩本APCS解題攻略後果然有所收穫，這次觀念題寫起來比上次更順手，但實作考的分數不是很理想，第二題因為debug太久導致最後只有拿了第一題滿分，還有第二題的部分子題分，放榜後成績分別是 **(實作: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)



## 反思
##### 實作題
考試當下想的測資不夠刁鑽導致沒找出問題，最終成績比原本想的差了35分。當時寫的程式都還有很大的優化空間，第一題當時沒想到可以邊輸入邊做，不用存成陣列。第二題當時開了兩個for迴圈把每個位子都跑過，但這題有許多位子在處理後是可以過濾掉，不用跑的，這次考試結束後有開始讀AP325講義，希望下次考試能比這次進步。
 
## 成績證明
以下為成績證明
![image](https://hackmd.io/_uploads/HkXD-u5qT.png)
