# APCS 20240616 題解

## 第一題：特技表演(Accepted) [（題目敘述）](https://zerojudge.tw/ShowProblem?problemid=o076)
* 考點：迴圈、陣列、判斷
* 用for迴圈直接遍歷找到最長遞減(不變)的值
:::spoiler Example

#include <bits/stdc++.h>
using namespace std;
// 第一題程式碼 by 小律
int main() {
    int n, arr[100005], cnt = 1, Max = 1;
    cin >> n;
    for(int i=0; i<n; i++) cin >> arr[i];
    for(int i=1; i<n; i++){
        if(arr[i] <= arr[i-1]){
            cnt++;
            Max = max(Max, cnt);
        }
        else cnt = 1;
    }
    cout << Max;
}

:::

## 第二題：電子畫布(Accepted) [（題目敘述）](https://zerojudge.tw/ShowProblem?problemid=o077)
* 考點：二維陣列
* 找到開始的地方為中心，從左上角 {${y-t, x-t}$} 的地方開始遍歷邊長為＄$t*2-1$ 的正方形，在判斷是否為曼哈頓距離即可
:::spoiler Example

#include <bits/stdc++.h>
using namespace std;
// 第二題程式碼 by 小律
int main() {
    int n, m, k, x, y, t, d, arr[105][105];
    cin >> n >> m >> k;
    memset(arr, 0, sizeof(arr));
    while(k--){
        cin >> x >> y >> t >> d;
        int sy = y-t, sx = x-t;
        for(int i=0; i<t*2+1; i++){
            for(int j=0; j<t*2+1; j++){
                if(sy+j >= 0 && sy+j < m && sx+i >= 0 && sx+i < n){
                    if(abs(sy+j - y) + abs(sx+i - x) <= t) arr[sx+i][sy+j] += d;
                }
            }
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cout << arr[i][j] << ' ';
        }
        cout << '\n';
    }
}

:::

## 第三題：缺字問題(Accepted) [（題目敘述）](https://zerojudge.tw/ShowProblem?problemid=o078)
* 考點：位元運算、DFS枚舉、二分搜
* 將子序列 $s$ 以sliding window 找到所有可能並且依字典序排序
* 接著用DFS枚舉 $C_k^L$ 種可能
* 最後用二分搜找字典序排序第一個的字串
:::spoiler Example

#include <bits/stdc++.h>
using namespace std;
// 第三題程式碼 by 小律
string alp, s, save, run;
vector <string> v;
int l, alp_S;
bool check = false;

void dfs(int now){
    if(check) return;
    if(now == l){
        auto it = lower_bound(v.begin(), v.end(), run);
        if(*it != run){
            cout << run << '\n';
            check = true;
        }
        return;
    }
    for(int i=0; i<alp_S; i++){
        run[now] = alp[i];
        dfs(now+1);
    }
}
int main() {
    cin >> alp >> l >> s;
    alp_S = alp.size();
    sort(alp.begin(), alp.end());
    for(int i=0; i<l; i++) save += s[i];
    v.push_back(save);
    for(int i=l; i<s.size(); i++){
        save.erase(0,1);
        save += s[i];
        v.push_back(save);
    }
    sort(v.begin(), v.end());
    for(int i=0; i<l; i++) run += alp[0];
    dfs(0);
}

:::

## 第四題：最佳選擇(Accepted) [（題目敘述）](https://zerojudge.tw/ShowProblem?problemid=o079)
* 考點：前後綴和、二分搜
* 先後綴和並且依據奇偶的差分類
* 再做前綴合搭配二分搜找到答案
* 要注意 $K$ 可能大於數列總和
* 要注意左右不一定都要拿（可以只拿左或只拿右）
:::spoiler Example

#include <bits/stdc++.h>
using namespace std;
// 第四題程式碼 by 小律
vector <int> odd[300005], even[300005];
int n, k, arr[300005] = {0}, tot = 0;
int main() {
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> arr[i];
        arr[i] *= -1;
        tot += arr[i];
    }
    // 解決k可能大於全部數字總和的問題
    k = max(-k, tot);
    int o = 0, e = 0, ans = 0, Min = 0;
    // 先後綴和依據機奇偶數分類
    for(int i=n; i>0; i--){
        ans += arr[i];
        if(arr[i] % 2) o++;
        else e++;
        if(e >= o) even[e-o].push_back(ans);
        if(o >= e) odd[o-e].push_back(ans);
    }
    o = 0, e = 0, ans = 0;
    // 再前綴和+二分搜找到要的答案
    for(int i=0; i<=n; i++){
        ans += arr[i];
        if(arr[i] % 2) o++;
        else if(arr[i] % 2 == 0 && arr[i]) e++;
        if(o == e){
            if(k <= ans) Min = min(Min, ans);
        }
        int save = e - o, div = k - ans;
        if(e >= o){
            auto it = lower_bound(odd[save].rbegin(), odd[save].rend(), div);
            if(it != odd[save].rend()) Min = min(Min, *it+ans);
        }
        else if(o >= e){
            save *= -1;
            auto it = lower_bound(even[save].rbegin(), even[save].rend(), div);
            if(it != even[save].rend()) Min = min(Min, *it+ans);
        }
    }
    cout << -Min << '\n';
}

:::