2019CPS-J真题题解
2026-08-10 09:55:03
发布于：广东
CSP-J 2019 公交换乘 题解
1. 题意理解
这道题是在模拟一次次出行。
每次出行有三种信息：
opt=0：坐地铁；opt=1：坐公交；pri：本次票价；t：本次出行时间。
规则是：
坐地铁必须付钱，但会得到一张优惠票。
这张优惠票可以在 45 分钟内坐公交时使用，并且只能用于票价不超过它面值的公交。
每张优惠票只能用一次。
要求我们算出所有出行最少一共花多少钱。
2. 解题思考
我们按输入顺序处理每一次出行。
如果是地铁：
- 直接加上本次票价；
- 得到一张优惠票，放起来。
如果是公交：
- 先把已经超过
45分钟的优惠票删掉； - 再从剩下的优惠票里找一张能用的；
- 如果找到了，就使用这张票，不用付钱；
- 如果找不到，就正常付公交票价。
这里要注意：
如果有多张优惠票都能用，应该使用最早获得的那一张。
所以我们可以用队列维护优惠票，因为队列正好是“先来的先处理”。
3. 部分解
如果数据比较小，可以不用队列。
我们把每一次地铁产生的优惠票都存下来。
每次遇到公交时，就从最早的优惠票开始扫描：
- 如果这张票已经用过，跳过；
- 如果时间超过
45分钟，跳过； - 如果票价面值不够，跳过；
- 找到第一张能用的票，就使用它。
这样写最容易理解，因为完全按照题目规则模拟。
但每次公交都可能扫描很多张优惠票，所以复杂度是 O(n^2)，只能过小数据。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
struct node{
int opt,pri,t;
}a[N];
int vis[N];
void solve(){
int n;
cin>>n;
int ans=0;
vector<int>tick;
for(int i=1;i<=n;i++){
cin>>a[i].opt>>a[i].pri>>a[i].t;
if(a[i].opt==0){
ans+=a[i].pri;
tick.push_back(i);
}
else{
int ok=0;
for(auto id:tick){
if(vis[id])continue;
if(a[i].t-a[id].t>45)continue;
if(a[id].pri>=a[i].pri){
vis[id]=1;
ok=1;
break;
}
}
if(ok==0)ans+=a[i].pri;
}
}
cout<<ans<<"\n";
}
signed main(){
std::ios::sync_with_stdio(false);
cout.tie(0);cin.tie(0);
int _=1;
// cin>>_;
while(_--){
solve();
}
}
4. 核心细节
队列里存还没有使用、也还可能有效的优惠票。
每张优惠票记录两个信息：
pri：优惠票面值
t：获得优惠票的时间
处理公交时：
while(q.size()!=0&&当前时间-q.front().t>45)q.pop();
这一步是在删除过期优惠票。
然后扫描队列，找第一张 pri>=公交票价 的优惠票。
为什么要用临时队列？
因为扫描时会把队首弹出来，如果这张票没有使用，就要按原顺序放回去。
如果直接弹出后再放回原队列，可能会打乱优惠票的先后顺序，后面就不一定能使用“最早获得的票”。
5. 例子模拟
假设有三次出行：
0 10 1
0 5 2
1 6 3
第 1 次坐地铁，花 10 元，得到面值 10 的优惠票。
第 2 次坐地铁，花 5 元，得到面值 5 的优惠票。
第 3 次坐公交，票价 6。
队列中优惠票按时间顺序是：
10元优惠票，5元优惠票
第一张 10>=6，可以用，所以公交不花钱。
总花费是：
10+5=15
6. 代码实现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
struct str{
int pri,t,op;
}a[N];
struct sub{
int pri,t;
};
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].op>>a[i].pri>>a[i].t;
}
queue<sub>q;
int ans=0;
for(int i=1;i<=n;i++){
if(a[i].op==0){
ans+=a[i].pri;
q.push({a[i].pri,a[i].t});
}
else{
int ok=1;
queue<sub>tmp;
while(q.size()!=0){
sub f=q.front();
if(a[i].t-f.t<=45&&a[i].pri<=f.pri&&ok==1){
ok=0;
}
else if(a[i].t-f.t<=45)tmp.push(f);
q.pop();
}
q=tmp;
if(ok==1)ans+=a[i].pri;
}
}
cout<<ans<<"\n";
}
signed main(){
int _=1;
// cin>>_;
while(_--){
solve();
}
}
7. 复杂度分析
每次出行只会被处理一次。
优惠票进入队列一次，过期或使用后也只会离开一次。
由于优惠票只有 45 分钟有效，队列里同时存在的有效优惠票数量不会很大。
所以总时间复杂度可以看作：
O(n)
空间复杂度：
O(n)
8. 易错点
-
坐地铁一定要付钱，并且会产生优惠票。
-
坐公交不会产生优惠票。
-
优惠票必须满足两个条件：
时间不超过45分钟
面值 >= 公交票价
-
一张优惠票只能使用一次。
-
多张优惠票都能用时，要使用最早获得的那一张。
-
扫描队列时不能打乱剩余优惠票的顺序。
CSP-J 2019 纪念品 题解
1. 题意理解
有 n 天，m 种纪念品。
第 i 天第 j 种纪念品的价格是 a[i][j]。
一开始有 tot 元钱。
每天可以买纪念品，后面也可以卖掉，目标是让最后手里的钱最多。
本质问题：
如果今天买入，明天卖出，钱可能变多；我们要不断利用每天之间的价格变化，让资金尽量增加。
2. 解题思考
不要一开始就想很多天一起买卖。
我们可以一段一段看：
第 1 天 -> 第 2 天
第 2 天 -> 第 3 天
...
第 n-1 天 -> 第 n 天
对于相邻两天来说：
如果第 i-1 天买第 k 种纪念品，需要花：
a[i-1][k]
到了第 i 天卖掉，可以得到：
a[i][k]
这里有一个很容易想不明白的地方：
为什么只考虑“今天买，明天卖”，而不是“今天买，隔很多天以后再卖”？
原因是：每一天都可以把手里的纪念品按当天价格卖掉，也可以再按当天价格买回来。
比如你第 1 天买了某个纪念品，本来想第 3 天卖。
到了第 2 天时，你可以这样理解：
先把它按第 2 天价格卖掉
再立刻按第 2 天价格买回来
这样做以后，你手里的纪念品数量没有变，后面第 3 天仍然可以卖。
也就是说，跨很多天持有一件纪念品，可以拆成很多段相邻两天的操作：
第 1 天 -> 第 2 天
第 2 天 -> 第 3 天
如果中间有更好的买法，我们还可以换成别的纪念品；如果没有更好的买法，就相当于卖掉再买回原来的。
所以每天结束时，我们只需要关心“当前这些东西按今天价格最多值多少钱”，不需要记录它们到底是哪一天买的。
也就是说，这件纪念品可以看成一个“物品”：
花费 = 前一天价格
收益 = 后一天价格
只要钱够，同一种纪念品可以买很多个，所以这是完全背包。
完全背包的意思是：每种物品可以选多次。
3. 部分解
如果数据很小，可以直接暴力枚举。
对于相邻两天，假设当前有 money 元。
我们可以枚举：
第 1 种纪念品买几个
第 2 种纪念品买几个
...
第 m 种纪念品买几个
只要总花费不超过当前的钱，就是一种合法购买方案。
然后把买到的纪念品在第二天全部卖掉，得到新的钱，再继续处理下一天。
这个做法非常直观，但枚举数量太多，只适合 n,m,tot 都很小的数据。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=20;
int n,m,tot;
int a[N][N];
int dfs(int day,int money);
int buy(int day,int k,int money,int val){
if(k>m){
return dfs(day+1,money+val);
}
int ans=0;
for(int cnt=0;cnt*a[day][k]<=money;cnt++){
int left=money-cnt*a[day][k];
int get=val+cnt*a[day+1][k];
ans=max(ans,buy(day,k+1,left,get));
}
return ans;
}
int dfs(int day,int money){
if(day==n)return money;
return buy(day,1,money,0);
}
void solve(){
cin>>n>>m>>tot;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
cout<<dfs(1,tot)<<"\n";
}
signed main(){
std::ios::sync_with_stdio(false);
cout.tie(0);cin.tie(0);
int _=1;
// cin>>_;
while(_--){
solve();
}
}
暴力解的问题是：
每种纪念品可以买 0 个、1 个、2 个……
组合数量会非常大。
所以正解要用完全背包，把这些重复枚举压缩成数组转移。
4. 状态设计
处理从第 i-1 天到第 i 天时，设：
dp[j]
表示：
手里最多有 j 元钱时，经过“第 i-1 天买、第 i 天卖”后，最多能变成多少钱。
为什么初始化为：
dp[j]=j;
因为你可以什么都不买。
如果什么都不买，那么有 j 元，第二天还是 j 元。
这就是最基础的情况。
然后枚举每种纪念品 k：
for(int j=a[i-1][k];j<=tot;j++)
如果当前有 j 元，可以拿出 a[i-1][k] 元买一个第 k 种纪念品。
买完后剩下 j-a[i-1][k] 元。
这部分钱经过处理后最多能变成：
dp[j-a[i-1][k]]
再加上这个纪念品明天卖出的价格：
a[i][k]
所以转移是：
dp[j]=max(dp[j],dp[j-a[i-1][k]]+a[i][k]);
这里 j 从小到大枚举，是因为同一种纪念品可以买多次。
5. 例子理解
假设当前有 10 元。
某种纪念品今天价格 3，明天价格 5。
如果买 1 个：
花 3 元，明天变回 5 元，相当于多赚 2 元
如果买 3 个：
花 9 元，明天卖 15 元
原本 10 元就可能变成：
1 元剩余 + 15 元卖出 = 16 元
所以同一种纪念品确实可能买很多个，这就是为什么要用完全背包。
6. 代码实现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+5;
int a[N][N];
int dp[N];
void solve(){
int n,m,tot;
cin>>n>>m>>tot;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=2;i<=n;i++){
for(int j=0;j<=tot;j++)dp[j]=j;
for(int k=1;k<=m;k++){
for(int j=a[i-1][k];j<=tot;j++){
dp[j]=max(dp[j-a[i-1][k]]+a[i][k],dp[j]);
}
}
tot=max(tot,dp[tot]);
}
cout<<tot<<"\n";
}
signed main(){
std::ios::sync_with_stdio(false);
cout.tie(0);cin.tie(0);
int _=1;
// cin>>_;
while(_--){
solve();
}
}
7. 复杂度分析
外层枚举天数，共 n-1 次。
每相邻两天之间，要枚举 m 种纪念品，并枚举当前资金 tot。
所以时间复杂度大约是：
O(n*m*tot)
题目中初始资金范围不大，且资金增长也在可接受范围内，所以可以通过。
空间复杂度：
O(tot)
因为背包数组只需要一维。
8. 易错点总结
dp[j]初始化不能全设成0。
因为不买纪念品时，钱不会消失，应该有 dp[j]=j。
- 循环
j要从小到大。
同一种纪念品可以买多次，所以是完全背包。
- 买入价格用前一天的价格。
也就是：
a[i-1][k]
- 卖出价格用后一天的价格。
也就是：
a[i][k]
- 每处理完相邻两天，要更新当前资金：
tot=max(tot,dp[tot]);
这样下一天才是在新的资金基础上继续赚钱。
这里空空如也
有帮助，赞一个