# 2023.1.8 **APCS** 實作題

---

## P1

就那個負數設 $0$ 在搞，我沒有 $5$ 級分了

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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, k, a, b, t, mxm = -10000, m = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        if (b > mxm) {
            mxm = b;
            t = a;
        }
        if (b == -1)
            m -= 2;
    }
    cout << max(0, mxm - n + m) << ' ' << t << '\n';
    return 0;
}

---

## P2

這題是來水的嗎？
以前要 $100$ 行以上的題目怎麼這次只要 $30$ 行就過關？

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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s, tmp;
    int a, b, c, t;
    cin >> a >> b >> c >> s;
    tmp = s;
    vector <string> ans(c);
    while (b--) {
        for (int i = 0; i < a; i++) {
            cin >> t;
            tmp[t - 1] = s[i];
        }
        s = tmp;
        for (int i = 0; i < c; i++)
            ans[i].push_back(s[i]);
    }
    for (int i = 0; i < c; i++)
        cout << ans[i] << '\n';
    return 0;
}

---

## P3

搞得跟往年的第 $2$ 題一樣，妥妥的遞迴實作題，煩死人

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

string s;
int i =0;
long long getnum();
long long f();

long long add() {
    long long ret;
    if (s[i] == 'f') {
        i++;
        ret = f();
    }
    else
        ret = getnum();
    while (i < s.length() && (s[i] == '+' ||s[i] == 'f')) {
            i++;
            if (s[i] == 'f') {
                i++;
                ret += f();
            }
            else
                ret += getnum();
    }
    return ret;
}

long long calc() {
    long long ret;
    if (s[i] == 'f') {
        i++;
        ret = f();
    }
    else
        ret = add();
    while (i < s.length() && (s[i] == '*' || s[i] == 'f')) {
            i++;
            if (s[i] == 'f') {
                i++;
                ret *= f();
            }
            else
                ret *= add();
    }
    return ret;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> s;
    cout << calc() << '\n';
    return 0;
}

long long getnum() {
    long long ret = 0;
    for ( ; i < s.length() && isdigit(s[i]); i++)
        ret = ret * 10 + s[i] - '0';
    return ret;
}

long long f() {
    i++;
    long long mxm = INT_MIN, mnm = INT_MAX, tmp;
    while (s[i] != ')') {
        tmp = calc();
        mxm = max(mxm, tmp);
        mnm = min(mnm, tmp);
        if (s[i] == ',')
            i++;
    }
    i++;
    return mxm - mnm;
}

---

## P4

`greedy` 題型，先 `sort` 完再搭配 `STL` 中的 `multiset` 進行二分搜
解完之後發現要能推則推

==\~QQ~==

可能沒有 $4$ 級分了

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

bool cmp(pair <int, int> a, pair <int, int> b) {
    if (a.second == b.second)
        return a.first > b.first; // 其實這裡不用排也沒差
    return a.second < b.second;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, k, ans = 0;
    cin >> n >> k;
    vector < pair<int, int> > vec(n);
    for (int i = 0; i < n; i++)
        cin >> vec[i].first;
    for (int i = 0; i < n; i++)
        cin >> vec[i].second;
    sort(vec.begin(), vec.end(), cmp);
    multiset < int, greater<int> > st;
    for (int i = 0; i < n; i++) {
        auto it = st.upper_bound(vec[i].first);
        if (it != st.end()) {
            st.erase(it);
            st.insert(vec[i].second);
            ans++;
        }
        else if (st.size() < k) {
            ans++;
            st.insert(vec[i].second);
        }
    }
    cout << ans << '\n';
    return 0;
}

---

> [color=#000000] [name= 編者：frankie 阮豐翗]