APCS

中高級

比例分割

題目連結

思路

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

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

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

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

取滿足此不等式的最小 $m$ 即為答案。單筆查詢 $O(\log n)$，總時間複雜度 $O(n+q\log 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
#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';
	}
}

觀光旅遊

題目連結

思路

旅行社接待 $n$ 個旅行團，第 $i$ 團於第 $t_i$ 天抵達；共有 $m$ 場表演，第 $j$ 場從第 $s_j$ 天演到第 $e_j$ 天。若 $s_j\le t_i\le e_j$，該團即可觀看第 $j$ 場表演，求所有旅行團能觀看的總場次。

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

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

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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;
}

校運代表隊

題目連結

思路

全校 $m$ 個班級、每班 $r$ 人，學生編號 $1$ 至 $m\cdot r$，每人擅長 $n$ 種項目之一。需選 $k$ 人組成代表隊，滿足：(1) $k$ 人的擅長項目互不相同；(2) 每班至多選 2 人。求字典序第 $t$ 小的合法組合。

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

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

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

程式碼

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

高級

步道規劃

題目連結

思路

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

$$C_j=(d_{j+1}-d_j)+\max(0,\,2(h_{j+1}-h_j)). $$

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

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

程式碼

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

骨牌堆疊

題目連結

思路

有 $m$ 張骨牌，每張以 $(a_i,b_i,w_i)$ 表示，代表從 $a_i$ 連接到 $b_i$，權重為 $w_i$；骨牌不可翻轉，且所有 $a_i$ 互不相同、所有 $b_i$ 互不相同。需找出一條合法接龍序列（前一張的 $b$ 等於後一張的 $a$），使權重總和最大。

由於每個節點出度與入度皆至多 $1$，整張圖由若干鏈（路徑）與環組成：

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

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

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

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

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

程式碼

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

貨物運送

題目連結

思路

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

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

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

  1. 同一外送員繼續：工作中的外送員從 $p_{i-1}$ 前往 $p_i$，閒置者不動：

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

  1. 換人執行：閒置外送員從其所在位置前往 $p_i$，原工作者變為閒置（其最後任務為 $i$）：

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

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

最終答案為

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

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

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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;
}

說些什麼吧！

waline