3

给定一个数字 N 和一个整数数组（均不小于 2^15）。（A 是数组 100000 的大小）从数组
中找到 N 的最大 XOR 值和一个整数。

Q 是查询数（50000），开始，停止是数组中的范围。

输入：
AQ
a1 a2 a3 ...
N 开始停止

输出：
N 的最大 XOR 值和指定范围内的数组中的整数。

例如：输入
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）

输出：
13
13

代码：

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

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

2x - 3x 的改进怎么样？是否可以通过优化。

4

5 回答 5

5

可以开发更快的算法。

让我们调用 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。

算法的主要思想如下：如果 a[0] == 1，则最佳可能答案将该位归零。如果 a[0] == 0，则最佳可能答案在此位置有一个。因此，首先您检查是否有一些带有所需位的数字。如果是，您应该只使用该位的数字。如果不是，你认为它是相反的。然后您以相同的方式处理其他位。例如如果a[0] == 1, a[1] == 0，首先检查是否有以0开头的数字，如果有则检查是否有以01开头的数字。如果没有以0开头的数字，则你检查是否有一个以 11 开头的数字。等等......

因此，您需要一个快速算法来回答以下查询：是否有一个以位开头的数字......在范围开始，停止？

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

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

这是代码，它没有经过太多测试，可能包含错误：

#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);
  }
}
于 2012-05-24T09:54:40.277 回答
1

如果您有多个具有相同范围的查询，则可以使用该范围内的数字构建一棵树，如下所示：

使用深度为 15 的二叉树，其中数字位于叶子处，数字对应于通向它的路径（左侧为 0，右侧为 1）。

例如对于 0 1 4 7：

    /   \
  /      /\
/ \     /  \
0 1    4    7

那么您的查询是 N=n_1 n_2 n_3 … n_15 其中 n_1 是 N 的第一位，n_2 是第二位 … 从根到叶，当你必须做出选择时，如果 n_i = 0（其中 i 是深度当前节点）然后向右，否则向左。当您在叶子上时，它是最大叶子。

一个查询的原始答案：

您的算法是最优的，您需要检查数组中的所有数字。

可能有一种方法可以通过使用编程技巧来获得稍快的程序，但它与算法没有联系。

于 2012-05-24T09:11:25.870 回答
1

您的算法以线性时间运行（O(start-stop)或O(N)在整个范围内）。如果你不能假设输入数组已经有一个特殊的排序，你可能无法更快地得到它。

您只能尝试优化循环内的开销，但这肯定不会显着提高速度。

编辑：

看起来您必须多次搜索同一个列表，但使用不同的开始和结束索引。

这意味着对数组进行预排序也是不可能的，因为这会改变元素的顺序。start并且end毫无意义。

如果一个查询完全包含已扫描的范围，您可以尝试做的是避免两次处理相同的范围。

或者在遍历数组时尝试同时考虑所有查询。

于 2012-05-24T09:13:30.887 回答
1

我只是想出了一个需要 O(AlogM) 时间和空间进行预处理的解决方案。每个查询的O(log 2 M) 时间。M 是整数的范围，在这个问题中是 2^15。

对于第
1..N 号，(Tree Group 1)
1st..(A/2)th 号，(A/2)th..Ath 号，(Tree Group 2)
1st..(A/4)th 号, (A/4)th..(A/2)th 数字, (A/2)th..(3A/4)th, (3A/3)th..Ath, (Tree Group 3)
... ...., (Tree Group 4)
...,
..., (Tree Group logA)
构造范围内所有数字的二进制表示的二进制trie。将有 2M 棵树。但是所有聚合的树都不会超过 O(AlogM) 元素。对于包含 x 个数字的树，树中最多可以有 logM*x 个节点。并且每个数字只包含在每个树组中的一棵树中。

对于每个查询，您可以将范围分成几个范围（不超过 2logA），我们已将它们处理成一棵树。并且对于每棵树，我们可以在 O(logM) 时间内找到最大的 XOR 值（稍后会解释）。那是 O(logA*logM) 时间。

如何在树中找到最大值？如果当前数字在 N 中为 0，则更喜欢第 1 个孩子，否则更喜欢第 0 个孩子。如果存在首选孩子，则继续该孩子，否则继续另一个孩子。

于 2012-05-24T09:56:04.080 回答
0

是的，或者你可以只计算它，而不是浪费时间思考如何做得更好。

int maxXor(int l, int r) {
    int highest_xor = 0;
    int base = l;
    int tbase = l;
    int val = 0;
    int variance = 0;
    do
    {
        while(tbase + variance <= r)
        {
            val = base ^ tbase + variance;
            if(val > highest_xor)
            {
                highest_xor = val;
            }
            variance += 1;
        }
        base +=1;
        variance = 0;
    }while(base <= r);
    return highest_xor;
}
于 2015-01-08T16:53:58.720 回答