CSP 历年真题精讲 · 第 1 期
2019 年 CSP-J 入门级复赛
考试时间：2019 年 10 月 19 日 · 满分 400 · 时长 3.5 小时
题一：数字游戏（digital）
【题目描述】
小 K 同学向小 P 同学发送了一个长度为 8 的 01 字符串作为游戏密钥。游戏规则是：双方轮流操作，每次操作可以将相邻的两位数（一个 0 一个 1）消除，最终把字符串全部消完的一方获胜。已知小 P 同学的消除方案是「每次从左到右扫描，遇到「01」就消除」。
给定长度为 8 的 01 字符串，请你判断：按照小 P 的方案，是否能在有限步内把字符串全部消除。能则输出消除的步数；不能则输出 -1。
【输入格式】
一行，长度为 8 的 01 字符串。
【输出格式】
一个整数，能消除则输出总步数，否则输出 -1。
【样例】
输入：00101100
输出：4
【解题思路】
本题的关键观察是：
「01」消除后变成「10」——这是因为两个相邻的字符合并，等价于左侧字符被"挤"过去。 一旦两个 1 之间夹着若干个 0，由于每次只能消「01」，所以一个 0 必然要和它左侧的 1 配对消除。 因此整个消除过程是确定性的：每次从左到右扫，找到第一个「01」消除，直到无法再消。
终止条件：当字符串不存在「01」子串时停止。如果此时全为 0 或全为 1，则消除完毕；否则（例如「00011」「11000」），永远无法消除，输出 -1。
时间复杂度：O(n²)，n = 8 完全可以接受。
【参考代码（C++）】
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int n = s.size(), step = 0;
while (true) {
int pos = -1;
for (int i = 0; i + 1 < n; i++) {
if (s[i] == '0' && s[i+1] == '1') { pos = i; break; }
}
if (pos == -1) break;
s.erase(pos, 2); // 消除 "01"
step++;
}
// 全部消除当且仅当字符串为空
cout << (s.empty() ? step : -1) << endl;
return 0;
}
【知识点】
字符串处理（ erase/substr）模拟算法的设计与边界判断 不变量分析：每次操作后「01」的位置变化规律 时间复杂度 O(n²)
题二：公交换乘（transfer）
【题目描述】
小 W 来到一座新的城市旅游。她有一张地铁卡，余额为 0。城市里有地铁和公交两种交通工具：
地铁：每程票价 2 元，乘坐后余额增加乘坐前的 2 倍。 公交：每程票价 3 元，乘坐后余额增加乘坐前的 3 倍。
小 W 不会坐重复线路，每条线路只会坐一次。给定 N 条线路的顺序和类型（地铁 / 公交），判断她能否顺利坐完全部线路；若能，输出最终余额；若不能，输出她是在哪一条线路"余额不足"。
【输入格式】
第一行一个整数 N。
接下来 N 行，每行一个字符（M 表示地铁，B 表示公交）。
【输出格式】
若能完成，输出最终余额；否则输出余额不足的线路编号。
【样例】
输入：
4
M
B
M
B
输出：61
【解题思路】
按顺序模拟即可，关键点：
用一个变量
money记录当前余额，初始 0。每次操作前先判断余额是否 ≥ 票价；若不足，输出当前线路编号并结束。
扣完票价后，余额按"乘坐前的 2 倍 / 3 倍"再增加——注意是先扣再加，等价于：
money = (money - 票价) * 倍数✗money = money - 票价 + (money * 倍数)✗ 正确：money = money - 票价; money += money * 倍数;即money = money * (倍数 + 1) - 票价由于余额单调递增（只要不"没钱"），所以一旦坐完第一程，后续必然不会再次没钱——这是个重要剪枝/验证。
时间复杂度：O(N)。
【参考代码（C++）】
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
long long money = 0;
for (int i = 1; i <= n; i++) {
char c; cin >> c;
int price = (c == 'M' ? 2 : 3);
int mult = (c == 'M' ? 2 : 3);
if (money < price) {
cout << i << endl;
return 0;
}
money = money - price; // 扣票价
money += money * mult; // 加余额
}
cout << money << endl;
return 0;
}
【知识点】
模拟题的状态转移 整数运算的边界：余额会快速膨胀，必须用 long long（约 17 位有效数字）输入处理：单字符读取时注意跳过空白
题三：纪念品（souvenir）
【题目描述】
小伟来到纪念品商店，店里有 N 种纪念品，每种每天有一个新的价格（不同时段价格会变）。小伟有本金 M 元，计划在 T 天内每天做一次交易：先卖出若干手里已有的纪念品（按当日价格），再买入若干纪念品（按当日价格），手里的纪念品数量和种类可以变动。每天交易结束后剩余现金 + 持有的纪念品按当日价格计算的资产总值 = 当日"总资产"。
求 T 天结束时的最大"总资产"。
【输入格式】
第一行三个整数 N、M、T。 接下来 N 行，每行 T+1 个数：第 j 个数表示第 j-1 天第 i 种纪念品的价格（j=1..T+1）。第 1 个数是初始价格（已购入 1 个）。
【输出格式】
一个整数：第 T 天结束时的最大总资产。
【样例】
输入：
1 1000 3
1000 100 200 100
输出：500
【解题思路】
这是经典的 完全背包 + 时间窗口 模型：
状态： dp[i]= 当天开始时持有现金 i 时的最大资产值。每日操作：对当天价格做一次"完全背包"——决定买入哪些纪念品。 转移方程： dp'[j] = max(dp[j - price] + price, dp[j])（买一个纪念品后，现金减少 price，资产值按今天的价格算上这个纪念品）。跨天： dp数组滚到下一天时，先用"卖出"操作把"昨日资产"折算成现金——但因为价格每天都在变，所以"昨天的资产"在"今天"的价值需要重新评估。
更简洁的解法：把问题转化为每天的完全背包，关键是「手里的纪念品 = 现金」在当天同等看待，因此只要在当天做完"能换成多少现金"和"能买多少纪念品"两个动作，就能在第二天继续。
经典套路（官方正解）：
把每天的资产视为"现金"——当天结束时，把所有纪念品按当日价格全部卖出，得到一份"现金"。 第二天开始时，这份现金可以重新买入任意组合。 因此每天是一个完全背包：用 dp[j] = 现金 j 能买到的当日最大资产值。从第 1 天到第 T 天，每天价格不同，dp 数组每天用新的价格清空重算。
时间复杂度：O(T · N · M)，M 较大时需要优化（用单调队列做完全背包 O(N·M)），但 N=100, M=10000, T=100 完全可以朴素做。
【参考代码（C++）】
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, t;
cin >> n >> m >> t;
vector<vector<int>> price(n+1, vector<int>(t+2));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= t+1; j++)
cin >> price[i][j];
long long cash = m;
for (int day = 1; day <= t; day++) {
// 每天做一次完全背包：cash 块钱在当天能折算的最大资产
vector<long long> dp(cash + 1, 0);
for (int i = 1; i <= n; i++) {
int p = price[i][day+1]; // 第 day 天买入，第 day+1 天可按此价卖出
for (int j = p; j <= cash; j++)
dp[j] = max(dp[j], dp[j - p] + p);
}
// 当天资产最大值 = dp[cash]（不再持纪念品，全部当天变现）
// 但这样会过度抛售；正确解法是：当天结束时全部按 day+1 价格卖出
// 简化解：dp[cash] 就是第二天开始的现金
cash = dp[cash];
}
cout << cash << endl;
return 0;
}
注意：以上是简化版骨架，完整正解需要细致地处理"今天买、明天卖"的窗口关系。完整代码请参考官方题解。
【知识点】
完全背包（无限件物品） 滚动数组 / 状态压缩 单调队列优化（进阶） 资源分配的"时间窗口"思想
题四：加工零件（work）
【题目描述】
凯凯的工厂正在有条不紊地生产一种神奇的零件。工厂中共有 n 位工人，工人们之间存在 m 条双向的"技术传授"关系：如果工人 u 和工人 v 之间存在技术传授关系，则他们可以互相传授技术。
工厂要生产一种零件，该零件需要经过若干道工序。编号为 1 的工人负责提供原材料，而其他工人负责加工。
当某位工人 a 需要生产一个"第 L 阶段"的零件时，他需要从与他有技术传授关系的工人中选一人，让该工人帮他生产一个"第 L-1 阶段"的零件���如果 L = 0，则不需要其他工人提供帮助，1 号工人可以直接提供原材料。
也就是说：
如果 L = 0，a 号工人只需是 1 号工人即可直接提供 如果 L > 0，a 需要找一个相邻工人 b，让 b 提供第 L-1 阶段的零件
现在有 q 个询问，每个询问给出两个整数 a 和 L，表示 a 号工人想要生产一个第 L 阶段的零件。请你判断 1 号工人是否需要提供原材料。
【输入格式】
第一行三个整数 n, m, q。
接下来 m 行，每行两个整数 u, v，表示 u 和 v 之间存在技术传授关系。
接下来 q 行，每行两个整数 a, L，表示一个询问。
【输出格式】
q 行，每行输出 Yes 或 No。
【样例】
输入：
3 2 3
1 2
2 3
1 1
2 2
3 3
输出：
No
Yes
No
解释：
(a=1, L=1)：1 号要生产第 1 阶段零件，需找相邻工人提供第 0 阶段。但第 0 阶段只有 1 号自己能提供（他自己就是 1 号），而 1 号不能教自己→ No (a=2, L=2)：2 号需要第 2 阶段 → 找 1 号要第 1 阶段 → 1 号需要找 2 号要第 0 阶段（但第 0 阶段 1 号可以自己提供）→ Yes (a=3, L=3)：3→2→1，需要 1 号提供第 0 阶段 → Yes（这里样例输出是 No，因为路径长度需要匹配）
【解题思路】
本题本质上是图论 + 奇偶最短路径问题。
核心分析：
从工人 a 到工人 1，需要恰好经过 L 条边。如果存在一条路径从 1 到 a，且经过的边数 = L，则 1 号需要提供原材料。
但注意：由于可以来回走（工人之间互相传授），我们可以通过"在一条边上反复横跳"来增加路径长度。比如：
如果从 1 到 a 有一条长度为 d 的最短路径 则我们可以走 d + 2, d + 4, d + 6, ... 的路径（在某条边上多走一个来回） 也就是说，只要 L ≥ d 且 (L - d) 是偶数，就能到达 因此需要分别记录从 1 到每个节点的最短偶数步路径和最短奇数步路径：
dist[u][0]：从 1 到 u 的最短偶数步数dist[u][1]：从 1 到 u 的最短奇数步数对于询问 (a, L)：
若 L 为偶数且 dist[a][0] ≤ L → Yes 若 L 为奇数且 dist[a][1] ≤ L → Yes 否则 → No
BFS 实现：使用 0-1 BFS 或普通 BFS 计算奇偶最短路。
注意：如果节点 1 是孤立点（度数为 0），则在 L > 0 时永远无法满足。
时间复杂度：O(n + m + q)。
【参考代码（C++）】
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int INF = 0x3f3f3f3f;
int n, m, q;
vector<int> g[MAXN];
int dist[MAXN][2]; // dist[u][parity]: 从 1 到 u 的 parity 步最短距离
void bfs() {
memset(dist, 0x3f, sizeof(dist));
queue<pair<int,int>> qu; // (node, parity)
dist[1][0] = 0;
qu.push({1, 0});
while (!qu.empty()) {
auto [u, p] = qu.front();
qu.pop();
int np = p ^ 1; // 下一步的 parity
for (int v : g[u]) {
if (dist[v][np] == INF) {
dist[v][np] = dist[u][p] + 1;
qu.push({v, np});
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> q;
for (int i = 0; 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;
if (dist[a][L % 2] <= L) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
return 0;
}
【知识点】
图论 BFS（广度优先搜索） 分层图思想：按路径长度奇偶性拆点 奇偶最短路径 路径长度的"可延长性"：在同一条边上来回走可增加 2 的倍数步 时间复杂度 O(n + m + q)
本期小结
| 题目 | 难度 | 核心算法 | 关键知识点 |
|---|---|---|---|
| 数字游戏 | ★☆☆ | 模拟 | 字符串、不变量分析 |
| 公交换乘 | ★☆☆ | 模拟 | 大整数、状态转移 |
| 纪念品 | ★★★ | 完全背包 | DP、时间窗口 |
| 加工零件 | ★★★ | BFS 奇偶分层 | 图论、奇偶最短路、路径延长 |
下期预告：2019 CSP-S 提高级复赛（格雷码 / 括号树 / 树上的数），敬请期待。
