【C++题解】[CSP-J2020]优秀的拆分-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C++题解】[CSP-J2020]优秀的拆分。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

$P a r t$ $1$ 读题

题目描述

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

例如： $1 = 1$ ， $10 = 1 + 2 + 3 + 4$ 等。对于正整数 $n$ 的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下， $n$ 被分解为了若干个不同的 $2$ 的正整数次幂。

注意，一个数 $n$ 能被表示成 $2$ 的正整数次幂，当且仅当 $n$ 能通过正整数个 $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

4 2

输入样例2

输出样例2

-1

输入样例3

输出样例3

512 256 128 64 32 4 2

样例说明

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

数据范围与提示

对于 $20\%$ 的数据： $n \leq 10$

对于另外 $20\%$ 的数据：保证 $n$ 为奇数。

对于另外 $20\%$ 的数据：保证 $n$ 为 $2$ 的正整数次幂。

对于 $80\%$ 的数据： $n \leq 1024$

对于 $100\%$ 的数据： $1≤n≤1\times10^7$

$P a r t$ $2$ 思路

看到这个题，可能瞬间就蒙了，作为 $CSP - J$ 第二轮的第一题，难度却不小。

又看了一遍题，我们知道本题要想判断是否为“优秀的拆分”（也就是说拆成 $2$ 的幂的形式），我们就想到了一个知识点——十进制转二进制（对于此方法，博主不进行讲述，可自行询问度娘），也就是如下代码：

for(int i=n;i!=0;i/=2){//也可以用while循环，只不过得在最后加上i/=2
	j++;//记录位数
	a[j]=i%2;
}

请大家再回忆一个小学学过的知识点：奇数+奇数=偶数，偶数+偶数=偶数，偶数+奇数=奇数，这也就说明任何两数相加要想是奇数，都必须是“偶数+奇数”的形式，所以奇数的拆分都会存在 $2^0$ （也就是 $1$ ），而想要做到“优秀的拆分”，幂得是 $2$ 的正整数次的，所以若 $n$ 是奇数，直接输出 $- 1$ 结束就可以了。

接下来就是判断偶数了，我们就只需要运用二进制转十进制的知识，若该位为 $0$ ，就不需要乘 $2$ 的对应幂了，也就是说，若数组得这一位是 $0$ ，就跳过不进行计算，但是我们也要注意一个坑，最大值会到 $10^7$ ，我们需要开 $l o n g$ $l o n g$ 才能避免。也就是如下代码：

k=j-1;//这里要减去1，要不然会多算一次
for(int i=j;i>=1;i--){//倒取余数，所以需要从大到小枚举
	long long s=pow(2,k);//十年信奥一场空，不开long long见祖宗
	if(a[i]!=0)cout<<s<<" ";//判断
	k--;//记得每次-1
}

然后我们再加上定义、输入和判断奇数就可以啦！

小tip：大家可以先根据思路，写一下代码哦！

$P a r t$ $3$ 代码

#include <bits/stdc++.h>
using namespace std;
int n,a[30],j,k;//j记录位数 k后期代替j进行计算
int main(){
	cin>>n;
	if(n%2==1)cout<<-1;
	else{
		for(int i=n;i!=0;i/=2){//也可以用while循环，只不过得在最后加上i/=2
			j++;
			a[j]=i%2;
		}
		k=j-1;//这里要减去1，要不然会多算一次
		for(int i=j;i>=1;i--){//倒取余数，所以需要从大到小枚举
			long long s=pow(2,k);//十年信奥一场空，不开long long见祖宗
			if(a[i]!=0)cout<<s<<" ";//判断
			k--;//记得每次-1
		}
	}
    return 0;
}