最大异或和 - 滴滴校招

题目描述

异或运算是一种二进制位运算，运算规则是: 首先将两个数写成二进制形式，然后对于相同位上的两个数，如果相等，那么该位取0，否则取1。例如，十进制5和9的异或运算结果为12; 十进制7和6的异或运算结果为1。

小明有了一个含有 n 个数的序列 。他会对这个序列进行Q次询问，每次询问的形式为 l r m, 表示他要找到一个非负整数k，使得 且 最大。其中 ⊕ 表示异或运算。

对于每次询问，小明想要知道 的最大值。

输入描述

第一行输入两个正整数n,Q，分别表示序列中数的个数以及询问次数。 第二行输入n个非负整数 。 第三行输入Q个正整数 ，表示每次询问对应的左端点 第四行输入Q个正整数 ，表示每次询问对应的右端点。 第五行输入Q个非负整数 ，表示每次询问对应的k能选择的最大值,

输出描述

为了避免较大的输出量，你需要将所有询问得到的答案全部异或起来再输出，也就是仅输出一个非负整数。

示例1

输入：
5 3
2 0 3 6 5
2 1 3
4 3 5
3 1 0

输出：
6

说明：
三次询问对应的答案分别是:7，1，0

题解

分析

1. 题目类型

该题属于典型的前缀异或与贪心算法相结合的应用。我们需要处理序列区间的异或值，并在每次查询时通过贪心算法找到使结果最大的非负整数k。

2. 解题思路

该题的核心是如何快速计算某个区间内所有数的异或值，并结合这个异或值找到使得 x ⊕ k 最大的 k，其中 x 是这个区间的异或值，k 的值需满足 0 <= k <= m。

• 异或前缀和：为了快速计算区间的异或值，我们可以使用前缀异或和，类似前缀和的思路。假设 prefixXor[i] 表示数组前i个元素的异或和，那么区间 [l, r] 的异或值就可以通过 prefixXor[r] ⊕ prefixXor[l-1] 计算得到。

• 贪心策略求最大异或：对于给定的异或值 x 和范围 m，我们使用贪心的方式，逐位从高到低选择 k 的每一位，尝试使得 x ⊕ k 的值最大。

3. 代码描述

• 首先，通过计算前缀异或和，快速得到每次查询的区间 [l, r] 的异或值。
• 然后，针对每个查询，通过贪心算法计算在给定 m 范围内能使结果最大的 k。
• 最后，将每次查询的结果依次异或，并输出最终结果。

4. 时间复杂度

• 计算前缀异或和的时间复杂度为 O(n)，其中 n 为数组长度。
• 对于每次查询，计算区间异或值的时间复杂度为 O(1)，贪心求解最大 k 的时间复杂度为 O(1)，因此每次查询的总时间复杂度为 O(1)。
• 整体的时间复杂度为 O(n + Q)，其中 Q 为查询的次数。

5. 空间复杂度

• 前缀异或数组需要 O(n) 的空间。
• 其他变量所需的空间为常数级，因此总体空间复杂度为 O(n)。

总结

这道题结合了前缀异或和贪心算法的思想，重点在于如何通过贪心策略逐位确定最大的 k。使用前缀异或和可以快速计算区间的异或值，使得每次查询的时间复杂度极低，适合大规模数据的处理。

Java

此代码未进行大量数据的测试，仅供参考

import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {

    /**
     * 计算整数 x 的二进制位长度
     *
     * @param x
     * @return
     */
    public static int bitLength(int x) {
        // 对于 int 类型的整数的二进制位长度，使用 32 减去前导零的个数
        return 32 - Integer.numberOfLeadingZeros(x);
    }


    /**
     * 返回最大 x ^ k 的值（0 <= k <= m）
     *
     * 使用更优化的贪心策略，从最高位到最低位逐位考虑如何构造最优的k，使得  x ^ k 最大化。
     * 步骤： 在满足 k <= m 的前提下
     * 1. 从 m 的最高位开始，尝试确定 k 的每一位。
     * 2. 通过比较 x 和 m 在当前位上的值，来决定 k 的这一位取 1 还是 0。
     * 3. 如果 x 当前位是 0，那么可以尝试让 k 的这一位尽量取 1， 以便使 x ^ k 最大化； 如果当前位是 1，则让 k 当前位取 0 来保持较大值。
     *
     * @param x
     * @param m
     * @return
     */
    public static int findMaxXor(int x, int m) {
        int mBitLength = bitLength(m);
        int k = 0;
        boolean up = false;  // 表示 m 的二进制位能否从 0 -> 1 且满足 k <= m
        for (int i = mBitLength; i >= 0; i--) {
            int xBit = (x >> i) & 1;
            int mBit = (m >> i) & 1;

            if (xBit == 1 && mBit == 1) {
                up = true; // 此时 m 的第 i 位取 0 才能使得异或值最大
            } else if (xBit == 0 && (mBit == 1 || up)) {
                k |= (i << i);
            }
        }

//        System.out.println( x ^ k);
        return x ^ k;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        //读取n（序列长度）和Q(询问次数)
        int n = in.nextInt();
        int Q = in.nextInt();

        //读取序列中n个非负整数并计算前缀和
        int[] prefixSumXor = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prefixSumXor[i] = prefixSumXor[i - 1] ^ in.nextInt();
        }

        //读取Q个正整数作为左端点l
        int[] l = new int[Q];
        for (int i = 0; i < Q; i++) {
            l[i] = in.nextInt();
        }


        //读取Q个正整数作为左端点r
        int[] r = new int[Q];
        for (int i = 0; i < Q; i++) {
            r[i] = in.nextInt();
        }

        //读取Q个非负整数m
        int[] m = new int[Q];
        for (int i = 0; i < Q; i++) {
            m[i] = in.nextInt();
        }

        int result = 0;
        for (int i = 0; i < Q; i++) {
            // 根据异或前缀和快速计算数组区间的异或值
            int sumXor = prefixSumXor[r[i]] - prefixSumXor[l[i] - 1];
            result ^= findMaxXor(sumXor, m[i]);
        }

        System.out.println(result);
    }
}

/*
5 3
2 0 3 6 5
2 1 3
4 3 5
3 1 0

 */

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏