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

我们这样考虑，一个十进制整数必然可以化为二进制，也就是写成若干个 $2$ 的非负整数次幂之和，如果这个数是奇数，那么它二进制的末尾必然是 $1$ ，也就是它的拆分中必然有一项 $2^0$ ，故无解。
如果是偶数则它的二进制末位是 $0$ ，也就是必定能写成若干个 $2$ 的正整数次幂之和，因此必然有解。我们可以先记录 $10^7$ 以内的 $2$ 的正整数次幂，然后从大到小，将 $n$ 试着减去这些 $2$ 的正整数次幂。（感性地理解一下，这样做是正确的。）然后输出答案即可。

我采用了递归的写法，相对比较直观。

CPP

#include<bits/stdc++.h>
using namespace std;
int n;
int p[40]={0,2,4,8,16,32,64,128,256,512,1024,2048,\
4096,8192,16384,32768,65536,131072,262144,524288,\
1048576,2097152,4194304,8388608,16777216,33554432,\
67108864,134217728,268435456,536870912,1073741824};
void f(int x){
	if(x==1||x==0) return;
	for(int i=30;i>=1;i--){
		if(x>=p[i]){
			cout<<p[i]<<" ";
			f(x-p[i]);
			break;
		}
	}
}
int main()
{
	cin>>n;
	if(n%2==1){
		cout<<-1<<endl;
		return 0;
	}
	else{
		f(n);
	}
}

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

文章操作

相关推荐

评论

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