题解 P2320 【[HNOI2006]鬼谷子的钱袋】

· · 题解

本蒟蒻怒写一发题解

收到本校神犇@Herself32 的邀请，过来做这道题

结果被题怒切

不扯了

首先考虑一个弱化版的题目，只输出最小袋子数 稍微找一下规律就知道是总钱数的二进制位数

好 那么数据范围就出来了

本题我们还是手动模拟一下

1 -> 1
2 -> 1, 1
3 -> 1, 2
4 -> 1, 1, 2
5 -> 1, 1, 3
6 -> 1, 2, 3
7 -> 1, 2, 4
8 -> 1, 1, 2, 4

我们再把7和8的过程单独拿出来看

7 -> 3, 4 -> 1, 2, 4
8 -> 4, 4 -> 2, 2, 4 -> 1, 1, 2, 4

我们能发现什么？ 对于一个数 n，我们可以把它用 \lceil \frac{n}{2} \rceil + \lfloor \frac{n}{2} \rfloor 表示，同时依照题意， \lfloor \frac{n}{2} \rfloor 也是可以用 \lceil \frac{\lfloor \frac{n}{2} \rfloor}{2} \rceil + \lfloor \frac{\lfloor \frac{n}{2} \rfloor}{2} \rfloor 进行表示的，这么一直递归下去，直到两个多项式中至少有一个为 1 ，此时反向（即从小到大）输出答案即可

代码实现

#include <iostream>
#include <cstdio>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

const int MAXANS = 30 + 10;

int m;

int ans[MAXANS], cnt = 0;

void Search(int now) {
    if (now == 0) return;
    int mid = now / 2, mid2 = now / 2 + (now % 2);
    ans[++cnt] = mid2;
    Search(mid);
}

int main() {
    scanf("%d", &m);
    Search(m);
    printf("%d\n", cnt);
    for (int i = cnt; i >= 1; --i) printf("%d ", ans[i]);
    printf("\n");
    return 0;
}