1 条题解

  • 0
    @ 2022-8-8 16:54:14

    按照数位一位一位贪心,因为整体加了一个x,所以我们考虑对于所有的(ai+x)与b的按位异或。

    还是考虑按位贪心,不过这里每个数都加上了一个数,所以会复杂一些 假设我们已经处理到b二进制下的第i位,假设是1(0同理), 那么我们只需要查找是否存在aj+x使得其二进制第i位数字是0,我们已经处理了前i-1位了,设当前结果是ans,那么我们需要查找的数的大小就是区间[ans-x,ans+(1<<i)-1-x] 那么现在我们就是要在a[l]...a[r]中找出是否存在于[ans-x,ans+(1<<i)-1-x]的数字,可以使用区间小于x的数个数来做 总时间复杂度O( nlogn + mlognlogv ),可以除polyloglogn

    • 1

    信息

    ID
    2342
    时间
    3000ms
    内存
    252MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者