-2

A[]サイズn<=100000との配列が与えられ、 の0<=A[i]<=2^64隣接する 2 つの要素ごとA[]に、バイナリ表現で 1 つの異なる数字が含まれます。4と のような要素A[i1],A[i2],A[i3] and A[i4]が配列に存在するかどうかを確認する必要があり1<=i1<i2<i3<i4<=nますA[i1] xor A[i2] xor A[i3] xor A[i4] = 0。

4

6 に答える 6

4

ヒント: これらのルールの下で、2 つの数値を XOR してゼロにすることはできますか? なぜですか、そうでないのですか？これらの 2 つの数値は、互いにどのように見えるでしょうか?

于 2012-07-02T22:27:56.193 に答える
4

隣接する 2 つの数値は 1 バイナリ ビットだけ異なるため、隣接する 2 つの数値を XOR した結果は非常に予測可能です。

x値は重要ではありませんが、そのx下/上の対応するビットと同じです。

        xxxxxxxxxxxxx1xxxxxxxxxxxx
xor:    xxxxxxxxxxxxx0xxxxxxxxxxxx
__________________________________
        00000000000001000000000000

これは、説明したセット内の任意の 2 つの隣接する数字に当てはまります。

同じビットが異なる隣接する数値の別のペアを見つけることができる場合、それらは同じ値に XOR アウトされます。00000000000001000000000000

そして最後に、これら 2 つの値を XOR すると、最終的な答えは間違いなくゼロになります。

したがって、必要なアルゴリズムは次のようになります。

  • 数値とその後継との間でどのビットが異なるかを識別します (ビット 0 ～ 63)
  • 手順 1 で識別された同じビットが異なる別の数値のペアを見つけます。

それがあなたの4つの価値です。

N > 64 の場合、ピジョンホールの原理により、このような解決策が存在しなければならないことに注意してください。
ならばN <= 64、この形の解もあれば別の形の解もあるかもしれませんが、ここでは書きませんでした。

一緒に 0 になる 4 つの数値を見つけることができる他の制約もあります
。しかし、これはおそらく解を探す最も簡単な方法です。
ただし、この方法で解決策を見つけられなくても、解決策がないことを保証するものではありません。

于 2012-07-03T20:26:39.943 に答える
2

ヒント: XOR の真理値表を見てください。

A | B | Output
- + - + - - - 
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0

では、10101 を XOR すると 0 になる 2 進数は?

これらは、探すべき数のタイプです。

編集: @abelenky の回答に対するコメントから、これらの数値間の関係が何であるかがわかったら、問題の他の部分を調べる必要があります。隣接する各要素は、2 進表現で正確に 1 つの異なる数字を持っているため、2 つの隣接する要素が探しているものである可能性について、それは何を意味するのでしょうか?

于 2012-07-02T22:30:29.073 に答える
1

これは、CodeChef で現在開催されているアルゴリズム コンテストからの質問です。質問のリンクはhttp://www.codechef.com/JULY12/problems/GRAYSCです。したがって、不当な手段の使用であり、質問は削除する必要があります。

于 2012-07-05T21:12:05.860 に答える
0

隣接する 2 つの数値の xor のすべての可能な値について、いくつかの注意深い観察を行います。合計で、いくつの異なる値が可能ですか? これが分かれば答えが出ます。

于 2012-07-03T02:03:43.713 に答える
0

ヒント:完全に立ち往生している場合は、O(n^4) ソリューションを試してください。

for i = 0 to N-3
  for j = i+1 to N-2
    for k = j+1 to N-1
      for l = k+1 to N
         if a[i] XOR a[j] XOR a[k] XOR a[l] is equal to 0 then
           print a[i], a[j], a[k], a[l]
于 2012-07-03T10:49:36.610 に答える