CSP-J 2020 题解

优秀的拆分

前置知识:位运算。

题面

题目描述

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

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

例如,10=8+2=23+2110=8+2=2^3+2^1 是一个优秀的拆分。但是,7=4+2+1=22+21+207=4+2+1=2^2+2^1+2^0 就不是一个优秀的拆分,因为 11 不是 22 的正整数次幂。

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

输入输出格式

输入格式

输入只有一行,一个整数 nn,代表需要判断的数。

输出格式

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

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

思路

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

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

11 左移 nn 位(1<<n)和 2n2^n 是等效的。同理,将 11 右移 nn 位(1>>n)等同于 1÷2n1\div 2^n 。取 xx 的二进制第 ii 位可以写成 x >> i & 1

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

(1010)2=1×23+0×22+1×21+0×20=23+21=8+2=10\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次幂就足够了。

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

代码

#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\%,即当前排名前 w%w\% 的选手的最低成绩就是即时的分数线。

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

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

输入输出格式

输入格式

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

输出格式

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

思路

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

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

代码

#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×mn \times m 的方格图,每个方格中都有一个整数。现有一只小熊,想从图的左上角走到右下角,每一步只能向上、向下或向右走一格,并且不能重复经过已经走过的方格,也不能走出边界。小熊会取走所有经过的方格中的整数,求它能取到的整数之和的最大值。

输入输出格式

输入格式

第一行有两个整数 n,mn, m

接下来 nn 行每行 mm 个整数,依次代表每个方格中的整数。

输出格式

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

思路

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

若搜到以前搜过的状态则直接返回搜过的最大和(也就是 FF 中的值),否则继续搜索到达该格时的最大和。

代码

#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;
}
CSP-J 2020 题解
本文作者
宝硕
发布于
2020-11-16
更新于
2021-03-21
许可协议
喜欢这篇文章?为什么不考虑打赏一下作者呢?
爱发电
文章目录
  1. 优秀的拆分
    1. 题面
      1. 题目描述
      2. 输入输出格式
    2. 思路
    3. 代码
  2. 直播获奖
    1. 题面
      1. 题目描述
      2. 输入输出格式
    2. 思路
    3. 代码
  3. 方格取数
    1. 题面
      1. 题目描述
      2. 输入输出格式
    2. 思路
    3. 代码