CSP-J 2020 题解 - Baoshuo's OI Blog

#优秀的拆分

前置知识：位运算。

#题面

#题目描述

一般来说，一个正整数可以拆分成若干个正整数的和。

例如， $1=1$ ， $10=1+2+3+4$ 等。对于正整数 $n$ 的一种特定拆分，我们称它为"优秀的"，当且仅当在这种拆分下， $n$ 被分解为了若干个不同的 $2$ 的正整数次幂。注意，一个数 $x$ 能被表示成 $2$ 的正整数次幂，当且仅当 $x$ 能通过正整数个 $2$ 相乘在一起得到。

例如， $10=8+2=2^3+2^1$ 是一个优秀的拆分。但是， $7=4+2+1=2^2+2^1+2^0$ 就不是一个优秀的拆分，因为 $1$ 不是 $2$ 的正整数次幂。

现在，给定正整数 $n$ ，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案。

#输入格式

输入只有一行，一个整数 $n$ ，代表需要判断的数。

#输出格式

如果这个数的所有拆分中，存在优秀的拆分。那么，你需要从大到小输出这个拆分中的每一个数，相邻两个数之间用一个空格隔开。可以证明，在规定了拆分数字的顺序后，该拆分方案是唯一的。

若不存在优秀的拆分，输出 -1。

#思路

首先，如果 $n$ 是奇数，那么肯定不可能拆分成若干个不同的 $2$ 的正整数次幂。以 $11$ 的拆分结果 $11=2^3+2^1+2^0$ 为例，可以看到结果里面存在一个 $2$ 的 $0$ 次幂。所以当 $n$ 是奇数时不存在优秀的拆分，输出 $-1$ 即可。

C++

1
2
3

if (n & 1) {
    cout << -1 << endl;
}

将 $1$ 左移 $n$ 位（1<<n）和 $2^n$ 是等效的。同理，将 $1$ 右移 $n$ 位（1>>n）等同于 $1\div 2^n$ 。取 $x$ 的二进制第 $i$ 位可以写成 x >> i & 1 。

我们观察一下 $10$ 转换成二进制后的结果： $(1010)_2$ ，再将它转换成十进制的式子列出来：

$\begin{aligned} (1010)_2 & = 1 \times 2^3 + 0\times 2^2 + 1 \times 2^1 + 0 \times 2^0 \\ & = 2^3 + 2^1 \\ & = 8 + 2 \\ & = 10 \end{aligned}$

再看下数据范围，24 次幂就足够了。

C++

for (int i = 24; i > 0; i--) {
    if (n >> i & 1) {
        cout << (1 << i) << ' ';
    }
}

#代码

C++

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    if (n & 1) {
        cout << -1 << endl;
    }
    else {
        for (int i = 24; i > 0; i--) {
            if (n >> i & 1) {
                cout << (1 << i) << ' ';
            }
        }
    }
    return 0;
}

#直播获奖

#题面

#题目描述

NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 $w\%$ ，即当前排名前 $w\%$ 的选手的最低成绩就是即时的分数线。

更具体地，若当前已评出了 $p$ 个选手的成绩，则当前计划获奖人数为 $\max(1, \lfloor p * w \%\rfloor)$ ，其中 $w$ 是获奖百分比， $\lfloor x \rfloor$ 表示对 $x$ 向下取整， $\max(x,y)$ 表示 $x$ 和 $y$ 中较大的数。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。

作为评测组的技术人员，请你帮 CCF 写一个直播程序。

#输入输出格式

#输入格式

第一行有两个整数 $n, w$ 。分别代表选手总数与获奖率。第二行有 $n$ 个整数，依次代表逐一评出的选手成绩。

#输出格式

只有一行，包含 $n$ 个非负整数，依次代表选手成绩逐一评出后，即时的获奖分数线。相邻两个整数间用一个空格分隔。

#思路

每读入一个数，使用二分插入到 vector 中，然后按照题意输出即可。

注意： $score$ 数组内成绩是由小到大排列的，所以输出的时候要使用 score.size() - max(1, i * w / 100) 作为下标。

#代码

C++

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, w, t;
    vector<int> score;
    cin >> n >> w;
    for (int i = 1; i <= n; i++) {
        cin >> t;
        score.insert(lower_bound(score.begin(), score.end(), t), t);
        cout << score[score.size() - max(1, i * w / 100)] << ' ';
    }
    return 0;
}

#方格取数

#题面

#题目描述

设有 $n \times m$ 的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。

#输入输出格式

#输入格式

第一行有两个整数 $n, m$ 。

接下来 $n$ 行每行 $m$ 个整数，依次代表每个方格中的整数。

#输出格式

一个整数，表示小熊能取到的整数之和的最大值。

#思路

设 $F_{i,j,0}$ 表示从一个格子上方走到该格子的路径最大和， $F_{i,j,1}$ 表示从一个格子下方走到该格子的路径最大和。

若搜到以前搜过的状态则直接返回搜过的最大和（也就是 $F$ 中的值），否则继续搜索到达该格时的最大和。

#代码

C++

#include <bits/stdc++.h>

using namespace std;

int       n, m;
long long w[1005][1005], f[1005][1005][2];

long long dfs(int x, int y, int from) {
    if (x < 1 || x > n || y < 1 || y > m) {
        return -0x3f3f3f3f;
    }
    if (f[x][y][from] != -0x3f3f3f3f) {
        return f[x][y][from];
    }
    if (from == 0) {
        f[x][y][from] = max({dfs(x + 1, y, 0), dfs(x, y - 1, 0), dfs(x, y - 1, 1)}) + w[x][y];
    }
    else {
        f[x][y][from] = max({dfs(x - 1, y, 1), dfs(x, y - 1, 0), dfs(x, y - 1, 1)}) + w[x][y];
    }
    return f[x][y][from];
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> w[i][j];
            f[i][j][0] = f[i][j][1] = -0x3f3f3f3f;
        }
    }
    f[1][1][0] = f[1][1][1] = w[1][1];
    cout << dfs(n, m, 1) << endl;
    return 0;
}