โปรแกรม C++ หาค่าสูงสุดของผลรวม XOR กับอาร์เรย์ในช่วง 0 ถึง K

คำอธิบายปัญหา

สมมติว่าเรามีอาร์เรย์ A N องค์ประกอบ และค่า K สำหรับจำนวนเต็ม X ในช่วง 0 ถึง K ให้ f(X) = (X xor A[1]) + (X xor A[2]) + ... + (X xor A[N]) ต้องการหาค่าสูงสุดของ f

ตัวอย่าง: K = 7; A = [1, 6, 3] ผลลัพธ์คือ 14 เพราะ f(4) = (4 XOR 1) + (4 XOR 6) + (4 XOR 3) = 5 + 2 + 7 = 14

ขั้นตอนการแก้ปัญหา

n := ขนาดของ A
สำหรับ i := 45 ถึง 0 ลดทีละ 1:
    p := 2^i
    m := 0
    สำหรับ j := 0 ถึง n-1:
        ถ้า A[j] AND p ไม่เป็นศูนย์: เพิ่ม m ขึ้น 1
    ถ้า o + p <= k:
        ถ้า m < n - m:
            m := n - m
            o := o + p
    d := d + p * m
คืนค่า d

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

long solve(int k, vector<int> A){
    long n = A.size(), d = 0, m, p, o = 0;
    for (long i = 45; i >= 0; i--){
        p = pow(2, i);
        m = 0;
        for (int j = 0; j < n; j++){
            if (A[j] & p) m++;
        }
        if (o + p <= k){
            if (m < n - m){
                m = n - m;
                o += p;
            }
        }
        d += p * m;
    }
    return d;
}

int main(){
    int K = 7;
    vector<int> A = { 1, 6, 3 };
    cout << solve(K, A) << endl;
}

อินพุต

7, { 1, 6, 3 }

เอาต์พุต

14