1 条题解

  • 0
    @ 2026-11-15 13:51:53

    题目分析

    30 分

    暴力即可。

    60 分

    对每一位滚一个前缀和就好,查询就对每一位查能否为 11。

    正解

    二进制问题就按位做,考虑 l∼rl\sim r 中是否存在一个数满足二进制第 ii 位为 11。

    考虑贪心的构造尽量一个大的满足 ≤r\le r 的数,那么肯定是找到 rr 中第 j(j>i)j(j>i) 位为 11 的位置,把这一位变成 00,更高的位不动,第 jj 位后面的全部变成 11,那么这是一个合法的 ≤r\le r 且最大的数,检查其是否 ≥l\ge l 即可。

    时间复杂度 O(Tlog⁡2r)\mathcal{O}(T\log_2 r)。

    • 1

    信息

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