CSP 历年真题精讲 · 第 3 期
2020 年 CSP-J 入门级复赛
考试时间：2020 年 11 月 7 日 · 满分 400 · 时长 3.5 小时
题一：优秀的拆分（power）
【题目描述】
一般来说，一个正整数可以拆分成若干个正整数的和。例如，， 等。
对于正整数 的一种特定拆分，我们称它为"优秀的"，当且仅当在这种拆分下， 被分解为了若干个不同的 的正整数次幂。注意，一个数 能被表示成 的正整数次幂，当且仅当 能通过正整数个 相乘在一起得到。
例如， 是一个优秀的拆分。但是， 就不是一个优秀的拆分，因为 （即 ）不是 的正整数次幂。
现在，给定正整数 ，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案（从大到小输出）。
【输入格式】
一行一个正整数 。
【输出格式】
如果存在优秀的拆分，从大到小输出拆分中的每一个数，相邻两数之间用一个空格隔开。可以证明，在规定了拆分数字的顺序后，该拆分方案是唯一的。
若不存在优秀的拆分，输出 -1。
【样例 1】
输入：6
输出：4 2
解释： 是一个优秀的拆分。注意 不满足"互不相同"的条件。
【样例 2】
输入：7
输出：-1
解释： 是奇数，必然包含 ，不满足" 的正整数次幂"条件。
【数据范围】
对于 的数据， 对于另外 的数据，保证 为奇数 对于另外 的数据，保证 为 的正整数次幂 对于 的数据，
【解题思路】
本题的核心是二进制拆分。注意到任何一个正整数本身就可以按二进制位拆分成若干不同 的幂之和，但题目的限制是不能包含 ——即拆分必须使用 。
关键观察：
如果 是奇数，其二进制最低位必定为 （即包含 ），且无论如何拆分都会留下一个奇数，无法用 的正整数次幂组合。因此奇数直接输出 -1。 如果 是偶数，将其二进制表示的每一位对应的 （）依次输出即可。这正是 的唯一优秀拆分。
算法流程：
若 ，输出 -1并结束。从高位到低位遍历 的二进制位（ 从大到小，）。 若第 位为 ，输出 。
时间复杂度：。
【参考代码（C++）】
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
// 奇数必然包含 2^0=1，无解
if (n & 1) {
cout << -1 << endl;
return 0;
}
// 从大到小输出二进制位
// 2^30 = 1073741824 > 10^7，所以从 2^30 开始足够
for (int k = 30; k >= 1; k--) {
if (n & (1 << k)) {
cout << (1 << k) << " ";
}
}
cout << endl;
return 0;
}
【知识点】
二进制/位运算： n & 1判奇偶，1 << k表示唯一分解性质：偶数的二进制拆分是唯一的优秀拆分 关键结论：奇数无解（因为必然会用到 ） 时间复杂度：
题二：直播获奖（live）
【题目描述】
NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。
本次竞赛的获奖率为 ，即当前排名前 的选手的最低成绩就是即时的分数线。
更具体地，若当前已评出了 个选手的成绩，则当前计划获奖人数为：
如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。
作为评测组的技术人员，请你帮 CCF 写一个直播程序：每输入一个选手成绩，输出当前获奖分数线。
【输入格式】
第一行两个正整数 ，分别代表选手总数与获奖率（）。 第二行 个非负整数，依次代表逐一评出的选手成绩。
【输出格式】
一行 个非负整数，依次代表每个选手成绩评出后，即时的获奖分数线。相邻两个整数间用一个空格分隔。
【样例】
输入：
10 60
200 300 400 500 600 600 0 300 200 100
输出：
200 300 400 400 400 500 400 400 300 300
【数据范围】
对于所有测试点，每个选手的成绩均为不超过 的非负整数 ，
浮点数提示：计算 时，如果用浮点类型（如 C/C++ 的
float/double）， 的结果可能为 或 ，向下取整结果不确定。建议仅使用整型变量计算。
【解题思路】
暴力做法（50 分）：每加入一个新成绩，对前面所有成绩 sort 一次，取第 大的值。时间复杂度 ， 会超时。
满分做法 —— 桶排序（计数排序）：
观察到选手成绩范围仅 ，可以维护一个桶数组 cnt[score]：
每加入一个分数 ， cnt[x]++。求第 大（）时，从 倒序遍历到 ，累加 cnt[j]，当累加人数 时，当前分数 即为分数线。
时间复杂度：每次查询 ，总复杂度 ，在 C++ 中可轻松通过。
整除技巧： 直接使用整数除法，避免浮点误差。
【参考代码（C++）】
#include <bits/stdc++.h>
using namespace std;
const int MAX_SCORE = 600;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, w;
cin >> n >> w;
int cnt[MAX_SCORE + 1] = {0}; // 桶
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
cnt[x]++; // 入桶
// 计算当前计划获奖人数
int plan = max(1, i * w / 100);
// 从高分往低分扫描
int sum = 0;
for (int j = MAX_SCORE; j >= 0; j--) {
sum += cnt[j];
if (sum >= plan) {
cout << j << " ";
break;
}
}
}
cout << endl;
return 0;
}
【知识点】
计数排序 / 桶排序：值域有限时替代快速排序 动态求第 k 大：值域较小时用桶比堆/平衡树更优 整数运算避免浮点误差： 替代 时间复杂度分析：，
题三：表达式（expr）
【题目描述】
小 C 热衷于学习数理逻辑。有一天，他发现了一种特别的逻辑表达式。
在这种逻辑表达式中，所有操作数都是变量，取值只能为 或 。运算包括：
与运算 &：。当且仅当 和 的值都为 时结果为 。或运算 |：。当且仅当 和 的值都为 时结果为 。取反运算 !：。当且仅当 时结果为 。
小 C 想知道：给定一个逻辑表达式和其中每一个操作数的初始取值后，再取反某一个操作数的值时，原表达式的值为多少。
约定：表达式采用后缀表达式的方式输入。变量由小写字母 x 与正整数拼接而成（如 x10）。每个变量在表达式中出现恰好一次。
【输入格式】
第一行一个字符串 ，表示后缀表达式。运算符与操作数之间有一个空格，表达式末尾没有空格。 第二行一个正整数 ，表示变量的数量。变量下标为 。 第三行 个整数（ 或 ），第 个表示 的初值。 第四行一个正整数 ，表示询问个数。 接下来 行，每行一个正整数，表示需要取反的变量下标。每次询问的修改是临时的，不影响后续询问。
【输出格式】
行，每行一个 或 ，表示该询问下表达式的值。
【样例 1】
输入：
x1 x2 & x3 |
3
1 0 1
3
1
2
3
输出：
1
1
0
解释：中缀表达式为 。初始值 ，结果为 。
取反 → 赋值 → 取反 → 赋值 → 取反 → 赋值 →
【数据范围】
对于 的数据，表达式有且仅有 &或仅有|对于另外 的数据，，， 对于 的数据，，，
【解题思路】
本题是 2020 CSP-J 中最难的一题，核心是表达式树 + 短路性质。
第一步：建表达式树
后缀表达式可以用栈轻松建立二叉树：
遇到操作数（如 x3），新建叶子节点并入栈。遇到 !，弹出栈顶节点，新建节点作为其父节点（取反）。遇到 &或|，弹出栈顶两个节点，新建节点作为其父节点（二元运算）。
建树后，从根节点递归计算原表达式的值。
第二步：利用短路性质
& 和 | 具有"短路"特性——在某些条件下，一侧的值无论如何变化，都不会影响结果：
| 运算符 | 一侧为 | 短路效果 |
|---|---|---|
& |
无论另一侧是什么，结果恒为 ，另一侧的变化不影响结果 | |
| ` | ` |
判断逻辑（设左右子树值分别为 ）：
若当前节点是 &：如果 ，则右子树的所有变量不影响结果；如果 ，则左子树的所有变量不影响结果。若当前节点是 |：如果 ，则右子树的所有变量不影响结果；如果 ，则左子树的所有变量不影响结果。
第三步：标记影响性
从根节点出发 DFS：
初始 （根节点对结果有影响）。 对每个 &节点，若左子树值为 ，则标记右子树为不影响（），因为无论右子树怎么变，0 & X = 0。对每个 |节点，若左子树值为 ，则标记右子树为不影响。对每个 !节点，影响性直接传递给子节点。DFS 到达叶子节点时，记录该变量是否对结果有影响（）。
第四步：回答询问
设原表达式结果为 ，对询问的变量 ：
若 （影响结果），则取反后结果变为 。 若 （不影响），则结果仍为 。
时间复杂度：建树 + DFS + 回答 ，总计 。
【参考代码（C++）】
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
// 表达式树节点
struct Node {
int val; // 该节点的值（0 或 1）
int lc, rc; // 左右孩子编号（0 表示无）
int opt; // 运算符：0=叶子, 1=!, 2=&, 3=|
};
Node t[MAXN];
int tot = 0; // 已使用的节点数
int a[MAXN]; // 变量的初值
bool flag[MAXN]; // flag[i] = 变量 i 是否对最终结果有影响
// 建树：后缀表达式 → 表达式树
int build(string s, int n) {
stack<int> st;
// 注意：s 以空格分隔
stringstream ss(s);
string token;
while (ss >> token) {
if (token[0] == 'x') {
int id = stoi(token.substr(1));
++tot;
t[tot].val = a[id];
t[tot].lc = t[tot].rc = 0;
t[tot].opt = id; // 存下标
st.push(tot);
} else if (token[0] == '!') {
int x = st.top(); st.pop();
++tot;
t[tot].val = !t[x].val;
t[tot].lc = x;
t[tot].rc = 0;
t[tot].opt = 1;
st.push(tot);
} else if (token[0] == '&') {
int r = st.top(); st.pop();
int l = st.top(); st.pop();
++tot;
t[tot].val = t[l].val & t[r].val;
t[tot].lc = l;
t[tot].rc = r;
t[tot].opt = 2;
st.push(tot);
} else if (token[0] == '|') {
int r = st.top(); st.pop();
int l = st.top(); st.pop();
++tot;
t[tot].val = t[l].val | t[r].val;
t[tot].lc = l;
t[tot].rc = r;
t[tot].opt = 3;
st.push(tot);
}
}
return st.top(); // 根节点编号
}
// DFS：标记哪些叶子变量对结果有影响
void dfs(int u, bool mark) {
if (t[u].lc == 0 && t[u].rc == 0) {
// 叶子节点
flag[t[u].opt] = mark;
return;
}
if (!mark) {
// 已标记为不影响，子节点都不影响
if (t[u].lc) dfs(t[u].lc, false);
if (t[u].rc) dfs(t[u].rc, false);
return;
}
if (t[u].opt == 1) {
// ! 节点
dfs(t[u].lc, mark);
} else if (t[u].opt == 2) {
// & 节点
if (t[t[u].lc].val == 0) dfs(t[u].rc, false);
else dfs(t[u].rc, mark);
if (t[t[u].rc].val == 0) dfs(t[u].lc, false);
else dfs(t[u].lc, mark);
} else if (t[u].opt == 3) {
// | 节点
if (t[t[u].lc].val == 1) dfs(t[u].rc, false);
else dfs(t[u].rc, mark);
if (t[t[u].rc].val == 1) dfs(t[u].lc, false);
else dfs(t[u].lc, mark);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
getline(cin, s); // 读取后缀表达式整行
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int root = build(s, n); // 建树
int ans = t[root].val; // 原表达式结果
dfs(root, true); // 标记影响性
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
// flag[x] 为真 → 取反影响结果 → 输出 !ans
cout << (flag[x] ? !ans : ans) << "\n";
}
return 0;
}
【知识点】
后缀表达式求值 + 建表达式树 栈 + 二叉树 短路求值（short-circuit evaluation）： &遇 、|遇 即短路DFS / 树形 DP：标记影响性（mark propagation） 时间复杂度
题四：方格取数（number）
【题目描述】
设有 的方格图，每个方格中都有一个整数。
现有一只小熊，想从图的左上角 走到右下角 ，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。
小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。
【输入格式】
第一行有两个整数 。 接下来 行每行 个整数，依次代表每个方格中的整数。
【输出格式】
一个整数，表示小熊能取到的整数之和的最大值。
【样例 1】
输入：
3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1
输出：9
最优路径：，和 ？
正确答案：，和 ... 实际最优路径和为 。
【数据范围】
对于 的数据， 对于 的数据， 对于 的数据， 对于 的数据，，方格中整数的绝对值不超过
【解题思路】
经典的动态规划题，但由于"只能向右、向上、向下"的移动约束（即不能向左），需要在 DP 时按列处理。
关键分析
移动规则：每一步可以向右、向上、向下。不能向左意味着一旦到达某一列，就再也不能回到更左边的列。因此可以按列递推。
状态定义：
：从 走到 ，最后一步从上方（）到达时的最大和。 ：从 走到 ，最后一步从下方（）到达时的最大和。 转移方程（按列 处理）：
考虑从第 列进入第 列。进入点是 ，然后可以在第 列内上下移动。
从上往下扫（ 从 到 ）：
解释：到达 可以来自上方 ，或来自左方 （从左边直接过来）。
从下往上扫（ 从 到 ）：
边界：
第 列只能从上往下走到，。 其余位置初始设为 。 答案：。
时间复杂度：，空间复杂度：（按列滚动，每列只需保留上一列信息）。
【参考代码（C++）】
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1005;
const ll INF = 1e18;
ll a[MAXN][MAXN];
ll up[MAXN], down[MAXN]; // 当前列
ll prev_up[MAXN], prev_down[MAXN]; // 前一列
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
// 第一列特殊处理：只能从上往下走
prev_up[1] = prev_down[1] = a[1][1];
for (int i = 2; i <= n; i++) {
prev_up[i] = prev_down[i] = prev_up[i-1] + a[i][1];
}
// 按列 DP
for (int j = 2; j <= m; j++) {
// 初始化当前列为 -INF
fill(up, up + n + 1, -INF);
fill(down, down + n + 1, -INF);
// 从上往下扫
for (int i = 1; i <= n; i++) {
ll from_left = max(prev_up[i], prev_down[i]);
if (from_left != -INF)
up[i] = max(up[i], from_left + a[i][j]);
if (i > 1 && up[i-1] != -INF)
up[i] = max(up[i], up[i-1] + a[i][j]);
}
// 从下往上扫
for (int i = n; i >= 1; i--) {
ll from_left = max(prev_up[i], prev_down[i]);
if (from_left != -INF)
down[i] = max(down[i], from_left + a[i][j]);
if (i < n && down[i+1] != -INF)
down[i] = max(down[i], down[i+1] + a[i][j]);
}
// 滚动
for (int i = 1; i <= n; i++) {
prev_up[i] = up[i];
prev_down[i] = down[i];
}
}
cout << max(up[n], down[n]) << endl;
return 0;
}
【知识点】
动态规划（按列递推） 状态设计：区分"从上到达"和"从下到达"两种转移方向 滚动数组：空间优化， 不能向左走的约束 → 转化为按列处理的 DP 边界初始化： 表示不可达状态
本期小结
| 题目 | 难度 | 核心算法 | 关键知识点 |
|---|---|---|---|
| 优秀的拆分 | ★☆☆ | 位运算 / 二进制拆分 | 奇数无解、按位分解 |
| 直播获奖 | ★★☆ | 计数排序（桶排序） | 值域 600 的妙用、整除避浮点 |
| 表达式 | ★★★★ | 表达式树 + DFS | 后缀表达式建树、短路标记传播 |
| 方格取数 | ★★★ | 动态规划 | 按列 DP、双向扫、滚动数组 |
下期预告：2020 CSP-S 提高级复赛 4 题（贪吃蛇 / 函数调用 / 动物园 / 儒略日），敬请期待。
