题目描述 农民约翰在喂奶牛的时候被另一个问题卡住了。他的所有N(1 <= N <= 100,000)个奶牛在他面前排成一行(按序号1..N的顺序)，按照它们的社会等级排序。奶牛#1由最高的社会等级，奶牛#N最低。每个奶牛同时被赋予了一个唯一的数在0..2^21 - 1的范围内。帮助农民约翰找出应该从那一头奶牛开始喂，使得从它开始的某一个连续的自序列上的奶牛的数的异或最大。如果有多个这样的子序列，选择结尾的奶牛社会等级最高的。如果还不唯一，选择最短的。
输入 • 第1行:一个单独的整数N。 • 第2到N + 1行:N个0..2^21 – 1之间的整数，代表每头奶牛的被赋予的数。第j行描述了社会等级j – 1的奶牛。
输出 • 第 1 行: 3个空格隔开的整数，分别为：最大的异或值，序列的起始位置、终止位置。
样例输入 5 1 0 5 4 2 样例输出 6 4 5
trie树的应用
#include<cstdio>#include<cstring>#include<iostream>using namespace std;int n,v,tot,ans,cow;int a[100005],s[100005],b[40];struct ty{ int Next[2]; void init() { memset(Next,-1,sizeof(Next)); }}p[3000005];void work(int x){ int k=0; while(x>0) { k++; b[k]=x%2; x=x/2; } for(int i=k+1;i<=31;i++) b[i]=0;}void Insert(){ int now,k; now=0; for(int i=31;i>=1;i--) { k=b[i]; if(p[now].Next[k]==-1) { tot++; p[tot].init(); p[now].Next[k]=tot; } now=p[now].Next[k]; }}void query(int id){ int now,k,val; now=0;val=0; for(int i=31;i>=1;i--) { k=b[i]; if(p[now].Next[k^1]!=-1) { val+=(1<<(i-1)); now=p[now].Next[k^1]; } else now=p[now].Next[k]; } if(val>ans) { ans=val; cow=id; } if(val==ans) { if(id<cow) cow=id; }}int main(){ cin>>n; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); s[i]=s[i-1]^a[i]; } ans=-1e9; p[0].init(); work(0); Insert(); for(int i=1;i<=n;i++) { work(s[i]); Insert(); query(i); } for(int i=cow;i>=1;i--) { v=v^a[i]; if(v==ans) { cout<<ans<<' '<<i<<' '<<cow; return 0; } } return 0;}新闻热点
疑难解答
