# APCS 2024/1月題解
---
::: success
## 遊戲選角
:::
:::info
### <font color="#1B3B69">敘述:</font>
有n個角色，每個角色有攻擊力和防禦力。
角色的能力值是攻擊力和防禦力的平方和，輸出能力值第二大的攻擊力和防禦力數值。
保證每個角色的能力值相異。
### <font color="#1B3B69">輸入說明</font>:
第一行包含一個整數n(1<=n<=20)，表示有多少個角色。
接下來的n行，每行包含兩個整數ai和di(1<=ai,di<=100)，表示第i個角色的攻擊力和防禦力。
### <font color="#1B3B69">輸出說明</font>:
輸出兩個整數，表示能力值第二大的角色的攻擊力和防禦力。
:::
:::warning
### <font color="#DF630E">核心:</font>
#### 陣列、排序、自訂比較函數
### <font color="#DF630E">思路:</font>
創一個陣列存攻擊力和防禦力，我這裡用pair，也可以用struct。
接著自訂比較函數後將此陣列排序，第二個即為答案。
:::

#include <bits/stdc++.h>
using namespace std;
int cmp(pair<int,int> &a, pair<int,int> &b)
{
    return  (a.first*a.first+a.second*a.second)>(b.first*b.first+b.second*b.second);
}
int main()
{
    int n;
    pair<int,int> p[25];
    scanf("%d", &n);
    for (int i=0; i<n; i++)
    {
        scanf("%d %d", &p[i].first, &p[i].second);
    }
    sort(p, p+n, cmp);
    printf("%d %d", p[1].first, p[1].second);
}

---
:::success
## 蜜蜂觀察
:::
:::info
### <font color="#1B3B69">敘述:</font>
蜜蜂Bob在一個大小是m*n的蜂巢，並且每個蜂巢格上會有一個代表字母（大小或小寫英文字母)。
Bob一開始在蜂巢左下角，行走方向定義如圖：0是往右上;1是往右邊;2是往右下;3是往左下;4是往左邊;5是往左上。
輸入每步移動的方向，請輸出經過的路徑每格的代表字母，以及經過字元的種類數（大小寫相異），若經過時碰到牆壁該行動會停在原地。
### <font color="#1B3B69">輸入說明:</font>
第一行包含三個整數m、n(1<=m,n<=20、k(1<=k<=100)，表示蜂巢的大小是m*n，Bob的行走路徑有k步。
接下來的m行，每行包含n個字母（大小寫英文字母），代表蜂巢的狀態。
最後一行包含k個整數，表示Bob的移動路徑方向。
### <font color="#1B3B69">輸出說明:</font>
輸出一行，包含兩個部分：
由 Bob 每步經過的每格代表字母所組成的字串。
經過字元的種類數（大小寫視為相異），用一個整數表示。
:::
:::warning
### <font color="#DF630E">核心:</font>
#### 模擬、二維陣列
### <font color="#DF630E">思路:</font>
利用二維陣列模擬蜂巢，這裡採用特殊的儲存方式，目前蜂巢比上一排蜂巢向前位移1格，來滿足數字0和3的方向。
**(注意!! 列經過位移，1和4方向不影響，但5和2要做些更正，5方向移至(i-1,j)位置，2則移至(i+1,j)位置)**
接著利用set不重覆特性，來找字元種類數。
:::

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int m,n,k;
    char B[25][45];
    memset(B, '0', sizeof(B));

    scanf("%d %d %d", &m,&n,&k);
    for (int i=1; i<=m; i++)
    {
        scanf("%s", B[i]+(m-i));
        B[i][m-i+n]='0';
    }

    int step;
    int I=m,J=0;
    set<char> S;
    for (int i=0; i<k; i++)
    {
        scanf("%d", &step);
        if(step==0)
        {
            if (B[I-1][J+1]!='0')
            {
                printf("%c", B[I-1][J+1]);
                I--;
                J++;
            }
            else printf("%c", B[I][J]);
        }
        else if(step==1)
        {
            if (B[I][J+1]!='0')
            {
                printf("%c", B[I][J+1]);
                J++;
            }
            else printf("%c", B[I][J]);
        }
        else if(step==2)
        {
            if (B[I+1][J]!='0')
            {
                printf("%c", B[I+1][J]);
                I++;
            }
            else printf("%c", B[I][J]);
        }
        else if(step==3)
        {
            if (B[I+1][J-1]!='0')
            {
                printf("%c", B[I+1][J-1]);
                I++;
                J--;
            }
            else printf("%c", B[I][J]);
        }
        else if(step==4)
        {
            if (B[I][J-1]!='0')
            {
                printf("%c", B[I][J-1]);
                J--;
            }
            else printf("%c", B[I][J]);
        }
        else
        {
            if (B[I-1][J]!='0')
            {
                printf("%c", B[I-1][J]);
                I--;
            }
            else printf("%c", B[I][J]);
        }
        S.insert(B[I][J]);
    }
    printf("\n");
    printf("%d", S.size());
}

---
:::success
## 邏輯電路
:::
:::info
### <font color="#1B3B69">敘述:</font>
請設計一個程式，模擬一個基本的邏輯電路系統。這個電路系統由數個輸入端口、邏輯閘和輸出端口組成，您需要模擬電路中的訊號傳遞與閘的運算求出所有輸出端口的數值，並計算整個電路的最大延遲時間。

電路包含以下元件：

輸入端口（Input Ports）：您將接收幾個二進制訊號，每個訊號的值為0或1。這些訊號將用作電路的輸入。電路內共有p個輸入端口，編號為1到p。

> 邏輯閘（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。

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

### <font color="#1B3B69">輸入說明:</font>
第一行包含四個整數，依序為p、q、r、m。
p(1<=p<=10^3^)代表輸入端口的數量，q(1<=q<=5*10^4^)代表邏輯閘的數量，r(1<=r<=10^3)代表輸出端口的數量，而m代表連接線的數量。
接下來一行有p個整數，代表編號為1到p輸入端口的二進制值（0或1）。
接下來一行有q個整數，代表編號為p+1到p+q的邏輯閘的類型（1為AND、2為OR、3為XOR、4為NOT）。
最後的m行，每行包含兩個整數，代表連接線的起始端口和終端端口的編號。
每個輸入端口和邏輯閘的輸出會連到至少1個至多20個其他邏輯閘和輸出端口的輸入，且邏輯閘電路不會接出迴路。
### <font color="#1B3B69">輸出說明:</font>
第一行輸出一個整數，表示計算出的特定端口的最大延遲時間，測試資料保證最大延遲不高過100。
第二行輸出r個二進制值（0或1），代表每一個輸出閘編號由小到大的輸出數值。
:::
:::warning
### <font color="#DF630E">核心:</font>
#### BFS、DP
### <font color="#DF630E">思路:</font>
這裡我判斷輸入數值轉輸出數值的方式比較特別，詳細在logic函式中，有興趣者可觀察看看。
binary存放的便是端口和閘的值，每個閘會有1~2個的輸入。一開始將輸入端口全部推入queue，後一一取出更新它連接的閘值，當閘經過2次累加或此閘為NOT(1次累加)後便可推入queue，取出時利用logic函式推斷此閘的輸出值，以便下一個閘輸入。
當下一個為輸出端口，更新端口值就好。
計算經過的最多閘數是很容易的DP，存取每一個閘的先前經過最大閘數，每一個閘去更新它所連接的下一個閘，取當前最大值，queue做完便能算出總最大值。
:::

#include <bits/stdc++.h>
#define N 52005
using namespace std;
int binary[N]={0};
int brake[N];
int brakeCnt[N]={0};
int maxCnt=0;
int brakeInput[N]={0};
vector<int> adj[N];
bool logic(int v)
{
    int n=brake[v];
    if (n==1) binary[v]=(binary[v]==2) ? 1 : 0;
    else if (n==2) binary[v]=(binary[v]>=1) ? 1 : 0;
    else if (n==3) binary[v]=(binary[v]%2==1) ? 1 : 0;
    else binary[v]=1-binary[v];
}

int main()
{
    int p,q,r,m;
    scanf("%d%d%d%d",&p,&q,&r,&m);
    for(int i=1;i<=p;i++) scanf("%d",binary+i); //1~p
    for(int i=1;i<=q;i++) scanf("%d",brake+i+p); //p+1~p+q
    for(int i=0;i<m;i++)
    {
        int from,to;
        scanf("%d%d",&from,&to);
        adj[from].push_back(to);
    }
    queue<int> Q;
    for(int i=1;i<=p;i++) Q.push(i);
    while(!Q.empty())
    {
        int v=Q.front();
        Q.pop();
        if(v>=p+1&&v<=p+q) logic(v);
        for(int u:adj[v])
        {
            binary[u]+=binary[v];
            if(u>p+q) continue; //output
            brakeCnt[u]=max(brakeCnt[u],brakeCnt[v]+1);
            maxCnt=max(brakeCnt[u],maxCnt);
            brakeInput[u]++;
            if(brakeInput[u]==2||brake[u]==4) Q.push(u);
        }
    }
    printf("%d\n",maxCnt);
    for(int i=1;i<=r;i++) printf("%d ",binary[p+q+i]);
    printf("\n");
}

---
:::success
## 合併成本
:::
:::info
### <font color="#1B3B69">敘述:</font>
有n個數字排成一列，依序是a[1],a[2],...,a[n]。
每次可以挑選兩個相鄰的數字(u,v)合併，合併會花費|u-v|的元，合併起來的數字會變為u+v。
問把n個東西合成一個數字的最小花費是多少？
### <font color="#1B3B69">輸入說明:</font>
第一行有一個正整數n(1<=n<=100)，表示有多少個東西。
第二行包含n個整數a[1],a[2],...,a[n] (|a[i]|<=1000)，相鄰兩個數字之間用空格隔開。
### <font color="#1B3B69">輸出說明:</font>
輸出最小花費。
:::
:::warning
### <font color="#DF630E">核心:</font>
#### 遞迴、DP
### <font color="#DF630E">思路:</font>
以cost[i][j] 表合併第i個到第j個數字的最小成本，
以v[i][j] 表合併完後的數字。
建構遞迴關係式:
i<=k<j
cost[i][j] = min( cost[i][j] , cost[i][k]+cost[k+1][j]+abs( v[i][k]-v[k+1][j] ) )
v[i][j] = v[i][k] + v[k+1][j]
接著用一個函數spend來遞迴，如果cost[i][j]已經算過，就不必再算一次。
:::

#include<bits/stdc++.h>
using namespace std;
#define N 105
#define oo 100005
int cost[N][N];
int v[N][N];
int spend(int i,int j)
{
    if(cost[i][j]!=oo) return cost[i][j];
    for(int k=i;k<j;k++)
    {
        cost[i][j]=min(cost[i][j],spend(i,k)+spend(k+1,j)+abs(v[i][k]-v[k+1][j]));
        v[i][j]=v[i][k]+v[k+1][j];
    }
    return cost[i][j];
}
int main()
{
    int n,a[N];
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        for(int j=i;j<n;j++) cost[i][j]=oo;
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",a+i);
        v[i][i]=a[i];
        cost[i][i]=0;
    }
    printf("%d\n",spend(0,n-1));

}