题集

· · 个人记录

U622716

主包也是被坑惨了，这题写了3个多小时. . .

首先第一眼看过去，这不就是一道 找规律 数学题吗。嗯，规律确实找到了，只不过不对而已(☆-ｖ-). . .但凡样例稍微大一点我都不用调那么久。

最开始想到的是：求出 \le n 的第一个 2 ^ k。实际上这个算法没有任何正确性可言. . .

一个反例： n = 8 时的拆分方案，我们想到的就是：

\{8\} \{4,\ 4\} \{2,\ 2,\ 4\} \{2,\ 2,\ 2,\ 2\} \{1,\ 1,\ 2,\ 2,\ 2\} \{1,\ 1,\ 1,\ 1,\ 2,\ 2\} \{1,\ 1,\ 1,\ 1,\ 1,\ 1,\ 2\} \{1,\ 1,\ 1,\ 1,\ 1,\ 1,\ 1,\ 1\}

实际上还有两种：

\{1,\ 1,\ 2,\ 4\}$ 和 $\{1,\ 1,\ 1,\ 1,\ 4\}

就这么轻轻松松的推翻了我们的猜想。然后问题就来了，知道哪儿错了以后怎么改呢？

完全背包

首先我们来转化一下问题：用无限多个面额 2^t（t=0..k） 的“硬币”凑出总额 2^k，统计不同的非负解（每种面额可用0、1、2... 次）。这就是经典的完全背包。

为什么可以转化成这样呢？n为2的幂次时，这样转化当然成立。为什么 n 不为 2 的幂次时也成立呢？举个例子：

$n = 12 →$ 最小单位：$4$根长度为$3$的木棍 我们发现这没有什么区别，也就是说$n = 4$和$n = 12$其实是等价的。 --- ### 这是纯dp的写法 $$ 总长是i的方案个数dp_i = \begin{cases} 包含长度1的木棍:去掉一根长度为1的木棍，对应 dp_{i - 1}\\ 不包含长度1的木棍:仅使用长度为2，4，8，. . . 2^ t的木棍凑出 i\\ \ \ \ \ → 仅使用长度为1，2，4， ... 2 ^ {t - 1}的木棍凑出 \frac{i}{2} \end{cases} $$ ## [CF1811E](https://codeforces.com/problemset/problem/1811/E) 这题看上去挺麻烦的，需要算 $k$ 以内有多少数码不包含 $4$ 的数，实际上有一个小技巧可以处理：进制映射。 不包含 $4$ 的数其实就是由 $\{0, 1, 2, 3, 5, 6, 7, 8, 9\}$ 组成的数，我们将其看成九进制，映射为 $\{0, 1, 2, 3, 4, 5, 6, 7, 8\}$，这样每个数转化成十进制后就是不含 $4$ 的数了。 > 举个例子：$(14365)_{映射} =(15376)_9= (5 + 1) \times 9^0 + (6 + 1) \times 9^1 + 3 \times 9^2 + (4 + 1) \times 9^3 + 1 \times 9^4 = (10332)_{10}

确实没有包含 4，所以序列中第 k 个数就是 k 映射后的结果。

练习题：

样例：

Input

6
1
2
3
4
5
6

Output

A
B
C
E
F
AA