APCS

高級

字母配對

題目連結

思路

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

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

$$\text{id} = \sum_{i=0}^{k-1} p_i \cdot m_i,\quad m_i = \prod_{j=0}^{i-1}(n_j+1). $$

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

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

$$\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} $$

其中 $\text{id}'=\text{id}+m_i+m_j$ 表示同時從堆疊 $i$ 和 $j$ 各取出一個物品後的新狀態；$a_i[p_i]$ 與 $b_i[p_i]$ 分別為堆疊 $i$ 頂部（第 $p_i$ 個）物品的字母與分數。初始狀態為所有 $p_i=0$，即 dfs(0)。

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

時間 / 空間複雜度：

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

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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);
}

列印工廠

題目連結

思路

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

核心策略：枚舉所有可能的任務排列順序（共 $8!=40320$ 種），對每個排列使用二分搜尋找出最大可行的固定間隔 $g$。

演算法流程：

  1. 排列枚舉：使用 next_permutation 枚舉所有 $n!$ 種任務排列順序（對陣列 v 先排序，再反覆呼叫 next_permutation 直到回到初始狀態）。

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

  3. 可行性檢查：對固定的 $g$，從頭到尾模擬任務執行：

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

  4. 輸出最大值：所有排列檢查完畢後，輸出 ans。

時間 / 空間複雜度：

  • 排列數：$O(n!)$；每個排列需二分搜尋 $O(\log V)$ 次（$V=1000$ 為時間值域），每次檢查需 $O(n)$；總時間複雜度為

$$O(n! \cdot n \log V). $$

在 $n\le 8$ 時，$8!\cdot 8\cdot\log 1000\approx 8!\cdot 80\approx 3.2\times 10^6$，可接受。

  • 空間用於儲存任務資訊與排列狀態，為

$$O(n). $$

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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;
}

翻來覆去

題目連結

思路

給定長度為 $n$ 的排列 $P$，初始時所有元素從 $p_n$ 到 $p_1$ 依序推入堆疊 $S_2$（$p_n$ 在底、$p_1$ 在頂）。目標是使用兩個堆疊的 push 與 pop 操作將排列排序成遞增順序，並求最少需要多少次 pop 操作。

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

資料結構與維護：

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

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

演算法流程（按 $i=1,2,\ldots,n$ 順序處理）：

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

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

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

    • 若 $t=1$（$S_2$，左側為頂）：需 pop 出 $[l,p]$ 共 $p-l+1$ 個元素。若 $l<p$，將左側部分 $[l,p-1]$ 推入 to；若 $p<r$，更新 from 的頂部區間為 $[p+1,r]$，否則移除該區間。

    • 若 $t=0$（$S_1$，右側為頂）：需 pop 出 $[p,r]$ 共 $r-p+1$ 個元素。若 $p<r$，將右側部分 $[p+1,r]$ 推入 to；若 $l<p$，更新 from 的頂部區間為 $[l,p-1]$，否則移除該區間。

  4. 累加 pop 次數到 ans。

時間 / 空間複雜度：

  • 每個區間最多被建立與刪除各一次，總區間數 $O(n)$；每次查詢 BIT 與區間加減皆為 $O(\log n)$；總時間複雜度為

$$O(n\log n). $$

  • 空間用於 BIT 與區間列表，為

$$O(n). $$

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#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;
}

說些什麼吧！

waline