2025年第七届传智杯程序设计挑战赛复赛（第二场）补题
E-小苯的水瓶
题意：
给定 n 个水瓶，每个水瓶有一些水，这些水瓶可以倒水给其他水瓶，但是转移的总和不能超过 m，可以操作任意次，此外还有 k 的水量可以分配给这些水瓶，最后小红会喝掉水量最少的水瓶里的水，问小红最多可以喝多少水
思路：
如果 小红最多能喝 h 的水，那么 h-1, h-2 .... 比 h 少的水量他肯定可以喝到这么多水，满足单调性，可以二分。
check 函数就是把 < limit 的水瓶需要的水量全部加起来，记为 need，另外把多的加起来记为 res，再加上 k，看 need 与 min(res,m)+k 的大小
// https://ac.nowcoder.com/acm/contest/103864/E
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
int T, n, m, k;
int a[200005];
bool check(int limit)
{
int res = 0, need = 0;
for (int i = 0; i < n; i++)
{
if (a[i] < limit)
need += limit - a[i];
else
res += a[i] - limit;
}
res = min(res, m);
return need <= res + k;
}
void solve()
{
cin >> n >> m >> k;
int mx = 0;
for (int i = 0; i < n; i++)
cin >> a[i], mx = max(mx, a[i]);
// sort(a,a+n);
int l = 0, r = mx + k / n + 1, ans;
while (l <= r)
{
int mid = (r - l) / 2 + l;
if (check(mid))
l = mid + 1, ans = mid;
else
r = mid - 1;
}
cout << ans << "\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
D-小苯的ovo
题意：
给定一个只包含 'o'、'v' 的字符串，最多能进行 K 次以下操作：
- 将 'o' -> 'v' 或者 'v' -> 'o'
问最后子串 "ovo" 的数量（字串之间互相独立）
思路：
dp
dp[ i ][ j ] 表示前 i 个位置，花费 j 次操作的最大数量
// https://ac.nowcoder.com/acm/contest/103864/D
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
int T, n, m, k;
void solve()
{
cin >> n >> k;
string s;
cin >> s;
vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
int ans = 0;
for (int i = 3; i <= n; i++)
{
for (int j = 0; j <= k; j++)
{
dp[i][j] = dp[i - 1][j];
int cnt = 0;
if (s[i - 1] != 'o')
cnt++;
if (s[i - 2] != 'v')
cnt++;
if (s[i - 3] != 'o')
cnt++;
if (j >= cnt)
dp[i][j] = max(dp[i - 3][j - cnt] + 1, dp[i][j]);
// ans = max(ans, dp[i][j]);
}
}
cout << dp[n][k] << "\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
G-小苯的奇怪最短路
题意：
定义最短路：从 1 -> n 的边中 最大值 + 最小值，求 1 -> n 的最短路
思路：
最小生成树 + 并查集
最小生成树求连通图的过程中再开一个 min 数组用来存每个集合的最小边，如果 1 和 n 连通了，那么最大值的边就是现在这条边，因为 K 算法求最小生成树就是将边按边权从小到大排好序了，那么答案就是 min[f[1]] + 当前的边的权值
// https://ac.nowcoder.com/acm/contest/103864/G
#include <bits/stdc++.h>
using namespace std;
#define int long long
int t, n, m;
int find(vector<int> &f, int a)
{
if (a != f[a])
f[a] = find(f, f[a]);
return f[a];
}
void Union(vector<int> &f, vector<int> &mi, int a, int b, int w)
{
int fa = find(f, a);
int fb = find(f, b);
f[fb] = fa;
mi[fa] = min(mi[fa], min(mi[fb], w));
}
void solve()
{
cin >> n >> m;
vector<vector<int>> v(m, vector<int>(3));
vector<int> f(n + 1, 0), mi(n + 1, 1e18);
for (int i = 0; i <= n; i++)
f[i] = i;
for (int i = 0; i < m; i++) // m条边
cin >> v[i][0] >> v[i][1] >> v[i][2];
// 按边的权值从小到大排序
sort(v.begin(), v.end(), [](const vector<int> &v1, const vector<int> &v2)
{ return v1[2] < v2[2]; });
int ans = 1e18;
for (int i = 0; i < m; i++)
{
Union(f, mi, v[i][0], v[i][1], v[i][2]);
if (find(f, 1) == find(f, n))
{
ans = min(ans, mi[find(f, 1)] + v[i][2]); // 因为边按大小已经排好序了，所以现在的 v[i][2] 就是目前的最大边
}
}
cout << (ans == 1e18 ? -1 : ans) << "\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
