欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P2320 [HNOI2006]鬼谷子的钱袋

程序员文章站 2022-05-08 22:36:39
...

神奇的解法(分治)

这道题是亲爱的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;
}