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

說些什麼吧！

waline