CP002818 题解

需要算法：递归，分治(应该是分治吧)

为什么有人说是二进制啊

思路：先把 $n$ 里面的 $2$ 的最大正整数次幂给算出来，减掉，继续递归

代码：

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int func(int s){//判断一个数里面含有最大的2的幂次方的数
	int ans=0;
	int t=1;
	for (int i=0;t<=s;++i){
		ans=t;
		t*=2;
	}
	return ans;
}
void m(vector<int> &ans,int s,bool &flag){//递归函数
	int t=func(s);
	if (t==1){//有1(递归边界1)
		flag=false;
		return;
	}
	if (t==0){//完美结束(递归边界2)
		return;
	}
	ans.push_back(t);
	m(ans,s-t,flag);//递归分治减掉那部分的值
}
int main(){//主函数
	bool flag=true;//能否得到正整数次幂
	int a;
	scanf("%d",&a);
	vector<int> ans;//答案数组
	m(ans,a,flag);//开始递归
	if (flag){
		for_each(ans.begin(),ans.end(),[](const int a){printf("%d ",a);});//遍历输出答案
	}else{
		printf("-1");//输出
	}
	return 0;
}

PS：我是从洛谷那里来的