APCS 2026/03 解題紀錄(C++)

2026 年 3 月 APCS 檢定中高級與高級完整解析:比例分割、觀光旅遊、校運代表隊、步道規劃、骨牌堆疊、貨物運送,附解題思路與 C++ 程式碼。

發布
更新
字數
2,275
閱讀
約 6 分鐘
瀏覽
1,602
本頁目錄
  1. 中高級
  2. 比例分割
  3. 觀光旅遊
  4. 校運代表隊
  5. 高級
  6. 步道規劃
  7. 骨牌堆疊
  8. 貨物運送

中高級

比例分割

題目連結

思路

給定長度 nn 的正整數序列 ww,對每筆查詢 (l,r,a,b)(l,r,a,b) 需找到唯一的分割點 kk,使得

S(l,k−1)S(l,r)<aa+b≤S(l,k)S(l,r). \frac{S(l,k-1)}{S(l,r)}<\frac{a}{a+b}\le\frac{S(l,k)}{S(l,r)}.

先建前綴和陣列 pre,令 S(l,r)=pre[r]−pre[l−1]S(l,r)=\text{pre}[r]-\text{pre}[l-1],即可 O(1)O(1) 取得任意區間和。因所有元素為正整數,S(l,k)S(l,k) 隨 kk 嚴格遞增,故滿足條件的 kk 恰好一個,可在 [l,r][l,r] 上二分搜尋。為避免浮點除法,將判斷條件交叉相乘改寫為整數形式:

S(l,m)⋅(a+b)≥a⋅S(l,r), S(l,m)\cdot(a+b)\ge a\cdot S(l,r),

取滿足此不等式的最小 mm 即為答案。單筆查詢 O(log⁡n)O(\log n),總時間複雜度 O(n+qlog⁡n)O(n+q\log 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() {
	int n, q;
	cin >> n >> q;
	vector<int> v(n + 1), pre(n + 1);
	for (int i = 1;i <= n;i++) {
		cin >> v[i];
		pre[i] = v[i] + pre[i - 1];
	}
	while (q--) {
		int l, r, a, b, ans, L, R;
		cin >> l >> r >> a >> b;
		L = l, R = r;
		while (L <= R) {
			int m = (L + R) / 2;
			if ((pre[m] - pre[l - 1]) * (a + b) >= a * (pre[r] - pre[l - 1])) ans = m, R = m - 1;
			else L = m + 1;
		}
		cout << ans << '\n';
	}
}

觀光旅遊

題目連結

思路

旅行社接待 nn 個旅行團,第 ii 團於第 tit_i 天抵達;共有 mm 場表演,第 jj 場從第 sjs_j 天演到第 eje_j 天。若 sj≤ti≤ejs_j\le t_i\le e_j,該團即可觀看第 jj 場表演,求所有旅行團能觀看的總場次。

將旅行團抵達日 t 與表演 v(依開始日 first 排序)分別排序後,以掃描線搭配最小堆處理:依抵達日由小到大掃描每個旅行團,用指標 j 將所有開始日 sj≤xs_j\le x 的表演之結束日 eje_j 推入 min-heap q;接著將堆頂中結束日 ej<xe_j < x(已過期)的表演彈出。此時堆中剩餘的元素數量即為該旅行團可觀看的表演數,累加至 ans。

每場表演至多入堆、出堆各一次,總時間複雜度 O((n+m)log⁡m)O((n+m)\log m)。


程式碼

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() {
	int n, m;
	cin >> n >> m;
	vector<int> t(n);
	for (auto &x : t) cin >> x;
	vector<pair<int, int>> v(m);
	for (auto &[x, y] : v) cin >> x >> y;
	sort(t.begin(), t.end());
	sort(v.begin(), v.end());
	priority_queue<int, vector<int>, greater<int>> q;
	int ans = 0, j = 0;
	for (auto x : t) {
		while (j < m and v[j].first <= x) q.push(v[j++].second);
		while (!q.empty() and q.top() < x) q.pop();
		ans += q.size();
	}
	cout << ans;
}

校運代表隊

題目連結

思路

全校 mm 個班級、每班 rr 人,學生編號 11 至 m⋅rm\cdot r,每人擅長 nn 種項目之一。需選 kk 人組成代表隊,滿足:(1) kk 人的擅長項目互不相同;(2) 每班至多選 2 人。求字典序第 tt 小的合法組合。

以 DFS 回溯法從編號小到大列舉,對每位選手做「選」或「不選」的分支:

  1. 專長不重複:用位元遮罩 used 紀錄已選專長(v[pos] 為第 pos 位的專長),選人前檢查 !(used & (1 << v[pos]))。
  2. 班級限額:用 class_cnt[pos / r] 計數各班已選人數,選人前檢查 < 2。

「選」的分支先於「不選」,確保以編號遞增順序產生組合,等價於字典序由小到大枚舉。加入剪枝 pos + (k - deep) > m * r(剩餘人數不足以湊滿則回退)。當湊滿 kk 人時計數器遞增,達到第 tt 組即排序輸出。由於 n≤9, m≤17, r≤4, k≤5n\le 9,\,m\le 17,\,r\le 4,\,k\le 5,搜索空間有限,加上剪枝可在時限內完成。


程式碼

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();
int n, m, r, k, t, cnt = 0;
vector<int> v, ans, class_cnt;
void dfs(int pos, int used, int deep) {
	if (deep == k) {
		if (++cnt == t) {
			sort(ans.begin(), ans.end());
			for (auto x : ans) cout << x << ' ';
			exit(0);
		}
		return;
	}
	if (pos + (k - deep) > m * r) return;
	if (!(used & (1ll << v[pos])) and class_cnt[pos / r] < 2) {
		ans[deep] = pos + 1;
		class_cnt[pos / r]++;
		dfs(pos + 1, used | (1ll << v[pos]), deep + 1);
		class_cnt[pos / r]--;
	}
	dfs(pos + 1, used, deep);
}
signed main() {
	cin >> n >> m >> r >> k >> t;
	v.resize(m * r);
	ans.resize(k);
	class_cnt.resize(m);
	for (auto &x : v) cin >> x;
	dfs(0, 0, 0);
}

高級

步道規劃

題目連結

思路

山脈上有 nn 個觀景點,各自具有水平座標 did_i 與高度 hih_i,需將其劃分為 kk 段連續步道,使得難度最大的那條步道之難度值最小化。相鄰兩點間的體力消耗定義為

Cj=(dj+1−dj)+max⁡(0, 2(hj+1−hj)). C_j=(d_{j+1}-d_j)+\max(0,\,2(h_{j+1}-h_j)).

先將觀景點依水平座標排序,計算相鄰點間的體力消耗陣列 v。問題等價於:將陣列 v[2..n] 切成 kk 段,使各段之和的最大值最小——經典的「最小化最大值」問題,適合對答案二分搜尋。

對猜測的上界 mm,以貪心法驗證:從左到右累加,當前段和超過 mm 時便開一段新的,最終所需段數 ≤k\le k 即表示 mm 可行。二分範圍 [0,∑vi][0,\sum v_i],時間複雜度 O(nlog⁡(∑vi))O(n\log(\sum v_i))。


程式碼

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() {
	int n, k;
	cin >> n >> k;
	vector<int> v(n + 1);
	vector<pair<int, int>> p(n + 1);
	for (int i = 1;i <= n;i++) cin >> p[i].first;
	for (int i = 1;i <= n;i++) cin >> p[i].second;
	int l = 0, r = 0, ans;
	sort(p.begin(), p.end());
	for (int i = 2;i <= n;i++) v[i] = (p[i].first - p[i - 1].first) + max(0ll, 2 * (p[i].second - p[i - 1].second)), r += v[i];
	while (l <= r) {
		int m = (l + r) / 2, sum = 0, cnt = 1;
		for (int i = 2;i <= n and cnt <= k;i++) {
			if (sum + v[i] <= m) sum += v[i];
			else sum = 0, cnt++;;
		}
		if (cnt <= k) r = m - 1, ans = m;
		else l = m + 1;
	}
	cout << ans << '\n';
}

骨牌堆疊

題目連結

思路

有 mm 張骨牌,每張以 (ai,bi,wi)(a_i,b_i,w_i) 表示,代表從 aia_i 連接到 bib_i,權重為 wiw_i;骨牌不可翻轉,且所有 aia_i 互不相同、所有 bib_i 互不相同。需找出一條合法接龍序列(前一張的 bb 等於後一張的 aa),使權重總和最大。

由於每個節點出度與入度皆至多 11,整張圖由若干鏈(路徑)與環組成:

  • 鏈:即一般的序列,直接套用 Kadane 演算法求最大連續子陣列和。

  • 環:需求環形最大連續子陣列和。環上的連續子陣列只有兩種情況:

    1. 不跨越斷點:等同一般的最大連續子陣列和 maxSub\text{maxSub}。
    2. 跨越斷點:此時「未被選取」的部分形成一段不跨越斷點的連續子陣列,故跨越斷點的最大和 =totalSum−minSub=\text{totalSum}-\text{minSub}。

    取兩者較大值即可。特別地,當所有權重皆為負時,totalSum−minSub=0\text{totalSum}-\text{minSub}=0 會選取空序列,此時應直接回傳 maxSub\text{maxSub}(至少選一張骨牌)。

實作上,先從入度為 00 的節點出發走訪所有鏈並標記已訪問,再對剩餘未訪問且有出邊的節點走訪環。取所有鏈與環中的最大值即為答案。時間複雜度 O(n+m)O(n+m)。


程式碼

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 line(vector<int> &v) {
	int now = 0, best = -INF;
	for (auto x : v) {
		now += x;
		best = max(best, now);
		now = max(0, now);
	}
	return best;
}
int cycle(vector<int> &v) {
	int sum = 0, mx_now = 0, mx_best = -INF, mn_now = 0, mn_best = INF;
	for (auto x : v) {
		sum += x, mx_now += x, mn_now += x;
		mx_best = max(mx_best, mx_now);
		mx_now = max(0, mx_now);
		mn_best = min(mn_best, mn_now);
		mn_now = min(0, mn_now);
	}
	if (mx_best < 0) return mx_best;
	return max(mx_best, sum - mn_best);
}
int main() {
	int n, m;
	cin >> n >> m;
	vector<int> to(n + 1, -1), w(n + 1, -INF), in(n + 1);
	for (int i = 0;i < m;i++) {
		int a, b, c;
		cin >> a >> b >> c;
		to[a] = b;
		w[a] = c;
		in[b]++;
	}
	vector<bool> vis(n + 1);
	int ans = *max_element(w.begin(), w.end());
	for (int i = 1;i <= n;i++) {
		if (to[i] != -1 and !in[i]) {
			vector<int> v;
			int t = i;
			while (to[t] != -1) {
				vis[t] = 1;
				v.push_back(w[t]);
				t = to[t];
			}
			ans = max(ans, line(v));
		}
	}
	for (int i = 1;i <= n;i++) {
		if (to[i] != -1 && !vis[i]) {
			vector<int> v;
			int t = i;
			while (!vis[t]) {
				vis[t] = 1;
				v.push_back(w[t]);
				t = to[t];
			}
			ans = max(ans, cycle(v));
		}
	}
	cout << ans;
}

貨物運送

題目連結

思路

城市有 nn 個地點與 kk 個外送任務,任務必須依序完成。兩位外送員 A、B 初始皆在地點 11,每個任務恰由其中一人執行,全部完成後兩人皆須回到地點 nn。給定 n×nn\times n 的費用矩陣 cost[u][v]\text{cost}[u][v],求最小總花費。

令 dp[i][j]\text{dp}[i][j] 表示已完成前 ii 個任務、「閒置外送員」最後執行的任務編號為 jj(j=0j=0 表示該外送員尚未執行任何任務,仍在起點 11)時的最小花費。此時「工作中的外送員」剛完成第 ii 個任務,位於 pi−1p_{i-1}。

初始狀態 dp[1][0]=cost[1][p0]\text{dp}[1][0]=\text{cost}[1][p_0](A 執行第一個任務,B 閒置於起點)。轉移時對第 i+1i+1 個任務考慮兩種指派:

  1. 同一外送員繼續:工作中的外送員從 pi−1p_{i-1} 前往 pip_i,閒置者不動:

    dp[i+1][j]=min⁡(dp[i+1][j],  dp[i][j]+cost[pi−1][pi]).\text{dp}[i+1][j]=\min\bigl(\text{dp}[i+1][j],\;\text{dp}[i][j]+\text{cost}[p_{i-1}][p_i]\bigr).

  2. 換人執行:閒置外送員從其所在位置前往 pip_i,原工作者變為閒置(其最後任務為 ii):

    dp[i+1][i]=min⁡(dp[i+1][i],  dp[i][j]+cost[pos(j)][pi]),\text{dp}[i+1][i]=\min\bigl(\text{dp}[i+1][i],\;\text{dp}[i][j]+\text{cost}[\text{pos}(j)][p_i]\bigr),

    其中 pos(j)={1j=0pj−1j≥1\text{pos}(j)=\begin{cases}1&j=0\\p_{j-1}&j\ge 1\end{cases}。

最終答案為

min⁡0≤j<k(dp[k][j]+cost[pk−1][n]+cost[pos(j)][n]),\min_{0\le j<k}\bigl(\text{dp}[k][j]+\text{cost}[p_{k-1}][n]+\text{cost}[\text{pos}(j)][n]\bigr),

即兩位外送員分別從各自位置返回終點 nn。時間複雜度 O(k2)O(k^2)。


程式碼

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 n, k;
	cin >> n >> k;
	vector<int> p(k);
	for (auto &x : p) cin >> x;
	vector<vector<int>> dp(k + 1, vector<int>(k + 1, INF)), v(n + 1, vector<int>(n + 1));
	for (int i = 1;i <= n;i++) for (int j = 1;j <= n;j++) cin >> v[i][j];
	dp[1][0] = v[1][p[0]];
	for (int i = 1;i < k;i++) for (int j = 0;j < i;j++) {
		if (dp[i][j] == INF) continue;
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + v[p[i - 1]][p[i]]);
		dp[i + 1][i] = min(dp[i + 1][i], dp[i][j] + v[(j == 0 ? 1 : p[j - 1])][p[i]]);
	}
	int ans = INF;
	for (int i = 0;i < k;i++) ans = min(ans, dp[k][i] + v[p[k - 1]][n] + v[(i == 0 ? 1 : p[i - 1])][n]);
	cout << ans;
}
最後更新 2026.03.20

Comments

留言

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

載入留言中…

Esc

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

↑ ↓ 選擇Enter 開啟