【思维构造】Vampiric Powers, anyone?—CF1847C

本文主要是介绍【思维构造】Vampiric Powers, anyone?—CF1847C，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Vampiric Powers, anyone?—CF1847C
参考文章

这个思路完美利用了 $a_i$ 很小的这个特点，通过异或前缀和完美地将循环数组的长度变为循环元素的范围，极快地提升了代码的效率。

思路

手推一遍“召唤”的过程可以发现，能召唤出的最大力量即 $a$ 数组中连续子串中元素异或和的最大值。用代码表示就是：

	int res = a[1];for (int l = 1; l <= n; l ++) {int now = 0;for (int r = l; r <= n; r ++) {now ^= a[r];res = max(res, now);}}

当然这样是一定会超时的，我们需要考虑一个更高效的方法。
观察题目可以发现，$a_i<256$ 这个条件还没有用到，那么可以发现一个新的思路：
求 $a$ 的前缀异或和数组，数组中任意两个元素异或的最大值即为所求。虽然这样也是两层循环，但每层循环的循环次数最多不过 $256$ 次，可以通过本题。

$Code$

#include <bits/stdc++.h>
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 1e5 + 10;int n;
int a[N];void solve() {cin >> n;map<int, int> mp;mp[0] = 1;for (int i = 1; i <= n; i ++) {cin >> a[i];a[i] ^= a[i - 1];mp[a[i]] = 1;}int res = -1;for (auto i : mp) {if (i.second) {for (auto j : mp) {if (j.second) {res = max(res, i.first ^ j.first);}}}}cout << "         ";cout << res << "\n";
}signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T = 1;cin >> T; cin.get();while (T --) solve();return 0;
}

这篇关于【思维构造】Vampiric Powers, anyone?—CF1847C的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---