1 条题解

  • 0
    @ 2026-11-15 21:43:58

    题目分析

    • 观察发现可以发现小于 s 的数是不符合要求的,所以这部分我们可以直接省掉。
    • 对于大于 s+9∗18s+9∗18 的数一定是符合要求的,这相当于每一位都是 9 的情况,这一部分我们可以直接加上。
    • 对于中间的部分,我们直接枚举判断就能通过此题。

    B 最小异或和 (xor) 题解

    设 x>1x > 1,并设 cc 表示其二进制表示中 11 的位数。显然,当 n≤cn \leq c 时,最优的做法是简单地在数组的元素间分配不同的 22 的幂,从而得到可达到的最小和 xx。然而,如果 n>cn > c,那么显然在额外的 n−cn - c 个元素中仅添加 11 是有利的。在 n−cn - c 为奇数的情况下,我们还需要向 cc 个具有 22 的幂的块中的一个再添加一个 11,以便所有 11 的异或等于 x mod 2x \bmod 2。

    如果 x=1x = 1,那么对于奇数 nn,我们显然可以简单地将所有数组元素都填 11。否则,我们需要使用对 [2,3][2, 3],其异或为 11,得到最小分数 n+3n + 3。

    在剩下的 x=0x = 0 的情况下,情况几乎与前面的情况相同,唯一的例外是对于 n=1n = 1 不存在有效的示例(这是唯一答案为 −1-1 的情况)。所以对于偶数 nn,答案就是 nn,否则是 n+3n + 3(因为我们使用三元组 1⊕2⊕3=01 \oplus 2 \oplus 3 = 0)。

    每个测试的时间复杂度是 O(1)O(1)​。

    • 1

    信息

    ID
    207
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者