中高級
比例分割
思路
給定長度
先建前綴和陣列 pre,令
取滿足此不等式的最小
程式碼
#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';
}
}觀光旅遊
思路
旅行社接待
將旅行團抵達日 t 與表演 v(依開始日 first 排序)分別排序後,以掃描線搭配最小堆處理:依抵達日由小到大掃描每個旅行團,用指標 j 將所有開始日 q;接著將堆頂中結束日 ans。
每場表演至多入堆、出堆各一次,總時間複雜度
程式碼
#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;
}校運代表隊
思路
全校
以 DFS 回溯法從編號小到大列舉,對每位選手做「選」或「不選」的分支:
- 專長不重複:用位元遮罩
used紀錄已選專長(v[pos]為第pos位的專長),選人前檢查!(used & (1 << v[pos]))。 - 班級限額:用
class_cnt[pos / r]計數各班已選人數,選人前檢查< 2。
「選」的分支先於「不選」,確保以編號遞增順序產生組合,等價於字典序由小到大枚舉。加入剪枝 pos + (k - deep) > m * r(剩餘人數不足以湊滿則回退)。當湊滿
程式碼
#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);
}高級
步道規劃
思路
山脈上有
先將觀景點依水平座標排序,計算相鄰點間的體力消耗陣列 v。問題等價於:將陣列 v[2..n] 切成
對猜測的上界
程式碼
#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';
}骨牌堆疊
思路
有
由於每個節點出度與入度皆至多
-
鏈:即一般的序列,直接套用 Kadane 演算法求最大連續子陣列和。
-
環:需求環形最大連續子陣列和。環上的連續子陣列只有兩種情況:
- 不跨越斷點:等同一般的最大連續子陣列和
。 - 跨越斷點:此時「未被選取」的部分形成一段不跨越斷點的連續子陣列,故跨越斷點的最大和
。
取兩者較大值即可。特別地,當所有權重皆為負時,
會選取空序列,此時應直接回傳 (至少選一張骨牌)。 - 不跨越斷點:等同一般的最大連續子陣列和
實作上,先從入度為
程式碼
#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;
}貨物運送
思路
城市有
令
初始狀態
-
同一外送員繼續:工作中的外送員從
前往 ,閒置者不動:
-
換人執行:閒置外送員從其所在位置前往
,原工作者變為閒置(其最後任務為 ):
其中。
最終答案為
即兩位外送員分別從各自位置返回終點
程式碼
#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;
}
載入留言中…