APCS 2025/06 解題紀錄（C++）

小心陷阱

題目連結

思路

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

$$\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], $$

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

---

程式碼

#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，以安全索引

$$\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\cdot(m+26))$，總計 $O(k\cdot n\cdot(m+26))$。

---

程式碼

#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)$。

---

程式碼

#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 則必須同組，而不同連通塊間距離皆 $\ge m$ 可任意合併，故可行條件為

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

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

程式碼

#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;
}