APCS 2025/06 解題紀錄(C++)

2025 年 6 月 APCS 檢定四題完整解析:小心陷阱、轉盤得分、貪心闖關、分組遊戲,每題附解題思路與 C++ 程式碼。

發布
字數
936
閱讀
約 2 分鐘
瀏覽
189
本頁目錄
  1. 小心陷阱
  2. 思路
  3. 程式碼
  4. 轉盤得分
  5. 思路
  6. 程式碼
  7. 貪心闖關
  8. 思路
  9. 程式碼
  10. 分組遊戲
  11. 思路
  12. 程式碼

小心陷阱

題目連結

思路

採直接模擬並嚴格遵循「先移動、後扣血」。初始化 now = k 表示從位置 0 以步長 k 跳到第一個落點;在 while (k > 0) 的每輪,先依 now 是否分別為 x1、x2 的倍數扣除 y1、y2(可同時扣),若仍 k>0,則續行 now += k 進入下一輪。形式化遞推為

nowt=nowt−1+kt−1,kt=kt−1−y1 [x1∣nowt]−y2 [x2∣nowt], \text{now}_t=\text{now}_{t-1}+k_{t-1},\qquad k_t = k_{t-1}-y_1\,[x_1\mid \text{now}_t]-y_2\,[x_2\mid \text{now}_t],

當 kt≤0k_t\le 0 停止並輸出 nowt\text{now}_t。不變量為「每輪開頭的 now 等於上一輪完成跳躍的落點」,據此流程與題意等價;時間複雜度為回合數的線性時間。


程式碼

C++
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
int main() {
    int k, x1, y1, x2, y2;
    cin >> k >> x1 >> y1 >> x2 >> y2;
    int now = k;
    while (k > 0) {
        if (now % x1 == 0) k -= y1;
        if (now % x2 == 0) k -= y2;
        now += max(0, k);
    }
    cout << now;
}

轉盤得分

題目連結

思路

以 pos[j] 表示第 j 個輪盤的總旋轉量;每回合讀入位移 x 後做 pos[j] -= x。對每個直欄 i=0..n-1,以安全索引

idx(i,j)=((i+pos[j]) mod n+n) mod n \mathrm{idx}(i,j)=\big((i+\mathrm{pos}[j]) \bmod n + n\big)\bmod n

取得 s[j][idx(i,j)],用陣列 a[26] 統計該欄 m 個字元的頻率,取最大值 MAX 累加至 ans。本質為將每個 s[j] 旋轉 pos[j] 後逐欄取眾數;單回合成本 O(n⋅(m+26))O(n\cdot(m+26)),總計 O(k⋅n⋅(m+26))O(k\cdot n\cdot(m+26))。


程式碼

C++
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
int main() {
    int m, n, k;
    cin >> m >> n >> k;
    vector<string> s(m);
    for (auto &x : s) cin >> x;
    vector<int> pos(m, 0);
    int ans = 0;
    while (k--) {
        for (int i = 0; i < m; i++) {
            int x; cin >> x;
            pos[i] -= x;
        }
        for (int i = 0; i < n; i++) {
            int a[26] = {}, MAX = 0;
            for (int j = 0; j < m; j++) {
                MAX = max(MAX, ++a[s[j][(((i + pos[j]) % n) + n) % n] - 'a']);
            }
            ans += MAX;
        }
    }
    cout << ans;
}

貪心闖關

題目連結

思路

以嚴格遞減單調棧 st 模擬「較小堆優先被搬空並併入較大堆」:讀入一堆 x 時,只要 st.back() ≤ x,即將 st.back() 全量加到 ans,並合併至 x(x += st.back())後彈出,直到棧頂 > x 才停止;合併完若 x ≤ t 則把 x 推回 st。全部處理後,再把 st 內殘餘總和加進 ans 即為答案。交換論證可證「先處理較小堆」不劣於任何合法搬運序;每堆至多入棧、出棧各一次,時間複雜度 O(n)O(n)。


程式碼

C++
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
const long long INF = numeric_limits<int>::max();
signed main() {
    IO
    int n, t; cin >> n >> t;
    vector<int> st;
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long x; cin >> x;
        while (!st.empty() && st.back() <= x) {
            ans += st.back();
            x += st.back();
            st.pop_back();
        }
        if (x <= t) st.push_back(x);
    }
    for (auto x : st) ans += x;
    cout << ans;
}

分組遊戲

題目連結

思路

二分門檻 m。對固定 m,在鄰接表 v 上僅沿「權重 < m」的邊用 vis + BFS/DFS 計算連通塊數 cnt:任兩點若距離 < m 則必須同組,而不同連通塊間距離皆 ≥m\ge m 可任意合併,故可行條件為

f(m)  =  ( cnt≥k ). f(m)\;=\;(\,\text{cnt}\ge k\,).

在距離值域以 l..r 二分最大可行 m:若 f(m) 成立則更新 ans=m, l=m+1,否則 r=m-1。單次檢查 O(n2)O(n^2),總複雜度 O(n2log⁡V)O(n^2\log V)(V 為距離值域或不同距離數)。

程式碼

C++
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
int n, k;
vector<vector<pair<int,int>>> v;
bool f(int m) {
    bitset<505> vis;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        cnt++;
        queue<int> q; q.push(i); vis[i] = 1;
        while (!q.empty()) {
            int t = q.front(); q.pop();
            for (auto [nt, x] : v[t]) {
                if (vis[nt] || x >= m) continue;
                vis[nt] = 1;
                q.push(nt);
            }
        }
    }
    return cnt >= k;
}
int main() {
    IO
    cin >> n >> k;
    v.resize(n + 1);
    int l = INF, r = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int x; cin >> x;
            if (i != j) v[i].push_back({j, x});
            r = max(r, x);
            l = min(l, x);
        }
    }
    while (l <= r) {
        int m = (l + r) / 2;
        if (f(m)) { ans = m; l = m + 1; }
        else r = m - 1;
    }
    cout << ans;
}
最後更新 2025.09.08

Comments

留言

支援 Markdown、程式碼高亮(```cpp)與 LaTeX($E=mc^2$),Ctrl + Enter 送出。頭像會用你的 e-mail 去 Gravatar 找,e-mail 本身不會公開。

載入留言中…

Esc

輸入關鍵字,例如「線段樹」「Makefile」「面試」。

↑ ↓ 選擇Enter 開啟