此筆記為APCS 2026年03月中高級實作題考試的題目詳解。每一題的題解都包含解題思路、C++範例程式碼。

第一題 比例分割 (ZeroJudge s179.)

題目

小明有一個由 $n$ 個正整數組成的序列 $w_1, w_2, \cdots, w_n$。他對序列中區間的「比例分割點」非常感興趣。 對於任何子區間 $[l,r]$，我們定義其區間和為 $S(l, r)=\sum_{i=l}^{r}w_i$。若 $l > r$，則 $S(l, r) = 0$。 現在小明有 $m$ 個詢問。每個詢問包含四個整數 $l, r, a, b$，請你找到一個唯一的分割點 $k$ ( $l \le k \le r$ )，使得該點滿足以下兩個條件： 1. $\frac{S(l, k-1)}{S(l, r)} < \frac{a}{a+b}$ 2. $\frac{S(k+1, r)}{S(l, r)} \ge \frac{a}{a+b}$ 由於序列中的元素皆為正整數，可以保證對於每一組詢問，符合條件的 $k$ 恰好只有一個。 例如序列為 $2, 2, 6, 3, 1, 5$，當 $a = 1, b = 1$ 時，$k = 3$ 恰好會滿足條件。 $S(1, 2) = 4, S(1, 3) = 10, S(1, 6) = 19$ 1. 4 / 19 < 1 / 2 2. 10 / 19 < 1 / 2

輸入 / 輸出說明

輸入說明 輸出說明
第一行包含兩個整數 $n$ 和 $m$ ( $1 \le n, m \le 10^5$ )，分別代表序列長度與詢問次數。
第二行包含 $n$ 個整數 $w_1, w_2, \cdots, w_n$ ( $1 \le w_i \le 10^4$ )。
接下來的 $m$ 行，每行包含四個整數 $l, r, a, b$ ( $1 \le l \le r \le n, 1 \le a \le b \le 10$ )。
(40分)：$1 \le n, m \le 10^3$
(60分)：無限制		 對於每個詢問，輸出一行包含一個整數 $k$，即滿足條件的分割點索引。

解題思路

這一題提到區間和，然後又可以知道數量級很大，因此一定要用前綴和來做。 接著題目有提到要在區間內找某一個數，這也可以看出來需要用二分搜尋，才能夠在時間內找到答案。 題目有給兩個條件： 1. $\frac{S(l, k-1)}{S(l, r)} < \frac{a}{a+b}$ 2. $\frac{S(k+1, r)}{S(l, r)} \ge \frac{a}{a+b}$ 但其實我們只需要其中一個，這邊我是用第一個，因為題目說 k 只有唯一解，因此第一個滿足時第二個同時也會滿足。 這邊為了避免浮點數運算，我們把第一個條件交叉相乘，得到 $S(l, k-1) * (a+b) < S(l, r) * a$。 偷偷告訴大家，如果你發現執行時間太久，可以試著把 endl 改成 '\n'，我改了之後從 60ms 到 21ms，不過都是會過。

範例程式碼

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
#include <iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, n, m;
	int l, r, a, b;
	int left, right, mid;
	
	cin >> n >> m;
	
	long long int w[n+1], s[n+1]={}, ans;
	
	for (i=1;i<=n;i++) {
		cin >> w[i];
		
		s[i] = s[i-1] + w[i];
	}
	
	for (i=0;i<m;i++) {
		cin >> l >> r >> a >> b;
		
		left = l;
		right = r;
		while (left <= right) {
			mid = (left + right) / 2;
			
			if ((s[mid-1]-s[l-1])*(a+b) < (s[r]-s[l-1])*a) {
				left = mid + 1;
				ans = mid;
			}
			else {
				right = mid - 1;
			}
		}
		
		cout << ans << '\n';
	}

	return 0;
}

運行結果

AC (21ms, 1.8MB)

第二題 觀光旅遊 (ZeroJudge s180.)

題目

某旅行社正準備接待 $n$ 個不同的旅行團。第 $i$ 個旅行團預計在第 $t_i$ 天抵達觀光景點。 當地共有 $m$ 個表演，第 $j$ 個表演的演出期間是從第 $s_j$ 天到第 $e_j$ 天（包含首尾兩天），且每天都會演出一場。為了確保遊客體驗，景點保證：在同一天內，任何兩個不同的表演演出時間都不會重疊。這意味著如果一個旅行團在第 $t_i$ 天在場，且當天有多個表演正在展演期內，該團可以看完當天所有的表演。 如果第 $i$ 團旅行團的抵達日期 $t_i$ 滿足 $s_j \le t_i \le e_j$，則該團可以觀看第 $j$ 個表演。旅行社想要計算這 $n$ 團旅行團總共最多可以看多少場表演（即：將每個旅行團能看到的表演數量加總）。 例如有 $3$ 組旅行團抵達時間為 $7, 5, 10$，總共有 $5$ 種表演時間分別為 $(2, 5), (3, 9), (7, 8), (4, 6), (5, 6)$。 第 $1$ 組旅行團可以看編號為 $2, 3$ 共 $2$ 場表演。 第 $2$ 組旅行團可以看編號為 $1, 2, 4, 5$ 共 $4$ 場表演。 第 $3$ 組旅行團沒有任何表演可以看。 這 $3$ 組旅行團總共可以看 $6$ 場表演。

輸入 / 輸出說明

輸入說明 輸出說明
第一行包含兩個整數 $n$ 和 $m$ ( $1 \le n, m \le 10^5$ )，分別代表旅行團的數量與表演的數量。
第二行包含 $n$ 個整數 $t_1, t_2, \cdots, t_n$ ( $1 \le t_i \le 10^8$ )，代表每個旅行團抵達的日期。
接下來的 $m$ 行，每行包含兩個整數 $s_j$ 和 $e_j$ ( $1 \le s_j \le e_j \le 10^8$ )，代表第 $j$ 個表演的開始與結束日期。
(40分)：$1 \le n, m \le 10^3$
(60分)：無限制		 輸出一個整數，代表所有旅行團總共能觀看的最大表演場次總和。

解題思路

這題因為日期最大可能到 $10^8$，我們不可能直接開一個 $10^8$ 的陣列去存，因此我們改用差分陣列來做。 最重要的一點就是我們存的是相對的日期排名。 我們用 struct 定義一個 Event，其中 time 存日期、type 存類型，用 1 代表表演開始, 0 代表旅行團抵達, -1 代表表演結束。 接著用陣列存 Event，用 cmp 進行排序，規則如下： 1. 日期 (time) 小的先 2. 類型 (type) 大的先 最後我們遍歷一次，遇到 type 是 1 就把 sum + 1，type 是 0 就把 sum 累積到 total，type 是 -1 就把 sum - 1。 又因為我們在同日期會以類型大的優先，這樣就會先表演開始，接著是旅行團抵達，最後才是表演結束。這樣當表演開始與旅行團抵達同一天，會先執行 sum + 1 再累積到 total；當表演結束與旅行團抵達同一天，會先累積到 total 再執行 sum - 1。

範例程式碼

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
#include <bits/stdc++.h>
using namespace std;

struct Event {
	int time = 0;
	// type: 1 開始, 0 旅行團抵達, -1 結束 
	int type;
};

bool cmp(const Event &a, const Event &b) {
	if (a.time == b.time)
		return a.type > b.type;
	return a.time < b.time;
} 

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i;
	int n, m;
	
	cin >> n >> m;

	int t[n], s[m], e[m];
	long long int now = 0, sum = 0, total = 0;
	Event event[2*m+n];
	
	for (i=0;i<n;i++) {
		cin >> t[i];
	}
	
	for (i=0;i<m;i++) {
		cin >> s[i] >> e[i];
		
		event[now].time = s[i];
		event[now].type = 1;
		
		event[now+1].time = e[i];
		event[now+1].type = -1;
	
		now += 2;
	}
	
	for (i=0;i<n;i++) {
		event[now].time = t[i];
		event[now].type = 0;
		now++;
	}
	
	sort(event, event+2*m+n, cmp);
	
	for (i=0;i<2*m+n;i++) {
		if (event[i].type == 1) {
			sum++;
		}
		else if (event[i].type == 0) {
			total += sum;
		}
		else {
			sum--;
		}
	}
	
	cout << total;

	return 0;
}

運行結果

AC (33ms, 3.8MB)

查看更多資訊請至：https://www.tseng-school.com/