将数组拆分为两个子序列，使得子序列的xor值之间的差值最小为

Question

我正在做一些关于按位运算的问题。所以我在想什么是找出xor值（涵盖整个数组的两个非重叠的子序列）之间的差异的最快方法。我无法找到解决此问题的快速方法。我认为这个问题解决起来会很有趣。我希望任何人都能想出一个快速解决方案并分享这篇文章。

我为我的英语不好:)

Answer 1

我假设我们必须给定的数组分成两个子阵列道歉这样一个子数组的元素的XOR和其他子数组的元素之间的区别是最小。

int main() { 
int n,*a; 
cin>>n; 
a = new int[n]; 
for(int i=0;i<n;i++) { 
    cin>>a[i]; 
} 
int total_xor=0; 
for(int i=0;i<n;i++) { 
    total_xor ^=a[i]; 
} 
int min_diff = 1000000009,part_xor=0,split_index=0,i; 
for(i=0;i<n;i++) { 
    total_xor^=a[i]; 
    part_xor^=a[i]; 
    if((abs(total_xor-part_xor))<min_diff) { 
     min_diff=abs(total_xor-part_xor); 
     split_index = i; 
    } 
    //cout<<abs(total_xor-part_xor)<<"\n"; 
} 
cout<<"First subarray 1 to "<<split_index+1<<"\n"; 
cout<<"Second subarray "<<(split_index+2)<<" to "<<n<<"\n"; 
} 

Answer 2

如果子序列的意思是一个连续的子阵列，那么Sanjeevkumar的答案就足够了。然而，如果你的意思是你需要将数组拆分成两个数组，而且条件不是它们都是由连续的范围组成的，那么我想到的最简单的解决方案就是使用动态规划。

您DP阵列需要有2个维度：

1. i：你想目前的指数选择是否要添加到第一或第二序列。

2. firstXOR：异或对于已经加入到第一序列的所有元素。

您DP关系如下：

DP[i][firstXOR]=分钟（DP[i+1][firstXOR^a[i]]，DP[i+1][firstXOR]）

1. DP[i+1][firstXOR^a[i]]表示将当前元件的选择到第一个子。

2. DP[i+1][firstXOR]表示将当前元素添加到第二子序列的选择。

当到达基本状态（i == end of the array）你应该返回firstXOR和secondXOR之间的差值（secondXOR是添加到第二子序列的元素的XOR）。

请注意，可以容易地获得secondXOR通过执行以下操作（您已经添加到所述第二子序列元件的XOR）：

secondXOR = （的阵列中的所有元件XOR）^（firstXOR）