2020年CSP-J入门级复赛真题解析
第一题：优秀的拆分（power）
题目描述
一般来说，一个正整数可以拆分成若干个正整数的和。例如，1=1，10=1+2+3+4等。对于正整数n的一种特定拆分，我们称它为"优秀的"，当且仅当在这种拆分下，n被分解为了若干个不同的2的正整数次幂。
注意，一个数x能被表示成2的正整数次幂，当且仅当x能通过正整数个2相乘在一起得到。
例如，10=8+2=2³+2¹是一个优秀的拆分。但是，7=4+2+1=2²+2¹+2⁰就不是一个优秀的拆分，因为1不是2的正整数次幂。
现在，给定正整数n，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案。
输入输出格式
输入格式
- 输入文件名为
power.in - 输入文件只有一行，一个正整数n，代表需要判断的数
输出格式
- 输出文件名为
power.out - 如果存在优秀的拆分，从大到小输出拆分中的每一个数，相邻两个数之间用一个空格隔开
- 若不存在优秀的拆分，输出"-1"
样例
样例1
输入：
6输出：
4 2解释： 6=4+2=2²+2¹是一个优秀的拆分。注意，6=2+2+2不是优秀的拆分，因为拆分成的3个数不满足每个数互不相同。
样例2
输入：
7输出：
-1数据范围
| 数据范围 | 条件 |
|---|---|
| 20% | n ≤ 10 |
| 另外20% | 保证n为奇数 |
| 另外20% | 保证n为2的正整数次幂 |
| 80% | n ≤ 1024 |
| 100% | 1 ≤ n ≤ 1×10⁷ |
题目解析
核心思路
一个数本来就可以拆分成2的正整数次幂，因为利用它的二进制即可得到。
例如：6的二进制是110，分别代表2²，2¹，2⁰，所以6可以看成2²+2¹=4+2。
对n进行二进制分解，然后倒序输出即可。
参考程序：
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n;
int main() {
cin >> n;
if (n % 2 == 1) {
cout << -1;
return 0;
}
int a[30], cnt = 0;
int base = 1;
while (n) {
if (n % 2 == 1) {
a[++cnt] = base;
}
n /= 2;
base *= 2;
}
for (int i = cnt; i >= 1; i--) {
cout << a[i] << " ";
}
return 0;
}零一点评
本题难度显著高于2019、2018、2017年的第一题。没有联想到二进制转化的同学可能会被卡住。一旦联想到，就是一个【入门】级题目。
骗分方法
- 第一个20%：对每个n，打表
- 第二个20%：根据题意，不存在，直接输出-1
- 第三个20%：它的拆分就是它本身，直接输出n本身
第二题：直播获奖（live）
题目描述
NOI2020即将举行。为了增加观赏性，CCF决定逐一评出每个选手的成绩，并直播即时的获奖分数线。
本次竞赛的获奖率为w%，即当前排名前w%的选手的最低成绩就是即时的分数线。
更具体地，若当前已评出了p个选手的成绩，则当前计划获奖人数为max(1, ⌊p×w%⌋)，其中w是获奖百分比，⌊x⌋表示对x向下取整，max(x,y)表示x和y中较大的数。
如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。
输入输出格式
输入格式
- 输入文件名为
live.in - 第1行两个正整数n，w，分别代表选手总数与获奖率
- 第2行有n个非负整数，依次代表逐一评出的选手成绩
输出格式
- 输出文件名为
live.out - 只有一行，包含n个非负整数，依次代表选手成绩逐一评出后，即时的获奖分数线
- 相邻两个整数间用一个空格分隔
样例
输入：
10 60
200 300 400 500 600 600 0 300 200 100输出：
200 300 400 400 400 500 400 400 300 300数据范围
| 测试点编号 | n值 |
|---|---|
| 1~3 | = 10 |
| 4~6 | = 500 |
| 7~10 | = 2000 |
| 11~17 | = 10000 |
| 18~20 | = 100000 |
注意事项
- 每个选手的成绩均为不超过600的非负整数
- 获奖百分比w是一个正整数，1 ≤ w ≤ 99
- 建议仅使用整型变量，以避免浮点数精度问题
题目解析
算法思路：
50分程序：对于每个选手，把之前的数据进行sort排序，选择max(1, ⌊p×w%⌋)人处的分数。时间复杂度约为O(n²)。
100分程序：观察到数据范围里成绩在600以内，因此可以变sort排序为桶排序。准备600个桶，每个选手处，把他分数对应的桶里的个数++。然后从第600号桶倒序循环到1号桶，进行人数统计，输出max(1, ⌊p×w%⌋)人处的分数。时间复杂度为O(600n)。
100分程序：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, w, b[605];
int main() {
cin >> n >> w;
for (int i = 1; i <= n; i++) {
int v;
cin >> v;
b[v]++;
int cnt = max(1, i * w / 100);
int k = 600, sum = 0;
while (k >= 0) {
if (sum + b[k] < cnt) {
sum += b[k];
k--;
} else {
cout << k << " ";
break;
}
}
}
return 0;
}零一点评
本题延续了2019年第二题的风格：除了基础代码能力，增加了对时间复杂度的考察。如果时间复杂度过关，那么难度要弱于2019年的公交换乘。另外本题对于浮点数运算的考察也是一个易错点。
第三题：表达式（expr）
题目描述
小C热衷于学习数理逻辑。有一天，他发现了一种特别的逻辑表达式。在这种逻辑表达式中，所有操作数都是变量，且它们的取值只能为0或1，运算从左往右进行。
特别的，这种表达式有且仅有以下几种运算：
- 与运算：a&b，当且仅当a和b的值都为1时，该表达式的值为1，其余情况该表达式的值为0
- 或运算：a|b，当且仅当a和b的值都为0时，该表达式的值为0，其余情况该表达式的值为1
- 取反运算：!a，当且仅当a的值为0时，该表达式的值为1，其余情况该表达式的值为0
小C想知道，给定一个逻辑表达式和其中每一个操作数的初始取值后，再取反某一个操作数的值时，原表达式的值为多少。
输入格式约定
表达式格式
- 表达式采用后缀表达式的方式输入
- 与运算符（&）、或运算符（|）、取反运算符（!）的左右均有一个空格，但表达式末尾没有空格
- 操作数由小写字母x与一个正整数拼接而成，正整数表示这个变量的下标
- 数据保证每个变量在表达式中出现恰好一次
输入输出格式
输入格式
- 输入文件名为
expr.in - 第一行包含一个字符串s，表示后缀表达式
- 第二行包含一个正整数n，表示表达式中变量的数量
- 第三行包含n个整数，第i个整数表示变量xi的初值
- 第四行包含一个正整数q，表示询问的个数
- 接下来q行，每行一个正整数，表示需要取反的变量的下标
输出格式
- 输出文件名为
expr.out - 输出一共有q行，每行一个0或1，表示该询问下表达式的值
样例
样例1
输入：
x1 x2 & x3 |
3
1 0 1
3
1
2
3输出：
1
1
0解释： 该后缀表达式的中缀表达式形式为(x1 & x2) | x3
对于第一次询问，将x1的值取反。此时，三个操作数对应的赋值依次为0，0，1，原表达式的值为(0 & 0) | 1 = 1.
对于第二次询问，将x2的值取反。此时，三个操作数对应的赋值依次为1，1，1，原表达式的值为(1&1) |1 = 1.
对于第三次询问，将x3的值取反。此时，三个操作数对应的赋值依次为1，0，0，原表达式的值为(1& 0) | 0 = 0.
样例2
输入：
x1 ! x2 x4 | x3 x5 ! & & ! &
5
0 1 0 1 1
3
1
3
5输出：
0
1
1解释： 该表达式的中缀表达式形式为（! x1）&（!（（x2 | x4）&（x3 &（! x5））））。
数据范围
| 数据范围 | 条件 |
|---|---|
| 20% | 表达式中有且仅有与运算（&）或者或运算（ |
| 另外30% | |
| 另外20% | 变量的初值全为0或全为1 |
| 100% | 1 ≤ |
题目解析
算法分析：
- 20分程序：表达式只有&运算，或者表达式只有|运算
- 30分程序：利用栈处理后缀表达式
- 100分程序：利用&运算和|运算的性质进行优化，建立表达式二叉树
100分程序：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, a[1000005], q;
int z[1000005], top;
int cnt;
struct tree {
int l;
int r;
int v;
} t[1000005];
bool f[1000005];
bool change[1000005];
bool calc(int i) { // 计算每个二叉树结点的运算结果
if (t[i].v >= 0) { // 数值结点
f[i] = a[t[i].v];
return f[i];
}
bool x1 = calc(t[i].l);
bool x2 = calc(t[i].r);
if (t[i].v == -1) f[i] = !x1;
else if (t[i].v == -2) f[i] = x1 & x2;
else f[i] = x1 | x2;
return f[i];
}
void affect(int i) { // 看看i结点的运算会不会受左右孩子影响
if (t[i].v >= 0) { // 如果能递归到数值结点
change[t[i].v] = 1; // 说明这个数值的变化会改变结果
return;
}
if (t[i].v == -1) affect(t[i].l); // !运算
else if (t[i].v == -2) { // &运算
if (f[t[i].l] == 1 && f[t[i].r] == 1) {
affect(t[i].l);
affect(t[i].r);
} else if (f[t[i].l] == 0 && f[t[i].r] == 1) {
affect(t[i].l);
} else if (f[t[i].l] == 1 && f[t[i].r] == 0) {
affect(t[i].r);
}
} else { // |运算
if (f[t[i].l] == 0 && f[t[i].r] == 0) {
affect(t[i].l);
affect(t[i].r);
} else if (f[t[i].l] == 0 && f[t[i].r] == 1) {
affect(t[i].l);
} else if (f[t[i].l] == 1 && f[t[i].r] == 0) {
affect(t[i].r);
}
}
}
int main() {
char ch;
while((ch=getchar())!='\n') {
int v;
if(ch=='x') {
++cnt; // 新建表达式树的结点
scanf("%d",&v);
t[cnt].v = v;
z[++top] = cnt;
}
else if(ch==' ') continue;
else {
++cnt; // 新建表达式树的结点
if (ch == '!') {
t[cnt].l = z[top--];
t[cnt].v = -1;
} else if (ch == '&') {
t[cnt].r = z[top--];
t[cnt].l = z[top--];
t[cnt].v = -2;
} else {
t[cnt].r = z[top--];
t[cnt].l = z[top--];
t[cnt].v = -3;
}
z[++top] = cnt;
}
}
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
calc(cnt);
affect(cnt);
cin >> q;
for (int i = 1; i <= q; i++) {
int x;
cin >> x;
if (change[x]) cout << !f[cnt] << endl;
else cout << f[cnt] << endl;
}
return 0;
}零一点评
本题第一个20%的样例非常具有迷惑性，很多同学以为是&和|混杂，实际是单纯只有&，或者单纯只有|。如果读题读对了，20分非常容易骗得。接下来30%的数据，需要懂得栈和后缀表达式的原理，并且熟悉字符串的操作。对于基础算法掌握好的同学比较容易骗到。100%的思路是全场最难的，需要对位运算有很强的洞悉能力，或者练习到过类似的高级数据结构的题目。
第四题：方格取数（number）
题目描述
设有n×m的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。
小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。
输入输出格式
输入格式
- 输入文件名为
number.in - 第1行两个正整数n，m
- 接下来n行每行m个整数，依次代表每个方格中的整数
输出格式
- 输出文件名为
number.out - 一个整数，表示小熊能取到的整数之和的最大值
样例
样例1
输入：
3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1输出：
9样例2
输入：
2 5
-1 -1 -3 -2 -7
-2 -1 -4 -1 -2输出：
-10数据范围
| 数据范围 | 条件 |
|---|---|
| 20% | n，m ≤ 5 |
| 40% | n，m ≤ 50 |
| 70% | n，m ≤ 300 |
| 100% | 1 ≤ n，m ≤ 1000，方格中整数的绝对值不超过10⁴ |
题目解析
算法分析：
- 20分程序：基础搜索算法，时间复杂度3^(nm)
- 40分程序：动态规划，时间复杂度O(N³M)
- 70分程序：前缀和优化，时间复杂度O(N²M)
- 100分程序：状态分离优化，时间复杂度O(NM)
100分程序：
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long int
using namespace std;
ll n, m, a[1005][1005];
ll f[1005][1005];
ll fl[1005][1005], fu[1005][1005], fd[1005][1005];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
for (int i = 0; i <= n+1; i++) {
for (int j = 0; j <= m+1; j++) {
f[i][j] = fl[i][j] = fu[i][j] = fd[i][j] = -1e18;
}
}
for (int i = 1; i <= n; i++) {
ll sum = 0;
for (int k = 1; k <= i; k++) sum += a[k][1];
f[i][1] = sum;
}
for (int j = 2; j <= m; j++) {
for (int i = 1; i <= n; i++) {
fl[i][j] = f[i][j-1] + a[i][j];
}
for (int i = 2; i <= n; i++) {
fu[i][j] = max(fl[i-1][j], fu[i-1][j]) + a[i][j];
}
for (int i = n-1; i >= 1; i--) {
fd[i][j] = max(fl[i+1][j], fd[i+1][j]) + a[i][j];
}
for (int i = 1; i <= n; i++) {
f[i][j] = max(fl[i][j], fu[i][j]);
f[i][j] = max(f[i][j], fd[i][j]);
}
}
cout << f[n][m];
return 0;
}零一点评
本题第一个20%的数据采用经典基础搜索算法即可骗到分，剩下的思路需要动态规划算法，且要有较好的实战能力，对于能力高的同学有一定的区分度。
总体点评
难度分析
第一题：显著难于17、18、19年第一题。往年第一题对于二三等奖区分度不高，希望今年有好的划线。
第二题：果然延续了去年第二题公交换乘对于时间复杂度的考察，但是代码实现起来比18、19年简单一些。
第三题：第一个20%的样例描述十分具有迷惑性，否则非常容易骗分。100分的算法属于本场最难，需要很好的洞察力和数据结构实战能力。
第四题：第一个20%的数据采用经典基础搜索算法即可骗到分，剩下的思路需要动态规划算法，且要有较好的实战能力。
原文链接：https://blog.csdn.net/kittyover/article/details/109625249