题解：P7071 [CSP-J2020] 优秀的拆分

遇到这种与

2

的次幂有关的题目，一个显然的思路是将所有数转化为二进制表示，这样可以很直观地发现一些性质。

本题即为一个很好的例子。我们把输入的

n

转换为二进制表示，显然地，任意一个十进制数都可以用二进制表示。

对于一个二进制数，其十进制即为：对于每一个二进制上为

1

的数位，设其为从小到大第

i

位，令

m_i

为

2^{i+1}

，则

\sum m

即为其十进制表示下的数。

由于

2^0

不能参与构造，那么二进制表示下

n

的最低位也不能为

1

，显然地，对于所有奇数，无法构造。对于所有偶数，可以构造，且为唯一解。

那么我们模仿上述思考的方法，从小到大依次枚举

n

的二进制位，遇到

1

就加入数组中，最后倒序输出即可。

本题数据范围

1 \le n \le 10^7

，因此枚举

30

位即可。

CPP

#include<iostream>
#include<cstdio>
using namespace std;
const int N=36;
int a[N];
int res=0;
int main(){
	int n;
	cin>>n;
	if(n&1){
		cout<<"-1";
		return 0;
	}
	int p=0;
	while(n>=1){
		if(n&1){
			a[++res]=(1<<p);
		}
		n>>=1;
		++p;
	}
	for(int i=res;i>=1;i--){
		cout<<a[i]<<" ";
	}
	return 0;
}

题解：P7071 [CSP-J2020] 优秀的拆分

文章操作

相关推荐

评论

题解：P7071 [CSP-J2020] 优秀的拆分