---
# System prepended metadata

title: APCS 2024 6月

---

邊喝酒邊寫的，有點亂抱歉QQ
# [P1 特技表演](https://zerojudge.tw/ShowProblem?problemid=o076)
## 解析
整體題目要求的是尋找最長長度的遞減數列大小，只需要左右比較，累加求最大值即可。
## 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define SIZE 105
int main()
{
    int n;
    cin>>n;
    int a[SIZE];
    for(int i=0;i<n;i++)
        cin>>a[i];
    int sum=1,maxs=-1;
    for(int i=1;i<n;i++)
    {
        if(a[i-1]>a[i])
            sum++;
        else
            sum=1;
        maxs=max(maxs,sum);
    }
    cout<<maxs;
    return 0;
}
```

# [P2 電子畫布](https://zerojudge.tw/ShowProblem?problemid=o077)

## 解析
我的解法跟別人蠻不一樣的，我選擇以噴射的點為橫軸，砍半，分成上下兩半來做，不太直覺，我會附上按照題目所提的曼哈頓距離版本。

## 程式碼
分上下半做法
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
    int h,w,n;
    cin>>h>>w>>n;
    int a[105][105];
    memset(a,0,sizeof(a));
    while(n--)
    {
        int r,c,t,x;
        cin>>r>>c>>t>>x;
        for(int i=t;i>0;i--)
        {
            a[r+i][c]+=x;
            for(int j=1;j<=t-i;j++)
            {
                if(r+i>=0&&c+j>=0)
                    a[r+i][c+j]+=x;
                if(r+i>=0&&c-j>=0)
                    a[r+i][c-j]+=x;
            }
        }
        for(int i=0;i<=t;i++)
        {
            a[r-i][c]+=x;
            for(int j=1;j<=t-i;j++)
            {
                if(r-i>=0&&c+j>=0)
                    a[r-i][c+j]+=x;
                if(r-i>=0&&c-j>=0)
                    a[r-i][c-j]+=x;
            }
        }
    }
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
            cout<<a[i][j]<<' ';
        cout<<endl;
    }
}
```
曼哈頓距離做法
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
    int h,w,n;
    cin>>h>>w>>n;
    int a[105][105];
    memset(a,0,sizeof(a));
    while(n--)
    {
        int r,c,t,x;
        cin>>r>>c>>t>>x;
         for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                if(abs(i-r) + abs(j-c) <= t){
                    a[i][j] += x;
                }
            }
        }
    }
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
            cout<<a[i][j]<<' ';
        cout<<endl;
    }
}
```
# [o078. 3. 缺字問題](https://zerojudge.tw/ShowProblem?problemid=o078)
## 解析
按照他給的資料量下去分析時間複雜度，只需要直接枚舉所有組合後線性搜即可。
## 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
string k;
int n;
vector<string> v;
void p(string str)
{
    if(str.size()>=n)
    {
        v.push_back(str);
        return;
    }
    for(int i=0;i<k.size();i++)
        p(str+k[i]);
    return;
}
int main() {
    string s;
    cin>>k>>n>>s;
    for(int i=0;i<k.size();i++)
        p(k.substr(i,1));
    vector<string> vv;
    for(int i=0;i<s.size()-n+1;i++)
        vv.push_back(s.substr(i,n));
    sort(v.begin(),v.end());
    for(auto e:v)
    {
        if(find(vv.begin(),vv.end(),e)==vv.end())
        {
            cout<<e<<endl;
            break;
        }
    }

}
```
