3

数値 N と整数の配列 (すべて 2^15 未満の数値) が与えられます。(A は配列のサイズ 100000)
N の最大 XOR 値と配列から整数を見つけます。

Q はクエリ数 (50000) で、start、stop は配列内の範囲です。

入力:
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 倍高速なアルゴリズムが必要です。並べ替えにはコストがかかりすぎます。二分木、ビット操作も試しました。

2 倍から 3 倍の改善はいかがでしょうか。それは最適化によって可能ですか?

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の場合、最良の答えはこの位置に1つあります。したがって、最初に、目的のビットを持つ番号があるかどうかを確認します。はいの場合、このビットの数字のみを取得する必要があります。いいえの場合は、逆になります。次に、他のビットを同じ方法で処理します。たとえば、a [0] == 1、a [1] == 0の場合、最初にゼロで始まる数字があるかどうかを確認します。はいの場合、01で始まる数字があるかどうかを確認します。ゼロで始まる数字がない場合は、 11で始まる番号があるかどうかを確認します。

したがって、次のクエリに答えるには、高速なアルゴリズムが必要です。ビットで始まる数値はありますか...範囲の開始、停止にありますか?

1つの可能性:数値の2進表現からトライを構成します。各ノードに、このプレフィックスが配列内にあるすべての位置を格納します(そしてそれらをソートします)。次に、このクエリに答えるのは、このトライを簡単に説明することができます。開始、停止範囲に適切なプレフィックスがあるかどうかを確認するには、ノードに格納されている配列に対してバイナリ検索を実行する必要があります。

これは、より高速な複雑さ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

前処理にO(AlogM)の時間とスペースを必要とするソリューションを思いついたところです。そして、各クエリのO(log 2 M)時間。Mは整数の範囲であり、この問題では2^15です。

1番目..N番目の
番号、(ツリーグループ1)
1番目..(A / 2)番目の番号、(A / 2)番目..A番目の番号、(ツリーグループ2)
1番目..(A / 4)番目の番号、(A / 4)番目..(A / 2)番目の番号、(A / 2)番目..(3A / 4)番目、(3A / 3)番目..Ath、(ツリーグループ3)
..。 ....、(Tree Group 4)
.......、
.......、(Tree Group logA)は、範囲内のすべての数値の2進表現の2
トライを作成します。200万本の木があります。ただし、集約されたすべてのツリーには、O(AlogM)要素しか含まれません。x個の数値を含むツリーの場合、ツリーには最大でlogM*xノードが存在する可能性があります。また、各番号は、各ツリーグループの1つのツリーにのみ含まれます。

クエリごとに、範囲をいくつかの範囲(2logA以下)に分割して、ツリーに処理することができます。また、ツリーごとに、O(logM)時間で最大XOR値を見つけることができます(後で説明します)。それはO(logA * logM)時間です。

ツリーで最大値を見つける方法は?現在の桁がNで0の場合は、単に1の子を優先します。それ以外の場合は、0の子を優先します。優先する子が存在する場合はその子に進み、そうでない場合は他の子に進みます。

于 2012-05-24T09:56:04.080 に答える
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は2番目のビットです…ルートからリーフに移動し、n_i = 0(iは深さ)の場合に選択する必要がある場合現在のノードの)次に右に移動し、そうでない場合は左に移動します。あなたが葉の上にいるとき、それは最大の葉です。

1つのクエリに対する元の回答:

アルゴリズムは最適です。配列内のすべての数値をチェックする必要があります。

プログラミングのトリックを使用して少し高速なプログラムを作成する方法があるかもしれませんが、アルゴリズムとのリンクはありません。

于 2012-05-24T09:11:25.870 に答える
1

アルゴリズムは線形時間(O(start-stop)、またはO(N)全範囲)で実行されます。入力配列にすでに特別な順序があると想定できない場合は、おそらくそれをより速く取得することはできません。

ループ内のオーバーヘッドを最適化することしかできませんが、それによって速度が大幅に向上することはありません。


編集:

同じリストを複数回検索する必要があるようですが、開始インデックスと終了インデックスが異なります。

つまり、要素の順序が変わるため、配列を事前に並べ替えることも問題外です。意味がstartありません。end

1つのクエリにすでにスキャンされた範囲が完全に含まれている場合は、同じ範囲を2回処理しないようにすることができます。

または、配列を反復処理しながら、すべてのクエリを同時に検討しようとしている可能性があります。

于 2012-05-24T09:13:30.887 に答える
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 に答える