2023 Benelux算法编程竞赛（BAPC 23）题目解析
A - 软件包下载优化
给定 n 个软件包的大小，可同时下载 k 个，已有 m 个完成。目标是选择 k 个新包下载，使总完成进度最大化，输出百分比。
解法：优先选择最大的 m + k 个包，排序后累加前 m + k 项即可。
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<int> sizes(n);
long long total = 0;
for (int i = 0; i < n; ++i) {
cin >> sizes[i];
total += sizes[i];
}
if (m + k >= n) {
cout << fixed << setprecision(12) << 100.0 << endl;
return;
}
sort(sizes.rbegin(), sizes.rend());
long long completed = 0;
for (int i = 0; i < m + k; ++i) {
completed += sizes[i];
}
cout << fixed << setprecision(15) << (double)completed / total * 100.0 << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T--) solve();
return 0;
}
B - 机器人归零操作
给定整数 n，支持两种操作：n /= 2（向下取整）或 n -= 1。求将 n 变为 0 的最少步数。
贪心策略：若 n 为偶数，除以 2；若为奇数，先减 1 再除以 2。使用高精度浮点类型避免溢出。
#include <bits/stdc++.h>
using namespace std;
void solve() {
long double num;
cin >> num;
int steps = 0;
while (num > 1) {
num /= 2;
steps++;
}
cout << steps + 1 << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T--) solve();
return 0;
}
D - 民主命名系统
给定 n 个长度为 m 的字符串，对每一位找出出现频率最高的字符，若有多个则选字典序最小者。
使用计数数组统计每列字符频次，遍历取最大值并处理字典序。
#include <bits/stdc++.h>
using namespace std;
const int MAX_LEN = 1005;
void solve() {
int n, m;
cin >> n >> m;
vector<string> strs(n);
for (int i = 0; i < n; ++i) {
cin >> strs[i];
}
for (int j = 0; j < m; ++j) {
int count[26] = {};
for (int i = 0; i < n; ++i) {
count[strs[i][j] - 'a']++;
}
int max_freq = 0;
char best_char = 'z' + 1;
for (int c = 0; c < 26; ++c) {
if (count[c] > max_freq || (count[c] == max_freq && 'a' + c < best_char)) {
max_freq = count[c];
best_char = 'a' + c;
}
}
cout << best_char;
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T--) solve();
return 0;
}
E - 考试复习规划
有 n 场考试，每场有两种状态：准备或不准备。准备需耗时 c[i]，结束时间不同。已知各场开始与结束时间，求最多能通过多少场。
动态规划：状态 dp[i][j] 表示前 i 场考试中通过 j 场所需的最早完成时间。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2005;
long long dp[MAX_N][MAX_N];
void solve() {
int n;
cin >> n;
vector<int> start(n+1), no_prep_end(n+1), prep_end(n+1), cost(n+1);
for (int i = 1; i <= n; ++i) {
cin >> start[i] >> prep_end[i] >> no_prep_end[i] >> cost[i];
}
// 初始化
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
dp[i][j] = -1e18;
dp[0][0] = start[1];
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= i; ++j) {
// 不准备该考试
dp[i][j] = max(dp[i][j], dp[i-1][j] + (i == n ? 0 : start[i+1] - no_prep_end[i]));
if (j == 0) continue;
// 准备该考试且时间足够
if (dp[i-1][j-1] >= cost[i]) {
dp[i][j] = max(dp[i][j], dp[i-1][j-1] + (i == n ? 0 : start[i+1] - prep_end[i]) - cost[i]);
}
}
}
for (int j = n; j >= 0; --j) {
if (dp[n][j] >= 0) {
cout << j << '\n';
return;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T--) solve();
return 0;
}
G - 几何图形识别
给定四个点坐标，判断其构成的四边形类型：正方形、菱形、矩形、平行四边形、梯形、筝形或无匹配。
通过向量运算判断边长、角度和对边平行性，避免浮点误差。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Vector {
ll x, y;
};
void solve() {
ll x1, y1, x2, y2, x3, y3, x4, y4;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
// 边长平方
ll l1 = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
ll l2 = (x3-x2)*(x3-x2) + (y3-y2)*(y3-y2);
ll l3 = (x3-x4)*(x3-x4) + (y3-y4)*(y3-y4);
ll l4 = (x1-x4)*(x1-x4) + (y1-y4)*(y1-y4);
// 向量
Vector a = {x1-x2, y1-y2};
Vector b = {x3-x2, y3-y2};
Vector c = {x3-x4, y3-y4};
Vector d = {x1-x4, y1-y4};
// 对边相等且平行
if (l1 == l3 && l2 == l4 && a.x * c.y == a.y * c.x && b.x * d.y == b.y * d.x) {
if (l1 == l2) {
if (a.x*b.x + a.y*b.y == 0) {
cout << "square";
return;
}
cout << "rhombus";
return;
}
if (a.x*b.x + a.y*b.y == 0) {
cout << "rectangle";
return;
}
cout << "parallelogram";
return;
}
// 一组对边平行 → 梯形
if (a.x * c.y == a.y * c.x || b.x * d.y == b.y * d.x) {
cout << "trapezium";
return;
}
// 两组邻边相等 → 筝形
if ((l1 == l2 && l3 == l4) || (l2 == l3 && l4 == l1)) {
cout << "kite";
return;
}
cout << "none";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T--) solve();
return 0;
}
L - 门锁问题
有 n 个房间，m 条通路，初始所有门开放。每扇门只能从一端上锁。求最少需要添加多少个额外出口，使得所有门都能被锁定。
建图后求强连通分量（SCC），统计没有出边的 SCC 数量即为答案。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
vector<int> graph[MAXN];
int dfn[MAXN], low[MAXN], id[MAXN], cnt, tot;
bool in_stack[MAXN];
stack<int> stk;
void tarjan(int u) {
dfn[u] = low[u] = ++tot;
stk.push(u);
in_stack[u] = true;
for (int v : graph[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (in_stack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
++cnt;
int node;
do {
node = stk.top(); stk.pop();
in_stack[node] = false;
id[node] = cnt;
} while (node != u);
}
}
void solve() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
}
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) {
tarjan(i);
}
}
vector<bool> has_out(cnt + 1, false);
for (int u = 1; u <= n; ++u) {
for (int v : graph[u]) {
if (id[u] != id[v]) {
has_out[id[v]] = true;
}
}
}
int ans = 0;
for (int i = 1; i <= cnt; ++i) {
if (!has_out[i]) {
++ans;
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T--) solve();
return 0;
}
