【BZOJ4260】Codechef REBXOR（前i个数的最大区间异或值---01字典树+dp）题目：解题思路：ac代码：

43 阅读 0 评论 29 点赞

我是靠谱客的博主矮小身影，最近开发中收集的这篇文章主要介绍【BZOJ4260】Codechef REBXOR（前i个数的最大区间异或值---01字典树+dp）题目：解题思路：ac代码：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目地址：https://www.lydsy.com/JudgeOnline/problem.php?id=4260

题目：

给出一个序列，求两个不相交区间的异或值之和的最大值

解题思路：

异或基本性质：0^a=a,a^a=0

先求出前缀异或pre[]和后缀异或suf[]。

两个dp数组，dp1[i]表示[1，i]的最大区间异或值，dp2[i]表示[i,n]的最大区间异或值，dp1和dp2的求法相同，下面只介绍dp1的求法。

先初始化，将0插入01字典树中！！！因为0^a=0, 不能在一个空的01字典树上找一个数和指定的数异或值最大！！

dp1[i] =max(dp1[i -1], 以i为右边界的最大区间异或值) 即选择a[i]和选择a[i]，01字典树中插入的都是pre值。

例如求dp1[4]时：

01字典树中已经插入和pre[1],pre[2],pre[3]，若要选择a[4]的话，就要在pre[1],pre[2],pre[3]中选择一个和pre[4]的异或值最大，若pre[2]^pre[4]最大，相当于[1,4]中以4为右边界的最大区间异或值是a[3]^a[4],对应的区间是[3,4]，在a[3]^a[4]和dp1[3]中取较大值更新dp1[4]。

最终结果ans = max（dp1[i],dp2[i + 1]）i $large in$ [1,n-1]

ac代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4e5+5;
const int max_base = 32;
ll val[32*maxn], a[maxn], pre[maxn], suf[maxn], dp1[maxn], dp2[maxn];
int ch[32*maxn][2];
int tol = 0;
void init()
{
    tol = 1;
    ch[0][0] =  ch[1][0] = 0;
}
void insert(ll x)
{
    int u = 0;
    for(int i = max_base; i >= 0; i--)
    {
        int v = (x >> i & 1);
        if(!ch[u][v]) // 新建节点
        {
            ch[tol][1] = ch[tol][0] = 0;
            val[tol] = 0; //不是数值节点
            ch[u][v] = tol++;
        }
        u = ch[u][v];
    }
    val[u] = x;
}
ll query(ll x)
{
    int u = 0;
    for(int i = max_base; i >= 0; i--)
    {
        int v = x >> i & 1;
        if(ch[u][v^1]) u = ch[u][v^1]; // 贪心的找每位异或起来的1的节点, 且这个节点存在，可能其他数在该节点上有相应的值
        else u = ch[u][v];
    }
    return  x^val[u];
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    int  n;
    scanf("%d", &n);
    pre[0] = suf[n + 1] = 0;
    dp1[0] = dp2[n + 1] = 0;
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        pre[i] = pre[i - 1] ^ a[i];// 前缀异或
    }
    for(int i = n; i >= 1; i--)
        suf[i] = suf[i + 1] ^ a[i];// 后缀异或

    init();
    insert(0);//0^pre[1]=pre[1]，01字典树在query之间必须曾经插入过数
    for(int i = 1; i <= n; i++)
    {
        dp1[i] =  max(dp1[i - 1], query(pre[i]));//dp[i] 表示前i个数内的最大区间异或值
        insert(pre[i]);
    }

    init();
    insert(0);
    for(int i = n; i >= 1; i--)
    {
        dp2[i] = max(dp2[i + 1], query(suf[i]));
        insert(suf[i]);
    }

    ll ans = 0;
    for(int i = 1; i < n; i++)
        ans = max(ans, dp1[i] + dp2[i + 1]);//[1,i] [i+1,n]
    printf("%lldn", ans);
    return 0;
}