1 条题解

  • 0
    @ 2026-11-15 12:10:14

    题解:拆分数字(split)

    容易发现,对于所有 nn 都一定能表示(指用 30,31,…3^0,3^1,\dots),不过不一定是恰好 kk 个数。那我们可以求出最少和最多用多少个数表示,再看看能否累加或减少到 kk 个。

    首先最多一定是 n=30×nn = 3^0 \times n,即使用 nn 个 11;最少则是 nn 在三进制下的非零数位个数,不妨设其为 mm。

    • 如果 m>km > k,一定无解;
    • m=km = k 有解;
    • m<km < k 则需要尝试拆分调整。

    观察到我们可以进行这样的拆分:3i=3i−1+3i−1+3i−13^i = 3^{i-1} + 3^{i-1} + 3^{i-1},即进行一次拆分可以使原本的个数 mm 增加 22。而 n≥kn \ge k,所有 303^0 一直拆分下去,一定有一个时刻个数 ≥k\ge k。因此只需要判断 m,km,k 的奇偶性是否相同,即 (k−m)(k-m) 是否为偶数即可。

    • 1

    信息

    ID
    37
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者