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