前言

这是一篇来自某个爆零选手的题解

优秀的拆分

前置知识:位运算。

题面

题目描述

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

例如,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;
}