这道题的题目描述就是给你一个 a 数组,然后再给你个 m ,让你找一个最大的 k ,使 k 异或整个 a 数组的和小于等于 m。
笨蛋的方法就是从大到小枚举 k,一旦异或 a 数组的和小于等于 m,了,就输出 k,但这样的时效使绝对不行的。
所以我们来想一想异或的实质,两个数,A,B, A 异或 B 的值就是将 A 和 B 都转为二进制数,然后向右按位对其,将小的数左边塞 0 使 2 个数的二进制位数相等,然后从左往右扫,一旦这一位上的二进制不同,假设位数为 y ,异或的值 x 就要加上 2y。
好了既然是求 k 异或整个 a 数组的和,那其实就是将整个 a 数组转成二进制数,然后存在一个数组中,将 k 也转换成二进制数进行比对不就得了?但其实想到这里就不需要枚举 k,只需要通过模拟,当异或 y 这一位的时候,如果 k 的二进制数在这一位为0的时候,异或的值就加上 1<<(n−这一位上1的个数),为 1 时 异或的值就加上 1<<这一位上1的个数。只要为1时符合这一位就取 1 ,因为要 k 越大越好嘛,不符合再取 0 ,而如果2个都不符合时就回朔嘛,所以要用DFS来模拟这个过程。
但是!在处理异或和的过程中,1<<(n−这一位上1的个数) 或 1<<这一位上1的个数 的值可能会爆出long long,为了不开高精我们可以与处理一下,在代码中标出了。