APCS 2022年1月題解

這次去考了 $\text{APCS}$，不知道會有幾分，不過在 $\text{Zerojudge}$ 上都過了，就來寫個題解吧。

$\text{p1：}$ 程式交易 (Zerojudge_h081)

題目大意：在時刻 $1\sim n$ 有 $n$ 張價錢為 $a_i$ 的股票，第一天強制要買，之後幾天，如果手中持有股票，並且當天股票價格大於等於手中股票價值 $+D$，就強制售出；如果手中未持有股票，且當天股票價格小於等於上次售出股票價值 $-D$，就強制購入。問賺到多少錢，目前手中股票可忽視。

解法：用一個 $\text{last}$ 紀錄目前手中股票或是上次售出股票價值，並使用一個布林變數 $buy$ 紀錄現在手上是否持有股票，最後在答案加總。

$\text{Code：}$

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

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    int n, d, ans = 0, last;
    bool buy = 0;
    cin >> n >> d;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (i == 1)
            last = x, buy = 1;
        else if (buy && x >= last + d)
            ans += x - last, last = x, buy = 0;
        else if (!buy && x <= last - d)
            last = x, buy = 1;
    }
    cout << ans << '\n';
}

$\text{p2：}$ 贏家預測 (Zerojudge_h082)

題目大意：有 $n$ 個人編號 $1\times n$，每個人有各自的 $a,b$ 值，一開始會給一個打架順序，由左到右每兩個人一組打，最後一個人打不到架算直接獲勝。打架獲勝機制如下：如果 $a_1\times b_1≥a_2\times b_2$，第一個人獲勝，$a_1' = a_1 + a_2\times b_2/(2\times b_1)$，$b_1' = b_1 + a_2\times b_2/(2\times a_1)$，$a_2' = a_2 + a_2/2$，$b_2' = b_2 + b_2/2$，反之亦然。如果這個人累積失敗次數 $≥m$，就直接淘汰。新的隊伍先加入獲勝的人，再加入失敗但是沒被淘汰的人，如此下去直到剩一人為贏家。

解法：可以定義一個 $\text{struct}$，裡面存編號、$a,b$ 值、失敗次數，用一個 $\text{vector}$ 去存隊伍，用一些函數進行操作就可以了。

$\text{Code：}$記得要使用 $\text{long long}$

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

struct People {
    long long id, a, b, cnt = 0;
};

int n, m;
vector<People> v;

bool hit (int x, int y) {
    long long a = v[x].a, b = v[x].b, c = v[y].a, d = v[y].b;
    if (a * b >= c * d) {
        v[y].cnt++;
        v[x].a = a + c * d / (2 * b);
        v[x].b = b + c * d / (2 * a);
        v[y].a = c + c / 2;
        v[y].b = d + d / 2;
        return 1;
    } else {
        v[x].cnt++;
        v[y].a = c + a * b / (2 * d);
        v[y].b = d + a * b / (2 * c);
        v[x].a = a + a / 2;
        v[x].b = b + b / 2;
        return 0;
    }
}

void fight() {
    bool win[v.size()];
    fill (win, win + v.size(), 1);
    for (int i = 0; i < v.size(); i += 2) {
        if (i == v.size() - 1)
            break;
        if (hit (i, i + 1))
            win[i + 1] = 0;
        else
            win[i] = 0;
    }
    vector<People> tmp;
    for (int i = 0; i < v.size(); i++) {
        if (win[i])
            tmp.push_back (v[i]);
    }
    for (int i = 0; i < v.size(); i++) {
        if (!win[i] && v[i].cnt < m)
            tmp.push_back (v[i]);
    }
    v = tmp;
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    cin >> n >> m;
    People p[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> p[i].a, p[i].id = i;
    for (int i = 1; i <= n; i++)
        cin >> p[i].b;
    for (int i = 1; i <= n; i++) {
        int id;
        cin >> id;
        v.push_back (p[id]);
    }
    while (v.size() > 1)
        fight();
    cout << v[0].id << '\n';
}

$\text{p3：}$ 數位占卜 (Zerojudge_h083)

題目大意：給你 $n$ 個字串，問你有幾對字串可以組成一個新字串，且此字串前半部分與後半部分相同。

解法：我是用 $\text{unordered_map}$，枚舉每個字串的前半部分跟後半部分的一小部分，看有沒有字串符合條件。

$\text{Code：}$

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

unordered_map<string, bool> hs;

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    int n;
    cin >> n;
    string s[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> s[i], hs[s[i]] = 1;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int len = 1; len < s[i].size(); len++) {
            string s1, s2;
            s1 = s[i].substr (0, s[i].size() - len);
            s2 = s[i].substr (s[i].size() - len, len);
            if (s2.size() >= s1.size())
                break;
            string s3, s4;
            s3 = s[i].substr (0, s2.size());
            s4 = s[i].substr (s2.size(), s1.size() - s2.size());
            if (s2 == s3)
                ans += hs.count (s4);
        }
    }
    cout << ans << '\n';
}

$\text{p4：}$牆上海報 (Zerojudge_h084)

題目大意：有 $n$ 個木條，高度分別為 $h_1\sim h_n$，有 $k$ 張海報，高度為 $1$，寬度分別為 $w_1\sim w_k$，問海報從左往右按照順序貼在相同高度，且要貼在木條上，不可重疊，可以貼完又最高，高度可以是多少。

解法：可以發現貼在底下一定可以貼完，越往上就會發現越難貼完，或許可以發現，在答案求的最大高度以下的高度都可以成功貼完(因為貼的空間會越來越大)，超過的就都不行。對於這種判定特定高度是否符合條件很容易，直接想貪心找出答案很困難的問題，我們可以使用二分搜尋法找答案。設定 $l,r$ 為上界與下界，每次看中間值 $mid$ 符不符合，如果符合，可使 $l=mid$，否則使 $r=mid-1$，最後當 $l$ 與 $r$ 相同時，$l = r =$ 答案。

$\text{Code：}$

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

const int SIZE = 2e5 + 5;

int n, k, h[SIZE], w[SIZE];

bool ok (int x) {
    int now = 1, len = 0;
    for (int i = 1; i <= n; i++) {
        if (h[i] >= x)
            len++;
        else
            len = 0;
        if (len >= w[now])
            len -= w[now], now++;
        if (now > k)
            return 1;
    }
    return 0;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    for (int i = 1; i <= k; i++)
        cin >> w[i];
    int l = 0, r = *max_element (h + 1, h + n + 1);
    while (l < r) {
        int mid = l + (r - l) / 2 + 1;
        if (ok (mid))
            l = mid;
        else
            r = mid - 1;
    }
    cout << l << '\n';
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！