最大XOR值比仅使用XOR更快 [英] Maximum XOR value faster than just using XOR

问题描述

给出一个数字N和一个整数数组（所有不小于2 ^ 15的数）。 （A为数组100000的大小）

从数组中查找N和一个整数的最大XOR值。

Given a number N and an array of integers (all nos less than 2^15). (A is size of array 100000)
Find Maximum XOR value of N and a integer from the array.

Q不存在查询（50000） ），开始，结束是数组中的范围。

Q is no of queries (50000) and start, stop is the range in the array.

输入：

AQ

a1 a2 a3 ...

N开始停止

Input:
A Q
a1 a2 a3 ...
N start stop

输出：

N的最大XOR值和指定范围内的整数。

Output:
Maximum XOR value of N and an integer in the array with the range specified.

例如：输入

15 2（2是没有查询数）

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

10 6 10（查询1）

10 6 10（查询2）

Eg: Input
15 2 (2 is no of queries)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
10 6 10 (Query 1)
10 6 10 (Query 2)

输出：

13

13



代码：

Output:
13
13

Code:

for(int i=start-1;i<stop;i++){
int t =no[i]^a;
if(maxxor<t)
     maxxor=t;
}
cout << maxxor <<endl;

我需要一种比这快10-100倍的算法。排序过于昂贵。我也尝试过二叉树，位操作。

I need a algorithm 10-100 times faster than this. Sorting is too expensive. I have also tried binary trees,bit manipulation.

2到3倍的改进怎么样？通过优化可以做到这一点。

推荐答案

可以开发更快的算法。

让我们调用N的位：a [0]，a [1]，...，a [15]，例如，如果N = 13 = 0000000 00001101（二进制），则a [0 ] = a [1] = ... a [11] = 0，a [12] = 1，a [13] = 1，a [14] = 0，a [15] = 1。

Let's call bits of N: a[0], a[1], ..., a[15], e.g if N = 13 = 0000000 00001101 (in binary), then a[0] = a[1] = ... a[11] = 0, a[12] = 1, a[13] = 1, a[14] = 0, a[15] = 1.

算法的主要思想如下：如果a [0] == 1，则最佳答案是将该位清零。如果a [0] == 0，则最佳答案在此位置为1。
因此，首先，您检查是否有一些带有所需位的数字。如果是，则此位只能取数字。如果否，则取相反的值。
然后您以相同的方式处理其他位。例如。如果a [0] == 1，a [1] == 0，则首先检查是否存在以0开头的数字，如果是，则检查是否存在以01开头的数字。如果没有以0开头的数字，则您检查是否有一个以11开头的数字。依此类推...

The main idea of algorithm is following: If a[0] == 1, then best possible answer has this bit zeroed. If a[0] == 0, then best possible answer has one at this position. So at first you check if you have some number with the desired bit. If yes, you should take only number with this bit. If no, you take it's inverse. Then you process other bits in same manner. E.g. if a[0] == 1, a[1] == 0, you first check whether there is number beginning with zero, if yes then you check whether there is a number beginning with 01. If nothing begins with zero, then you check whether there is a number beggining with 11. And so on...

因此，您需要一种快速的算法来回答以下查询：是否有一个以bits开头的数字。 ..在范围的开始，结束之间？

So you need a fast algorithm to answer following query: Is there a number beginning with bits ... in range start, stop?

一种可能性：从数字的二进制表示构造trie。在每个节点中，存储此前缀在数组中的所有位置（并对其进行排序）。然后，可以通过简单地遍历此查询来回答此查询。要检查起始，终止范围中是否有合适的前缀，您应该对节点中存储的数组进行二进制搜索。

One possibility: Constuct trie from binary representation of numbers. In each node store all positions where this prefix is in array (and sort them). Then answering to this query can be a simple walk through this trie. To check whether there is suitable prefix in start, stop range you should do a binary search over stored array in a node.

这可能导致算法的复杂度为O（lg ^ 2 N）更快。

This could lead to algorithm with complexity O(lg^2 N) which is faster.

这是代码，未经大量测试，可能包含错误：

Here is the code, it hasn't been tested much, may contain bugs:

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

class TrieNode {
 public:
  TrieNode* next[2];
  vector<int> positions;

  TrieNode() {
    next[0] = next[1] = NULL;
  }

  bool HasNumberInRange(int start, int stop) {
    vector<int>::iterator it = lower_bound(
        positions.begin(), positions.end(), start);
    if (it == positions.end()) return false;
    return *it < stop;
  }
};

void AddNumberToTrie(int number, int index, TrieNode* base) {
  TrieNode* cur = base;
  // Go through all binary digits from most significant
  for (int i = 14; i >= 0; i--) {
    int digit = 0;
    if ((number & (1 << i)) != 0) digit = 1;
    cur->positions.push_back(index);
    if (cur->next[digit] == NULL) {
      cur->next[digit] = new TrieNode;
    }
    cur = cur->next[digit];
  }
  cur->positions.push_back(index);
}

int FindBestNumber(int a, int start, int stop, TrieNode* base) {
  int best_num = 0;
  TrieNode* cur = base;
  for (int i = 14; i >= 0; i--) {
    int digit = 1;
    if ((a & (1 << i)) != 0) digit = 0;
    if (cur->next[digit] == NULL || 
        !cur->next[digit]->HasNumberInRange(start, stop))
      digit = 1 - digit;
    best_num *= 2;
    best_num += digit;
    cur = cur->next[digit];
  }
  return best_num;
}


int main() {
  int n; scanf("%d", &n);
  int q; scanf("%d", &q);
  TrieNode base;
  for (int i = 0; i < n; i++) {
    int x; scanf("%d", &x);
    AddNumberToTrie(x, i, &base);
  }

  for (int i = 0; i < q; i++) {
    int a, start, stop;
    // Finds biggest i, such that start <= i < stop and XOR with a is as big as possible
    // Base index is 0
    scanf("%d %d %d", &a, &start, &stop);
    printf("%d\n", FindBestNumber(a, start, stop, &base)^a);
  }
}

这篇关于最大XOR值比仅使用XOR更快的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！