分类 CodeChef 下的文章

Nikitosh and xor

题目链接

CodeChef Nikitosh and xor

题解

中档题。找出两段连续区间的异或和使之最大。
首先借助trie树查询以某点作为右端点与左端点的异或最大值,然后枚举每一点作为中间的分界点即可。

代码

#include <iostream>
using namespace std;

const int MAXN = 500005;

int input[MAXN], maxl[MAXN], maxr[MAXN];
int nxt[MAXN * 40][2];
int nodenum, n, now, ans, temp;

void insert(int x) {
    for (int i = 30, pos = 1; i >= 0; i--) {
        temp = (x & (1 << i)) > 0 ? 1 : 0;
        if (nxt[pos][temp] == 0) {
            nxt[pos][temp] = ++nodenum;
            nxt[nodenum][0] = nxt[nodenum][1] = 0;
        }
        pos = nxt[pos][temp];
    }
}

int query(int x) {
    int ans = 0;
    for (int i = 30, pos = 1; i >= 0; i--) {
        temp = (x & (1 << i)) > 0 ? 1 : 0;
        if (nxt[pos][1^temp] > 0) {
            ans |= (1 << i);
            temp ^= 1;
        }
        pos = nxt[pos][temp];
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> input[i];

    nodenum = 1;
    nxt[1][0] = nxt[1][1] = 0;
    insert(0);
    now = 0;
    maxl[0] = 0;
    for (int i = 1; i <= n; i++) {
        now ^= input[i];
        maxl[i] = query(now);
        if (maxl[i - 1] > maxl[i]) maxl[i] = maxl[i - 1];
        insert(now);
    }

    nodenum = 1;
    nxt[1][0] = nxt[1][1] = 0;
    insert(0);
    now = 0;
    maxr[n + 1] = 0;
    for (int i = n; i >= 1; i--) {
        now ^= input[i];
        maxr[i] = query(now);
        if (maxr[i + 1] > maxr[i]) maxr[i] = maxr[i + 1];
        insert(now);
    }

    for (int i = 2; i <= n; i++) {
        temp = maxl[i - 1] + maxr[i];
        if (temp > ans) ans = temp;
    }

    cout << ans;
    return 0;
}