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

2025 年 11 月 APCS 檢定高級三題完整解析:字母配對、列印工廠、翻來覆去,每題附解題思路與 C++ 程式碼。

發布
字數
2,128
閱讀
約 5 分鐘
瀏覽
1,267
本頁目錄
  1. 高級
  2. 字母配對
  3. 列印工廠
  4. 翻來覆去

高級

字母配對

題目連結

思路

此題給定 kk 個堆疊(2≤k≤62\le k\le 6),每個堆疊包含若干物品,每個物品有一個字母標識與分數。每次操作可選擇兩個不同的非空堆疊,若它們的頂部物品字母相同,則同時移除並獲得兩者分數之和。目標是最大化總分數。

採用 DFS + 記憶化搜尋 策略。定義狀態為各堆疊當前已取出的物品數量 (p0,p1,…,pk−1)(p_0,p_1,\ldots,p_{k-1}),其中 0≤pi≤ni0\le p_i\le n_i(nin_i 為第 ii 個堆疊的物品總數)。為了高效儲存與查詢狀態,將多維狀態編碼為單一整數 id:

id=∑i=0k−1pi⋅mi,mi=∏j=0i−1(nj+1). \text{id} = \sum_{i=0}^{k-1} p_i \cdot m_i,\quad m_i = \prod_{j=0}^{i-1}(n_j+1).

即以混合進位制(每維的進位基數為 ni+1n_i+1)將 (p0,…,pk−1)(p_0,\ldots,p_{k-1}) 壓縮成一個整數。

定義 dp[id] 為從狀態 id 開始(即各堆疊分別已取出 p0,…,pk−1p_0,\ldots,p_{k-1} 個物品)到結束所能獲得的最大分數。遞推關係為:

dp[id]=max⁡i<j{bi[pi]+bj[pj]+dp[id′],若 pi<ni,pj<nj 且 ai[pi]=aj[pj],0,否則(無法配對). \text{dp}[\text{id}] = \max_{i<j} \begin{cases} b_i[p_i]+b_j[p_j]+\text{dp}[\text{id}'],&\text{若 }p_i<n_i,p_j<n_j\text{ 且 }a_i[p_i]=a_j[p_j],\\ 0,&\text{否則(無法配對)}. \end{cases}

其中 id′=id+mi+mj\text{id}'=\text{id}+m_i+m_j 表示同時從堆疊 ii 和 jj 各取出一個物品後的新狀態;ai[pi]a_i[p_i] 與 bi[pi]b_i[p_i] 分別為堆疊 ii 頂部(第 pip_i 個)物品的字母與分數。初始狀態為所有 pi=0p_i=0,即 dfs(0)。

遞迴實作時,對所有可行的堆疊對 (i,j)(i,j) 檢查頂部字母是否相同,若相同則嘗試取出並遞迴至新狀態;dp[id] 記錄該狀態下所有可行決策的最大值。使用記憶化陣列 dp(初始化為 -1)避免重複計算。

時間 / 空間複雜度:

  • 狀態數:最多有 ∏i=0k−1(ni+1)\prod_{i=0}^{k-1}(n_i+1) 個狀態。在題目限制下(每個堆疊最多 12 個物品、k≤6k\le 6),狀態數上界為 (12+1)6=136≈4.8×106(12+1)^6=13^6\approx 4.8\times 10^6;實際上題目保證「所有堆疊的物品總數 ∑ni≤12\sum n_i\le 12」,故可行狀態數遠小於此值。
  • 單次狀態轉移:對每個狀態枚舉所有堆疊對 (i,j)(i,j),共 (k2)≤(62)=15\binom{k}{2}\le\binom{6}{2}=15 對,每對常數時間判斷與轉移,故單狀態時間為 O(k2)O(k^2)。
  • 總時間複雜度:O(k2⋅∏i=0k−1(ni+1))O\Big(k^2\cdot\prod_{i=0}^{k-1}(n_i+1)\Big),在題目規模下可接受。
  • 空間複雜度:O(∏i=0k−1(ni+1))O\Big(\prod_{i=0}^{k-1}(n_i+1)\Big) 用於儲存 dp 陣列。

程式碼

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();
vector<vector<char>> a;
vector<vector<int>> b;
vector<int> n, pos, dp, m;
int k;
int dfs(int id) {
	if (dp[id] != -1) return dp[id];
	int now = 0;
	for (int i = 0;i < k;i++) if (pos[i] < n[i]) {
		for (int j = i + 1;j < k;j++) if (pos[j] < n[j] and a[i][pos[i]] == a[j][pos[j]]) {
			now = max(now, b[i][pos[i]++] + b[j][pos[j]++] + dfs(id + m[i] + m[j]));
			pos[i]--, pos[j]--;
		}
	}
	return dp[id] = now;
}
int main() {
	IO
	cin >> k;
	a.resize(k), b.resize(k), n.resize(k), pos.resize(k), m.resize(k);
	int t = 1;
	for (int i = 0;i < k;i++) {
		cin >> n[i];
		a[i].resize(n[i]), b[i].resize(n[i]);
		for (int j = 0;j < n[i];j++) cin >> a[i][j] >> b[i][j];
		m[i] = t;
		t *= n[i] + 1;
	}
	dp.resize(t, -1);
	cout << dfs(0);
}

列印工廠

題目連結

思路

給定 nn 個印刷任務(1≤n≤81\le n\le 8),每個任務 ii 有開始時間 sis_i、截止時間 did_i 與所需時間 tit_i。任務必須在 [si,di][s_i, d_i] 內完成,且執行期間不可中斷。目標是找出一個任務排程順序,使得所有任務都能在截止時間內完成,並且最大化相鄰任務間的最小間隔時間(即所有相鄰任務對的間隔時間都至少為某個固定值 gg,求 gg 的最大值)。

核心策略:枚舉所有可能的任務排列順序(共 8!=403208!=40320 種),對每個排列使用二分搜尋找出最大可行的固定間隔 gg。

演算法流程:

  1. 排列枚舉:使用 next_permutation 枚舉所有 n!n! 種任務排列順序(對陣列 v 先排序,再反覆呼叫 next_permutation 直到回到初始狀態)。

  2. 二分搜尋間隔 gg:對每個排列,在 [0,1000][0, 1000] 區間內二分搜尋最大可行間隔 gg。定義「可行」為:按照該排列順序依次執行任務,每兩個任務之間至少休息 gg 秒,且所有任務都能在截止時間內完成。

  3. 可行性檢查:對固定的 gg,從頭到尾模擬任務執行:

    • 設 last 為當前時間(初始為 0)。
    • 對排列中的第 ii 個任務(i=0,1,…,n−1i=0,1,\ldots,n-1):
      • 若 i>0i>0,先讓印刷機休息 gg 秒:last += g。
      • 更新開始時間為「當前時間」與「任務最早開始時間 sis_i」的較大值:last = max(last, s[i])。
      • 檢查是否能在截止時間前完成:若 last + t[i] > d[i],則不可行(can = false)。
      • 更新當前時間為任務結束時間:last += t[i]。
    • 若所有任務都通過檢查,則 gg 可行,更新答案 ans = max(ans, g) 並嘗試更大的 gg(l = m + 1);否則縮小 gg(r = m - 1)。
  4. 輸出最大值:所有排列檢查完畢後,輸出 ans。

時間 / 空間複雜度:

  • 排列數:O(n!)O(n!);每個排列需二分搜尋 O(log⁡V)O(\log V) 次(V=1000V=1000 為時間值域),每次檢查需 O(n)O(n);總時間複雜度為
O(n!⋅nlog⁡V). O(n! \cdot n \log V).

在 n≤8n\le 8 時,8!⋅8⋅log⁡1000≈8!⋅80≈3.2×1068!\cdot 8\cdot\log 1000\approx 8!\cdot 80\approx 3.2\times 10^6,可接受。

  • 空間用於儲存任務資訊與排列狀態,為
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);
const long long INF = numeric_limits<int>::max();
int main() {
	IO
	int n;
	cin >> n;
	vector<array<int, 3>> v(n);
	for (auto &[s, d, t] : v) cin >> s >> d >> t;
	sort(v.begin(), v.end());
	int ans = 0;
	do {
		int l = 0, r = 1000;
		while (l <= r) {
			int m = (l + r) / 2;
			int last = 0;
			bool can = 1;
			for (int i = 0;i < n;i++) {
				if (i) last += m;
				last = max(last, v[i][0]);
				if (last + v[i][2] > v[i][1]) {
					can = 0;
					break;
				}
				last += v[i][2];
			}
			if (can) ans = max(ans, m), l = m + 1;
			else r = m - 1;
		}
	} while(next_permutation(v.begin(), v.end()));
	cout << ans;
}

翻來覆去

題目連結

思路

給定長度為 nn 的排列 PP,初始時所有元素從 pnp_n 到 p1p_1 依序推入堆疊 S2S_2(pnp_n 在底、p1p_1 在頂)。目標是使用兩個堆疊的 push 與 pop 操作將排列排序成遞增順序,並求最少需要多少次 pop 操作。

核心觀察:要輸出遞增序列 1,2,…,n1,2,\ldots,n,最佳策略是按順序從 1 到 nn 依次取出每個數字。對於當前要取出的數字 ii,設其在原始排列中的位置為 p=pos[i]p=\text{pos}[i],則需要將該數字從所在堆疊的頂部「挖」出來,過程中會連帶 pop 出擋在它上方的所有元素(這些元素會被推入另一個堆疊)。

資料結構與維護:

  1. 堆疊表示:不顯式儲存堆疊內容,而是用區間列表 s1 與 s2 維護兩個堆疊當前擁有的連續區間 [l,r][l,r](表示原始排列位置 ll 到 rr 的元素都在該堆疊)。堆疊頂部對應最後加入的區間;同一堆疊內各區間不重疊。

  2. 位置標記:使用 BIT(樹狀陣列) 進行區間加減,維護每個位置屬於哪個堆疊:bit.get(p) 返回 1 表示位置 pp 在 S2S_2,返回 0 表示在 S1S_1。初始時所有位置標記為 1(全在 S2S_2)。

演算法流程(按 i=1,2,…,ni=1,2,\ldots,n 順序處理):

  1. 查詢 p=pos[i]p=\text{pos}[i] 與其所屬堆疊 t=bit.get(p)t=\text{bit.get}(p)(from 為當前堆疊,to 為另一堆疊)。

  2. 堆疊頂部調整:若 from 的最頂區間 [l,r][l,r] 不包含 pp(即 p∉[l,r]p\notin[l,r]),表示該區間整體在 pp 的上方,需先將其全部 pop(共 r−l+1r-l+1 次)並推入 to,同時更新 BIT 標記;重複此步驟直到頂部區間包含 pp。

  3. 取出目標元素:設頂部區間為 [l,r][l,r],根據堆疊類型分情況處理:

    • 若 t=1t=1(S2S_2,左側為頂):需 pop 出 [l,p][l,p] 共 p−l+1p-l+1 個元素。若 l<pl<p,將左側部分 [l,p−1][l,p-1] 推入 to;若 p<rp<r,更新 from 的頂部區間為 [p+1,r][p+1,r],否則移除該區間。

    • 若 t=0t=0(S1S_1,右側為頂):需 pop 出 [p,r][p,r] 共 r−p+1r-p+1 個元素。若 p<rp<r,將右側部分 [p+1,r][p+1,r] 推入 to;若 l<pl<p,更新 from 的頂部區間為 [l,p−1][l,p-1],否則移除該區間。

  4. 累加 pop 次數到 ans。

時間 / 空間複雜度:

  • 每個區間最多被建立與刪除各一次,總區間數 O(n)O(n);每次查詢 BIT 與區間加減皆為 O(log⁡n)O(\log n);總時間複雜度為
O(nlog⁡n). O(n\log n).
  • 空間用於 BIT 與區間列表,為
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);
const long long INF = numeric_limits<int>::max();
struct BIT{
	int n; vector<int> b;
	BIT(int n = 0) {init(n);}
	void init(int x) {
		n = x + 1;
		b.assign(n + 2, 0);
	}
	void add(int i, int v) {
		for (;i <= n;i += i & -i) b[i] += v;
	}
	void range_add(int l, int r, int v) {
		if (l <= r) {
			add(l, v);
			add(r+1,-v);
		}
	}
	int get(int i) {
		int s = 0;
		for (;i;i -= i & -i) s+=b[i];
		return s;
	} // 0=S1, 1=S2
};
int main() {
	IO
	int n;
	cin >> n;
	vector<int> pos(n + 1);
	for (int i = 1, x;i <= n;i++) {
		cin >> x;
		pos[x] = i;
	}
	vector<pair<int, int>> s1, s2;
	s2.push_back({1, n});
	BIT bit(n);
	bit.range_add(1, n, 1);
	int ans = 0;
	for (int i = 1;i <= n;i++) {
		int p = pos[i], t = bit.get(p);
		auto &from = (t ? s2 : s1), &to = (t ? s1 : s2);
		while (1) {
			auto [l, r] = from.back();
			if (l <= p and p <= r) break;
			ans += r - l + 1;
			bit.range_add(l, r, t ? -1 : 1);
			to.push_back({l, r});
			from.pop_back();
		}
		auto [l, r] = from.back();
		if (t) {
			ans += p - l + 1;
			if (l <= p - 1) {
				bit.range_add(l, p - 1, -1);
				to.push_back({l, p - 1});
			}
			if (p + 1 <= r) from.back().first = p + 1;
			else from.pop_back();
		}
		else {
			ans += r - p + 1;
			if (p + 1 <= r) {
				bit.range_add(p + 1, r, 1);
				to.push_back({p + 1, r});
			}
			if (l <= p - 1) from.back().second = p - 1;
			else from.pop_back();
		}
	}
	cout << ans;
}

最後更新 2025.11.16

Comments

留言

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

載入留言中…

Esc

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

↑ ↓ 選擇Enter 開啟