XP03-B1 比赛题解
2026-08-16 15:31:09
发布于：广东
第一题：星港补给舱调度
题意简化
有 N 个补给舱，第 i 个补给舱需要消耗 R[i] 燃料才能发射。
有 Q 次询问，每次给一个燃料数 X，问最多能发射多少个补给舱。
思路
想让发射数量尽可能多，就应该优先选择消耗燃料少的补给舱。
所以第一步：把所有 R[i] 从小到大排序。
排序后，如果想发射前 k 个补给舱，需要的总燃料就是：
R[1] + R[2] + ... + R[k]
为了快速算这个总和，使用前缀和：
s[0] = 0
s[i] = R[1] + R[2] + ... + R[i]
对于每个询问 X，问题变成：
在 s[0], s[1], ..., s[N] 中，找最后一个 <= X 的位置
这个位置就是最多能发射的数量。
因为 R[i] 排序后都是非负消耗，所以前缀和 s[i] 一定是递增的，可以用二分。
参考代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int r[N],s[N];
void solve(){
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>r[i];
}
sort(r+1,r+n+1);
for(int i=1;i<=n;i++){
s[i]=s[i-1]+r[i];
}
while(q--){
int x;
cin>>x;
int ans=upper_bound(s,s+n+1,x)-s-1;
cout<<ans<<"\n";
}
}
signed main(){
ios::sync_with_stdio(false);
cout.tie(0);cin.tie(0);
int _=1;
while(_--){
solve();
}
return 0;
}
为什么要减 1
upper_bound(s, s + n + 1, x) 找到的是第一个 > x 的位置。
我们要的是最后一个 <= x 的位置，所以要往前退一格：
答案 = 第一个 > x 的位置 - 1
复杂度
排序：O(N log N)
每次询问：O(log N)
总复杂度：O(N log N + Q log N)
第二题：魔法石补给（考试版）
题意简化
有 n 种魔法石，第 i 种魔法石：
占用容量：w[i]
价值：v[i]
数量：无限个
背包容量是 M，问最多能装出多少价值。
这是典型的完全背包。
为什么是完全背包
判断背包类型时，先看每种物品能选几次：
每种只能选 0 次或 1 次：01 背包
每种可以选无限次：完全背包
每种最多选 c[i] 次：多重背包
本题说每种魔法石可以使用任意多个，所以是完全背包。
状态设计
设：
f[j] 表示容量不超过 j 时，能获得的最大价值
一开始什么都不选：
f[0] = f[1] = ... = f[M] = 0
对于第 i 种魔法石，如果当前容量 j 能放下它，那么有两种选择：
不选：f[j] 不变
选一个：f[j - w[i]] + v[i]
所以转移是：
f[j] = max(f[j], f[j - w[i]] + v[i])
完全背包的重点：容量要从小到大枚举。
因为从小到大枚举时，同一种物品刚刚更新出来的结果还可以继续被后面使用，这就实现了“同一种物品可以选很多次”。
参考代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=60005;
int dp[N];
int w[N],v[N];
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
}
for(int i=1;i<=n;i++){
for(int j=w[i];j<=m;j++){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[m]<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cout.tie(0);cin.tie(0);
int _=1;
while(_--){
solve();
}
return 0;
}
复杂度
时间复杂度：O(nM)
空间复杂度：O(M)
第四题：小码君买饮料 II
题意简化
有 n 种饮料，第 i 种饮料：
价格：c[i]
容量：l[i]
数量：无限瓶
小码君至少要买到 L 的饮料量，问最少花多少钱。
注意关键词是“至少 L”，不是“刚好 L”。
部分分思路
n = 1
如果只有一种饮料，只能一直买这一种。
需要买的瓶数是：
ceil(L / l[1])
在 C++ 中常用写法是：
(L + l[1] - 1) / l[1]
答案：
瓶数 * c[1]
所有 l[i] 都等于 1
如果所有饮料容量都是 1，那么买每一瓶都只增加 1 的容量。
要买到 L 的容量，就要买 L 瓶。
为了最省钱，每次都买价格最小的那种饮料。
答案：
L * min(c[i])
L 较小
当 L 比较小的时候，可以直接做动态规划。
本题满分范围中 L <= 20000，其实也可以直接动态规划。
满分思路
这题也是完全背包，但是目标从“最大价值”变成了“最小花费”。
设：
f[j] 表示买到 j 的容量，最少需要多少钱
但是题目要求“至少 L”，可能会买超过 L。
例如：
L = 10
某瓶饮料容量 = 12
买一瓶就够了，虽然不是刚好 10。
一种常见写法是把容量最多算到 2L。
最后在 L 到 2L 之间取最小花费
为什么算到 2L 就够？
如果最后一瓶容量不超过 L，那么总容量第一次达到 L 时，一定小于 2L。
如果最后一瓶容量超过 L，那么只买这一瓶就已经够了，可以把它的容量看成 2L。
所以读入每瓶饮料容量时，可以先写：
l[i] = min(l[i], 2 * L)
这样既能处理买超的情况，又不会把数组开得太大。
状态转移
一开始：
f[0] = 0
其他 f[j] = INF
枚举每一种饮料，再枚举当前容量 j。
如果现在已经能花 f[j] 元买到 j 的容量，那么再买一瓶第 i 种饮料：
f[j] = min(f[j], f[j - l[i]] + c[i])
因为每种饮料可以买无限瓶，所以 j 从小到大枚举。
参考代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int dp[N];
int c[N],l[N];
void solve(){
int n,L;
cin>>n>>L;
for(int i=1;i<=n;i++){
cin>>c[i]>>l[i];
l[i]=min(l[i],2*L);
}
for(int i=1;i<N;i++){
dp[i]=1e18;
}
for(int i=1;i<=n;i++){
for(int j=l[i];j<=2*L;j++){
dp[j]=min(dp[j],dp[j-l[i]]+c[i]);
}
}
int ans=1e18;
for(int i=L;i<=2*L;i++){
ans=min(ans,dp[i]);
}
cout<<ans<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cout.tie(0);cin.tie(0);
int _=1;
while(_--){
solve();
}
return 0;
}
易错点
不能只考虑刚好买到 L。
比如：
L = 10
只有一种饮料：价格 5，容量 12
正确答案是 5，因为买一瓶就已经够了。
如果只做“刚好装满”，会认为无解，这是错误的。
复杂度
时间复杂度：O(nL)
空间复杂度：O(L)
第五题：沙漠商队补给（easy）
题意简化
有 n 种补给，第 i 种补给：
重量：w[i]
价值：v[i]
最多有 c[i] 个
背包容量是 M，问最多能获得多少价值。
这是多重背包。
部分分思路
c[i] = 1
如果每种物品最多只有 1 个，那么题目就变成了 01 背包。
枚举容量时要从大到小：
for j = M 到 w[i]
c[i] 比较小
如果每种物品数量很少，比如 c[i] <= 20，可以把同一种物品拆成很多个独立物品。
例如：
第 i 种物品有 3 个
就当成 3 个普通的 01 背包物品。
这样容易写，但如果 c[i] 很大，会超时。
所有 w[i] 都等于 1
如果所有物品重量都是 1，那么背包最多能装 M 个物品。
这时应该优先拿价值大的物品。
做法：
按 v[i] 从大到小排序
每种最多拿 c[i] 个
直到拿满 M 个或者没有物品可拿
满分思路：二进制拆分
多重背包的问题是：每种物品最多能选 c[i] 个。
如果直接一个一个拆，遇到 c[i] 很大就会很慢。
二进制拆分的想法是：把 c[i] 个物品拆成若干组，每组只能选 0 次或 1 次。
例如有 13 个同样的物品，可以拆成：
1, 2, 4, 6
为什么这样拆？
因为：
13 = 1 + 2 + 4 + 6
用这些组，可以拼出从 0 到 13 的任意数量。
比如：
选 7 个：1 + 2 + 4
选 9 个：1 + 2 + 6
选 13 个：1 + 2 + 4 + 6
拆完之后，每一组就变成一个 01 背包物品。
如果一组代表 k 个原物品，那么它的：
重量 = k * w[i]
价值 = k * v[i]
然后做 01 背包即可。
为什么要限制可用数量
即使 c[i] 非常大，也不一定真的能用那么多个。
因为背包容量只有 M，第 i 种物品最多也只能放：
M / w[i]
所以实际拆分前可以先写：
num = min(c[i], M / w[i])
这样可以减少很多无用拆分。
参考代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5010;
const int M=305;
int dp[N];
int w[M],v[M],c[M];
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i]>>c[i];
}
for(int i=1;i<=n;i++){
int num=min(c[i],m/w[i]);
int k=1;
while(num>0){
int take=min(k,num);
int weight=take*w[i];
int value=take*v[i];
for(int j=m;j>=weight;j--){
dp[j]=max(dp[j],dp[j-weight]+value);
}
num-=take;
k*=2;
}
}
cout<<dp[m]<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cout.tie(0);cin.tie(0);
int _=1;
while(_--){
solve();
}
return 0;
}
易错点
二进制拆分后，每一组只能用一次，所以容量必须从大到小枚举。
如果从小到大枚举，就可能让同一组被重复使用，数量限制会被破坏。
复杂度
每种物品会被拆成大约 log c[i] 组。
时间复杂度：O(M * sum(log c[i]))
空间复杂度：O(M)
第六题：拯救oibh总部
题意简化
有一个地图，地图中：
0 表示空地
1 表示墙
洪水会从地图外面流进来，只能经过 0，不能穿过 1。
问最后有多少个 0 不会被洪水淹到。
核心思路
洪水从外面来，所以只有和边界连通的 0 会被淹。
也就是说：
边界上的 0
以及能从这些 0 走到的 0
都会被淹
剩下没有被访问过的 0，就是安全区域。
这类题适合用 BFS。
算法步骤
- 读入地图。
- 把边界上的所有
0加入队列。 - 从这些边界
0开始 BFS，把能到达的0全部标记为“会被淹”。 - 最后遍历整张地图，统计没有被标记的
0。
参考代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;
int x,y;
char a[N][N];
bool vis[N][N];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
queue<int> qx, qy;
void add(int i,int j){
if (i < 1 || i > x || j < 1 || j > y) return;
if (a[i][j] != '0') return;
if (vis[i][j]) return;
vis[i][j] = true;
qx.push(i);
qy.push(j);
}
void solve(){
cin>>x>>y;
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=x;i++){
add(i, 1);
add(i, y);
}
for(int j=1;j<=y;j++){
add(1, j);
add(x, j);
}
while(!qx.empty()){
int nowx=qx.front();
int nowy=qy.front();
qx.pop();
qy.pop();
for(int k=0;k<4;k++){
int nx=nowx+dx[k];
int ny=nowy+dy[k];
add(nx, ny);
}
}
int ans=0;
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
if(a[i][j]=='0'&&!vis[i][j]){
ans++;
}
}
}
cout<<ans<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cout.tie(0);cin.tie(0);
int _=1;
while(_--){
solve();
}
return 0;
}
易错点
不要从内部的 0 开始搜索。
本题问的是“不会被外面洪水淹到的地方”，所以应该从边界开始搜索，先找出所有会被淹的地方。
复杂度
每个格子最多进队一次。
时间复杂度：O(xy)
空间复杂度：O(xy)
第七题：滑雪
题意简化
有一个 n * m 的高度地图。
从一个格子可以走到上下左右相邻的格子，但只能走到高度更低的格子。
问最长能经过多少个格子。
普通 DFS 为什么可能超时
如果从每个格子都直接 DFS，会有大量重复计算。
比如一个格子的答案已经算过了，别的起点走到它时，又会重新算一遍。
所以我们需要记忆化搜索。
状态设计
设：
dp[x][y] 表示从 (x, y) 出发，最多能滑过多少个格子
如果 dp[x][y] 已经算过，就直接返回，不再重复搜索。
转移思路
从 (x, y) 出发，先至少能经过自己这个格子，所以：
dp[x][y] = 1
然后尝试走向上下左右四个方向。
如果相邻格子 (nx, ny) 在地图内，并且：
h[nx][ny] < h[x][y]
说明可以滑过去。
那么答案可以更新为：
dp[x][y] = max(dp[x][y], dp[nx][ny] + 1)
为什么不会死循环
因为每一步都必须走到更低的地方。
高度一直变小，不可能走一圈又回到原来的格子。
所以 DFS 是安全的。
参考代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105;
int n,m;
int h[N][N];
int dp[N][N];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int dfs(int x,int y){
if(dp[x][y]!=0){
return dp[x][y];
}
dp[x][y]=1;
for(int k=0;k<4;k++){
int nx=x+dx[k];
int ny=y+dy[k];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
if (h[nx][ny] >= h[x][y]) continue;
dp[x][y]=max(dp[x][y],dfs(nx,ny)+1);
}
return dp[x][y];
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>h[i][j];
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans=max(ans,dfs(i,j));
}
}
cout<<ans<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cout.tie(0);cin.tie(0);
int _=1;
while(_--){
solve();
}
return 0;
}
复杂度
每个格子的答案只会真正计算一次。
时间复杂度：O(nm)
空间复杂度：O(nm)
第八题：炼金工坊升级
题意简化
有 D 轮实验，一开始有 M 点魔力。
每一轮有 n 种配方，第 i 种配方：
本轮占用魔力：c[i]
本轮结束返还：r[i]
同一轮中，每种配方可以使用任意多次。
但是这一轮使用配方时，占用的总魔力不能超过当前拥有的魔力。
如果使用一次第 i 种配方，本轮结束后魔力的净变化是：
r[i] - c[i]
问经过 D 轮后，最多能有多少魔力。
先理解“一轮”在做什么
假设当前有 M 点魔力。
在这一轮里，每个配方可以看成一个物品：
重量 = c[i]
价值 = r[i] - c[i]
数量 = 无限个
本轮能占用的总魔力不能超过 M，这就像背包容量是 M。
目标是让本轮结束后魔力增加得最多，也就是让净收益最大。
所以每一轮其实都是一次完全背包。
为什么 r[i] <= c[i] 的配方通常不用
如果：
r[i] <= c[i]
那么净收益：
r[i] - c[i] <= 0
使用它不会让魔力变多，甚至可能变少。
题目要求最大魔力，所以这种配方可以不选。
部分分思路
D、n、M 都很小
可以用动态规划或搜索尝试每一轮的选择。
不过只要理解成“每轮完全背包”，这个部分分也可以直接用满分做法通过。
n = 1
每轮只有一种配方。
如果这个配方不赚钱：
r <= c
这一轮不做。
如果这个配方赚钱：
r > c
最多能做：
M / c
次。
本轮结束后：
M = M + (M / c) * (r - c)
每一轮最多只有一种赚钱配方
如果一轮里最多只有一种配方满足：
r[i] > c[i]
那么这一轮只需要考虑这一种赚钱配方。
处理方式和 n = 1 类似：
能做几次就做几次
因为没有别的赚钱配方可以搭配。
D <= 30，n <= 30，M <= 20000
可以每一轮做一次完全背包。
这也是满分做法的核心。
满分思路
题目保证：
M <= 20000
任意合法方案中，每轮结束后的魔力不会超过 20000
D * n <= 500
所以每一轮都开一个 f[0...M] 数组是可以接受的。
设当前轮开始时魔力是 M。
定义：
f[j] 表示本轮占用魔力不超过 j 时，最多能获得多少净收益
初始：
f[0] = f[1] = ... = f[M] = 0
对于每个配方，如果它的净收益 r[i] - c[i] 是正数，就按完全背包转移：
f[j] = max(f[j], f[j - c[i]] + (r[i] - c[i]))
容量从小到大枚举，因为同一种配方可以在同一轮使用多次。
这一轮结束后：
M = M + f[M]
然后进入下一轮。
和普通完全背包的区别
普通完全背包通常是：
给定一个固定容量 M，求最大价值
本题是：
第 1 轮用当前 M 做完全背包
做完后 M 变大
第 2 轮用新的 M 做完全背包
继续往后做
也就是说，背包容量会随着轮数变化。
参考代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105;
const int M=20005;
int c[N], r[N];
int dp[M];
void solve(){
int D,n,now;
cin>>D>>n>>now;
for(int day=1;day<=D;day++){
for(int i=1;i<=n;i++){
cin>>c[i];
}
for(int i=1;i<=n;i++){
cin>>r[i];
}
int cap=now;
for(int j=0;j<=cap;j++){
dp[j]=0;
}
for(int i=1;i<=n;i++){
int profit=r[i]-c[i];
if (profit <= 0) continue;
for(int j=c[i];j<=cap;j++){
dp[j]=max(dp[j],dp[j-c[i]]+profit);
}
}
now+=dp[cap];
}
cout<<now<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cout.tie(0);cin.tie(0);
int _=1;
while(_--){
solve();
}
return 0;
}
样例解释
输入：
2 3 10
4 5 6
6 4 8
6 4 5
9 5 5
一开始有 10 点魔力。
第 1 轮：
配方 1：消耗 4，返还 6，净赚 2
配方 2：消耗 5，返还 4，亏 1，不选
配方 3：消耗 6，返还 8，净赚 2
当前容量是 10。
可以选择：
配方 1 用 1 次，配方 3 用 1 次
总消耗 4 + 6 = 10
总净赚 2 + 2 = 4
第 1 轮后：
M = 10 + 4 = 14
第 2 轮：
配方 1：消耗 6，返还 9，净赚 3
配方 2：消耗 4，返还 5，净赚 1
配方 3：消耗 5，返还 5，净赚 0
当前容量是 14。
最优是配方 1 用 2 次：
总消耗 12
总净赚 6
最后：
M = 14 + 6 = 20
答案是 20。
易错点
第一，不要把 r[i] 当成价值。真正增加的魔力是：
r[i] - c[i]
因为消耗的 c[i] 本来就要扣掉。
第二，每一轮的配方不同，所以每一轮都要重新清空 f 数组。
第三，完全背包容量从小到大枚举。
如果从大到小枚举，就会变成每种配方最多只能用一次，这是 01 背包，不符合题意。
复杂度
每一轮做一次完全背包。
时间复杂度：O(D * n * M)
空间复杂度：O(M)
其中题目保证 D * n <= 500，并且魔力不会超过 20000，所以可以通过。
总结
这套题的核心不是代码很长，而是要先判断题型：
能选无限次：完全背包
有数量限制：多重背包
询问最多能买/发射几个：排序 + 前缀和 + 二分
从边界扩展：BFS
从每个点出发求最长路：记忆化搜索
分很多轮，每轮选择无限次：每轮做一次完全背包
做题时建议先问自己三件事：
1. 题目要最大值、最小值，还是计数？
2. 当前选择是否能重复使用？
3. 有没有顺序、边界、单调性这些隐藏条件？
把题型判断对，代码就会顺很多。
有帮助，赞一个