8288分类目录 8288分类目录 8288分类目录
  当前位置:海洋目录网 » 站长资讯 » 站长资讯 » 文章详细 订阅RssFeed

BZOJ 4260: Codechef REBXOR

来源:本站原创 浏览:119次 时间:2021-10-11
Description

 

Input

输入数据的第一行包含一个整数N,表示数组中的元素个数。

第二行包含N个整数A1,A2,…,AN。

 

 

 

Output

输出一行包含给定表达式可能的最大值。

 

 

Sample Input

5
1 2 3 1 2

Sample Output

6

HINT

 

满足条件的(l1,r1,l2,r2)有:(1,2,3,3),(1,2,4,5),(3,3,4,5)。


对于100%的数据,2 ≤ N ≤ 4*105,0 ≤ Ai ≤ 109。

 

Solution:

  01trie树求异或和最大。

  先正反都求一遍异或前缀和,每次都将当前的前缀和加入01tire树中,同时查询并更新$ln[i]$和$rn[i]$(分别表示$[1,i]$的最大连续异或和,$[i,n]$的最大连续异或和),那么答案$ans=max(ln[i]+rn[i+1])$,注意的细节是trie树要清0并在tire树中先插入一个0以便保证第一次插入的异或前缀和是其本身。

代码:

 

#include#define il inline#define ll long lo���,�߷�ng#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)using namespace std;const int N=4e5+7;int trie[N*31][2],cnt,n,a[N],sum,ln[N],rn[N],ans; il void insert(int a){    int x,p=0;    Bor(i,0,31){        x=(1<<i)&a?1:0;        if(!trie[p][x])trie[p][x]=++cnt;        p=trie[p][x];    }} il int search(int a){    int x,p=0,ans=0;    Bor(i,0,31){        x=(1<<i)&a?0:1;        if(trie[p][x])ans+=1<<i,p=trie[p][x];        else p=trie[p][x^1];        if(!p)return ans;    }    return ans;} il void init(){    scanf("%d",&n);    For(i,1,n) scanf("%d",&a[i]);    sum=0,insert(0);    For(i,1,n) sum^=a[i],insert(sum),ln[i]=max(search(sum),ln[i-1]);    sum=0;    memset(trie,0,sizeof(trie)),cnt=0,insert(0);    Bor(i,1,n) sum^=a[i],insert(sum),rn[i]=max(search(sum),rn[i+1]);    For(i,1,n) ans=max(ln[i]+rn[i+1],ans);    cout<<ans;} int main(){    init();    return 0;}

 

  推荐站点

  • At-lib分类目录At-lib分类目录

    At-lib网站分类目录汇集全国所有高质量网站,是中国权威的中文网站分类目录,给站长提供免费网址目录提交收录和推荐最新最全的优秀网站大全是名站导航之家

    www.at-lib.cn
  • 中国链接目录中国链接目录

    中国链接目录简称链接目录,是收录优秀网站和淘宝网店的网站分类目录,为您提供优质的网址导航服务,也是网店进行收录推广,站长免费推广网站、加快百度收录、增加友情链接和网站外链的平台。

    www.cnlink.org
  • 35目录网35目录网

    35目录免费收录各类优秀网站,全力打造互动式网站目录,提供网站分类目录检索,关键字搜索功能。欢迎您向35目录推荐、提交优秀网站。

    www.35mulu.com
  • 就要爱网站目录就要爱网站目录

    就要爱网站目录,按主题和类别列出网站。所有提交的网站都经过人工审查,确保质量和无垃圾邮件的结果。

    www.912219.com
  • 伍佰目录伍佰目录

    伍佰网站目录免费收录各类优秀网站,全力打造互动式网站目录,提供网站分类目录检索,关键字搜索功能。欢迎您向伍佰目录推荐、提交优秀网站。

    www.wbwb.net