题意:给你一个数 mm (1m10000000001\leq m\leq 1000000000),把 mm 分成 ansans 个数,且每两个大于 11 的数都不相同,求出当 ansans 最小时,输出 ansans 和从小到大的 ansans 个数。

很明显,看到这么大的数据范围,也只有二分这种 O(logN) 的能够做到了。

我们从特殊到一般分析,先随便一个数假设 m=20m=20

那么 112011\sim 20 也就比 1101\sim 10 多了 1010,所以只要我们拆一个 1010 出来,我们就可以用 1101\sim 10 来表示 112011\sim 20

同理,我们再针对 1101\sim 10 来分析,拆一个 55 出来就只用考虑怎么凑 151\sim 5

如此循环下去,那么最后拆成的数就为:1,1,3,5,101,1,3,5,10

所以我们可以用这种二分的方法来处理 mm,每次拆出一个 m2\lceil \frac{m}{2}\rceil 的数,然后再用剩下的继续拆,直到 mm 被拆完。

没想到居然是到省选题。。。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
long long m;
long long ans[5010101],cnt;
int main()
{
	scanf("%lld",&m);
	while(m)
	{
		ans[++cnt]=m-m/2;
		m/=2;
	}
	printf("%lld\n",cnt);
	for(int i=cnt;i>=1;i--)
		printf("%lld ",ans[i]);
	return 0;
}