更新题目 拆成 4 的幂：最少拆几个
题目 visa-split-into-powers-of-four · 修改（rev 4） · · 2026-10-27 00:33
body
@@ -1,7 +1,7 @@ ## 题目 -给一个整数数组。对每个整数 x，求最小的正整数 k，使 x 能写成 k 个数之和：其中**一个**是 1、2 或 3，其余 k − 1 个都是 2 的偶数次方、但不含 2^0（也就是 4、16、64……，可以重复用）。做不到返回 -1。题面没写整个数组的返回格式，下面按逐个求、返回等长数组写。 +给一个整数数组。对每个整数 x，求最小的正整数 k，使 x 能写成 k 个数之和：其中**一个**是 1、2 或 3，其余 $k - 1$ 个都是 2 的偶数次方、但不含 $2^0$（也就是 4、16、64……，可以重复用）。做不到返回 -1。题面没写整个数组的返回格式，下面按逐个求、返回等长数组写。 -例子：x = 30 时，30 = 2 + 16 + 4 + 4 + 4，共 5 项，答案是 5。x = 8 时做不到，答案是 -1（原因见下一节）。 +例子：x = 30 时，$30 = 2 + 16 + 4 + 4 + 4$，共 5 项，答案是 5。x = 8 时做不到，答案是 -1（原因见下一节）。 ## 面经里怎么考的 @@ -11,10 +11,10 @@ ## 思路 -2 的偶数次方写成 2^(2j)，也就是 4^j。题目去掉了 j = 0（即 2^0 = 1），所以能用的数正好是 4 的正整数次幂：4、16、64……下面把那一项 1、2 或 3 叫做「小项」，记作 r，把 x 减去小项以后剩下的部分记作 m = x − r。 +2 的偶数次方写成 $2^{2j}$，也就是 $4^j$。题目去掉了 j = 0（即 $2^0 = 1$），所以能用的数正好是 4 的正整数次幂：4、16、64……下面把那一项 1、2 或 3 叫做「小项」，记作 r，把 x 减去小项以后剩下的部分记作 $m = x - r$。 -小项只有一种取法。4、16、64 都是 4 的倍数，它们的和 m 也一定是 4 的倍数（m = 0 也算，这时 k − 1 = 0）。m = x − r 是 4 的倍数，等价于 r 和 x 除以 4 的余数相同。r 只能在 1、2、3 里选，所以 r 就是 `x % 4`。由此得到两种无解的情况： +小项只有一种取法。4、16、64 都是 4 的倍数，它们的和 m 也一定是 4 的倍数（m = 0 也算，这时 $k - 1 = 0$）。$m = x - r$ 是 4 的倍数，等价于 r 和 x 除以 4 的余数相同。r 只能在 1、2、3 里选，所以 r 就是 `x % 4`。由此得到两种无解的情况： - x 是 4 的倍数时，余数是 0，1、2、3 里没有合法的小项，返回 -1。比如 x = 8，减 1、2、3 分别剩 7、6、5，都不是 4 的倍数。 -- x ≤ 0 时，k 项都是正数，和不可能 ≤ 0，返回 -1。 +- $x \le 0$ 时，k 项都是正数，和不可能 $\le 0$，返回 -1。 x 是 1、2、3 时，m = 0，只用小项一项，答案是 1。 @@ -22,12 +22,12 @@ > [!say] Every allowed power is a power of four, so they all sum to a multiple of four. That forces the small term to be x mod 4, and if x itself is a multiple of four there is no valid small term, so the answer is minus one. -剩下的 m 用最少几个 4 的幂凑出来，答案是 m 的 4 进制各位数字之和。把 m 写成 4 进制，第 j 位的数字 d_j 表示用 d_j 个 4^j，这样凑出来的个数就是各位数字之和。它是最少的，推导分两步： +剩下的 m 用最少几个 4 的幂凑出来，答案是 m 的 4 进制各位数字之和。把 m 写成 4 进制，第 j 位的数字 $d_j$ 表示用 $d_j$ 个 $4^j$，这样凑出来的个数就是各位数字之和。它是最少的，推导分两步： -1. 任取一种凑法，如果某个 4^j 用了 4 个或更多，把其中 4 个换成 1 个 4^(j+1)，和不变、个数少 3。反复换下去个数一直变少，所以最少的凑法里每个 4^j 最多用 3 个。 -2. 每个 4^j 最多用 3 个的凑法，就是 m 的 4 进制写法，而一个数的 4 进制写法只有一种。所以最少的凑法只能是 4 进制写法。 +1. 任取一种凑法，如果某个 $4^j$ 用了 4 个或更多，把其中 4 个换成 1 个 $4^{j+1}$，和不变、个数少 3。反复换下去个数一直变少，所以最少的凑法里每个 $4^j$ 最多用 3 个。 +2. 每个 $4^j$ 最多用 3 个的凑法，就是 m 的 4 进制写法，而一个数的 4 进制写法只有一种。所以最少的凑法只能是 4 进制写法。 -m 是 4 的倍数，4 进制最低位（4^0 那一位）一定是 0，正好对上「不能用 1」这条限制。 +m 是 4 的倍数，4 进制最低位（$4^0$ 那一位）一定是 0，正好对上「不能用 1」这条限制。 -例子：x = 30，30 % 4 = 2，小项取 2，m = 28。28 = 1 × 16 + 3 × 4 + 0 × 1，4 进制是 130，数字和 1 + 3 + 0 = 4，答案 1 + 4 = 5，和题目一节的拆法一致。 +例子：x = 30，$30 \bmod 4 = 2$，小项取 2，m = 28。$28 = 1 \times 16 + 3 \times 4 + 0 \times 1$，4 进制是 130，数字和 $1 + 3 + 0 = 4$，答案 $1 + 4 = 5$，和题目一节的拆法一致。 > [!say] For the remaining part, the fewest powers of four that add up to m is the digit sum of m in base four. If any power were used four or more times, I could merge four copies into the next power and save three terms, so an optimal answer uses each power at most three times, which is exactly the base-four representation. @@ -65,10 +65,10 @@ Python 的整数不会溢出，x 很大时也不用特殊处理。 -> [!optional] 用 Java 或 C++ 写时，x 超过 2^31 − 1 就要用 64 位整数（`long` / `long long`）。 +> [!optional] 用 Java 或 C++ 写时，x 超过 $2^{31} - 1$ 就要用 64 位整数（`long` / `long long`）。 2026-10-26 在云端用 python3 跑了三组，代码和上面逐字一致： -- **和暴力对拍**：暴力解是完全背包（硬币取 4、16、64……求凑出 x − r 的最少硬币数，再枚举 r = 1、2、3），不复用 4 进制的推导。x 取 -5 到 2000 共 2006 个值，`min_parts` 和暴力全部一致。 -- **一种错误写法对照**：把「4 进制各位数字之和」写成「4 进制非零位的个数」，也就是把 2 × 4 当成一项。错误写法只换掉 `base4_digit_sum`，`min_parts` 其余部分不变： +- **和暴力对拍**：暴力解是完全背包（硬币取 4、16、64……求凑出 $x - r$ 的最少硬币数，再枚举 r = 1、2、3），不复用 4 进制的推导。x 取 -5 到 2000 共 2006 个值，`min_parts` 和暴力全部一致。 +- **一种错误写法对照**：把「4 进制各位数字之和」写成「4 进制非零位的个数」，也就是把 $2 \times 4$ 当成一项。错误写法只换掉 `base4_digit_sum`，`min_parts` 其余部分不变： ```python @@ -90,14 +90,14 @@ | 暴力 | 1 | -1 | 2 | 3 | 4 | 5 | 6 | 7 | -1 | -1 | - x = 9 时 m = 8，4 进制是 20，非零位只有 1 个，错误写法得 2。可是 8 本身不是 4 的幂，要写成 4 + 4，正确答案是 1 + 2 = 3。在 -5 到 2000 上，错误写法有 1404 个值和暴力不一致。 + x = 9 时 m = 8，4 进制是 20，非零位只有 1 个，错误写法得 2。可是 8 本身不是 4 的幂，要写成 $4 + 4$，正确答案是 $1 + 2 = 3$。在 -5 到 2000 上，错误写法有 1404 个值和暴力不一致。 - **大输入**：`min_parts(10**18 + 1)` 返回 38，单次调用约 2 微秒（重复调用 10 万次取平均）。`min_parts(4**31 - 1)` 返回 91（m 的 4 进制是 30 个 3 后面跟一个 0）。 ## 复杂度 -每个数 x 的循环次数等于 m 的 4 进制位数，约 log₄ x，时间 O(log x)，额外空间 O(1)。整个数组是 O(n log X)，X 是数组里的最大值。 +每个数 x 的循环次数等于 m 的 4 进制位数，约 $\log_4 x$，时间 $O(\log x)$，额外空间 $O(1)$。整个数组是 $O(n \log X)$，X 是数组里的最大值。 ## 易错点 -- 「2 的偶数次方」不含 2^0 = 1，所以能用的只有 4 的幂。看清这一句，题就变成了上面的取余加数位和（见思路一节第一段）。 +- 「2 的偶数次方」不含 $2^0 = 1$，所以能用的只有 4 的幂。看清这一句，题就变成了上面的取余加数位和（见思路一节第一段）。 - 答案按 4 进制各位数字之和算。只数非零位会少算，因为一位上的 2 或 3 代表要用 2 个或 3 个同样的幂（见代码一节的对照表）。 -- 题面没说 4 的幂能不能重复用，上面按可以重复写。如果不能重复，m 的 4 进制某一位大于 1 就无解，答案改成「有某位 ≥ 2 时返回 -1，否则 1 加非零位个数」（2026-10-26 和穷举所有子集的暴力在 -3 到 1499 上对拍过，全部一致）。 +- 题面没说 4 的幂能不能重复用，上面按可以重复写。如果不能重复，m 的 4 进制某一位大于 1 就无解，答案改成「有某位 $\ge 2$ 时返回 -1，否则 1 加非零位个数」（2026-10-26 和穷举所有子集的暴力在 -3 到 1499 上对拍过，全部一致）。
meta
@@ -1,5 +1,5 @@ { "depth_guide": "2026-10-23", - "rewritten_by": "cloud:20261026-1620", + "rewritten_by": "cloud:20261026-2312", "rewritten_at": "2026-10-27" }