資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究尋找可進行異或運算的和的最大可能值的 C++ 程式
假設我們有一個包含 N 個元素的陣列 A 和另一個值 K。對於在 0 至 K 範圍內的整數 X，設 f(X) = (X 異或 A[1]) + (X 異或 A[2]) + ... + (X 異或 A[N])。我們必須找到 f 的最大可能值。
因此，如果輸入類似於 K = 7；A = [1, 6, 3]，那麼輸出將為 14，因為 f(4) = (4 異或 1) + (4 異或 6) + (4 異或 3) = 5 + 2 + 7 = 14。
步驟
要解決這個問題，我們將遵循以下步驟 −
n := size of A for initialize i := 45, when i >= 0, update (decrease i by 1), do: p := 2^i m := 0 for initialize j := 0, when j < n, update (increase j by 1), do: if A[j] AND p is non-zero, then: (increase m by 1) if o + p <= k, then: if m < n - m, then: m := n - m o := o + p d := d + p * m return d
示例
讓我們看看以下實現以獲得更好的理解 −
#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
更新日期：03-Mar-2022
108 次瀏覽
廣告