Нахождение максимального значения всех возможных подмножеств XOR, если подмножества могут генерироваться бесконечно
Я хотел решить эту проблему: C. Vampiric Powers, кто-нибудь?, Codeforces
Короче говоря, существует последовательность a, и мы можем бесконечное количество раз находить исключающее ИЛИ любого подмножества и добавлять исключающее ИЛИ этого подмножества в конец a. Наш ответ — максимальное значение, присутствующее в a (включая добавленные).
Моя идея следующая:
- Найдите максимальное значение в оригинале
a - Найдите префикс XOR в оригинале
a - Отсортируйте найденные префиксы в порядке убывания. Устанавливаем
ans = 0, перебираем отсортированный массив префиксов, и если в какой-то моментans XOR prefix[i] > ans, мы устанавливаемans = ans XOR prefix[i].
Почему этот шаг работает? Представьте, что a имеет 3 элемента [x, y, z]. Мы можем добавить x XOR y XOR z в конец a, теперь он равен [x, y, z, (x XOR y XOR z)]. Если мы вычислим еще один XOR для всего обновленного a, в конце будет 0. На этом этапе мы можем выбрать индексы (и вычислить суммы префиксов к ним), которые только увеличивают наш ответ. Итак, мы сортируем префиксный массив XOR в порядке убывания и проверяем, улучшит ли это наш результат.
Сортируем по убыванию, потому что если начать с возрастания, то меньшие элементы, которые также входят (их биты) в старшие элементы, будут просто вычтены из ответа операцией XOR.
Это код:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
int maxi = 0;
vector<int> a(n);
vector<int> xors(n);
for (int i = 0; i < n; ++i)
{
cin >> a[i];
maxi = max(maxi, a[i]);
if (i > 0)
xors[i] = a[i] ^ xors[i - 1];
else
xors[i] = a[i];
}
sort(xors.begin(), xors.end(), greater<int>());
int cur = xors[0];
for (int i = 1; i < n; ++i)
{
if ((cur ^ xors[i]) > cur)
{
cur ^= xors[i];
}
}
cout << max(maxi, cur) << '\n';
}
}
Проблема в том, что эта идея (или код?) не проходит некоторые тестовые случаи (она дает слишком большой ответ, но я не знаю входных данных). Я действительно не понимаю, почему.
Кроме того, жадный алгоритм не работает для XOR. Если массив xors содержит [6, 5, 4], ваш алгоритм вернет 6, пока максимальное значение равно 6^5^4 = 7. Ваш алгоритм не подойдет 6^5, поскольку промежуточный результат 3 меньше 6, хотя добавление 4 позже будет улучшением.
Ох, после перерыва я понимаю, насколько глупа моя идея. Но все еще не вижу правильного решения.
Если моя догадка верна, вам нужно найти непрерывную подпоследовательность с наибольшим XOR. Другими словами, max(max(xors[i]), max(xors[i] ^ xors[j])), поскольку XOR непрерывной подпоследовательности можно представить как XOR двух префиксов. Это можно сделать наивно за квадратичное время (если есть более быстрый алгоритм, я не знаю его сверху).
@IgorTandetnik Это можно решить быстрее с помощью попытки.
Ответы 1
Поскольку каждый элемент массива находится в диапазоне [0, 255], эту проблему можно решить с помощью динамического программирования. Обратите внимание, что порядок применения операций не имеет значения.
Значение добавленного элемента в конце можно использовать в качестве состояния, и для каждого состояния мы можем сохранить значение самого большого элемента, видимого на данный момент.
#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
// no need to untie cout; it's not tied by default
int t, n;
for (std::cin >> t; std::cin >> n;) {
std::vector<int> a(n);
for (int& v : a) std::cin >> v;
std::vector<int> dp(1 << 8, -1);
dp[0] = 0;
int suffXOR = 0;
for (int v : std::views::reverse(a)) {
suffXOR ^= v;
int best = -1;
for (int m = 0; m < 1 << 8; ++m)
if (~dp[m])
best = std::max(best, suffXOR ^ m);
dp[suffXOR] = std::max(dp[suffXOR], best);
}
std::cout << std::ranges::max(dp) << '\n';
}
}
Обратите внимание, что это также можно свести к проблеме поиска наибольшего XOR любого подмассива, которую можно решить в O(N log MAX_VALUE) с помощью дерева.
Обратите внимание, что на каждом шаге вы не можете выполнять XOR для произвольной подпоследовательности, а только для некоторого суффикса текущей последовательности. Моя (недоказанная) догадка состоит в том, что достижимы только смежные подпоследовательности; например начиная с
[X, Y, Z]невозможно получитьX^Z