Cho mảng A kích thước N và K. Với X trong [0, K], f(X) = sum (X xor A[i]). Tìm max f(X).
Ví dụ
Với K=7, A=[1,6,3], đầu ra 14. f(4) = (4^1)+(4^6)+(4^3) = 5+2+7=14.
Giải thuật
Xét từng bit từ cao xuống thấp (45..0). Đếm m = số phần tử có bit đó = 1. Nếu đặt bit này của X = 1 (tức o+p <= K) và m < n-m (số 0 nhiều hơn số 1), thì đặt bit = 1 để tối đa hóa đóng góp. Cập nhật o và d.
Mã 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;
}
Đầu vào / Đầu ra
Input: 7, { 1, 6, 3 }
Output: 14