C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++の特定の範囲に偶数回出現した数値のXOR


この問題では、n個の要素の配列が与えられ、配列の開始点から終了点までの範囲のクエリがいくつかあります。私たちのタスクは、範囲内に何度も出現した要素のXORを2つ見つけることです。

問題を理解するために例を見てみましょう

入力

array = {1, 2, 3, 1, 1, 2, 2, 3}
querries = 2
R = 4
L = 2, R = 5
L = 2, R = 7

出力

0
1
0

この問題の解決策は非常に簡単です。各クエリによって、指定された範囲内の配列のすべての要素のXORの合計が見つかります。このために、プレフィックス合計xorを使用します。

ソリューションの実装を示すプログラム

#include <bits/stdc++.h>
using namespace std;
struct que {
   int L, R, idx;
};
bool cmp(que a, que b){
   if (a.R != b.R)
      return a.R < b.R;
   else
      return a.L < b.L;
}
int findXORSum(int BIT[], int index){
   int xorSum = 0;
   index = index + 1;
   while (index > 0){
      xorSum ^= BIT[index];
      index -= index & (-index);
   }
   return xorSum;
}
void updateBIT(int BIT[], int N, int index, int val){
   index = index + 1;
   while (index <= N){
      BIT[index] ^= val;
      index += index & (-index);
   }
}
int* createBitTree(int arr[], int N){
   int* BIT = new int[N + 1];
   for (int i = 1; i <= N; i++)
      BIT[i] = 0;
   return BIT;
}
void findXORSolution(int arr[], int N, que queries[], int Q, int BIT[]){
   int* prefixXOR = new int[N + 1];
   map<int, int> XORval;
   for (int i = 0; i < N; i++) {
      if (!XORval[arr[i]])
         XORval[arr[i]] = i;
      if (i == 0)
         prefixXOR[i] = arr[i];
      else
         prefixXOR[i] = prefixXOR[i - 1] ^ arr[i];
   }
   int lastOcc[1000001];
   memset(lastOcc, -1, sizeof(lastOcc));
   sort(queries, queries + Q, cmp);
   int res[Q];
   int j = 0;
   for (int i = 0; i < Q; i++){
      while (j <= queries[i].R){
         if (lastOcc[XORval[arr[j]]] != -1)
            updateBIT(BIT, N, lastOcc[XORval[arr[j]]], arr[j]);
         updateBIT(BIT, N, j, arr[j]);
         lastOcc[XORval[arr[j]]] = j;
         j++;
      }
      int allXOR = prefixXOR[queries[i].R] ^ prefixXOR[queries[i].L - 1];
      int distinctXOR = findXORSum(BIT, queries[i].R) ^ findXORSum(BIT, queries[i].L - 1);
      res[queries[i].idx] = allXOR ^ distinctXOR;
   }
   for (int i = 0; i < Q; i++)
      cout << res[i] << endl;
}
int main() {
   int arr[] = {1, 2, 1, 1, 2, 2, 3, 1, 3};
   int N = sizeof(arr) / sizeof(arr[0]);
   int* BIT = createBitTree(arr, N);
   que queries[4];
   queries[0].L = 1;
   queries[0].R = 4; queries[0].idx = 0;
   queries[1].L = 2;
   queries[1].R = 7, queries[1].idx = 1;
   queries[2].L = 0;
   queries[2].R = 3, queries[2].idx = 2;
   queries[3].L = 3;
   queries[3].R = 6, queries[3].idx = 3;
   int Q = sizeof(queries) / sizeof(queries[0]);
   cout<<"Xor sum for all queries is \n";
   findXORSolution(arr, N, queries, Q, BIT);
   return 0;
}

出力

Xor sum for all queries is
3
2
0
2

  1. C++で指定されたN個の範囲のすべての要素をカバーする範囲を検索します

    LとRを含むn個の範囲があるとします。他のすべてのn– 1範囲をカバーする範囲に基づいて、0のインデックスをチェックまたは見つける必要があります。そのような範囲がない場合は、-1を表示します。たとえば、L =[2、4、3、1]、R =[4、6、7、9]の場合、出力は3になります。つまり、3番目のインデックス(1〜9)の範囲がすべてをカバーすることを意味します。他のn–1の範囲の要素。 すべてのLポイントとRポイントが異なるため、最小のLポイントと最大のRポイントの範囲を見つけます。両方が同じ範囲である場合は、他のすべての範囲がその範囲内にあることを示します。それ以外の場合は不可能です。 例

  2. 番号がC++のミステリー番号であるかどうかを確認します

    ここでは、番号がミステリー番号であるかどうかを確認する方法を説明します。ミステリーナンバーは、2つの数字の合計で表すことができる数字であり、数字は互いに逆になります。より良いアイデアを得るためにコードを見てみましょう。すべてのペアをチェックして、決定を見つける必要があります。 例 #include <bits/stdc++.h> using namespace std; int revNum(int str) {    string s = to_string(str);    reverse(s.begin(), s.end()); &nb