神奇的解法(分治)
这道题是亲爱的dhk推荐给我写一写的水题,我TM还写出来了。。。
题意简化:把\(n\)分成若干份,满足用这若干份能表达出\([1,n]\)内任意的整数且没有重复的大于1的,求最小划分的份数。
感觉自己简化得很鸡肋
看上去就想打暴力,但是又好像挺难打的。因为要算出每个数能否被表达,我想了一下好像挺复杂的。
那我们来递推找规律吧。
手动枚举到10的时候我就发现了一个奇怪的现象:取\(\lceil \frac{n}{2} \rceil\)作为第一个最大分的,对答案很友好啊!
想了一下,很有道理,并且发现我可以对剩下的部分也这么进行!
所以每次都能减小一半,这是\(\log n\)级别的复杂度,绝对能够通过那么大的数据范围了。
事后翻了题解,原来这是一种分治的思想啊!
代码:
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#define ll long long
ll n, m;
std::vector<int> vec;
int main()
{
scanf("%lld", &m);
n = floor(log2(m)) + 1;
for(int i = 1; i <= n; i++)
{
ll temp = ceil(m / 2.0);
vec.push_back(temp);
m -= temp;
}
std::sort(vec.begin(), vec.end());
printf("%lld\n", n);
for(std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it)
{
printf("%lld ", *it);
}
return 0;
}