# APCS 2024/6月題解
::: success
## 1. 特技表演
:::
### 敘述:
一個城鎮有n棟高樓，樓高為h1,h2,...,hn。
城鎮中心將舉辦高空特技表演，該特技表演會從某棟大樓上朝右側滑翔至地面。
為了表演人員的安全，滑翔的路徑樓高必須越來越低，請找出一個最長的滑翔路徑。
**5<=n<=100, 1<=hi<=1000**
### 核心:
<font color="#F7A004">**迴圈、條件判斷**</font>
### 思路:
腦海中浮現第一個想法是用陣列存取後跑一次迴圈，找<font color="#4678C1">最長遞減序列</font>。這想法肯定沒錯，但還能更快。
利用兩變數<font color="#4678C1">**last,now**</font>當上一個樓高和目前樓高，直接在輸入迴圈中做運算。
如果now小於last，長度length++並更新最大值ans，else重新計算長度。
<font color="#f00">(注意!!若選擇在else中更新ans，最後於答案輸出前還需再更新一次ans值。)</font>

#include<bits/stdc++.h>
using namespace std;
#define oo 1005
int main()
{
    int n;
    int last=oo,now;
    int ans=0,length=0;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d", &now);
        if(now<last) length++,last=now,ans=max(ans,length);
        else length=1,last=now;
    }
    printf("%d\n",ans);
}

::: success
## 2. 電子畫布
:::
### 敘述:
有一個H*W的電子畫布，一開始數值都是0代表未填色，接下來請模擬N次畫筆操作。
每次操作為選一個座標(r,c)，他會將曼哈頓距離<=t的區塊染上顏色x。
若有多個顏色重複填到相同區塊，顏色的數值會累加起來。
請輸出N次操作後的畫布狀態。
**1<=H,W<=20, 1<=N<=100**
### 核心:
<font color="#F7A004">**模擬、二維陣列**</font>
### 思路:
模擬題，沒什麼好說的，模擬N次操作，用矩形範圍去判斷是否滿足曼哈頓距離。

#include<bits/stdc++.h>
using namespace std;
#define M 105

int main()
{
    int H,W,N;
    int paper[M][M]={0};
    scanf("%d%d%d",&H,&W,&N);
    int r,c,t,x;
    for(int n=0; n<N; n++)
    {
        scanf("%d%d%d%d",&r,&c,&t,&x);
        for (int i=max(0, r-t); i<min(H,r+t+1); i++)
        {
            for (int j=max(0,c-t); j<min(W,c+t+1); j++)
            {
                if (abs(r-i)+abs(c-j) <= t) paper[i][j]+=x;
            }
        }
    }
    for(int i=0; i<H; i++)
    {
        for(int j=0; j<W; j++) printf("%d ",paper[i][j]);
        printf("\n");
    }
}

::: success
## 3. 缺字問題
:::
### 敘述:
給定一個大小為K個字母的集合和字串S，求出在使用該集合所組出長度為L字串中，不為字串子字串的最小字典序字串為何。
### 核心:
<font color="#F7A004">**DFS枚舉、string處理、Sliding Window"**</font>
### 思路:
直接枚舉就對了，由於已經按字典序作枚舉，當找到的第一個不在set str中的字串即為答案。
**1<=K<=10, 1<=L<=8, 1<=|s|<=5*10^5**
此題參考APCS Guide寫法進行優化

#include <bits/stdc++.h>
using namespace std;
string K,S,ans;
int L;
set<string> str;
void dfs(int idx)
{
    if (idx==L)
    {
        if (str.count(ans)) return;
        cout<<ans<<endl;
        exit(0);
    }
    for (int i=0; i<K.size();i++)
    {
        ans[idx]=K[i];
        dfs(idx+1);
    }
}

signed main()
{
    cin>>K>>L>>S;
    ans=string(L,K[0]);
    for (int i=0;i<=S.size()-L;i++) str.insert(S.substr(i,L));
    dfs(0);
}

::: success
## 4. 最佳選擇
:::
### 敘述:
給一個長度為n的正整數序列a1,a2,...,an。
可以執行多次操作(包含0次)，每次操作只能選擇這個序列的第一個或最後一個數字，再將這個數字從序列中刪除並自己搜集起來。
求滿足總和不超過K且搜集的數字奇數和偶數個數相同的條件下，所能搜集的數字總和最大為多少。
### 直接看大佬解法:
[APCS Guide解](https://hackmd.io/@04vUD_k9QzqIoVtFM5Bm_g/apcs202406#%E5%9B%9B%E3%80%81%E6%9C%80%E4%BD%B3%E9%81%B8%E6%93%87)