เพื่อแก้ปัญหาที่เราได้รับอาร์เรย์และแบบสอบถามบางอย่าง ตอนนี้ในแต่ละแบบสอบถาม เราได้รับช่วง ตอนนี้เราต้องหาตัวเลขที่ทำให้ผลรวมของ xor กับ x ขยายใหญ่สุด ตัวอย่างเช่น
Input : A = {20, 11, 18, 2, 13}
Three queries as (L, R) pairs
1 3
3 5
2 4
Output : 2147483629
2147483645
2147483645 ในปัญหานี้ เราจะนับคำนำหน้าของ 1 ที่มีอยู่ในตัวเลขในแต่ละตำแหน่งในขณะนี้ เนื่องจากเราได้คำนวณจำนวนล่วงหน้าแล้ว ดังนั้น ในการหาจำนวนในช่วงที่กำหนดจาก L ถึง R เราจำเป็นต้อง ลบ สันนิษฐาน ถึง R โดย สันนิษฐาน ถึง L.
แนวทางในการหาแนวทางแก้ไข
ในแนวทางนี้ เนื่องจากเราต้องหาผลรวมสูงสุด เราจึงต้องทำให้บิตส่วนใหญ่ของ xor เท่ากับ 1 ดังนั้นเราจึงตรวจสอบว่าบิตใดมีค่ามากกว่า 0 หรือไม่ ดังนั้นเราจึงรีเซ็ตบิตของ x นั้น เนื่องจากตอนนี้ตัวเลขส่วนใหญ่มีบิตนั้นเท่ากับ 1 ดังนั้นเมื่อเราจับคู่ส่วนใหญ่ 1 กับ 0 ดังนั้นในที่สุดเราก็ได้เสียงส่วนใหญ่ บิตนั้นเท่ากับ 1 ดังนั้นเราจึงเพิ่มคำตอบให้สูงสุด
ตัวอย่าง
รหัส C++ สำหรับแนวทางข้างต้น
#include <bits/stdc++.h>
using namespace std;
#define MAX 2147483647 // 2^31 - 1
int prefix[100001][32]; // the prefix array
void prefix_bit(int A[], int n){ // taking prefix count of 1's present
for (int j = 0; j < 32; j++) // we keep 0th count as 0 and our prefix array starts with index 1
prefix[0][j] = 0;
for (int i = 1; i <= n; i++){ // making our prefix array
int a = A[i - 1]; // ith element
for (int j = 0; j < 32; j++){ // as our number is less than 2^32 so we traverse for bit 0 to 31
int x = 1 << j; // traversing in bits
if (a & x) // if this bit is one so we make the prefix count as prevcount + 1
prefix[i][j] = 1 + prefix[i - 1][j];
else
prefix[i][j] = prefix[i - 1][j];
}
}
}
int maximum_num(int l, int r){
int numberofbits = r - l + 1; // the number of elements in the range hence the number of bits
int X = MAX; // we take the max value such that all of it's bits are one
// Iterating over each bit
for (int i = 0; i < 31; i++){
int x = prefix[r][i] - prefix[l - 1][i]; // calculating the number of set bits in the given range
if (x >= numberofbits - x){ // is number of 1's is more than number of 0's
int currentbit = 1 << i; // we set the current bit to prefix for toggling that bit in x
X = X ^ currentbit; // we make toggle that bit from 1 to 0
}
}
return X; // answer
}
int main(){
int n = 5, q = 3; // number of element in our array and number of queries present
int A[] = { 210, 11, 48, 22, 133 }; // elements in our array
int L[] = { 1, 4, 2 }, R[] = { 3, 14, 4 }; // given queries
prefix_bit(A, n); // creating prefix bit array
for (int i = 0; i < q; i++)
cout << maximum_num(L[i], R[i]) << "\n";
return 0;
} ผลลัพธ์
2147483629 2147483647 2147483629
คำอธิบายของโค้ดด้านบน
ในแนวทางนี้ ก่อนอื่นเราจะคำนวณจำนวนคำนำหน้าของ 1 ปัจจุบันสำหรับแต่ละบิต ตอนนี้เมื่อเราได้จำนวนนี้แล้ว เราก็ได้แก้ปัญหาที่ใหญ่ที่สุดของเราซึ่งก็คือการข้ามผ่านข้อความค้นหา ณ ตอนนี้ เราจะไม่ข้ามผ่านแต่ละช่วง ดังนั้นเราสามารถคำนวณมันผ่านอาร์เรย์คำนำหน้าของเราได้แล้ว ตรรกะหลักของเราคือ เราคำนวณจำนวนการรีเซ็ตและการตั้งค่าบิตในช่วงเมื่อเราพบตำแหน่งที่หมายเลขบิตที่ตั้งไว้มากกว่าจำนวนบิตรีเซ็ต ดังนั้นเราจึงรีเซ็ตบิตนั้นใน x ของเราทันทีเมื่อเราเริ่มต้น x ด้วย 2^31 - 1 ดังนั้นบิตทั้งหมดจะถูกตั้งค่า และเราพบคำตอบของเราโดยสลับบิตใน x
บทสรุป
ในบทช่วยสอนนี้ เราแก้ปัญหาเพื่อค้นหาจำนวนที่ผลรวมของ XOR กับช่วงอาร์เรย์ที่กำหนดเป็นค่าสูงสุด นอกจากนี้เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ (ปกติ) ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์
