CSP2020-J2 题解 —— A题：优秀的拆分_优秀的拆分(power)贪心

题目相关

题目链接

目前还没有官方的题目，本题目来自洛谷，https://www.luogu.com.cn/problem/P7071?contestId=37027。等官方题目出来后，在补齐。

题目描述

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

例如，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。

样例 1

样例输入 1

6

样例输出 1

4 2

解释

$6=4+2=2^2+2^1$ 是一个优秀的拆分。注意，6=2+2+26=2+2+2 不是一个优秀的拆分，因为拆分成的 3 个数不满足每个数互不相同。

样例 2

样例输入 2

7

样例输出 2

-1

数据规模

• 对于 20% 的数据，n≤10。
• 对于另外 20% 的数据，保证 n 为奇数。
• 对于另外 20% 的数据，保证 n 为 2 的正整数次幂。
• 对于 80% 的数据，n≤1024。
• 对于 100% 的数据，$1 \le n \le 1 \times 10^7$。

题解报告

题目分析

第一题不是很难的一个题目，当然比起以前的打卡题，已经难了不少。

首先很容易知道，当 n 为奇数的时候，输出结果为 -1。20% 的分数拿到。当 n 为偶数的时候，怎么处理？一种方法是利用贪心，来构造 2 的正整数次幂。

最简单的方法是使用位运算。我们知道每次左移（<<）一位，表示数据乘 2。也就是说，我们有一个数据 64，表示为二进制为 0b0100 0000，什么意思呢？第几位为 1，表示几次幂。$2^6=64=0b01000000$。

我们可以使用这个技巧，轻松的实现本题。

基础知识

位操作。

数据范围

n 的最大值位 1e7，也就是说 int 可以表示。

AC 参考代码 1

//https://ac.nowcoder.com/acm/contest/8848/a
//优秀的拆分（power） 
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    long long n;
    cin>>n;
    if (1==n%2) {
        cout<<"-1\n";
        return 0;
    }
    long long t;
    for (int i=32; i>=0; i--) {
        t = 1ll<<i;
        if (n & t) {
            cout<<t<<' ';
        }
    }
    cout<<'\n';
 
    return 0;
}

AC 参考代码 2

可能不少人对位操作不是很了解，我们可以参考下面的代码。

//优秀的拆分（power） 
#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    long long n;
    cin>>n;
    if (1==n%2) {
        cout<<"-1\n";
        return 0;
    }
 
    //质因数分解
    long long t;
    while (n>0) {
        for (int i=32; i>=0; i--) {
            t=pow(2, i);
            if (t<=n) {
                cout<<t<<" ";
                n-=t;
                break;
            }
        }
 
    }
    cout<<"\n";
 
    return 0;
}

代码细节

由于 2^32 超过了 int 的范围，所以要使用 long long。

对拍

我们可以写一个简单的对拍来验证第二个代码正确性。

随机数产生

很简单，根据题目的数据范围，产生 1 ~ 1e7 的随机数据。文件名为 power.rand.cpp，生成的可执行文件为 power.rand.exe。

//Power 随机数产生
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int maxx=1e7;
    int minx=1;
 
    srand((unsigned int)time(NULL));
    int ans=rand()%(maxx-minx+1)+minx;
 
    cout<<ans<<"\n";
    return 0;
}

Win10 下批处理文件

就是比较两个不同算法的结果。文件名为 checkA.bat。

set var=1
echo off 
:loop
	echo 已运行%var%次
	set /a var+=1
	power.rand.exe>power.in
	a.power.1.exe<power.in>power.out
 	::自己认为的正解的exe
	a.power.exe<power.in>power.std.out
	::比较
	fc power.out power.std.out
	if not errorlevel 1 goto loop
pause
goto loop

对拍的过程

这样，我们通过 power.rand.exe 生成一个随机数。将这个随机数送到算法一程序，可以得到一个 power.std.out；将这个随机数送到算法一程序，可以得到一个 power.out，使用 fc 命令比较两个 out 文件差异性。就可以达到对拍目的。