APCS Guide

正在開發一個資源全面的免費 APCS 學習平台，涵蓋入門到滿級的需要的所有內容，帶你用最快的速度提高級分。

追蹤 APCS Guide 的 Instagram

APCS Simulation

每個月舉辦 APCS 模擬測驗，讓你可以更清楚準備方向和自己的弱點。

追蹤 APCS Simulation 的 Instagram

APCS 2024 6 月實作題解

一、特技表演

考點

陣列、迴圈、條件判斷

思路

首先，題目說「滑翔的路徑樓高必須越來越低」，轉換成更具體一點的概念就是要找到一對 \(l\)、\(r\) 滿足 \(h_l > h_{l+1}>\dots >h_{l+2}>h_r\)，並且 \(r-l+1\) 要盡可能的大。

接下來，我們只要透過檢查每一對 \(l、r\) 判斷是否合法，並記錄最大的答案就行了！

程式碼

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

// 大樓高度
int h[100];

// 判斷大樓 l 到大樓 r 是否可以滑翔 (是否嚴格遞減)
bool ok(int l, int r) {
    for (int i = l; i <= r-1; i++) {
        if (h[i + 1] >= h[i]) return false;
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) cin >> h[i];
    // 嘗試每一對 l r
    for (int l = 1; l <= n; l++) {
        for (int r = l + 1; r <= n; r++) {
            // 檢查是否合法，如果合法就嘗試更新答案
            if (ok(l, r)) ans = max(ans, r - l + 1);
        }
    }
    // 輸出答案
    cout << ans << endl;
}

二、電子畫布

考點

二維陣列、實作

思路

每次下筆時，直接用兩層 for 回圈遍歷整張畫布，並把所有距離小於 t 的顏色更新就行了。

程式碼

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

// 畫布
int pic[100][100];

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    // 處理每次下筆
    while (q--) {
        int x, y, t, k;
        cin >> x >> y >> t >> k;
        // 嘗試更新每個位置的值
        for (int j = 0; j < n; j++) {
            for (int l = 0; l < m; l++) {
                // 只修改距離 <= t 的位置
                if (abs(j - x) + abs(l - y) <= t) {
                    // 更新顏色 (因為會混色所以是 +=)
                    pic[j][l] += k;
                }
            }
        }
    }
    // 輸出畫布
    for (int j = 0; j < n; j++) {
        for (int l = 0; l < m; l++) {
            cout << pic[j][l] << ' ';
        }
        cout << endl;
    }
}

三、缺字問題

考點

遞迴枚舉、資料結構

思路

預處理先把 s 中所有的子字串記錄下來，然後因為字串長度很小，所以可以直接透過遞迴枚舉由字典序小到大嘗試所有的可能性，只要找到一個沒有被紀錄到的字串就可以直接輸出了！

程式碼

#include <bits/stdc++.h>

using namespace std;

string t, s, ans;
int n;
set<string> st;

// idx 代表目前填到 ans 的第幾個字母
// cnt 代表目前選了多少個字母
void dfs(int idx) {
    // 如果選到 n 個
    if (idx >= n) {
        // 已經被記錄的話就忽略
        if (st.count(ans)) return;
        // 否則就是答案了
        cout << ans << endl;
        exit(0);
    }
    if (idx >= ans.size()) return;
    // 每舉目前的位置放哪個字母
    for (int i = 0; i < t.size(); i++) {
        ans[idx] = t[i];
        // 繼續 DFS，因為選了一個字母所以 idx 和 cnt 都要 + 1
        dfs(idx + 1);
    }
}

signed main() {
    cin >> t >> n >> s;
    // ans 先初始化成字母集能拼出的最小字典序字串
    ans = string(n, t[0]);
    // 紀錄下 s 中的所有子字串
    for (int i = 0; i <= s.size() - n; i++) {
        st.insert(s.substr(i, n));
    }
    // 開始枚舉
    dfs(0);
}

四、最佳選擇

考點

前綴和、二分搜、資料結構

思路

首先，我們觀察到的重要性質是：選擇右邊的第 \(k\) 個數字後，左邊的奇數數量減去偶數數量的差值必須與右邊相反，即左右兩邊的奇偶數差相加為零。

為了快速計算任意範圍內的奇偶數差，我們可以將偶數視為 \(-1\)，奇數視為 \(1\)，並使用前綴和來維護這個差值。這樣，我們可以在 \(O(1)\) 的時間內查詢任意範圍內的奇偶數差。

接著，我們從右向左枚舉每個可能的右端點，同時維護目前的奇偶數差值以及總和。為了找到符合條件的最佳左端點，我們可以使用一個 map 來記錄不同奇偶數差值出現的位置和其對應的總和。在枚舉每個右端點時，我們可以使用二分搜從合法的左端點中找到一個最佳的左端點，滿足對應的總和加上當前右端點的總和最大且不超過 \(k\)，並嘗試更新答案。

當然，從左做到右或從右做到左都可以。

程式碼

#include <bits/stdc++.h>
using namespace std;
// 實作量稍微大一點，所以先 define 一些好用的東西
// #define int long long
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define ff first
#define ss second

const int MAXN = 3e5 + 10;

int v[MAXN];

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // IO 優化
    unordered_map<int, vector<pii>> mp; // 用來快速查詢每個奇偶差有哪些左端點，pair 的兩個數字分別為 index 和 sum
    int n, k;
    cin >> n >> k;
    int presum = 0; // 前綴和
    int predif = 0; // 前綴奇偶差
    mp[0].push_back({0, 0}); // 處理整個陣列都被選的 edge case
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        presum += v[i]; // 前綴和加上 v[i]
        predif += v[i] % 2 ? -1 : 1; // 計算前綴奇偶差
        if (presum > k) continue;
        mp[predif].push_back({i, presum}); // 根據奇偶差把目前的端點記錄起來
    }
    int ans = mp[0].size() ? mp[0].back().ss : 0; // 處理全部都選左邊的 edge case
    int sufsum = 0; // 後綴和
    int sufdif = 0; // 後綴奇偶差
    for (int i = n; i >= 1; i--) {
        sufsum += v[i]; // 後綴和加上 v[i]
        sufdif += v[i] % 2 ? -1 : 1; // 計算後綴奇偶差
        vector<pii> endpts = mp[-sufdif]; // 所有奇偶差合法的左端點
        int l = 0;
        int r = upper_bound(all(endpts), (pii){i, -1}) - endpts.begin(); // 不考慮重疊到的
        while (l < r) { // 透過二分搜找到最佳左端點 
            int mid = (l + r) / 2;
            if (endpts[mid].ss + sufsum > k)
                r = mid;
            else
                l = mid + 1;
        }
        if (l <= 0) continue;
        ans = max(ans, endpts[l - 1].ss + sufsum); // 嘗試更新答案
    }
    cout << ans << endl; // 輸出答案
}