Codeforces Round 882 (Div. 2) C

发布时间 2023-07-07 13:45:31作者: wuyoudexian

被c题的题意骗了

C. Vampiric Powers, anyone?

题意

转换一下原题的题意,就是求一个连续子区间的最大异或和。

思路

异或有一个性质,即\(a\oplus b\oplus b=a\),原题题意也是利用这个性质转化的。现在可以利用这个性质求出子区间的异或和。

先求出原区间的所有异或和前缀,再让前缀相互异或,即可求出子区间的异或和。

代码

void solve() {
    int n;
    cin >> n;

    int cur = 0, res = 0;
    set<int> pre;
    for(int i = 0; i < n; i++) {
        cin >> cur;
        res ^= cur;
        pre.insert(res);
    }
    pre.insert(0);

    int ans = 0;
    for(int i : pre) {
        for(int j : pre) {
            ans = max(ans, i ^ j);
        }
    }

    cout << ans << "\n";
}