Разбейте массив на две подпоследовательности так, чтобы разница между значением xor подпоследовательности была минимальной

Question

Я делаю некоторые вопросы о побитовых операциях. Поэтому я думаю, что это самый быстрый способ найти разницу между значением xor (две непересекающиеся подпоследовательности, которые охватывают весь массив). Я не мог найти быстрый способ решить эту проблему. Думаю, эту проблему будет довольно интересно решить. Я надеюсь, что любой может найти быстрое решение и поделиться этим постом.

Я прошу прощения за мой плохой английский:)

Answer 1

Я предполагаю, что мы должны разделить данный массив на два подмассива так, чтобы разница между xor элементов одного подмассива и x другого элемента была минимальной.

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

Если под подпоследовательностью вы подразумеваете непрерывный подмассив, то ответа Сандживкумара достаточно.

Однако, если вы имели в виду, что вам нужно разделить массив на два массива, при условии, что они не будут сформированы из непрерывных диапазонов, самое простое решение, которое приходит мне в голову, - это использовать динамическое программирование.

Ваш массив DP должен иметь 2 измерения:

1. i: Текущий индекс, который вы пытаетесь выбрать, добавить ли в первую или вторую подпоследовательность.

2. firstXOR: XOR для всех элементов, уже добавленных к первой подпоследовательности.

Ваше отношение 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)