CSP-J 2019 第二轮(复赛)真题解析

T1: 数字游戏 (number)

题目大意

输入一个只由字符 '0' 和 '1' 组成的长度为 8 的字符串，数一数里面一共有多少个字符 '1'，并输出这个数量。

考察知识点

• 字符串输入与遍历
• 计数器统计累加

思路分析

直接使用字符遍历统计：输入是一个长度为 8 的字符串，用一个 string 读入，写一个 for 循环从下标 0 遍历到 7。只要遇到 s[i] == '1'，就让计数器 ans++。遍历结束后输出 ans 即可。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intmain(){string s;cin >> s;int ans = 0;for (int i = 0; i < s.size(); i++) {if (s[i] == '1') {            ans++;        }    }cout << ans << "\n";return0;}

易错点提醒

1. 注意是字符 '1' 而不是数字 1，写成 if (s[i] == 1) 会出错。
2. 字符串下标从 0 开始，长度为 8 时下标范围是 0 到 7。

T2: 公交换乘 (transfer)

题目大意

小轩经常坐地铁和公交车。每次坐车有一条记录：

• 交通工具（0 代表地铁，1 代表公交车）
• 票价 
• 乘车时间 （分钟）

优惠规则如下：

1. 坐一次地铁，可以拿到一张优惠券。
2. 优惠券有效期为 45 分钟，也就是在  期间有效。
3. 坐公交车时，如果手里有未过期且面额不小于公交车票价的优惠券，就可以免费乘坐，并消耗掉这张优惠券（有多张符合要求时，优先使用最早获得的那张）。
4. 坐地铁不能使用优惠券。

请计算小轩一共花了多少钱。

考察知识点

• 模拟法与结构体数组
• 队列滑动窗口思想（丢弃过期优惠券）

思路分析

这是一道典型的模拟题，核心是维护当前还未过期的优惠券集合：

1. 每次坐地铁（opt == 0）：必须花费  元，同时获得一张优惠券，记录该券的票价 、获得时间  以及使用状态（初始为未用）。放入队列末尾。
2. 每次坐公交（opt == 1）：
• 先清理过期券：因为输入的时间  是单调递增的，所以如果队头的优惠券满足 ，说明它已经失效，以后也不可能再用到，直接将 head++ 移出队列。
• 在未过期的优惠券中从前往后顺序查找：找到第一张未被使用过且面额  的优惠券。
• 如果找到，标记该券已使用，当前公交免费；如果找不到，小轩必须自行花费  元乘车。
3. 复杂度分析：虽然 ，但因为优惠券有效期仅为 45 分钟，任意时刻队列里有效优惠券最多只有 45 张左右，单次扫描非常迅速，整体时间复杂度 ，不会超时。

代码实现

#include<bits/stdc++.h>usingnamespacestd;structticket {int price;int time;bool used;};ticket q[100005];int head = 1, tail = 0;intmain(){    ios::sync_with_stdio(false);cin.tie(0);int n;if (!(cin >> n)) return0;longlong sum = 0;for (int i = 1; i <= n; i++) {int opt, p, t;cin >> opt >> p >> t;if (opt == 0) {// 坐地铁：必须花钱，同时收获一张优惠券            sum += p;            tail++;            q[tail].price = p;            q[tail].time = t;            q[tail].used = false;        } else {// 坐公交：先清理过期的优惠券while (head <= tail && t - q[head].time > 45) {                head++;            }// 在未过期的优惠券里找最早的、面额足够的一张bool ok = false;for (int j = head; j <= tail; j++) {if (!q[j].used && q[j].price >= p) {                    q[j].used = true; // 用掉它                    ok = true;break;                }            }// 没有能用的优惠券，自己掏钱if (!ok) {                sum += p;            }        }    }cout << sum << "\n";return0;}

易错点提醒

1. 时间差是 ，包含第 45 分钟。
2. 总金额  建议开 long long，养成防溢出的好习惯。
3. 优惠券只能用一次，用完一定要打标记 used = true。

T3: 纪念品 (souvenir)

题目大意

有  天， 种纪念品。已知每种纪念品在每一天的价格。你第一天手里有  元现金。 每天你可以在市场上无限次买入或卖出任意纪念品（买卖价格相同），并且当天买入的纪念品当天也可以卖出，或者持有到后面几天卖出。 求第  天卖掉所有纪念品后，你手里最多能拥有多少现金。

考察知识点

• 动态规划（完全背包问题）
• 贪心转化思想

思路分析

这道题乍看是复杂的跨天买卖，但有一个极其巧妙的转化：跨天持有，等价于每天收盘卖出、次日开盘原价买回。比如第 1 天花 10 块买入，第 3 天 15 块卖出，赚了 5 块； 这完全等价于：

• 第 1 天买入，第 2 天卖出（赚第 1 天到第 2 天的差价）；
• 第 2 天再买回来，第 3 天卖出（赚第 2 天到第 3 天的差价）。

这样一来，问题被拆解成独立的  轮： 在第  天，手里有现金 。对于第  种纪念品：

• 花费（体积）：第  天的价格 
• 收益（价值）：次日价格减去今日价格 （如果差价大于 0 才有买的意义） 每种纪念品可以买任意多个，求在预算  下能赚到的最大利润。这就是标准的完全背包问题！ 每天做一次完全背包，求出最大收益，把赚到的钱加进手头现金 ，作为下一天的本金，循环  天即可。

代码实现

#include<bits/stdc++.h>usingnamespacestd;int t, n, m;int p[105][105]; // p[d][i]: 第 d 天第 i 种商品的价格int f[10005];    // f[j]: 投入 j 元能赚到的最大利润intmain(){    ios::sync_with_stdio(false);cin.tie(0);if (!(cin >> t >> n >> m)) return0;for (int d = 1; d <= t; d++) {for (int i = 1; i <= n; i++) {cin >> p[d][i];        }    }// 一共经历 t-1 次跨天for (int d = 1; d < t; d++) {memset(f, 0, sizeof(f));for (int i = 1; i <= n; i++) {int cost = p[d][i];int profit = p[d + 1][i] - p[d][i];// 只有第二天涨价才有买的必要if (profit > 0) {for (int j = cost; j <= m; j++) {                    f[j] = max(f[j], f[j - cost] + profit);                }            }        }// 这一天能赚到的最大利润加进总本金        m += f[m];    }cout << m << "\n";return0;}

易错点提醒

1. 完全背包内层循环从小到大枚举容量 for (int j = cost; j <= m; j++)。
2. 每天做完背包后，本金  必须累加当天利润 ，作为次日背包的上限。
3. 题目保证无论何时手头金币不超过 ，背包容量开到  即可。

T4: 加工零件 (work)

题目大意

有  个工人，编号  到 。工人之间有  条传送带（无向边）。 如果 1 号工人想在第  阶段生产一个零件，那么与 1 号直接相连的邻居必须在第  阶段提供原料；这些邻居的邻居又必须在第  阶段提供原料……依此类推。在第 0 阶段，提供原料意味着该工人自己手里本来就有现成的原材料。 现在有  次询问，每次给出一个工人编号  和阶段数 ，问：如果 1 号工人在第  阶段要生产零件，工人  是否需要在第 0 阶段准备原材料？（输出 Yes 或 No）。

考察知识点

• 图论与最短路（广度优先搜索 BFS）
• 奇偶最短路思想

思路分析

原材料从工人  传递到工人 1，每经过一条边阶段数加 1。因此题目的本质是：是否存在一条从 1 号点到  号点的路径，其边数恰好为 ？

注意：零件可以在两个相邻工人之间来回传递（走过去再走回来），来回一次路径长度增加 2。 这意味着：

• 如果 1 到  有一条长度为  的路径，那么  的步数都可以走通！
• 所以，只要 ，并且  与  的奇偶性相同即可！

因此，对于每个点 ，我们只需要关心两件事：

1. 从 1 到  的最短偶数长度路径
2. 从 1 到  的最短奇数长度路径

查询时，看  是奇数还是偶数：

• 若  为偶数，只要 ，就输出 Yes，否则 No。
• 若  为奇数，只要 ，就输出 Yes，否则 No。

由于边权都是 1，直接用分层图 BFS（拆成奇偶两层点）就能在  内跑出所有点的奇偶最短路。

代码实现

#include<bits/stdc++.h>usingnamespacestd;constint INF = 0x3f3f3f3f;int n, m, q;vector<int> g[100005];int d[100005][2]; // d[u][0]: 到 u 的最短偶数步数，d[u][1]: 最短奇数步数voidbfs(){memset(d, 0x3f, sizeof(d));queue<pair<int, int>> q;// 1 号点到自己偶数步为 0    d[1][0] = 0;    q.push({1, 0});while (!q.empty()) {auto cur = q.front();        q.pop();int u = cur.first;int step = cur.second;for (int v : g[u]) {int nstep = (step == 0 ? 1 : 0);if (d[v][nstep] > d[u][step] + 1) {                d[v][nstep] = d[u][step] + 1;                q.push({v, nstep});            }        }    }}intmain(){    ios::sync_with_stdio(false);cin.tie(0);if (!(cin >> n >> m >> q)) return0;for (int i = 1; i <= m; i++) {int u, v;cin >> u >> v;        g[u].push_back(v);        g[v].push_back(u);    }    bfs();while (q--) {int a, l;cin >> a >> l;int opt = l % 2; // 0 是偶数，1 是奇数if (d[a][opt] <= l) {cout << "Yes\n";        } else {cout << "No\n";        }    }return0;}

易错点提醒

1. 特判 1 号点自己孤立（没有邻居）的情况：如果 1 号点度数为 0，且 ，是无法制造任何零件的。上面的 BFS 中如果 1 没有任何邻居， 为 INF，询问自然会得到正确解答。
2. 记住奇偶分层图的技巧：边权都为 1 时，BFS 找出来的第一次到达就是该奇偶性下的最短距离。