Codeforces Round 882 (Div. 2) - C. Vampiric Powers, anyone?

Solost

2023 年 07 月 08 日

131 次浏览

暂无评论

1414字数

题目题解

## 题目链接

[链接](https://codeforces.com/contest/1847/problem/C)

## 题目大意

一个长度为n的数组，你可以选择序列中的一个位置，从i到m全部元素异或，然后把异或后的值放在最后，问你，能生成最大的的元素大小是多少？

## 题解

我们发现，s[i]为一个序列的前缀异或和，s[i, j] = s[i] ^ s[j - 1]，a ^ b ^ b = a, a ^ b ^ c  ^ b ^ c = a;

用这个性质，我们可以选择起点，而且可以通过添加末尾元素，可以选择中点，那么问题就转换为求一个序列的最大连续异或子序列，由于这个题目的a[i]比较小，最大为256,所以可以通过每次存下来异或的结果，然后和当前的异或和相异或，这样就相当于确定当时的中点，找起点，最终达到可以求出最大连续异或子序列的效果，但是这个方法不是通用的，如果a[i]的值大一点就用不了了。

## 代码

```cpp
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    set<int> v;
    int ans = 0, s = 0;
    for(int i = 0; i < n; i++){
        s ^= a[i];
        ans = max(ans, s);
        for(auto x : v){
            ans = max(ans, s ^ x);
        }
        v.insert(s);
    }
    cout << ans << endl;
}
int main()
{
    IOS;
    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 07 月 08 日