奶牛异或
奶牛异或
链接：https://ac.nowcoder.com/acm/problem/22998?&headNav=acm 来源：牛客网
题目描述
农民约翰在喂奶牛的时候被另一个问题卡住了。他的所有N(1 <= N <= 100,000)个奶牛在他面前排成一行(按序号1…N的顺序)，按照它们的社会等级排序。奶牛#1有最高的社会等级，奶牛#N最低。每个奶牛同时被指定了一个不唯一的附加值，这个数在 [0, 221 - 1] 的范围内。
帮助农民约翰找出应该从哪一头奶牛开始喂，使得从这头奶牛开始的一个连续的子序列上，奶牛的附加值的异或最大。
如果有多个这样的子序列，选择结尾的奶牛社会等级最高的。如果还不唯一，选择最短的。
输入描述:
第1行:一个单独的整数N。第2到N + 1行:N个 [0, 221 - 1] 之间的整数，代表每头奶牛的被赋予的数。第j行描述了社会等级j - 1的奶牛。输出描述:
第 1 行: 3个空格隔开的整数，分别为：最大的异或值，序列的起始位置、终止位置。示例1
输入
5
1
0
5
4
2输出
6 4 5说明
最大异或值为6，从第4个开始喂，到第5个结束。
4 异或 2 = 6
(100) 异或 (010) = (110)思路：利用异或、前缀的性质，这种题目一看就是要用线性复杂度，建立一颗字典树，树上每一个值都是1-n的某一项前缀异或，然后查询的时候就可以按照找两个异或最大的模板，注意记录左右边界，细节是先插入0,0为了防止只有一个数的情况
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
int n,cnt,a[maxn],l,r,ans=-1;
struct trie{
int nex[maxn*32][2],ed[maxn*32];
void insert(int x,int index)
{
int p=0;
for(int i=30;i>=0;i--)
{
int k=x>>i&1;
if(!nex[p][k])nex[p][k]=++cnt;
p=nex[p][k];
}
ed[p]=index;
}
void find(int x,int index)
{
int p=0,sum=0;
for(int i=30;i>=0;i--)
{
int k=x>>i&1;
if(nex[p][k^1])sum|=1<<i,p=nex[p][k^1];
else p=nex[p][k];
}
if(sum>ans)
{
ans=sum;
l=ed[p]+1;
r=index;
}
}
}t;
int main()
{
cin>>n;
int tep=0;
t.insert(0,0);
for(int i=0;i<n;i++)
{
cin>>a[i];
tep^=a[i];
t.insert(tep,i+1);
t.find(tep,i+1);
}
cout<<ans<<" "<<l<<" "<<r<<endl;
return 0;
}
/*
5
1
0
5
4
2
6 4 5
*/本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-10-30 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录