---
# System prepended metadata

title: APCS 2023 10月
tags: [C++, APCS(題解)]

---

# 前言
怎麼說呢，後面兩題是圖論+DP，我不知道我沒有報到名算不算一件好事:thinking:

# [P1 機械鼠](https://zerojudge.tw/ShowProblem?problemid=m370)

## 題目
有$n$個位置上有食物，另外有一隻老鼠一開始位於位置$x$。

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

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

## 解析

由於是第一題，我盡量使用簡單的字彙表達

首先，我們可以先假設一個數列已經排序好，我們要找的是
比$x$大和比$x$小的個數，取兩個的最大值 *(題目有保證不會等於)*


那最後位置呢?
一定是排序最後一個(right>left)或第一個(right<left)

好邏輯搞懂了，那麼實作吧!

## 程式碼

C++
時間複雜度$O(NlogN)$
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define maker a6
#define a6isweak ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int main()
{
    a6isweak;//IO優化，這題可加可不加
    int a[25];
    int x,n;
    cin>>x>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    int lit=0,big=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]<x) lit++;
        else big++;
    }
    cout<<max(big,lit)<<' ';
    if(big>lit) 
        cout<<a[n-1];
    else 
        cout<<a[0];
    return 0;
}
```

****
# [P2 卡牌遊戲](https://zerojudge.tw/ShowProblem?problemid=m371)

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

每一種數字在表格中出現恰好兩次。消除兩個相同的數字 $x$ 時，可以獲得 $x$ 分。

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

## 解析

看到 $n≦20,m≦40$ 可以知道 時間複雜度最大可以來到$O(N^3)$，所以我只要實際下去做就會過了

你要先做橫的或是直的都可以，答案是一樣的，我這裡是示範先橫後直

## 程式碼

C++
時間複雜度看起來好像$O(N^3)$，但其實不到$O(N^3)$
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define maker a6
#define a6isweak ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define N 25
#define M 35
int main()
{
    a6isweak;
    int a[N][M];
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
            cin>>a[i][j];
    }
    bool bl=1;
    int sum=0;
    while(bl)
    {
        bl=0;
        for(int i=0;i<n;i++)
        {
            int wnf=-1,z=0;
            for(int j=0;j<m;j++)
            {
                if(a[i][j]==-1) continue;
                if(a[i][j]!=-1&&wnf==a[i][j])
                {
                    sum+=wnf;
                    a[i][j]=-1;
                    a[i][z]=-1;
                    wnf=-1;
                    bl=1;

                }
                else if(wnf==-1||a[i][j]!=wnf)
                {
                    wnf=a[i][j];
                    z=j;
                }
            }
        }
        for(int j=0;j<m;j++)
        {
            int wnf=-1,z=0;
            for(int i=0;i<n;i++)
            {
                if(a[i][j]==-1) continue;
                if(a[i][j]!=-1&&wnf==a[i][j])
                {
                    sum+=wnf;
                    a[i][j]=-1;
                    a[z][j]=-1;
                    wnf=-1;
                    bl=1;
                }
                else if(wnf==-1||a[i][j]!=wnf)
                {
                    wnf=a[i][j];
                    z=i;
                }
            }
        }
    }
    cout<<sum;
}

```
****
# [P3 搬家](https://zerojudge.tw/ShowProblem?problemid=m372)

## 題目
忍者龜住在下水道中，他們正在準備搬家。下水道由$n×m$的矩陣表示，其中不同的字元代表著水管的開口方向。如果兩個水管可以互相連接，它們屬於同一個連通塊。你需要找出最大的連通塊的大小。

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

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

 

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


水管的開口方向與字元對應關係
F: 右和下
H: 左和右
7: 左和下
I: 上和下
X: 上、下、左和右
L: 右和上
J: 左和上
0: 沒有水管
![](https://hackmd.io/_uploads/HJp295IGa.png)

## 解析

一看到這題直覺就是DFSorBFS了，事實上，這就是這題的正解，但問題來了，要選擇誰?

首先，我們分析一下兩個差異

BFS:迴圈，相對難寫
DFS:遞迴，相對好寫

那我知道了，肯定是選DFS!

答案恰恰相反，首先，會遇到遞迴深度可能不夠的問題(現在很少卡這個了)，再來記憶體可能會不夠(因為要宣告很多東西)，在無法送出執行的情況下，只好選擇相對不好寫的BFS下去做了

## 程式碼
**這裡借鑑了吳邦一教授的程式碼**
~~主要是因為我知道這題要寫很多判斷式，有點懶惰~~
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define a6isweak ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int visited[510][510]={0};//開全域，否則會有爆掉的風險

bool east(char ch) {
    return ch=='H' || ch=='L' || ch=='F' || ch=='X';
}
bool west(char ch) {
    return ch=='H' || ch=='J' || ch=='7' || ch=='X';
}
bool south(char ch) {
    return ch=='I' || ch=='7' || ch=='F' || ch=='X';
}
bool north(char ch) {
    return ch=='I' || ch=='L' || ch=='J' || ch=='X';
}

int main()
{
    a6isweak;
    int m,n,i,j;
    string mat[510];
    cin>>m>>n;
    for (i=0;i<m;i++) cin >> mat[i];
    int imax=0, t;
    for (i=0;i<m;i++) for (j=0;j<n;j++) {
        if (mat[i][j]=='0' || visited[i][j]) continue;
        // BFS
        vector<pair<int,int>> qu;
        int head=0;
        qu.push_back({i,j});
        visited[i][j] = 1;
        while (head < qu.size()) {
            int r=qu[head].first, c=qu[head].second;
            head++;
            if (c<n-1 && !visited[r][c+1] && east(mat[r][c]) && west(mat[r][c+1])) {
                qu.push_back({r,c+1});
                visited[r][c+1] = 1;
            }
            if (c>0 && !visited[r][c-1] && west(mat[r][c]) && east(mat[r][c-1])) {
                qu.push_back({r,c-1});
                visited[r][c-1] = 1;
            }
            if (r<m-1 && !visited[r+1][c] && south(mat[r][c]) && north(mat[r+1][c])) {
                qu.push_back({r+1,c});
                visited[r+1][c] = 1;
            }
            if (r>0 && !visited[r-1][c] && north(mat[r][c]) && south(mat[r-1][c])) {
                qu.push_back({r-1,c});
                visited[r-1][c] = 1;
            }
        }
        imax = max(imax,(int)qu.size());
    }
    cout<<imax;
    return 0;

}

}
```
****
# [P4 投資遊戲](https://zerojudge.tw/ShowProblem?problemid=m373)
## 題目
你擁有一個長度為$n$的陣列，代表每天的投資收益，以及$k(k≦20)$張金牌。

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

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

## 解析(子題1,2)
在沒有k的限制下，這題可以變成一個greedy題目或是分治，其實就是熟知的最大連續子陣列。

在吳邦一教授的書中說:
「這就像一代一代累積財產，若爸媽給的是正總資產，則繼承過來，否則就拋棄繼承」
*~~雖然不符合民法，但教授說的永遠是對的~~*

## 程式碼(子題1,2)
*ZJ測資不好，會給50%*

C++(greedy)
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define maker a6
#define a6isweak ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int main() {
    // for k=0
    a6isweak;

    int n,k;
    cin>>n>>k;
    int sum=0,ans=0;
    for(int i=0;i<n;i++)
    {
        int z;
        cin>>z;
        if(sum>=0)
            sum+=z;
        else
            sum=z;
        ans=max(ans,sum);
    }
    cout<<ans;
    return 0;
}

```
人生總是要有點目標，沒有目標總有夢想吧，所以我們來看有K的情況

## 解析

首先我們繼續思考，greedy到底可不可以?
想想看，如果要greedy首先要知道，我們是可以決定開始時間，那麼我們要枚舉開始時間和結束時間，還要找到最好的可能，最壞的情況時間複雜度甚至會到$O(k×n^2)$，那這條路應該行不通，所以這時候我們就會想到DP(動態規劃)

這個問題會是$2D1D$的DP，時間複雜度降到$O(k×n)$，在$k$不大的情況下，很接近$O(n)$，這題便是如此，順便說一聲，這種情況稱為「偽多項式時間複雜度」。

講了這麼多，我們其實只確定了做法。

我們知道DP最困難的就是列出遞迴關係式了，這裡，我們可以設立一個陣列$d[n]$，$d[i]$表示前面$i$個的最佳解，可是在有金牌的時候，可能會改變最佳解，既然這樣不行，我就加條件，我改成$d[n][k]$，$d[i][j]$表示前面$i$個，用了$j$個金牌的最佳解，這樣就可以列式了!

### 當$j=0$時
$d[i][0]=max(d[i-1][0],0)+a[i]$

### 當$j>0$時
在第$i$天時，我們可以選擇用金牌或不用，找最好的
$d[i][j]=max(d[i-1][j]+v[i],d[i-1][j-1])$

往往dp難在列式，程式碼大多都是a piece of cake!

## 程式碼

C++
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define maker a6
#define a6isweak ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int a[150005],d[150005][25];
int main() {
    // for k!=0
    a6isweak;

    int n,k;
    cin>>n>>k;

    for(int i=0;i<n;i++)
        cin>>a[i];
    d[0][0]=a[0];
    for(int i=1;i<n;i++)
        d[i][0]=max(d[i-1][0],0)+a[i];
    for(int j=0;j<=k;j++)
    {
        if(a[0]>0)
        {
            d[0][j]=a[0];
        }
        else
            d[0][j]=0;
        for(int i=1;i<n;i++)
        {
            d[i][j]=max(d[i-1][j]+a[i],d[i-1][j-1]);
        }
    }
    int ans=0;
    for(int i=0;i<n;i++)
        ans=max(d[i][k],ans);
    cout<<ans;


    return 0;
}

```

# 心得
最後還是把這個題解弄出來了，這次我想考試時我應該寫不出來後面兩題，不過我覺得最後一題解出來的成就感很爽，這是我第一篇題解，而且寫最後一題的時候已經超過腦袋斷線時間了，如果有錯誤，麻煩私訊我DC，我看到的時候會改的!

DC:a6a6a6#5797