2 条题解

  • 5
    @ 2024-8-11 8:33:14

    显然,对于正整数 p,qp,q,设 p,qp,q 在二进制表示下的位数分别为 x,yx,y,若 p≤qp\le q,则:

    • p≤p⊕qp \le p \oplus q,当且仅当 x≠yx \ne y,因为若 x=yx=y 则 pp 和 qq 异或后最高位会抵消,p⊕qp \oplus q 一定小于 pp 和 qq;
    • p⊕q≤qp \oplus q \le q,当且仅当 qq 在二进制表示下的第 xx 位为 11,因为若 qq 在二进制表示下的第 xx 位为 00,则 qq 与 pp 异或后一定会变大。

    要注意,对于任意非负整数 mm,都满足 0≤0⊕m≤m0 \le 0 \oplus m \le m,所以需要特判 00。

    在特判 00 后,我们可以把剩下的元素从小到大排序,开一个桶,把枚举过的数在二进制表示下的位数记录在桶里,动态地根据上面的讨论计算即可。

    时间复杂度 O(nlog⁡n+nlog⁡V)\mathcal O(n \log n+n \log V),其中 VV 为值域。

    信息

    ID
    27
    时间
    1000ms
    内存
    512MiB
    难度
    3
    标签
    递交数
    797
    已通过
    243
    上传者